第8章分布估計算法

第8章分布估計算法目錄思想起源1發(fā)展歷史2基本原理3改進研究4應用領域５分布估計算法的思想起源什么是分布估計算法?EstimationofDistributionAlgorithm(EDA)基于種群的新型進化算法思想起源于遺傳算法算法的思想起源改進遺傳算法的交叉操作和變異操作,防止破環(huán)積木塊.采用概率模型和抽樣的隱式形式產生新個體.分布估計算法與遺傳算法的流程比較分布估計算法的發(fā)展歷史開山始祖PBIL:(1994Baluja)UMDA:(1996H.Miihlenbein&Paass)早期的算法專注于二進制編碼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與差分進化算法的混合并行分布估計算法主從模式島嶼模型收斂性證明應用領域越來越廣泛分布估計算法的通用流程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),初始化高斯模型的均值μ與方差σ.假設所有變量對應的高斯模型為:

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

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

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

第三步:若新個體的適應度大于原個體的的適應度則替換之

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

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

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

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

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