高維多目標(biāo)頭腦風(fēng)暴優(yōu)化算法

吳亞麗 付玉龍李國(guó)婷張亞崇

(1.西安理工大學(xué)自動(dòng)化與信息工程學(xué)院,陜西西安 710048;2.陜西省復(fù)雜系統(tǒng)控制與智能信息處理重點(diǎn)實(shí)驗(yàn)室,陜西西安 710048;3.西安飛行自動(dòng)控制研究所,陜西西安 710065)

1 引言

作為一種典型的復(fù)雜優(yōu)化問(wèn)題,多目標(biāo)優(yōu)化問(wèn)題(multi-objective optimization problem,MOP)已廣泛應(yīng)用于工程領(lǐng)域以及現(xiàn)實(shí)生活中,如地下水監(jiān)測(cè)問(wèn)題[1]、PID控制器設(shè)計(jì)問(wèn)題[2]、網(wǎng)絡(luò)社會(huì)物理系統(tǒng)[3]等領(lǐng)域.近幾年,隨著時(shí)代的發(fā)展,現(xiàn)實(shí)所面臨的問(wèn)題越來(lái)越復(fù)雜,并且呈現(xiàn)出動(dòng)態(tài)、多約束、大規(guī)模、目標(biāo)個(gè)數(shù)增加等特性.通常,稱目標(biāo)個(gè)數(shù)多于3個(gè)的MOP為高維多目標(biāo)優(yōu)化問(wèn)題(many-objective optimization problem,MaOP).

與單目標(biāo)優(yōu)化問(wèn)題(single-objective optimization problem,SOP)相比,MOP需要得到一組解來(lái)逼近問(wèn)題真實(shí)的前沿,這組解在決策空間中被稱為Pareto最優(yōu)解集(pareto set,PS),在目標(biāo)空間中被稱為Pareto最優(yōu)前沿(pareto front,PF).當(dāng)問(wèn)題的目標(biāo)個(gè)數(shù)增加時(shí),用來(lái)解決多目標(biāo)問(wèn)題的經(jīng)典算法表現(xiàn)出了較大的局限性,主要表現(xiàn)在收斂能力和多樣性保持能力兩個(gè)方面.

由于目標(biāo)數(shù)目的增加,種群中的非支配解所占比重隨著目標(biāo)個(gè)數(shù)急劇增加[4],選擇壓力減小,支配關(guān)系難以適用,導(dǎo)致算法的進(jìn)化速度降低.基于此問(wèn)題,主要研究分為以下兩點(diǎn):①開發(fā)或改進(jìn)支配方式,增加選擇壓力,如?--支配[5]、L--最優(yōu)[6]、模糊支配[7]、網(wǎng)格支配[8]、θ--支配[9]、增強(qiáng)支配(strengthened dominance relation,SDR)等[10],其主要通過(guò)更加松弛的支配關(guān)系來(lái)對(duì)原本互不支配的個(gè)體進(jìn)行區(qū)分,以更加合理地進(jìn)行適應(yīng)度選擇和環(huán)境選擇;②Pareto支配與其他選擇指標(biāo)相結(jié)合,如基于分解的多目標(biāo)進(jìn)化算法[11-13]、基于指標(biāo)的多目標(biāo)進(jìn)化算法[14-15]等,主要通過(guò)權(quán)重向量對(duì)個(gè)體進(jìn)行衡量或根據(jù)個(gè)體對(duì)整體指標(biāo)的貢獻(xiàn)來(lái)對(duì)個(gè)體進(jìn)行適應(yīng)度值分配.

在多樣性的保持能力方面,由于目標(biāo)函數(shù)的增加使得候選解稀疏地分布在高維空間里,導(dǎo)致了傳統(tǒng)多樣性維持策略的低效性.盡管擁擠距離的策略已較為成熟且表現(xiàn)出良好的性能[16],但在MaOP方面仍然表現(xiàn)出較低的效率.為此,文獻(xiàn)[17]提出角度懲罰距離的概念,并證明了基于角度的度量不僅具有可擴(kuò)展性,而且性能優(yōu)于基于歐氏距離的方式.基于參考點(diǎn)的選取也是當(dāng)前流行的一種Pareto解集的維持策略,已被應(yīng)用于很多比較流行的算法中[12,17-18].

