分布估計算法

1、關于分布估計算法第一張，PPT共三十二頁，創(chuàng)作于2022年6月綜述最近幾年，在進化計算領域興起的一類新型的優(yōu)化算法，即分布估計算法（Estimation of Distribution Algorithm）簡稱EDA，提出了一種全新的進化模式，并迅速成為進化計算領域的研究熱點和解決工程問題的有效方法分布估計算法的概念最初在1996年提出，在2000年前后迅速發(fā)展，成為當前進化計算領域前沿的研究內(nèi)容。第二張，PPT共三十二頁，創(chuàng)作于2022年6月綜述基本思想-遺傳算法和統(tǒng)計學習相結合基本方法-通過統(tǒng)計學習的手段建立解空間內(nèi)個體分布的概率模型，然后對概率模型隨即采樣產(chǎn)生新的群體，如此反復，實現(xiàn)群體

2、的進化第三張，PPT共三十二頁，創(chuàng)作于2022年6月綜述基本概念1個體與種群 個體就是模擬生物個體而對問題中的對象 （一般就是問題的解）的一種稱呼，一個個 體也就是搜索空間中的一個點。 種群(population)就是模擬生物種群而由若 干個體組成的群體, 它一般是整個搜索空間 的一個很小的子集。第四張，PPT共三十二頁，創(chuàng)作于2022年6月綜述基本概念概率模型-用于描述取值域中優(yōu)秀個體分布情況的一系列函數(shù)或其他數(shù)學工具（包括概率密度函數(shù)、條件概率、邊緣概率等等）第五張，PPT共三十二頁，創(chuàng)作于2022年6月綜述基本概念適應度與適應度函數(shù) 適應度(fitness)就是借鑒生物個體對環(huán)境的 適應

3、程度,而對問題中的個體對象所設計的 表征其優(yōu)劣的一種測度。 適應度函數(shù)(fitness function)就是問題中的 全體個體與其適應度之間的一個對應關系。 它一般是一個實值函數(shù)。該函數(shù)就是遺傳算 法中指導搜索的評價函數(shù)。第六張，PPT共三十二頁，創(chuàng)作于2022年6月綜述主要步驟（雖然有很多具體的實現(xiàn)方法，但是分布估計算法可以歸納為以下兩步）1：構建描述解空間的概率模型通過對種群的評估，選擇優(yōu)秀的個體集合，然后采用統(tǒng)計學習等手段構造一個描述當前解集的概率模型2：由概率模型隨機采樣產(chǎn)生新的種群。第七張，PPT共三十二頁，創(chuàng)作于2022年6月綜述分布估計算法的與遺傳算法的不同生物進化的數(shù)學模型遺

4、傳算法是對于個體進行遺傳操作（交叉、變異等），微觀層面模擬生物的進化。分布估計算法是對于整個群體的分布建立一個概率模型，通過這個概率模型來描述進化的方向，是“宏觀”層面的模擬。第八張，PPT共三十二頁，創(chuàng)作于2022年6月綜述 第九張，PPT共三十二頁，創(chuàng)作于2022年6月示例在這里，舉一個最簡單的離散的優(yōu)化的問題作為示例。Z=X1+X2，其中X1的取值域為1,2,3,4,5， x2的取值域為6,7,8,9,10第十張，PPT共三十二頁，創(chuàng)作于2022年6月示例建立模型建立一個概率模型。在這里我們只需要建立一個離散的概率模型（設X1，X2相互獨立），初始化如下（只列出邊緣概率）。第十一張，PP

5、T共三十二頁，創(chuàng)作于2022年6月示例采樣與擇優(yōu)根據(jù)概率模型，采樣若干個點（6個）。假設采到的點為2,7；3,9；3,10；4,8；2,9；5,6評估這六個點，帶入函數(shù)（適應度函數(shù)），分別得到9,12,13，12,11,11。因此我們選擇2,7；2,9和5,6來更新概率模型。第十二張，PPT共三十二頁，創(chuàng)作于2022年6月示例更新概率模型（根據(jù)2,7；2,9和5,6三個點）更新X1的分布總共有3個個體，三個個體對應的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

6、）=1/3;P2（x1=9）=1/3;P2（x1=8）=0;P2（x1=10）=0第十三張，PPT共三十二頁，創(chuàng)作于2022年6月示例更新概率模型對分布函數(shù)進行平滑處理（防止有一些點的概率為零，自變量的值相差較近則概率應該相差不大）以X1為例P1（X1=i）=并歸一化同理求P2得到P1(X=1)=0.139861 P1(X=2)=0.380183 P1(X=3)=0.16124P1(X=4)=0.117459 P1(X=5)=0.201247P2(X=6)=0.27714 P2(X=7)=0.27955 P2(X=8)=0.125736 P2(X=9)=0.108491 P2(X=10)=0.

