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

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

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