由上述分析可以看出,MaOP問(wèn)題的研究難點(diǎn)是收斂性和多樣性之間的權(quán)衡.大多數(shù)算法將其歸結(jié)于根據(jù)目標(biāo)值進(jìn)行適應(yīng)度值分配以及選擇問(wèn)題,并從各方面提出了分配以及選擇策略.文獻(xiàn)[13]和文獻(xiàn)[19]從問(wèn)題角度出發(fā),圍繞各決策變量對(duì)目標(biāo)的影響將其分為收斂性相關(guān)變量和多樣性相關(guān)變量,然后分別對(duì)其進(jìn)行優(yōu)化,增強(qiáng)優(yōu)化結(jié)構(gòu);此外,采用分而治之的思想對(duì)無(wú)關(guān)收斂性相關(guān)變量分別進(jìn)行優(yōu)化,提高優(yōu)化效率,取得了非常好的效果.

在眾多的智能優(yōu)化算法中,史玉回教授2011年提出的頭腦風(fēng)暴優(yōu)化算法(brain storm optimization,BSO)以聚類中心為導(dǎo)向,并以概率朝著其他個(gè)體進(jìn)行學(xué)習(xí),能夠較好地兼顧收斂性和多樣性[20].在經(jīng)典算法的基礎(chǔ)上,不同研究者圍繞其聚類、變異、以及更新歸檔集的方式衍生出了多種多目標(biāo)頭腦風(fēng)暴優(yōu)化算法(multi-objective brain storm optimization,MOBSO),均取得了較好的結(jié)果[21-23].文獻(xiàn)[21]將聚類應(yīng)用于目標(biāo)空間,并采用精英類策略,加快MOBSO的收斂速度.文獻(xiàn)[22]采用DBSCAN聚類代替經(jīng)典BSO中的k--means聚類,用差分變異代替高斯變異,提出了改進(jìn)的多目標(biāo)頭腦風(fēng)暴優(yōu)化算法(modified multi-objective brain storm optimization,MMBSO),效果大幅提高.文獻(xiàn)[23]采用了MBSO中的簡(jiǎn)單聚類,并在差分變異的基礎(chǔ)上引入了開放性概率,有效避免陷入局部最優(yōu)(self-adaptive multi-objective brain storm optimization,SMOBSO),吳亞麗等人[24]將其用于解決熱電聯(lián)供環(huán)境經(jīng)濟(jì)調(diào)度(environment economic dispatch,EED)問(wèn)題,結(jié)果優(yōu)于效果較好的準(zhǔn)對(duì)抗教學(xué)優(yōu)化算法(quasioppositional teaching learning based optimization,QOTLBO).

基于上述的研究基礎(chǔ),本文綜合BSO算法的進(jìn)化優(yōu)勢(shì)與聚類思想的選擇策略,提出一種有效的高維多目標(biāo)頭腦風(fēng)暴優(yōu)化算法.算法對(duì)MaOP問(wèn)題的決策變量特性進(jìn)行進(jìn)一步特征提取,并基于不同的特征設(shè)計(jì)不同的進(jìn)化策略.主要步驟為:首先,根據(jù)決策變量的特征將其分為收斂性相關(guān)變量和多樣性相關(guān)變量,并采取不同的優(yōu)化策略.對(duì)于收斂性相關(guān)變量,對(duì)收斂性相關(guān)變量進(jìn)行獨(dú)立性分析,對(duì)于相互獨(dú)立的變量“分而治之”,提高算法優(yōu)化效率;并采用分解的策略將多個(gè)目標(biāo)轉(zhuǎn)換為一個(gè)目標(biāo),增加選擇壓力,提高收斂速度;對(duì)于多樣性相關(guān)變量,提出了一種新的以角點(diǎn)為聚類中心的自適應(yīng)聚類方式,以一定的概率基于類中心產(chǎn)生新個(gè)體提高算法的擴(kuò)展性:采用參考點(diǎn)策略更新種群,提高算法的均勻性.此外,為了增強(qiáng)算法的導(dǎo)向性,個(gè)體對(duì)應(yīng)的權(quán)重向量和參考點(diǎn)均采用標(biāo)準(zhǔn)邊界交叉方法(normal-boundary intersection,NBI)方式生成且相對(duì)應(yīng),且每次迭代中進(jìn)行動(dòng)態(tài)分配.在以權(quán)重向量進(jìn)行目標(biāo)轉(zhuǎn)換和以參考點(diǎn)進(jìn)行更新時(shí),個(gè)體以參考點(diǎn)為導(dǎo)向.文中給出大量的仿真算例來(lái)驗(yàn)證算法的有效性.

2 頭腦風(fēng)暴優(yōu)化算法的基本原理

2.1 頭腦風(fēng)暴優(yōu)化算法

