分布式估計算法講解課件

算法設(shè)計與分析

分布式估計算法

主要知識點：1、傳統(tǒng)遺傳算法2、分布式估計算法與傳統(tǒng)遺傳算法的區(qū)別3、分布式估計算法應用舉例4、分布式估計算法的分類5、分布式估計算法的理論基礎(chǔ)21、傳統(tǒng)遺傳算法1.

個體與種群●個體就是模擬生物個體而對問題中的對象（一般就是問題的解）的一種稱呼，一個個體也就是搜索空間中的一個點。●種群(population)就是模擬生物種群而由若干個體組成的群體,它一般是整個搜索空間的一個很小的子集。33.染色體與基因

染色體（chromosome）就是問題中個體的某種字符串形式的編碼表示。字符串中的字符也就稱為基因（gene）。例如：個體染色體

9----

1001（2，5，6）----01010111054.遺傳操作亦稱遺傳算子(geneticoperator)，就是關(guān)于染色體的運算。遺傳算法中有三種遺傳操作:

●

選擇-復制(selection-reproduction)

●

交叉(crossover，亦稱交換、交配或雜交)

●

變異(mutation，亦稱突變)

6

選擇-復制通常做法是：對于一個規(guī)模為N的種群S,按每個染色體xi∈S的選擇概率P(xi)所決定的選中機會,分N次從S中隨機選定N個染色體,并進行復制。

這里的選擇概率P(xi)的計算公式為7

交叉就是互換兩個染色體某些位上的基因。

s1′=01000101,s2′=10011011可以看做是原染色體s1和s2的子代染色體。

例如,設(shè)染色體s1=01001011,s2=10010101,交換其后4位基因,即81.2基本遺傳算法

遺傳算法基本流程框圖生成初始種群計算適應度選擇-復制交叉變異生成新一代種群終止?結(jié)束10步5按選擇概率P(xi)所決定的選中機會，每次從S中隨機選定1個個體并將其染色體復制，共做N次，然后將復制所得的N個染色體組成群體S1；步6按交叉率Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機確定c個染色體，配對進行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體S2；121.3遺傳算法應用舉例

例1利用遺傳算法求解區(qū)間［0,31］上的二次函數(shù)y=x2的最大值，x為整數(shù)。

y=x2

31

XY14分析原問題可轉(zhuǎn)化為在區(qū)間［0,31］中搜索能使y取最大值的點a的問題。那么，［0,31］中的點x就是個體,函數(shù)值f(x)恰好就可以作為x的適應度，區(qū)間［0,31］就是一個(解)空間。這樣,只要能給出個體x的適當染色體編碼,該問題就可以用遺傳算法來解決。15

解(1)設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。將種群規(guī)模設(shè)定為4；用5位二進制數(shù)編碼染色體；取下列個體組成初始種群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

(2)定義適應度函數(shù),取適應度函數(shù)：f(x)=x2

16

(3)計算各代種群中的各個體的適應度,并對其染色體進行遺傳操作,直到適應度最高的個體(即31（11111）)出現(xiàn)為止。

17首先計算種群S1中各個體s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)的適應度f(si)。容易求得f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=36118●賭輪選擇法s40.31s20.49s10.14s30.0620

在算法中賭輪選擇法可用下面的子過程來模擬:①在［0,1］區(qū)間內(nèi)產(chǎn)生一個均勻分布的隨機數(shù)r。②若r≤q1,則染色體x1被選中。③若qk-1<r≤qk(2≤k≤N),則染色體xk被選中。其中的qi稱為染色體xi(i=1,2,…,n)的積累概率,其計算公式為21于是，經(jīng)復制得群體：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）

23交叉

設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運算。設(shè)s1’與s2’配對，s3’與s4’配對。分別交換后兩位基因，得新染色體：s1’’=11001（25）,s2’’=01100（12）

s3’’=11011（27）,s4’’=10000（16）

24于是，得到第二代種群S2：s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）

26

第二代種群S2中各染色體的情況

染色體適應度選擇概率積累概率估計的選中次數(shù)s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.00127如此不斷進化，直到種群中出現(xiàn)適應度最高的染色體s1=11111。于是，遺傳操作終止，將染色體“11111”作為最終結(jié)果輸出。然后，將染色體“11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解：31。將31代入函數(shù)y=x2中，即得原問題的解，即函數(shù)y=x2的最大值為961。28根據(jù)概率模型的復雜程度以及不同的采樣方法，分布式估計算法發(fā)展了很多不同的具體實現(xiàn)方法，但是都可以歸納為下面兩個主要步驟：1）、構(gòu)建描述解空間的概率模型。通過對種群的評估，選擇優(yōu)秀的個體集合，然后采樣統(tǒng)計學習等手段構(gòu)造一個描述當前解集的概率模型2）、由概率模型隨機采樣產(chǎn)生新的種群。一般的，采用蒙特卡羅方法，對概率模型采樣得到新的種群。30下面通過一個簡單的EDA算例，介紹該方法獨特的進化操作，使讀者對EDA方法有一個直觀的認識.3、分布式估計算法應用舉例31323334353637分布式估計和傳統(tǒng)遺傳算法的對比384、分布式估計算法的分類變量無關(guān)雙變量相關(guān)多變量相關(guān)394.1、變量無關(guān)的分布式估計算法最簡單，假設(shè)各變量之間是獨立的，那么任意解的概率可以表示為：比較有代表性的算法有如下幾種：PBIL(PopulationbasedIncrementalAlgorithm)UMDA(UnivariateMarginalDistributionAlgorithm)cGA(compactGeneticAlgorithm)40PBIL方法4142算法偽代碼43應用例子旅行推銷員問題（又稱為旅行商問題、TSP問題）是一個多局部最優(yōu)的最優(yōu)化問題：有n個城市，一個推銷員要從其中某一個城市出發(fā)，唯一走遍所有的城市，再回到他出發(fā)的城市，求最短的路線。工作調(diào)度問題。函數(shù)優(yōu)化問題。44UMDAUMDA與PBIL唯一不同在于概率向量的更新算法，前面的例子實際就是UMDA算法！算法描述如下：4546應用例子47484950515253545556請同學們繼續(xù)！57cGA

與UMDA、PBIL不同也在于概率向量的更新算法，并且種群規(guī)模很小，只產(chǎn)生兩個個體，算法描述如下：58594.2雙變量相關(guān)的分布式估計算法這類算法，概率模型可以表示至多兩個變量之間的關(guān)系。主要有MIMIC(Mutualinformationmaximizationforinputclustering)、COMIT、BMD