分布估計(jì)算法

關(guān)于分布估計(jì)算法第一頁(yè)，共三十二頁(yè)，2022年，8月28日綜述最近幾年，在進(jìn)化計(jì)算領(lǐng)域興起的一類(lèi)新型的優(yōu)化算法，即分布估計(jì)算法（EstimationofDistributionAlgorithm）簡(jiǎn)稱(chēng)EDA，提出了一種全新的進(jìn)化模式，并迅速成為進(jìn)化計(jì)算領(lǐng)域的研究熱點(diǎn)和解決工程問(wèn)題的有效方法．分布估計(jì)算法的概念最初在1996年提出，在2000年前后迅速發(fā)展，成為當(dāng)前進(jìn)化計(jì)算領(lǐng)域前沿的研究?jī)?nèi)容。第二頁(yè)，共三十二頁(yè)，2022年，8月28日綜述基本思想--遺傳算法和統(tǒng)計(jì)學(xué)習(xí)相結(jié)合基本方法--通過(guò)統(tǒng)計(jì)學(xué)習(xí)的手段建立解空間內(nèi)個(gè)體分布的概率模型，然后對(duì)概率模型隨即采樣產(chǎn)生新的群體，如此反復(fù)，實(shí)現(xiàn)群體的進(jìn)化第三頁(yè)，共三十二頁(yè)，2022年，8月28日綜述基本概念1個(gè)體與種群 ●個(gè)體就是模擬生物個(gè)體而對(duì)問(wèn)題中的對(duì)象（一般就是問(wèn)題的解）的一種稱(chēng)呼，一個(gè)個(gè)體也就是搜索空間中的一個(gè)點(diǎn)。 ●種群(population)就是模擬生物種群而由若干個(gè)體組成的群體,它一般是整個(gè)搜索空間的一個(gè)很小的子集。第四頁(yè)，共三十二頁(yè)，2022年，8月28日綜述基本概念概率模型--用于描述取值域中優(yōu)秀個(gè)體分布情況的一系列函數(shù)或其他數(shù)學(xué)工具（包括概率密度函數(shù)、條件概率、邊緣概率等等）第五頁(yè)，共三十二頁(yè)，2022年，8月28日綜述基本概念適應(yīng)度與適應(yīng)度函數(shù)●適應(yīng)度(fitness)就是借鑒生物個(gè)體對(duì)環(huán)境的適應(yīng)程度,而對(duì)問(wèn)題中的個(gè)體對(duì)象所設(shè)計(jì)的表征其優(yōu)劣的一種測(cè)度?！襁m應(yīng)度函數(shù)(fitnessfunction)就是問(wèn)題中的全體個(gè)體與其適應(yīng)度之間的一個(gè)對(duì)應(yīng)關(guān)系。它一般是一個(gè)實(shí)值函數(shù)。該函數(shù)就是遺傳算法中指導(dǎo)搜索的評(píng)價(jià)函數(shù)。第六頁(yè)，共三十二頁(yè)，2022年，8月28日綜述主要步驟（雖然有很多具體的實(shí)現(xiàn)方法，但是分布估計(jì)算法可以歸納為以下兩步）1：構(gòu)建描述解空間的概率模型．通過(guò)對(duì)種群的評(píng)估，選擇優(yōu)秀的個(gè)體集合，然后采用統(tǒng)計(jì)學(xué)習(xí)等手段構(gòu)造一個(gè)描述當(dāng)前解集的概率模型．2：由概率模型隨機(jī)采樣產(chǎn)生新的種群。第七頁(yè)，共三十二頁(yè)，2022年，8月28日綜述分布估計(jì)算法的與遺傳算法的不同生物進(jìn)化的數(shù)學(xué)模型遺傳算法是對(duì)于個(gè)體進(jìn)行遺傳操作（交叉、變異等），"微觀"層面模擬生物的進(jìn)化。分布估計(jì)算法是對(duì)于整個(gè)群體的分布建立一個(gè)概率模型，通過(guò)這個(gè)概率模型來(lái)描述進(jìn)化的方向，是“宏觀”層面的模擬。第八頁(yè)，共三十二頁(yè)，2022年，8月28日綜述

