第8章分布估計算法

第8章分布估計算法目錄思想起源1發(fā)展歷史2基本原理3改進(jìn)研究4應(yīng)用領(lǐng)域５分布估計算法的思想起源什么是分布估計算法?EstimationofDistributionAlgorithm(EDA)基于種群的新型進(jìn)化算法思想起源于遺傳算法算法的思想起源改進(jìn)遺傳算法的交叉操作和變異操作,防止破環(huán)積木塊.采用概率模型和抽樣的隱式形式產(chǎn)生新個體.分布估計算法與遺傳算法的流程比較分布估計算法的發(fā)展歷史開山始祖PBIL:(1994Baluja)UMDA:(1996H.Miihlenbein&Paass)早期的算法專注于二進(jìn)制編碼MIMIC:(1997J.S.D.Bonet)COMIT:(1997S.Baluja)FDA:(1998H.MUhlenbein)BOA:(1999M.Pelikan)逐漸擴展到連續(xù)分布估計算法PBILc(Sebag,1998)UMDAc

(Larra?aga,P.,etal,2000)CEDGA

(Q.Lu,2005)FWH&FHH(Tsutsuietal,2001)sur-shr-HEDA(N.Ding,etal,2006)分布估計算法的發(fā)展歷史混合分布估計算法EDA與粒子群優(yōu)化的混合EDA與遺傳算法的混合EDA與差分進(jìn)化算法的混合并行分布估計算法主從模式島嶼模型收斂性證明應(yīng)用領(lǐng)域越來越廣泛分布估計算法的通用流程RandomlygeneratedtheinitialpopulationP(0);t=0;WhilenotmettheterminationconditiondoBegin

SelectasetofpromisingindividualsD(t)formthecurrentpopulationP(t);

EstimatetheprobabilitydistributionoftheselectedsetD(t);

GenerateasetofnewindividualsN(t)accordingtotheestimate;

CreateanewpopulationP(t+1)byreplacingsomeindividualsofP(t)byN(t);

t=t+1;end一個簡單的分布估計算法例子一個簡單的分布估計算法例子一個簡單的分布估計算法例子一個簡單的分布估計算法例子基于高斯模型的EDA基于高斯模型的EDA的流程如下:第一步:隨機生成初始種群P(0),初始化高斯模型的均值μ與方差σ.假設(shè)所有變量對應(yīng)的高斯模型為:

(N(μ1,σ1),N(μ2,σ2),…,N(μD,σD))

其中D為待求解問題的維數(shù).第二步:根據(jù)各維變量對應(yīng)的高斯模型,抽樣產(chǎn)生新種群T(t).第三步:從新種群中選擇優(yōu)秀個體集合S(t).第四步:計算S(t)在各維變量上的均值與方差,對原有的高斯模型進(jìn)行更新.高斯模型的更新方法更新概率模型中的兩個重要參數(shù):均值和方差其中K為優(yōu)秀個體的個數(shù).xbest,1,xbest,2為最好的兩個個體,xworst則為最差的個體.更新的方式多種多樣,也可以直接用優(yōu)秀個體的均值和方差替代原來的均值與方差.Popsize,Parentsize,q0,k，LBOUND，UBOUND基于直方圖概率模型的EDA基于鏈?zhǔn)礁怕誓Ｐ偷腅DAMutualInformationMaximizationforInputClustering，MIMIC變量之間的關(guān)系是一種鏈?zhǔn)降年P(guān)系，即在n維隨機變量組成的鏈中，只有相鄰的變量之間才有關(guān)系.聯(lián)合概率密度在形式上產(chǎn)生變化:其中π是根據(jù)鏈?zhǔn)疥P(guān)系的一種排列.如何找出最優(yōu)的π?基于樹狀概率模型的EDACombiningOptimizersWithMutualInformationTrees,COMITCOMIT采用一種樹狀結(jié)構(gòu)來描述兩量變量之間的關(guān)系,表達(dá)能力比MIMIC更強.關(guān)鍵是如何確立變量之間樹狀關(guān)聯(lián)關(guān)系的結(jié)構(gòu)?采用機器學(xué)習(xí)領(lǐng)域中Chow和Liu提出的方法構(gòu)造概率模型基于貝葉斯網(wǎng)絡(luò)模型的EDA采用貝葉斯網(wǎng)絡(luò)來描述變量之間概率依賴關(guān)系

