分布式估計(jì)算法講解課件

算法設(shè)計(jì)與分析

分布式估計(jì)算法

主要知識(shí)點(diǎn)：1、傳統(tǒng)遺傳算法2、分布式估計(jì)算法與傳統(tǒng)遺傳算法的區(qū)別3、分布式估計(jì)算法應(yīng)用舉例4、分布式估計(jì)算法的分類(lèi)5、分布式估計(jì)算法的理論基礎(chǔ)21、傳統(tǒng)遺傳算法1.

個(gè)體與種群●個(gè)體就是模擬生物個(gè)體而對(duì)問(wèn)題中的對(duì)象（一般就是問(wèn)題的解）的一種稱(chēng)呼，一個(gè)個(gè)體也就是搜索空間中的一個(gè)點(diǎn)?！穹N群(population)就是模擬生物種群而由若干個(gè)體組成的群體,它一般是整個(gè)搜索空間的一個(gè)很小的子集。33.染色體與基因

染色體（chromosome）就是問(wèn)題中個(gè)體的某種字符串形式的編碼表示。字符串中的字符也就稱(chēng)為基因（gene）。例如：個(gè)體染色體

9----

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

●

選擇-復(fù)制(selection-reproduction)

●

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

●

變異(mutation，亦稱(chēng)突變)

6

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

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

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

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

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

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

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

y=x2

31

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

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

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

16

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

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

s3=8(01000),s4=19(10011)的適應(yīng)度f(wàn)(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

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

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）

23交叉

設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運(yùn)算。設(shè)s1’與s2’配對(duì)，s3’與s4’配對(duì)。分別交換后兩位基因，得新染色體：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中各染色體的情況

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

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