頭腦風(fēng)暴優(yōu)化算法(BSO)是受人類頭腦風(fēng)暴會(huì)議所啟發(fā),將產(chǎn)生的每一個(gè)想法看做是一個(gè)潛在的可行解,產(chǎn)生想法的過(guò)程遵循“庭外判決”、“各抒己見(jiàn)”、“取長(zhǎng)補(bǔ)短”、“追求數(shù)量”的原則,即產(chǎn)生盡可能多的解,量變產(chǎn)生質(zhì)變.與人類頭腦風(fēng)暴會(huì)議過(guò)程類似,頭腦風(fēng)暴優(yōu)化算法以聚類中心為導(dǎo)向產(chǎn)生新個(gè)體對(duì)應(yīng)于以一個(gè)較好的想法為參考生成新的想法.在得到導(dǎo)向之后,新個(gè)體通過(guò)在其基礎(chǔ)上進(jìn)行變異來(lái)產(chǎn)生,每一次迭代完后進(jìn)行比較,保留較好的個(gè)體進(jìn)入下一次迭代.頭腦風(fēng)暴優(yōu)化算法過(guò)程如下所示[20]:

Step 1種群初始化;

Step 2評(píng)價(jià)個(gè)體,聚類;

Step 3產(chǎn)生新個(gè)體;

Step 4更新種群和聚類中心;

Step 5若達(dá)到最大迭代次數(shù)則輸出最優(yōu)個(gè)體,否則轉(zhuǎn)Step 2.

傳統(tǒng)的BSO采用k--means進(jìn)行聚類,并將每個(gè)類中最優(yōu)的個(gè)體作為聚類中心.在產(chǎn)生新個(gè)體時(shí),選擇個(gè)體以一定的概率分別為一個(gè)聚類中心、一個(gè)類中個(gè)體、兩個(gè)聚類中心或者類中個(gè)體的加權(quán)和.在此基礎(chǔ)上,通過(guò)加變異實(shí)現(xiàn)對(duì)當(dāng)前解的探索過(guò)程,常用的高斯變異定義如下:

其中:logsig是一個(gè)S型對(duì)數(shù)傳遞函數(shù);T 為最大迭代次數(shù);t為當(dāng)前迭代次數(shù);K用來(lái)改變logsig的斜率,可調(diào)節(jié)算法由全局搜索到局部搜索的速度;rand產(chǎn)生(0,1)之間的隨機(jī)值.

張軍等人[25]提出以差分變異代替高斯變異,并取得了更好的效果且已經(jīng)成功用于多種版本的BSO中[23-24,26].差分變異如式(3)所示:

其中:Ld,Hd為第d維的上下界,為在當(dāng)代全局中選擇的兩個(gè)不同的個(gè)體的第d 維.為了保持種群的多樣性,防止陷入局部最優(yōu),設(shè)置開放性概率Pr.

從式(3)可以看出,與高斯變異相比,差分變異運(yùn)算量減小,運(yùn)行速度提高.而且變異量的產(chǎn)生是基于當(dāng)代種群內(nèi)其他個(gè)體而來(lái),可根據(jù)種群內(nèi)個(gè)體的離散程度來(lái)自適應(yīng)調(diào)節(jié),能夠更好地與種群內(nèi)其他個(gè)體共享信息,其搜索效率顯著提高.因此,差分變異能夠在搜索過(guò)程中更好地平衡局部搜索和全局搜索,有效地提高算法性能.

2.2 多目標(biāo)頭腦風(fēng)暴優(yōu)化算法

與BSO相比,MOBSO引入了歸檔集的策略,用來(lái)保存Pareto最優(yōu)解.在每次迭代中對(duì)種群進(jìn)行非支配排序,取非支配解計(jì)入歸檔集,然后進(jìn)行更新,最終得到一組足夠靠近最優(yōu)前沿且均勻的解.MOBSO采用循環(huán)擁擠距離策略更新歸檔集.首先令兩個(gè)端點(diǎn)的擁擠距離為無(wú)窮大,然后分別計(jì)算所有個(gè)體相鄰點(diǎn)在目標(biāo)空間的曼哈頓距離,逐次刪除擁擠距離最小的個(gè)體,以保持歸檔集內(nèi)的個(gè)體具有均勻性.MOBSO能夠很好地解決兩個(gè)目標(biāo)的優(yōu)化問(wèn)題并應(yīng)用于實(shí)際,由于其對(duì)新個(gè)體的選擇機(jī)制使得難以用于解決MaOP,且原始的基于Pareto支配策略導(dǎo)致使得算法收斂速度過(guò)慢.基于此,本文將歸檔集的更新策略和多樣性選擇機(jī)制進(jìn)行重新設(shè)計(jì),提出了一種求解高維多目標(biāo)優(yōu)化問(wèn)題的頭腦風(fēng)暴優(yōu)化算法.

3 高維多目標(biāo)頭腦風(fēng)暴優(yōu)化算法