(其中節(jié)點代表變量，邊表示變量之間的概率依賴關(guān)系)基于貝葉斯網(wǎng)絡(luò)的聯(lián)合概率密度為：基于貝葉斯網(wǎng)絡(luò)模型的EDA關(guān)鍵問題貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)如何確定?算法流程分布估計算法與遺傳算法混合分布估計算法與差分進(jìn)化算法混合第一步:從種群中選出M個較優(yōu)的個體，建立如下概率模型第二步:產(chǎn)生一個0~1之間的隨機值v，若v≤α，則按照DE方式產(chǎn)生新個體，否則按照EDA的方式取樣產(chǎn)生新個體。

第三步:若新個體的適應(yīng)度大于原個體的的適應(yīng)度則替換之

第四步:若產(chǎn)生了足夠數(shù)量的新種群則終止，否則執(zhí)行第一步并行分布估計算法(一)種群級別并行化思路:將種群分成多個子種群，每個子種群在不同的機器上運行，然后各個子種群通過遷移等機制進(jìn)行通信，達(dá)到綜合信息的目的

并行分布估計算法(二)適應(yīng)度評估并行化思路:適應(yīng)度評估通常是算法中最耗時的部分，因而,采用多臺機器并行計算種群中的適應(yīng)度可有效提高算法求解速度

主從模式并行計算并行分布估計法(三)概率模型構(gòu)建并行化思路:設(shè)計復(fù)雜的概率模型需要較大的計算量,并行求解復(fù)雜概率模型可有效提高算法計算速度.

其他并行機制采樣的操作進(jìn)行并行化混合并行機制分布估計算法的理論研究研究者說明MarkusHohfeld(1997)[63]證明PBIL在解決線性的二進(jìn)制優(yōu)化問題時，可以收斂到全局最優(yōu)解，解非線性問題可能會陷入局部最優(yōu)。H.Muhlenbein(1998)[64]對UMDA的收斂性進(jìn)行分析，假設(shè)種群無窮大。H.Muhlenbein(1998)[65]

對FDA的收斂性進(jìn)行分析。M.Pelikan(2001)[66]對BOA解決OneMax問題的收斂性進(jìn)行分析。Q.F.Zhang(2004)[67]對種群規(guī)模無窮大的EDA進(jìn)行數(shù)學(xué)建模，分析了EDA算法達(dá)到全局收斂的一些條件。R.Rastegar(2005)[68]分析了種群規(guī)模無窮大的EDA要達(dá)到全局收斂所需要的代數(shù)。TianshiChen(2007)[69]對早期的兩個分布估計算法：UMDA和增量UMDA進(jìn)行時間復(fù)雜度的分析。JiriOcenasek(2006)[70]提出用熵來度量分布估計算法收斂性的方法，并在此基礎(chǔ)上分析了EDA終止的條件?！植脊烙嬎惴ǖ膽?yīng)用領(lǐng)域(函數(shù)優(yōu)化)有效地保護(hù)“積木塊”，能夠高效求解高維的復(fù)雜函數(shù)優(yōu)化問題.在具有先驗知識的情況下，可有針對地選擇概率模型，從而設(shè)計出性能優(yōu)越的分布估計算法.已成功應(yīng)用于求解復(fù)雜的多峰函數(shù),關(guān)聯(lián)性強的復(fù)雜函數(shù)優(yōu)化以及多目標(biāo)函數(shù)優(yōu)化.分布估計算法的應(yīng)用領(lǐng)域(組合優(yōu)化)應(yīng)用（中文）英文參考文獻(xiàn)旅行商問題TravelingSalesmanProblemLarra?aga(2002)[33]作業(yè)調(diào)度問題JobShopSchedulingProblemLarra?aga(2002)[33]、Jarboui(2008)[38]護(hù)士調(diào)度問題NurseSchedulingProblemU.Aickelin(2006)[39]網(wǎng)絡(luò)控制NetworkControlH.B.Li(2008)[37]最大團(tuán)問題MaximumCliqueProblemQ.F.Zhang(2005)[34]核反應(yīng)堆燃料管理問題NuclearReactorFuelManagementS.Jiang(2006)[36]最大分集問題MaximumDiversityProbl