7、209084第十四張，PPT共三十二頁，創(chuàng)作于2022年6月示例更新概率模型P1=*P1+(1-)P1P2=*P2+(1-)P2其中是遺忘因子，取0.5第十五張，PPT共三十二頁，創(chuàng)作于2022年6月示例學習之前學習之后第十六張，PPT共三十二頁，創(chuàng)作于2022年6月示例說明可以看出，經(jīng)過學習之后，優(yōu)秀個體對應的坐標的概率會變高，平滑處理可以保證:若一個個體位置若和優(yōu)秀個體距離較近，那么該位置會受惠于該優(yōu)秀個體，概率也會比較高（基于這樣一個假設-若個體相差不大，則其適應度應該也相差不大）。第十七張，PPT共三十二頁，創(chuàng)作于2022年6月示例重復以上步驟從示例中可以看出，所謂的分布估計算法就是一

8、個不斷地更新概率模型，使概率模型越來越能反映優(yōu)秀個體的分布的過程。第十八張，PPT共三十二頁，創(chuàng)作于2022年6月基于不同概率模型的EDA變量無關的EDA如示例所示，X1和X2的概率是無關的，也可以認為為在概率模型中X1和X2兩個變量相互獨立。在這種情況下，聯(lián)合概率密度是邊緣概率密度的積，采樣的時候可以對于每個變量分別進行采樣，概率模型可以認為是：第十九張，PPT共三十二頁，創(chuàng)作于2022年6月基于不同概率模型的EDA雙變量相關的EDA在實際問題中，變量之間并不總是相互獨立的，最先考慮的是最多兩個變量相關的情況。這種情況下，其概率模型為代表算法 MIMC采樣方法如下1)J=n，根據(jù)第ij個變量

9、的概率分布P(xij)，隨機采樣產(chǎn)生第ij個變量2)根據(jù)第ij個變量的條件概率分布p(xij-1|xij)隨機采樣產(chǎn)生第ij-1個變量；3)J=J-1，如果J=1，則一個完整的解向量構造完成；否則轉2)第二十張，PPT共三十二頁，創(chuàng)作于2022年6月基于不同概率模型的EDA多變量相關EDA變量之間的關系更加復雜，需要更加復雜的概率模型來描述。代表算法EIGA，BOA連續(xù)域的EDA在示例中，我們解決了一個離散的問題，如果X1和X2的取值域是連續(xù)的，我們就需要一個連續(xù)的概率模型來描述解空間的分布。如正態(tài)分布、柯西分布代表算法 CMAES第二十一張，PPT共三十二頁，創(chuàng)作于2022年6月EDA的關鍵

10、問題概率模型選擇合適的概率模型，是發(fā)揮分布估計算法性能的關鍵所在，對于連續(xù)域的比較復雜問題來說，如果采用單峰的概率模型，會取得比較好的收斂速度，但是非常容易收斂到局部最優(yōu)。如果采用多峰的概率模型（如混合高斯模型），對與比較復雜的優(yōu)化問題可能有更強的描述能力，但是這種模型的更新會相對困難。第二十二張，PPT共三十二頁，創(chuàng)作于2022年6月EDA的關鍵問題學習方法如何根據(jù)每一代取得的優(yōu)秀個體來更新概率模型,隨著待解決問題的復雜化和概率圖模型的復雜化，分布估計算法中概率模型的學習占用了大部分的時間和空間開銷，這必然將成為分布估計算法發(fā)展的瓶頸采樣方法如何根據(jù)一個概率模型來采樣得到符合該概率模型的樣本

11、，如Gibbs抽樣。第二十三張，PPT共三十二頁，創(chuàng)作于2022年6月EDA的并行化1：將整個取值區(qū)域分成若干子區(qū)域，每個子區(qū)域并行。2：個體產(chǎn)生的采樣-由于每個個體都是根據(jù)概率模型隨機產(chǎn)生的，因此每個個體可以看做獨立的，所以個體可以并行產(chǎn)生。第二十四張，PPT共三十二頁，創(chuàng)作于2022年6月EDA的優(yōu)缺點優(yōu)點：為人們解決復雜的優(yōu)化問題提供了工具。分布估計算法能更加有效的解決高維問題，降低時間復雜性。缺點：同遺傳算法一樣，理論研究比較困難，很難從理論上解決它適合解決什么問題，概率模型的學習會占用很多時間和空間。第二十五張，PPT共三十二頁，創(chuàng)作于2022年6月示例2求下列函數(shù)的所有極值點y=-

12、試著使用變量無關的EDA解決這個問題第二十六張，PPT共三十二頁，創(chuàng)作于2022年6月示例2概率模型確定對于每一維度對應于一正態(tài)分布，那么 第二十七張，PPT共三十二頁，創(chuàng)作于2022年6月示例2取得優(yōu)秀個體連續(xù)采樣，直到采到N個個體的適應度比當前已經(jīng)取得的最佳適應度要好。如果連續(xù)采樣次數(shù)大于某個閾值，仍沒有得到比目前最好的點，則檢驗是否是極值點。檢驗的方法為令每一維的方差為一個極小值（設為1e-5），采樣多次，若無改進，則認為是極值點，記錄該極值點，若不是極值點，則考慮適當將方差變小，繼續(xù)采樣。第二十八張，PPT共三十二頁，創(chuàng)作于2022年6月示例2概率模型的更新根據(jù)得到的N個優(yōu)秀個體，求這N個點適應度最好的點，得到A=xu1,xu2.xun假設在此之前得到的最好的點為A=xb1,xb2.xb5令C=d1,d2.dn=A-Axui為第i維的正態(tài)分布的均值。di為第i維的正太分布的方差