3.1 主要框架

多目標(biāo)優(yōu)化算法的目的在于得到一組優(yōu)秀且均勻的Pareto最優(yōu)解,由于不同特性的決策變量對(duì)優(yōu)化結(jié)果有著不同的影響[19],因此在每一次迭代中先后進(jìn)行收斂性優(yōu)化和多樣性優(yōu)化,即先使得個(gè)體向好的方向移動(dòng),然后保持種群的多樣性.在進(jìn)行優(yōu)化之前,首先需產(chǎn)生參考點(diǎn)以及對(duì)決策變量進(jìn)行聚類.算法的主要框架見(jiàn)算法1.

算法1MaOBSO.

輸入:M(目標(biāo)個(gè)數(shù)),Emax(最大評(píng)價(jià)次數(shù)),Po(選擇一個(gè)個(gè)體產(chǎn)生新個(gè)體的概率),Pc(選擇聚類中心產(chǎn)生新個(gè)體的概率);

輸出:P(最終種群);

MaOBSO采用NBI[18]的方式生成權(quán)重向量,因此直接將種群視為歸檔集.在算法1中,首先進(jìn)行初始化,包括生成新的種群以和參考點(diǎn),并以角點(diǎn)為聚類中心對(duì)參考點(diǎn)進(jìn)行聚類.然后將個(gè)體與參考點(diǎn)進(jìn)行匹配,并將參考點(diǎn)的聚類結(jié)果對(duì)應(yīng)到種群中.接著將決策變量分為收斂性相關(guān)變量和多樣相關(guān)變量,并對(duì)收斂性相關(guān)變量進(jìn)行獨(dú)立性分析.最后進(jìn)行變量?jī)?yōu)化.

算法2VectorAllocation(P,w,M).

輸入:P(種群),w(參考向量),M(目標(biāo)個(gè)數(shù));

輸出:w(分配后的向量),cluster(聚類結(jié)果);

算法2為將參考點(diǎn)和個(gè)體相對(duì)應(yīng)以及聚類的過(guò)程.本文采用參考向量的策略,首先對(duì)參考向量根據(jù)以其角點(diǎn)(極端點(diǎn))為中心進(jìn)行聚類,確定每個(gè)向量所屬類別.然后計(jì)算每個(gè)向量與個(gè)體在目標(biāo)空間的夾角,根據(jù)角度進(jìn)行分配,并以分配關(guān)系將參考點(diǎn)的角力聚類結(jié)果對(duì)應(yīng)到種群.以3目標(biāo)DTLZ1為例,在進(jìn)化途中種群在目標(biāo)空間中的聚類結(jié)果如圖1所示.

圖1 3目標(biāo)DTLZ1進(jìn)化中聚類結(jié)果Fig.1 The cluster result of DTLZ1 of 3 objectives while evolutionary

3.2 決策變量聚類

現(xiàn)實(shí)中的問(wèn)題是多種多樣的.對(duì)于有的問(wèn)題來(lái)說(shuō),其對(duì)維度變化非常敏感,當(dāng)某些維度有較小偏離時(shí),其適應(yīng)度值便極度遠(yuǎn)離真實(shí)的Pareto前沿,或者對(duì)整體均勻性造成很大的影響.以以下多目標(biāo)問(wèn)題為例:

分別對(duì)式(4)中x1和x2保持不變,讓另一個(gè)變量在定義域內(nèi)均勻變化,觀察其在目標(biāo)空間中的變化,如圖2所示.

圖2 分別改變x1和x2得到的適應(yīng)度值分布Fig.2 The fitness distribution obtained by perturbing x1and x2respectively

由圖2可見(jiàn),當(dāng)分別改變x1和x2而固定其他維度時(shí)在目標(biāo)空間中有著不同的影響,顯然,x1影響MOP的收斂性,而x2影響多樣性,分別稱為收斂性相關(guān)變量(convergence variables,CV)和多樣性相關(guān)變量(diversity variables,DV).對(duì)于CV,需要找到一個(gè)最優(yōu)值,來(lái)支配其他所有值下對(duì)應(yīng)的解;而對(duì)于DV,需要使其合理分布,促使對(duì)應(yīng)的解在目標(biāo)空間中均勻分布[13,18].

算法3VariableCluster(P).

輸入:P(種群);

輸出:DV(多樣性相關(guān)變量);CV(收斂性相關(guān)變量);

算法3為決策變量聚類的過(guò)程.本文從定義出發(fā),對(duì)于每一個(gè)決策變量,分別在其他決策變量不變的情況下對(duì)其進(jìn)行擾動(dòng),即由一個(gè)個(gè)體得到種群,然后對(duì)種群進(jìn)行非支配排序,則非支配序列便可反映決策變量的特征.