第九頁(yè)，共三十二頁(yè)，2022年，8月28日示例在這里，舉一個(gè)最簡(jiǎn)單的離散的優(yōu)化的問(wèn)題作為示例。Z=X1+X2，其中X1的取值域?yàn)?,2,3,4,5，x2的取值域?yàn)?,7,8,9,10第十頁(yè)，共三十二頁(yè)，2022年，8月28日示例建立模型建立一個(gè)概率模型。在這里我們只需要建立一個(gè)離散的概率模型（設(shè)X1，X2相互獨(dú)立），初始化如下（只列出邊緣概率）。第十一頁(yè)，共三十二頁(yè)，2022年，8月28日示例采樣與擇優(yōu)根據(jù)概率模型，采樣若干個(gè)點(diǎn)（6個(gè)）。假設(shè)采到的點(diǎn)為2,7；3,9；3,10；4,8；2,9；5,6評(píng)估這六個(gè)點(diǎn)，帶入函數(shù)（適應(yīng)度函數(shù)），分別得到9,12,13，12,11,11。因此我們選擇2,7；2,9和5,6來(lái)更新概率模型。第十二頁(yè)，共三十二頁(yè)，2022年，8月28日示例更新概率模型（根據(jù)2,7；2,9和5,6三個(gè)點(diǎn)）更新X1的分布總共有3個(gè)個(gè)體，三個(gè)個(gè)體對(duì)應(yīng)的X1為2,2,5P1'（x1=1）=0;P1'（x1=2）=2/3;P1'（x1=5）=1/3;P1'（x1=3）=0;P1'（x1=4）=0同理得到P2'（x2=6）=1/3;P2'（x1=7）=1/3;P2'（x1=9）=1/3;P2'（x1=8）=0;P2'（x1=10）=0第十三頁(yè)，共三十二頁(yè)，2022年，8月28日示例更新概率模型對(duì)分布函數(shù)進(jìn)行平滑處理（防止有一些點(diǎn)的概率為零，自變量的值相差較近則概率應(yīng)該相差不大）以X1為例P1''（X1=i）=并歸一化同理求P2’得到P1''(X=1)=0.139861 P1''(X=2)=0.380183P1''(X=3)=0.16124 P1''(X=4)=0.117459P1''(X=5)=0.201247P2''(X=6)=0.27714 P2''(X=7)=0.27955P2''(X=8)=0.125736 P2''(X=9)=0.108491P2''(X=10)=0.209084第十四頁(yè)，共三十二頁(yè)，2022年，8月28日示例更新概率模型P1=θ*P1''+(1-θ)P1P2=θ*P2''+(1-θ)P2其中θ是遺忘因子，取0.5第十五頁(yè)，共三十二頁(yè)，2022年，8月28日示例學(xué)習(xí)之前學(xué)習(xí)之后第十六頁(yè)，共三十二頁(yè)，2022年，8月28日示例說(shuō)明可以看出，經(jīng)過(guò)學(xué)習(xí)之后，優(yōu)秀個(gè)體對(duì)應(yīng)的坐標(biāo)的概率會(huì)變高，平滑處理可以保證:若一個(gè)個(gè)體位置若和優(yōu)秀個(gè)體距離較近，那么該位置會(huì)受惠于該優(yōu)秀個(gè)體，概率也會(huì)比較高（基于這樣一個(gè)假設(shè)--若個(gè)體相差不大，則其適應(yīng)度應(yīng)該也相差不大）。第十七頁(yè)，共三十二頁(yè)，2022年，8月28日示例重復(fù)以上步驟從示例中可以看出，所謂的分布估計(jì)算法就是一個(gè)不斷地更新概率模型，使概率模型越來(lái)越能反映優(yōu)秀個(gè)體的分布的過(guò)程。第十八頁(yè)，共三十二頁(yè)，2022年，8月28日基于不同概率模型的EDA變量無(wú)關(guān)的EDA如示例所示，X1和X2的概率是無(wú)關(guān)的，也可以認(rèn)為為在概率模型中X1和X2兩個(gè)變量相互獨(dú)立。在這種情況下，聯(lián)合概率密度是邊緣概率密度的積，采樣的時(shí)候可以對(duì)于每個(gè)變量分別進(jìn)行采樣，概率模型可以認(rèn)為是：第十九頁(yè)，共三十二頁(yè)，2022年，8月28日基于不同概率模型的EDA雙變量相關(guān)的EDA在實(shí)際問(wèn)題中，變量之間并不總是相互獨(dú)立的，最先考慮的是最多兩個(gè)變量相關(guān)的情況。這種情況下，其概率模型為代表算法MIMC采樣方法如下1)J=n，根據(jù)第ij個(gè)變量的概率分布P(xij)， 隨機(jī)采樣產(chǎn)生第ij個(gè)變量2)根據(jù)第ij個(gè)變量的條件概率分布

p(xij-1|xij)隨機(jī)采樣產(chǎn)生第ij-1個(gè)變量；3)J=J-1，如果J=1，則一個(gè)完整的解向 量構(gòu)造完成；否則轉(zhuǎn)2)．

