第8章分布估計(jì)算法

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

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

(Q.Lu,2005)FWH&FHH(Tsutsuietal,2001)sur-shr-HEDA(N.Ding,etal,2006)分布估計(jì)算法的發(fā)展歷史混合分布估計(jì)算法EDA與粒子群優(yōu)化的混合EDA與遺傳算法的混合EDA與差分進(jìn)化算法的混合并行分布估計(jì)算法主從模式島嶼模型收斂性證明應(yīng)用領(lǐng)域越來(lái)越廣泛分布估計(jì)算法的通用流程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一個(gè)簡(jiǎn)單的分布估計(jì)算法例子一個(gè)簡(jiǎn)單的分布估計(jì)算法例子一個(gè)簡(jiǎn)單的分布估計(jì)算法例子一個(gè)簡(jiǎn)單的分布估計(jì)算法例子基于高斯模型的EDA基于高斯模型的EDA的流程如下:第一步:隨機(jī)生成初始種群P(0),初始化高斯模型的均值μ與方差σ.假設(shè)所有變量對(duì)應(yīng)的高斯模型為:

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

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

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

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

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

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

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

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

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