所有決策變量得到的非支配序列構(gòu)成的矩陣反映了所有的特征.嚴(yán)格來(lái)說(shuō),收斂性相關(guān)變量得到種群的非支配序列個(gè)數(shù)為1,而多樣性相關(guān)變量的序列個(gè)數(shù)等于對(duì)應(yīng)個(gè)體數(shù).因此,本文采用k--means聚類將序列得到的矩陣分為兩類,較小的類別為收斂性相關(guān)變量.較大的則為多樣性相關(guān)變量.

3.3 變量獨(dú)立性分析

決策變量規(guī)模增加時(shí)優(yōu)化難度也隨之增加,但現(xiàn)實(shí)中往往需要解決較大規(guī)模的問(wèn)題.一直以來(lái),學(xué)者們致力于找到一種更好的方法來(lái)找到全局最優(yōu)解,另一種策略便是對(duì)問(wèn)題進(jìn)行簡(jiǎn)化,將一個(gè)大規(guī)模優(yōu)化問(wèn)題分解為多個(gè)簡(jiǎn)單的小規(guī)模優(yōu)化問(wèn)題.對(duì)于一個(gè)SOP,稱滿足

的函數(shù)為可分離函數(shù),否則稱為不可分離函數(shù).

對(duì)優(yōu)化問(wèn)題“分而治之”能夠很大程度上提高優(yōu)化效率,其表示變量之間互不影響,因此能夠逐個(gè)對(duì)變量進(jìn)行優(yōu)化.但問(wèn)題的變量之間是否具有依賴性難以提前所知,判斷的方式為:對(duì)于兩個(gè)決策變量xi和xj,若存在a1,a2,b1,b2滿足

則稱xi和xj為互不獨(dú)立變量.對(duì)于收斂性相關(guān)變量獨(dú)立性分析算法見(jiàn)算法4.

算法4InteractionAnalysis(P,CV).

輸入:P(種群);CV(收斂性相關(guān)變量);

輸出:sub CVs(非獨(dú)立的收斂性相關(guān)變量集合);

3.4 變量?jī)?yōu)化

本文將決策變量分為收斂性相關(guān)變量和多樣性相關(guān)變量,對(duì)其進(jìn)行不同的優(yōu)化策略對(duì)算法的進(jìn)化結(jié)構(gòu)有著顯著的提升.算法5為收斂性優(yōu)化過(guò)程,為了增加選擇壓力,使種群更快地趨近于Pareto前沿,本文采用加權(quán)邊界相交(penalty-based boundary intersection,PBI)的策略來(lái)評(píng)價(jià)一個(gè)解的優(yōu)劣[12].PBI策略能將個(gè)體的多個(gè)目標(biāo)值轉(zhuǎn)換為一個(gè)目標(biāo)值,其計(jì)算公式為

其中:θ為自定義的懲罰參數(shù),可用來(lái)權(quán)衡解收斂性與多樣性.可見(jiàn),d1為所有目標(biāo)構(gòu)成的點(diǎn)f距離所有目標(biāo)最小值構(gòu)成的點(diǎn)的距離,能夠衡量x的收斂程度,d2表示點(diǎn)f 與權(quán)重w的間距,能夠衡量x的分布特性,因此PBI能夠更加全面地用一個(gè)值來(lái)衡量一個(gè)解的優(yōu)劣程度.

算法5ConverOptimi(P,sub CVs,Zmin).

輸入:P(種群),sub CVs(非獨(dú)立的收斂性相關(guān)變量集合),Zmin(當(dāng)前種群中每個(gè)目標(biāo)的最小值);

輸出:P(新種群);

算法5以個(gè)體的PBI值為標(biāo)準(zhǔn)以輪盤賭的方式選擇父代,通過(guò)模擬二進(jìn)制交叉(simulated binary crossover,SBX)來(lái)產(chǎn)生新個(gè)體,在種群更新方面,通過(guò)比較父代與新個(gè)體的PBI值保留較好的進(jìn)入新的種群.

算法6為多樣性優(yōu)化的過(guò)程.與原始BSO的機(jī)制類似,算法以聚類中心為導(dǎo)向,并以概率選擇其他個(gè)體作為當(dāng)前個(gè)體,通過(guò)變異實(shí)現(xiàn)對(duì)個(gè)體周圍的搜索.在得到新的種群后,將原種群與新種群進(jìn)行合并,通過(guò)計(jì)算與參考點(diǎn)的夾角來(lái)對(duì)種群進(jìn)行更新.