第二十頁(yè)，共三十二頁(yè)，2022年，8月28日基于不同概率模型的EDA多變量相關(guān)EDA變量之間的關(guān)系更加復(fù)雜，需要更加復(fù)雜的概率模型來(lái)描述。代表算法EIGA，BOA連續(xù)域的EDA在示例中，我們解決了一個(gè)離散的問(wèn)題，如果X1和X2的取值域是連續(xù)的，我們就需要一個(gè)連續(xù)的概率模型來(lái)描述解空間的分布。如正態(tài)分布、柯西分布代表算法CMAES第二十一頁(yè)，共三十二頁(yè)，2022年，8月28日EDA的關(guān)鍵問(wèn)題概率模型選擇合適的概率模型，是發(fā)揮分布估計(jì)算法性能的關(guān)鍵所在，對(duì)于連續(xù)域的比較復(fù)雜問(wèn)題來(lái)說(shuō)，如果采用單峰的概率模型，會(huì)取得比較好的收斂速度，但是非常容易收斂到局部最優(yōu)。如果采用多峰的概率模型（如混合高斯模型），對(duì)與比較復(fù)雜的優(yōu)化問(wèn)題可能有更強(qiáng)的描述能力，但是這種模型的更新會(huì)相對(duì)困難。第二十二頁(yè)，共三十二頁(yè)，2022年，8月28日EDA的關(guān)鍵問(wèn)題學(xué)習(xí)方法如何根據(jù)每一代取得的優(yōu)秀個(gè)體來(lái)更新概率模型,隨著待解決問(wèn)題的復(fù)雜化和概率圖模型的復(fù)雜化，分布估計(jì)算法中概率模型的學(xué)習(xí)占用了大部分的時(shí)間和空間開(kāi)銷(xiāo)，這必然將成為分布估計(jì)算法發(fā)展的瓶頸．采樣方法如何根據(jù)一個(gè)概率模型來(lái)采樣得到符合該概率模型的樣本，如Gibbs抽樣。第二十三頁(yè)，共三十二頁(yè)，2022年，8月28日EDA的并行化1：將整個(gè)取值區(qū)域分成若干子區(qū)域，每個(gè)子區(qū)域并行。2：個(gè)體產(chǎn)生的采樣--由于每個(gè)個(gè)體都是根據(jù)概率模型隨機(jī)產(chǎn)生的，因此每個(gè)個(gè)體可以看做獨(dú)立的，所以個(gè)體可以并行產(chǎn)生。第二十四頁(yè)，共三十二頁(yè)，2022年，8月28日EDA的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：為人們解決復(fù)雜的優(yōu)化問(wèn)題提供了工具。分布估計(jì)算法能更加有效的解決高維問(wèn)題，降低時(shí)間復(fù)雜性。缺點(diǎn)：同遺傳算法一樣，理論研究比較困難，很難從理論上解決它適合解決什么問(wèn)題，概率模型的學(xué)習(xí)會(huì)占用很多時(shí)間和空間。第二十五頁(yè)，共三十二頁(yè)，2022年，8月28日示例2求下列函數(shù)的所有極值點(diǎn)y= ---------試著使用變量無(wú)關(guān)的EDA解決這個(gè)問(wèn)題第二十六頁(yè)，共三十二頁(yè)，2022年，8月28日示例2概率模型確定對(duì)于每一維度對(duì)應(yīng)于一正態(tài)分布，那么

~第二十七頁(yè)，共三十二頁(yè)，2022年，8月28日示例2取得優(yōu)秀個(gè)體連續(xù)采樣，直到采到N個(gè)個(gè)體的適應(yīng)度比當(dāng)前已經(jīng)取得的最佳適應(yīng)度要好。如果連續(xù)采樣次數(shù)大于某個(gè)閾值，仍沒(méi)有得到比目前最好的點(diǎn)，則檢驗(yàn)是否是極值點(diǎn)。檢驗(yàn)的方法為令每一維的方差為一個(gè)極小值（設(shè)為1e-5），采樣多次，若無(wú)改進(jìn)，則認(rèn)為是極值點(diǎn)，記錄該極值點(diǎn)，若不是極值點(diǎn)，則考慮適當(dāng)將方差變小，繼續(xù)采樣。第二十八頁(yè)，共三十二頁(yè)，2022年，8月28日示例2概率模型的更新根據(jù)得到的N個(gè)優(yōu)秀個(gè)體，求這N個(gè)點(diǎn)適應(yīng)度最好的點(diǎn)，得到A=[xu1,xu2......xun]假設(shè)在此之前得到的最好的點(diǎn)為A'=[xb1,xb2....xb5]令C=[d1,d2.....dn]=A-A'xui為第i維的正態(tài)分布的均值。di為第i維的正太分布的方差。第二十九頁(yè)，共三十