基于變異粒子群優(yōu)化算法的全局搜索

基于變異粒子群優(yōu)化算法的全局搜索

在科學(xué)工程領(lǐng)域存在著許多多目標(biāo)優(yōu)化問題（mop）。多目標(biāo)優(yōu)化問題的解并非唯一,而是存在一個(gè)最優(yōu)解集合,集合中元素稱為Pareto最優(yōu)解或非劣最優(yōu)解。自從Schaffer的開創(chuàng)性工作,已經(jīng)形成了多種多目標(biāo)優(yōu)化進(jìn)化算法(Multi-objectiveOptimizationEvolutionaryAlgorithm,MOEA)。當(dāng)前MOEA主要是以模擬生物進(jìn)化或其它特性,比如多目標(biāo)遺傳算法直接采用交叉和變異、選擇等操作,多目標(biāo)粒子群優(yōu)化算法模擬鳥群或魚群的覓食的特性,其他的還有蟻群算法等。針對(duì)MOPSO(MultiobjutivePanticleSwarmOptimiztaim),文獻(xiàn)指出MOPSO具有收斂早熟的特性,為避免收斂早熟需引入各種變異操作,但也會(huì)帶來不穩(wěn)定性。為了提高M(jìn)OPSO的多樣性,Li引入了NSGA-II的非支配排序思想,文獻(xiàn)采用超矩形網(wǎng)格,文獻(xiàn)引入最近鄰的概念。但這些算法對(duì)最終解的多樣性的改進(jìn)能力是有限的。2002年,Larranga和Lozano提出了一種新的進(jìn)化算法:基于數(shù)學(xué)建模的分布估計(jì)算法(EstimationofDistributionAlgorithm,EDA)。在EDA中沒有交叉和變異,它從歷史解中提取決策空間的信息并建立期望解的概率分布模型,對(duì)這個(gè)分布模型進(jìn)行采樣而產(chǎn)生下一代的解。文獻(xiàn)開始利用EDA來求解多目標(biāo)優(yōu)化問題。2008年,QingfuZhang和AiminZhou等提出了基于規(guī)則模型的多目標(biāo)分布估計(jì)算法(RegularityModel-BasedMultiobjectiveEstimationofDistributionAlgorithm,RM-MEDA)。該算法與NSGA-II-PCX及GDE3相比在多樣性上顯示了其卓越的性能。近年來,混合算法已經(jīng)被提出用于提高多目標(biāo)優(yōu)化的搜索效率和性能。文獻(xiàn)指出單一種類的多目標(biāo)優(yōu)化算法很難有效地同時(shí)解決收斂性和多樣性的問題。在天氣預(yù)報(bào)等實(shí)際應(yīng)用領(lǐng)域,是多種算法混合在共同發(fā)揮作用?；旌纤惴删哂胁煌匦缘膬?yōu)化算法來共同解決多目標(biāo)優(yōu)化問題,它是今后多目標(biāo)優(yōu)化問題研究的重要內(nèi)容之一。筆者把MOPSO與RM-MEDA結(jié)合在一起的多目標(biāo)優(yōu)化算法MOPSO&EDA。增加了變異的MOPSO具有全局搜索能力,而RM-MEDA具有良好的局部搜索能力,因此將這兩種算法結(jié)合在一起可以發(fā)揮各自的優(yōu)勢(shì),從而可以期望獲得較佳的尋優(yōu)性能。筆者采用6個(gè)基準(zhǔn)函數(shù)進(jìn)行性能測(cè)試,實(shí)驗(yàn)結(jié)果驗(yàn)證了MOPSO&EDA的有效性。1莫斯洛和eda1.1種群q的更新MOPSO&EDA的算法框架如下:Step0)初始化。設(shè)定種群規(guī)模為N,和迭代次數(shù)Nt,迭代計(jì)數(shù)器t=0。產(chǎn)生一個(gè)具有N個(gè)個(gè)體的初始化種群Pop(0),并計(jì)算Pop(0)中個(gè)體的各個(gè)目標(biāo)值。從Pop(0)中隨機(jī)選擇N/2個(gè)粒子形成新的種群PSO_Pop。Step1)如果t等于Nt,停止優(yōu)化,并返回Pop(t)中的非支配解和相應(yīng)的目標(biāo)值。Step2)粒子群飛行。把PSO_Pop中的個(gè)體全部復(fù)制到新的種群Q,從Pop(t)選擇最優(yōu)粒子。種群中的粒子按式(1)和(2)進(jìn)行更新:vi(t)=wvi(t?1)+c1r1(pi?xi(t?1))+c2r2(pg?xi(t?1))?(1)xi(t)=vi(t)+xi(t?1)?(2)vi(t)=wvi(t-1)+c1r1(pi-xi(t-1))+c2r2(pg-xi(t-1))?(1)xi(t)=vi(t)+xi(t-1)?(2)其中:vi-粒子飛行速度;w-慣性權(quán)重;c1,c2-加速度系數(shù);r1,r2-是在范圍變化的隨機(jī)數(shù);Pi-粒子在歷史中的最好位置;pg-整個(gè)群體領(lǐng)導(dǎo)粒子的位置。評(píng)價(jià)種群Q中個(gè)體的各個(gè)目標(biāo)值,更新個(gè)體最優(yōu)位置。Step3)第一次選擇。從集合Pop(t)(PSO_Pop(Q選出N個(gè)粒子代替Pop(t);從PSO_Pop(Q選擇N/2個(gè)粒子代替PSO_Pop。清空Q中的解。Step4)采用RM-MEDA進(jìn)行訓(xùn)練、建模,及產(chǎn)生新個(gè)體。采用RM-MEDA提取Pop(t)中的解在決策空間的信息并建立期望解的概率分布模型(稱為訓(xùn)練和建模),并根據(jù)概率模型產(chǎn)生N/2個(gè)新的解到集合Q。評(píng)價(jià)種群Q中個(gè)體的各個(gè)目標(biāo)值。Step5)第二次選擇。從集合Pop(t)(Q選擇N個(gè)個(gè)體產(chǎn)生Pop(t+1)。令t=t+1,轉(zhuǎn)到Step1)。1.2基于pso算法的多目標(biāo)優(yōu)化在MOPSO&EDA的Step2)是采用粒子群優(yōu)化算法產(chǎn)生N/2個(gè)解。Sierra和Colleo指出將PSO算法應(yīng)用于多目標(biāo)優(yōu)化問題,需要考慮如何選擇最優(yōu)粒子,如何引入變異操作來增強(qiáng)多樣性等問題。下面對(duì)算法的細(xì)節(jié)進(jìn)行詳細(xì)討論。1新個(gè)體最優(yōu)位置如果當(dāng)前解支配個(gè)體歷史最好解,則更新個(gè)體最優(yōu)位置;如果當(dāng)前解不支配歷史最好解,則不更新個(gè)體最優(yōu)位置;否則按50%的概率更新個(gè)體最優(yōu)位置。2總體規(guī)劃是最好對(duì)Pop(t)進(jìn)行非支配排序,第一級(jí)粒子是當(dāng)前種群的非支配解。全局最優(yōu)粒子,就是在第一級(jí)粒子中隨機(jī)選擇產(chǎn)生。3入了變異操作為克服PSO的早熟收斂,很多PSO算法都引入了變異操作,有的是在位置上進(jìn)行變異,有的是在速度上進(jìn)行變異。本文采用HPSO中的變異方式:當(dāng)粒子的速度降為0時(shí),對(duì)速度進(jìn)行變異。4sso的穩(wěn)定性式(1)的第1部分為微粒先前的速度,第2部分為認(rèn)知部分,表示微粒本身的思考;第3部分為社會(huì)部分,表示微粒間的信息共享與相互合作。Ratnaweera評(píng)價(jià)權(quán)限權(quán)重w的作用是作為自我認(rèn)知和社會(huì)認(rèn)知間的平衡。ShiYH等建議權(quán)限權(quán)重w隨代數(shù)線性降落。Ratnaweera認(rèn)為加速度系數(shù)c1在尋優(yōu)初期較大而后期較小,而加速度系數(shù)c2在尋優(yōu)初期較小而后期較大,這樣的設(shè)計(jì)使得PSO在早期突出全局搜索能力,在后期強(qiáng)調(diào)局部搜索能力。文中綜合了文獻(xiàn)的理論,實(shí)驗(yàn)結(jié)果表明在尋優(yōu)過程中w從0.95下降到0.35,c1從2.5下降到0.5,c2從0.5上升到2.5是較佳的選擇。1.3k均值分簇算法文中EDA算法是來源于RM-MEDA。RM-MEDA具有良好多樣性,但其運(yùn)算時(shí)間也相對(duì)較長。RM-MEDA由訓(xùn)練分簇、建模、產(chǎn)生新解幾個(gè)環(huán)節(jié)組成,除訓(xùn)練分簇與RM-MEDA不同外其余環(huán)節(jié)是相同的,建模、產(chǎn)生新解環(huán)節(jié)的具體內(nèi)容參見。RM-MEDA的分簇方法是導(dǎo)致算法運(yùn)行效率低的主要原因,為此需要對(duì)訓(xùn)練環(huán)節(jié)進(jìn)行處理以提高算法執(zhí)行效率。在RM-MEDA的訓(xùn)練環(huán)節(jié),需要把Pop(t)分成K個(gè)簇S1,…,SK。RM-MEDA是采用(m-1)維局部主元分析算法通過最小化式(3)的誤差實(shí)例得到分區(qū)S1,…,SK:∑j=1K∑x∈Sjdist(x,Lm?1j)2。(3)∑j=1Κ∑x∈Sjdist(x,Ljm-1)2。(3)其中:Lm?1jjm-1是第j個(gè)簇中解的仿射(m-1)維主元子空間。dist(x,Lm?1jjm-1)是從x到其在Lm?1jjm-1子空間的映射點(diǎn)之間歐幾里得距離。文獻(xiàn)指出局部主元分析算法比起廣泛采用的K均值分簇法更適合將Pop(t)分簇。K均值分簇法每個(gè)簇的質(zhì)心是一個(gè)點(diǎn),而局部主元分析算法中每個(gè)簇的質(zhì)心是一個(gè)超矩形。但最小化式(3)需要進(jìn)行循環(huán)迭代,每循環(huán)一次都需要計(jì)算K個(gè)簇的協(xié)方差矩陣以及它的特征根和特征根向量,這需要花費(fèi)比較多的時(shí)間,最終影響了RM-MEDA的運(yùn)算效率。作者在先前的工作中采用了兩步訓(xùn)練法來實(shí)現(xiàn)分簇的操作。兩步訓(xùn)練法算法基于以下的假設(shè)推定:在搜索早期,用于建模的解集距離真實(shí)Pareto前沿距離較遠(yuǎn),過于精細(xì)的建模,對(duì)于未來的搜索意義并不大;在搜索后期,用于建模的解集距離真實(shí)Pareto前沿較近,非常細(xì)致的建模對(duì)解的改善作用是有限的。下面對(duì)兩步訓(xùn)練法對(duì)簡(jiǎn)單介紹。盡管K均值分簇法每個(gè)簇的質(zhì)心是一個(gè)點(diǎn),但是其分簇的快速性是很明顯的。訓(xùn)練的第一步首先采用K均值分簇法將Pop(t)分成K個(gè)解體的簇S1,…,SK。具體方法如下:1)在Pop(t)中隨機(jī)選擇K解,并令這個(gè)K個(gè)解分別作為各個(gè)簇的均值xˉˉxˉ。2)將Pop(t)分成K個(gè)解體的簇S1,…,SK,Sj={x|x∈Pop(t),anddist(x,xˉˉj)≤dist(x,xˉˉk)forallk≠j}。Sj={x|x∈Ρop(t),anddist(x,xˉj)≤dist(x,xˉk)forallk≠j}。通過這一步分解得到的簇,顯然是粗糙的。在第一步分簇的基礎(chǔ)上,按下列步驟進(jìn)行第二步細(xì)致分簇:1)采用式(2)計(jì)算每個(gè)簇的均值;2)采用式(3)計(jì)算每個(gè)簇的協(xié)方差矩陣,然后計(jì)算Sj中解的仿射(m-1)維空間Lm?1jjm-1;3)將Pop(t)分成K個(gè)解體的簇S1,…,SK,Sj={x|x∈Pop(t),anddist(x,xm?1j)≤dist(x,xm?1k)forallk≠j}。Sj={x|x∈Ρop(t),anddist(x,xjm-1)≤dist(x,xkm-1)forallk≠j}。實(shí)驗(yàn)結(jié)果表明:兩步訓(xùn)練法在不損失算法優(yōu)化收斂性和多樣性的同時(shí)大幅縮短了算法運(yùn)行時(shí)間。1.4與文獻(xiàn)的討論1文中的選擇操作是基于NSGA-II的非支配排序和RM-MEDA擁擠距離排序。本文與文獻(xiàn)兩者存在微小的差異,文獻(xiàn)是在進(jìn)行擁擠距離排序時(shí)將最小擁擠距離解移動(dòng)到末尾,最后一并刪除。文中是把需要淘汰的最小擁擠距離解直接刪除。2性能試驗(yàn)2.1多目標(biāo)優(yōu)化為對(duì)比MOPSO&EDA的性能,選擇了六個(gè)優(yōu)化測(cè)試實(shí)例ZDT1～ZDT4,ZDT6,ZDT6-1。其中ZDT1(30維)的Pareto前沿為凸實(shí)例,ZDT2(30維)則為非凸實(shí)例,ZDT3(30維)的Pareto前沿為非連續(xù)實(shí)例,而ZDT4(10維)是一個(gè)多峰實(shí)例,ZDT6和ZDT6-1(10維)非凸且非均勻分布。具體定義參見文獻(xiàn),在此不重復(fù)說明。多目標(biāo)優(yōu)化有兩個(gè)目標(biāo):1)收斂到真實(shí)的Pareto前沿;2)保持Pareto解的多樣性。文中采用收斂度Υ和多樣度(來評(píng)價(jià)這兩個(gè)性能。2.2算法c算法在實(shí)驗(yàn)當(dāng)中種群規(guī)模N是100,迭代次數(shù)Nt是250代(25000次實(shí)例評(píng)價(jià))。PSO部分的參數(shù)為:w=[0.95-0.35],c1=[2.5-0.5],c2=[0.5-2.5]最大速度是0.5;EDA部分的參數(shù)為:簇?cái)?shù)K是5,簇?cái)U(kuò)展系數(shù)是0.25。算法采用c++編寫,實(shí)驗(yàn)在CPU為Pentium42.66GHz的同一臺(tái)計(jì)算機(jī)進(jìn)行。為了體現(xiàn)充分性,每組實(shí)驗(yàn)均重復(fù)30次。用于對(duì)比的多目標(biāo)優(yōu)化算法包括:NSGA-II,MOPSO,NSPSO,AMOPSO和σ-MOPSO。實(shí)例評(píng)價(jià)都是25000次。各算法具體參數(shù)設(shè)置參見文獻(xiàn)。2.4mopso&eda在zdt1-zbt3中的測(cè)試結(jié)果多種多目標(biāo)優(yōu)化算法的實(shí)驗(yàn)結(jié)果見表1和表2。NSGA-II結(jié)果來自;NSPSO、MOPSO/C實(shí)驗(yàn)結(jié)果來自文獻(xiàn);RE-MEDA的計(jì)算結(jié)果是采用文獻(xiàn)的作者提供的程序運(yùn)算后獲得。表1顯示MOPSO&EDA相比其它幾種算法提高了在ZDT1-ZDT3測(cè)試實(shí)例上的收斂度。表1中的各種算法經(jīng)過采用25000次評(píng)價(jià)在ZDT4實(shí)例上均不能有效收斂,MOPSO&EDA在其中性能適中。在多樣性方面,MOPSO&EDA在ZDT1-ZDT2實(shí)例,取得了最好的指標(biāo),在ZDT3實(shí)例上僅次于AMOPSO,在ZDT4實(shí)例上性能適中。表3顯示了RM-MEDA與MOPSO&EDA在ZDT6和ZDT6-1上的對(duì)比實(shí)驗(yàn)結(jié)果。在ZDT6上,MOPSO&EDA相比RM_MEDA獲得了更佳的收斂性指標(biāo)和多樣性指標(biāo)。兩種算法在ZDT6-1函數(shù)上的收斂性能相當(dāng),但MOPSO&EDA的多樣性更好。3設(shè)計(jì)出一個(gè)新的最優(yōu)算法圖1顯示MOPSO&EDA與RM-MEDA算法各自在多個(gè)測(cè)試實(shí)例上重復(fù)運(yùn)行30次所得到的Pareto解。左邊列是RM-MEDA的尋優(yōu)結(jié)果,右邊列是MOPSO&EDA的尋優(yōu)結(jié)果。圖1顯示除ZDT6-1兩者收斂性能相當(dāng)外,MOPSO&EDA在其余測(cè)試函數(shù)上的收斂性能均優(yōu)于RM-MEDA。ZDT1實(shí)例是凸實(shí)例,在6個(gè)測(cè)試實(shí)例當(dāng)中難度最低。ZDT2實(shí)例是一個(gè)非凸實(shí)例,多種算法會(huì)最終收斂到1個(gè)點(diǎn)。ZDT3(30維)的Pareto前沿為非連續(xù)實(shí)例,盡管EDA算法是基于連續(xù)性多目標(biāo)優(yōu)化問題的,但是MOPSO&EDA可以有效應(yīng)用在非連續(xù)問題。ZDT6和ZDT6-1的Pareto前沿是非均勻分布的,很難獲得較佳的收斂性和多樣性指標(biāo)。圖1顯示MOPSO&EDA在上述5個(gè)實(shí)例上獲得的Pareto解能逼近真實(shí)Pareto前沿,分布上也較均勻,30次的優(yōu)化結(jié)果幾乎完全重復(fù)。對(duì)于多峰的ZDT4實(shí)例,MOPSO&EDA算法未能給出理想的收斂性。EDA對(duì)具有單一Pareto前沿的問題是比較有效的,而ZDT4具有219個(gè)前沿,會(huì)造成EDA算法陷入局部前沿,很難收斂到真實(shí)的Pareto前沿。盡管帶了變異的MOPSO具有跳出局部最優(yōu)的能力,但仍不能保證MOPSO&EDA收斂到全局的Pareto前沿,表1數(shù)據(jù)顯示其方差達(dá)到了