此外,為了避免不必要的搜索,本文設(shè)置了收斂?jī)?yōu)化指標(biāo).當(dāng)種群的收斂性相關(guān)變量的方差的平均值小于某一閾值時(shí)停止收斂性優(yōu)化.值得注意的是,在收斂性優(yōu)化和多樣性優(yōu)化時(shí),分別只改變收斂性相關(guān)變量和多樣性相關(guān)變量.

算法6DiverOptimi(P,Po,Pc,DV,w,cluster,Zmin,Znad).

輸入:P(當(dāng)前種群),Po(用一個(gè)個(gè)體產(chǎn)生新個(gè)體的概率),Pc(用聚類中心產(chǎn)生新個(gè)體的概率),DV(多樣性相關(guān)變量),w(參考點(diǎn)),cluster(聚類結(jié)果),Zmin(當(dāng)前種群中每個(gè)目標(biāo)上的最小值),Znad(Pareto前沿在每個(gè)目標(biāo)上的截距);

輸出:P(新種群);

4 仿真結(jié)果與分析

為了測(cè)試本文算法的性能,本文分別選擇ZDT和DTLZ測(cè)試函數(shù)集來(lái)評(píng)價(jià)算法解決MOP和MaOP的性能,以反演世代距離(inverted generational distance,IGD)[27]為指標(biāo)來(lái)綜合比較本文算法與幾種經(jīng)典算法的性能.

4.1 多目標(biāo)優(yōu)化問(wèn)題的性能

本文采用ZDT測(cè)試函數(shù)集來(lái)評(píng)價(jià)算法解決MOP的性能,并與算法MOBSO,MMBSO,SMOBSO以及經(jīng)典算法NSGA--II進(jìn)行綜合比較.其中,選用30維的ZDT1-ZDT4和ZDT6;歸檔集大小和總評(píng)價(jià)次數(shù)統(tǒng)一 為51 和20000;細(xì)節(jié)方面,MOBSO,MMBSO 和SMOBSO分別設(shè)p1,p2,p3,p4為0.8,0.8,0.2,0.2,聚類個(gè)數(shù)為4,NSGA--II采用模擬二進(jìn)制交叉和多項(xiàng)式變異,MaOBSO分別設(shè)Po和Pc為0.8,0.3.擁擠距離策略在處理雙目標(biāo)優(yōu)化問(wèn)題時(shí)非常高效且操作簡(jiǎn)單,因此在測(cè)試算法解決MOP能力時(shí),采用擁擠距離策略來(lái)進(jìn)行環(huán)境選擇.算法運(yùn)行30次,記錄平均值以及標(biāo)準(zhǔn)如表1所示,其中,加粗以及加黑的結(jié)果表示最優(yōu)的性能.

表1 MaOBSO與經(jīng)典算法解決MOP時(shí)IGD比較Table 1 The comparison of IGD between MaOBSO and classic algorithms while solving MOP

由表1 可見(jiàn),與其他算法相比,MaOBSO 表現(xiàn)出非常優(yōu)異的性能.對(duì)于較為常規(guī)的ZDT1 和ZDT2,MaOBSO較大幅度領(lǐng)先于經(jīng)典版本的多目標(biāo)BSO,與經(jīng)典算法NSGA--II相比也有所領(lǐng)先;對(duì)于有著不連續(xù)前沿的ZDT3,算法在收斂性能和多樣性能優(yōu)化方面均難度較大,MaOBSO性能提升更加明顯;對(duì)于具有大量局部極值點(diǎn)的ZDT4和非均勻函數(shù)ZDT6,其他算法綜合性能變差,而MaOBSO仍能夠保持非常優(yōu)異的性能.為了更加直接地觀察算法得到的Pareto最優(yōu)解,以ZDT1,ZDT3,ZDT4為例,取30 次中最接近IGD 平均值的一次結(jié)果如圖3所示.

圖3 MaOBSO與經(jīng)典算法解決MOP時(shí)的Pareto最優(yōu)解集Fig.3 The Pareto set of MaOBSO and classic algorithms while solving MOP

由圖3可見(jiàn),對(duì)于幾個(gè)測(cè)試函數(shù)而言,MaOBSO從綜合性能上有著最優(yōu)異的表現(xiàn).從收斂性角度看,MaOBSO在ZDT1,ZDT3上略微領(lǐng)先于其他算法,在ZDT1 以及SMOBSO 處理ZDT3 時(shí)更加明顯.對(duì)于ZDT4,MaOBSO與相比其他算法有著較為明顯的提升,對(duì)比幾種版本的頭腦風(fēng)暴優(yōu)化算法可見(jiàn),MMBSO中差分變異相比MOBSO的高斯變異能夠更加積極地促進(jìn)算法的收斂性,而SMOBSO引入的開放性概率對(duì)于算法收斂起到了進(jìn)一步的促進(jìn)作用.從多樣性角度來(lái)看,MaOBSO在ZDT1上略微領(lǐng)先于其他算法,對(duì)于ZDT3而言,MMBSO,SMOBSO和MaOBSO性能優(yōu)于MOBSO和NSGA--II,表明了循環(huán)擁擠距離在維持多樣性方面領(lǐng)先于擁擠距離.而對(duì)于ZDT4 而言,即使MMBSO和SMOBSO采用了循環(huán)擁擠距離,但依然有著較差的多樣性能,可見(jiàn)算法的收斂性能較差時(shí)對(duì)多樣性能有著一定程度的影響.

綜上分析,MaOBSO在處理MOP時(shí)從收斂性能和多樣性能方面均有較大幅度的提升,當(dāng)優(yōu)化難度增加時(shí)更為明顯,表明了采用決策變量聚類策略在改進(jìn)算法進(jìn)化結(jié)構(gòu)方面的合理性與高效性,且具有更大的潛力.此外,從穩(wěn)定性角度來(lái)說(shuō),MaOBSO處理MOP時(shí)IGD指標(biāo)標(biāo)準(zhǔn)差較小,表明了算法具有較好的穩(wěn)定性.

4.2 高維多目標(biāo)優(yōu)化問(wèn)題的性能

本文采用經(jīng)典的DTLZ測(cè)試函數(shù)集來(lái)評(píng)價(jià)算法解決MaOP 的性能,并與當(dāng)前較為流行的算法MOEA/DD,NSGA--III,LMEA,MOEA/DVA以及RVEA進(jìn)行綜合比較.對(duì)于DTLZ測(cè)試函數(shù)集而言,決策維度D=K+M?1,其中:M為目標(biāo)個(gè)數(shù),K為難度因子.本文對(duì)于DTLZ1設(shè)K=5,DTLZ2-DTLZ6設(shè)K=10,DTLZ7設(shè)K=20;分別測(cè)試M=3,5,8,10下的性能,歸檔集大小分別設(shè)置為105,126,72,65,最大迭代次數(shù)統(tǒng)一設(shè)為 100000;細(xì)節(jié)方面,MOEA/DD中設(shè)δ=0.9,RVEA中設(shè)α=2,fr=0.1;算法運(yùn)行30次,記錄平均值以及標(biāo)準(zhǔn)差如表2所示,其中,加粗以及加黑的結(jié)果表示最優(yōu)的性能.除了本文算法外,其他算法在高維多目標(biāo)優(yōu)化算法platEMO[28]上運(yùn)行.

表2 MaOBSO與幾種算法IGD的比較Table 2 The comparison of IGD between MaOBSO and several algorithms

由表2可見(jiàn),MaOBSO與其他算法相比整體表現(xiàn)出較為理想的性能.與現(xiàn)有的幾種算法相比,其處于同等數(shù)量級(jí)且表現(xiàn)略微優(yōu)異.具體分析如下:

對(duì)于同一測(cè)試函數(shù)而言,算法的IGD指標(biāo)隨著目標(biāo)個(gè)數(shù)增加而增加,驗(yàn)證了目標(biāo)個(gè)數(shù)的增加對(duì)優(yōu)化帶來(lái)的挑戰(zhàn)性.可見(jiàn)當(dāng)目標(biāo)個(gè)數(shù)的增加導(dǎo)致種群更加離散地分布在在高維目標(biāo)空間中,導(dǎo)致了種群的多樣性維護(hù)難度增加.

對(duì)于不同測(cè)試函數(shù)而言,大多數(shù)算法在處理DTLZ1-DTLZ4有著更優(yōu)秀的性能,因?yàn)樗麄冇兄右?guī)范的Pareto 前沿,算法進(jìn)化過(guò)程中更容易得到Pareto最優(yōu)解,且種群的多樣性維護(hù)更為容易.而對(duì)于DTLZ5-DTLZ7,算法整體性能較差,且受目標(biāo)個(gè)數(shù)的影響更大.

對(duì)于不同算法而言,在處理具有較為規(guī)范的Pareto前沿的DTLZ1-DTLZ4時(shí),MaOBSO與幾種經(jīng)典算法性能處于同一數(shù)量級(jí),但由于本文算法在處理均勻性優(yōu)化時(shí)有著更高的效率,最終性能更加優(yōu)秀.特別是對(duì)于DTLZ4,MaOBSO性能提升更為明顯.而在處理DTLZ5-DTLZ7方面,LMEA與其他算法以及本文算法有著不同的保留機(jī)制,具有更強(qiáng)的適應(yīng)性,最終得到更加均勻的前沿,算法性能最好且更加穩(wěn)定.但相比于其他算法,MaOBSO性能更優(yōu).

從算法穩(wěn)定性來(lái)講,MaOBSO整體標(biāo)準(zhǔn)差較小,表明算法有著較好的穩(wěn)定性.為了更加直接地觀察算法得 到 的Pareto 最 優(yōu) 解,以10 目 標(biāo)DTLZ1,DTLZ4,DTLZ5及DTLZ7為例,取30次中最接近IGD平均值的結(jié)果對(duì)應(yīng)的Pareto前沿的平行坐標(biāo)如圖4所示.

圖4 MaOBSO與經(jīng)典算法解決MaOP時(shí)的Pareto最優(yōu)解集Fig.4 The Pareto set of MaOBSO and classic algorithms while solving MaOP

由圖4可以看出,MaOBSO在4種測(cè)試函數(shù)上與其他幾種算法性能各有勝負(fù).對(duì)于DTLZ1,所有算法都表現(xiàn)出良好的性能,盡管幾種算法的IGD指標(biāo)較為接近,但從圖4(a1)-(a6)可明顯看到,LMEA均勻性稍差,MOEA/DVA收斂性稍差,多樣性較差;對(duì)于均勻性優(yōu)化難度較大的DTLZ4,從收斂性角度看,幾種算法均有著良好的收斂性能,NSGA--III稍差;從多樣性角度來(lái)看,NSGA--III,LMEA和MOEA/DVA性能較差,最優(yōu)解集在目標(biāo)空間中分布的廣度以及均勻程度均不理想,算法得到的Pareto最優(yōu)解大多數(shù)分布于邊界上,且在某些目標(biāo)上存在“缺失”現(xiàn)象,難以使得最優(yōu)解集廣泛地分布于整個(gè)非支配前沿上.而MaOBSO由于能夠不受約束地產(chǎn)生新個(gè)體則表現(xiàn)出最優(yōu)的性能,與其相比,而MOEA/DD和RVEA性能稍差;對(duì)于具有退化前沿的DTLZ5和不連續(xù)前沿的DTLZ7,LMEA表現(xiàn)出最優(yōu)的性能,盡管MaOBSO難以達(dá)到理想的水平,但與其他算法相比仍表現(xiàn)出良好的競(jìng)爭(zhēng)力,其中對(duì)于DTLZ5在收斂性能和多樣性能方面均較大程度領(lǐng)先于其他算法,而在DTLZ7上與其他算法相仿.

綜上所述,MaOBSO能夠較好地處理各種MaOP,與當(dāng)前流行的幾種算法相比表現(xiàn)出良好的競(jìng)爭(zhēng)力.對(duì)具有規(guī)則前沿的(高維)多目標(biāo)優(yōu)化問(wèn)題,MaOBSO與其他算法同樣表現(xiàn)出良好的性能且更加優(yōu)異,而對(duì)于具有不規(guī)則前沿的問(wèn)題,算法在多樣性方面稍遜于LMEA算法,但整體性能略微領(lǐng)先于其他算法.

5 總結(jié)與展望

本文針對(duì)高維多目標(biāo)優(yōu)化算法的收斂性和多樣性問(wèn)題,結(jié)合頭腦風(fēng)暴優(yōu)化算法的的思想,提出了一種高維多目標(biāo)頭腦風(fēng)暴優(yōu)化算法.算法采用決策變量聚類策略,對(duì)收斂性相關(guān)變量和多樣性相關(guān)變量分別做出優(yōu)化,并根據(jù)變量特征采用不同的個(gè)體產(chǎn)生策略和更新策略,融入了頭腦風(fēng)暴優(yōu)化算法產(chǎn)生新個(gè)體的機(jī)制,仿真結(jié)果表明了算法具有良好的性能.此外,本文根據(jù)角點(diǎn)的特性采用了基于角點(diǎn)聚類的思想,對(duì)于多目標(biāo)頭腦風(fēng)暴優(yōu)化算法提出了一種新的自適應(yīng)聚類策略,為之后的研究拓寬了方向.

在算法仿真研究時(shí),作者發(fā)現(xiàn)本文基于參考點(diǎn)更新的方式對(duì)不規(guī)則Pareto前沿問(wèn)題的性能還有待進(jìn)一步的提升.因此,如何設(shè)計(jì)不規(guī)則前沿的多樣性和收斂性更新策略,提高算法的普適性,并將其應(yīng)用于實(shí)際的高維多目標(biāo)優(yōu)化問(wèn)題將是作者今后進(jìn)一步研究的方向.