星型結(jié)構(gòu)的多目標(biāo)粒子群算法求解多模態(tài)多目標(biāo)問(wèn)題*

高海軍，潘大志

(西華師范大學(xué)數(shù)學(xué)與信息學(xué)院，四川 南充 637009)

1 引言

在實(shí)際生活中，存在很多需要同時(shí)優(yōu)化2個(gè)或2個(gè)以上目標(biāo)的問(wèn)題，這類問(wèn)題被稱為多目標(biāo)優(yōu)化問(wèn)題[1]。在該類問(wèn)題中，進(jìn)行優(yōu)化的目標(biāo)之間常常會(huì)相互制約，因此要使多個(gè)目標(biāo)同時(shí)達(dá)到最優(yōu)十分困難。

目前，多目標(biāo)優(yōu)化問(wèn)題的求解方法主要有2類：傳統(tǒng)的數(shù)學(xué)求解方法和進(jìn)化算法。傳統(tǒng)的數(shù)學(xué)解析方法[2]主要是通過(guò)動(dòng)態(tài)規(guī)劃求解問(wèn)題的解，但當(dāng)目標(biāo)過(guò)多或決策變量過(guò)多時(shí)，數(shù)學(xué)解析方法求解非常困難。進(jìn)化算法[3]是一種以種群進(jìn)化為基礎(chǔ)的啟發(fā)式隨機(jī)搜索算法，有不斷演化逼近真實(shí)Pareto前沿的能力，目前出現(xiàn)了很多求解多目標(biāo)優(yōu)化問(wèn)題的智能算法。Deb等人[4,5]提出NSGA-II(Non-dominated Sorting Genetic Algorithm Ⅱ)算法，使用帶精英策略的快速非支配排序，保證找到的最優(yōu)解不被拋棄，提高了算法的全局搜索能力。林震等人[6]提出多策略差分進(jìn)化算法，引入一種動(dòng)態(tài)多策略差分進(jìn)化模型，分析不同差分進(jìn)化策略，依據(jù)每種策略對(duì)鄰域更新的貢獻(xiàn)度，動(dòng)態(tài)地調(diào)整其子種群的大小，采用多策略相互協(xié)同進(jìn)化，提高了算法性能。肖閃麗等人[7]提出不同維度的粒子向不同種群學(xué)習(xí)的策略，以增加種群的多樣性。夏星宇等人[8]在算法中引入均衡因子，提高種群的全局搜索能力。薛蒙蒙等人[9]針對(duì)粒子群算法容易陷入局部最優(yōu)的缺點(diǎn)，提出了模擬退火粒子群算法，增強(qiáng)了算法全局搜索能力。以上算法中很少利用到多目標(biāo)優(yōu)化問(wèn)題的特性：在m個(gè)目標(biāo)的多目標(biāo)優(yōu)化問(wèn)題中，目標(biāo)空間中的Pareto前沿以及決策空間中的Pareto解集都可以形成一個(gè)m-1維的片段連續(xù)流型結(jié)構(gòu)[10]。針對(duì)多目標(biāo)優(yōu)化問(wèn)題的這種特性，Zhang等人[11]提出將自組織映射網(wǎng)絡(luò)應(yīng)用于種群重組操作，有效地提高了多目標(biāo)優(yōu)化算法的性能。梁靜等人[12]提出了自組織映射網(wǎng)絡(luò)結(jié)構(gòu)與多目標(biāo)粒子群優(yōu)化算法相結(jié)合的算法，為粒子結(jié)構(gòu)構(gòu)造新的鄰域關(guān)系，引導(dǎo)粒子在全局范圍內(nèi)得到更優(yōu)的解，平衡多目標(biāo)粒子群算法的多樣性和收斂性。

上面提到的進(jìn)化計(jì)算均是針對(duì)多目標(biāo)優(yōu)化問(wèn)題的目標(biāo)空間及性能分析，以算法獲得的Pareto解集與Pareto前沿的逼近程度進(jìn)行評(píng)價(jià)，而沒(méi)有考慮Pareto解集在決策空間中的分布情況。決策空間的多樣性吸引了一些研究人員的注意。Shir等人[13]改變CMA-ES(Covariance Matrix Adaptation Evolution Strategies)[14]中的選擇算子和多樣性的度量，同時(shí)引入了空間聚合的概念，用于聚合空間中的多樣性維護(hù)，從而提高決策空間的多樣性。Tahernezhad等人[15]在優(yōu)化系統(tǒng)中采用了基于聚類的創(chuàng)新方案，在解空間中獲得了更多樣化的非支配解集。Ulrich 等人[16]將決策空間多樣性納入超體積指標(biāo) ，以便同時(shí)優(yōu)化這2個(gè)集合度量。這些算法旨在通過(guò)考慮決策空間中的多樣性來(lái)改善Pareto前沿的分布，但是沒(méi)有保留具有不同決策值的相同目標(biāo)值的解。事實(shí)上，應(yīng)該同時(shí)考慮決策空間中解的多樣性和收斂性。針對(duì)該問(wèn)題，Liang等人[17,18]提出多模態(tài)多目標(biāo)優(yōu)化問(wèn)題，即同一個(gè)目標(biāo)值對(duì)應(yīng)多個(gè)解現(xiàn)象的問(wèn)題，在研究Pareto前沿的同時(shí)討論決策空間中Pareto解集的分布情況。

多模態(tài)多目標(biāo)優(yōu)化問(wèn)題[17]由Liang教授提出，并展開(kāi)相關(guān)研究的。Liang等人利用粒子群算法[18]、差分進(jìn)化算法[19]對(duì)多模態(tài)多目標(biāo)優(yōu)化問(wèn)題進(jìn)行求解，取得了有效的成果。受Schütze等人[10]、Li[20]和Liang等人[17,18]的啟發(fā)，本文對(duì)Pareto解集的個(gè)體信息交換的鄰域結(jié)構(gòu)進(jìn)行改進(jìn)，提出帶均勻計(jì)算方法的基于星型拓?fù)浣Y(jié)構(gòu)的多目標(biāo)粒子群優(yōu)化STMOPSONCMIU(Multi-Objective Particle Swarm Optimization algorithm using Star Topology and New Calculation Method of Individual Uniformity)算法，以提高個(gè)體之間信息交換的強(qiáng)度，增強(qiáng)算法的全局搜索能力。針對(duì)多模態(tài)多目標(biāo)問(wèn)題的決策空間，設(shè)計(jì)一種評(píng)價(jià)Perato解集個(gè)體分布均勻程度的新計(jì)算方法，以增強(qiáng)算法在求解多模態(tài)多目標(biāo)優(yōu)化問(wèn)題時(shí)獲得的Pareto解集與實(shí)際的Pareto解集的逼近度。

STMOPSONCMIU在解決多模態(tài)多目標(biāo)優(yōu)化問(wèn)題時(shí)具有2個(gè)較好的能力，一是盡可能多地找到Pareto最優(yōu)解的能力，二是能保持對(duì)應(yīng)目標(biāo)空間中同一點(diǎn)的Pareto最優(yōu)解的搜索能力。在STMOPSONCMIU算法中，借助于粒子的星型拓?fù)浣Y(jié)構(gòu)，使得每個(gè)粒子可以與與之相鄰的4個(gè)粒子交換信息，構(gòu)造小生物環(huán)境，從而提高種群的多樣性，搜索出更多的Pareto最優(yōu)解。另外，針對(duì)多模態(tài)問(wèn)題，如圖1所示，解決方案A1和A2均對(duì)應(yīng)目標(biāo)A，它們?cè)谀繕?biāo)空間中的擁擠距離為零，但這2個(gè)解在決策空間中的距離很大，本文通過(guò)設(shè)計(jì)新的均勻度距離計(jì)算方法來(lái)選擇決策空間中的粒子，使得粒子在決策空間中分布更加均勻。

Figure 1 Illustration of multi-modal multi-objective optimization problem圖1 多模態(tài)多目標(biāo)優(yōu)化問(wèn)題示意圖

1.1 多目標(biāo)優(yōu)化問(wèn)題

多目標(biāo)優(yōu)化問(wèn)題的數(shù)學(xué)模型(以最小化為例)[1]可表示為：

minF(X)=(f1(X),f2(X),…,fm(X))

其中,X=(x1,x2,…,xn)∈Ω是決策空間中的n維決策變量；Ω=[ai,bi]是搜索空間的可行域；m是待優(yōu)化的目標(biāo)函數(shù)個(gè)數(shù)；F:Ω→Rm是m個(gè)待優(yōu)化的目標(biāo)函數(shù)由決策空間Ω到目標(biāo)空間Rm的映射關(guān)系；gi(X)(i=1,2,…,k)為不等式約束條件；hj(X)(j=1,2,…,l)為等式約束條件。一些基礎(chǔ)的定義[12]如下所示：

定義1(Pareto支配性[1]) 決策變量X支配決策變量Y(記為XY)當(dāng)且僅當(dāng)滿足以下條件：

(fi(X)≤fi(Y))∧(fj(X)

其中，i,j=1,2,…,m0。

定義2(Pareto解) 決策變量X是Pareto解[1]:?Y∈Ω:YX，即在可行域內(nèi)，不存在任何可行解支配X。

定義3(Pareto解集PS(Pareto optional Set)[1])PS={X∈Ω|?Y∈Ω：YX}。

定義4(Pareto前沿PF(Pareto Front)[1])PF={F(X)|X∈PS}

定義5(多模態(tài)多目標(biāo)優(yōu)化問(wèn)題MMO(Multimodal Multi-Objective optimization problems)[2]) 對(duì)于多目標(biāo)優(yōu)化問(wèn)題，當(dāng)目標(biāo)空間的同一個(gè)區(qū)域?qū)?yīng)在決策空間中的解有2個(gè)或2個(gè)以上時(shí)，該問(wèn)題被稱為多模態(tài)多目標(biāo)優(yōu)化問(wèn)題。

圖1簡(jiǎn)潔地說(shuō)明了同一個(gè)Pareto前沿對(duì)應(yīng)2個(gè)Pareto解集的情況。

1.2 粒子群優(yōu)化算法

粒子群優(yōu)化PSO(Particle Swarm Optimization)[21 - 23]算法是一種基于種群群體演化的算法，算法思想來(lái)源于鳥(niǎo)類群體性的社會(huì)活動(dòng)，引導(dǎo)鳥(niǎo)群飛向食物。為求解多目標(biāo)優(yōu)化問(wèn)題，將PSO算法擴(kuò)展為多目標(biāo)粒子群優(yōu)化MOPSO(Multi-Objective Particle Swarm Optimization)[21]算法。在該算法中，一個(gè)粒子經(jīng)歷過(guò)的歷史最優(yōu)位置標(biāo)記為pbest，其鄰域內(nèi)所有粒子經(jīng)歷的歷史最優(yōu)位置標(biāo)記為nbest。種群中的每個(gè)粒子都由pbest和nbest引導(dǎo)，在可行域中飛行。設(shè)當(dāng)前種群中有n個(gè)粒子，第i個(gè)粒子的第t次迭代的位置為Xi(t)，速度為Vi(t)，粒子位置與速度更新公式可表示為：

Xi(t)=Xi(t-1)+Vi(t)

Vi(t)=ωVi(t-1)+c1r1(Xpbesti-Xi(t))+

c2r2(Xnbesti-Xi(t))

其中,ω為慣性權(quán)重，c1與c2為學(xué)習(xí)因子，r1與r2是在[0,1]內(nèi)均勻生成的隨機(jī)數(shù)。

2 星型拓?fù)浣Y(jié)構(gòu)的多目標(biāo)粒子群算法

針對(duì)多目標(biāo)問(wèn)題的Pareto前沿對(duì)應(yīng)決策空間中的多個(gè)非支配個(gè)體的問(wèn)題，Liang等人[17]對(duì)NSGAII[4]算法進(jìn)行擴(kuò)展提出DN-NSGAII(Decision space based Niching NSGAII)算法，該算法旨在定位更多的PS。Yue等人[18]利用環(huán)形拓?fù)浣Y(jié)構(gòu)構(gòu)建Pareto解集的鄰域關(guān)系，同時(shí)設(shè)計(jì)了一種特殊的擁擠度距離計(jì)算方法SCD(Special Crowding Distance)，對(duì)Pareto解集進(jìn)行排序，提出環(huán)形拓?fù)浣Y(jié)構(gòu)的多目標(biāo)優(yōu)化MO_Ring_PSO_SCD(Multi-Objective Particle Swarm Optimization using Ring topology and Special Crowding Distance)算法，有效地解決了多模態(tài)多目標(biāo)優(yōu)化問(wèn)題。受此啟發(fā)，為了進(jìn)一步加強(qiáng)粒子間信息的交換強(qiáng)度，本文修改Pareto解集中個(gè)體的鄰域結(jié)構(gòu)，增加鄰域中的個(gè)體數(shù)，將其變?yōu)樾切徒Y(jié)構(gòu)，提出基于星型拓?fù)浣Y(jié)構(gòu)的多目標(biāo)粒子群優(yōu)化STMOPSO(Multi-Objective Particle Swarm Optimization using Star Topology)算法。

2.1 Pareto解集的星型拓?fù)浣Y(jié)構(gòu)

一般的環(huán)形拓?fù)浣Y(jié)構(gòu)的粒子關(guān)系如圖2所示。

圖2和圖3中黑色的點(diǎn)表示粒子，從圖2中可知，粒子i只與粒子i-1和粒子i+1交換信息，形成線性結(jié)構(gòu)。在這種結(jié)構(gòu)中，鄰域內(nèi)個(gè)體少，粒子在位置更新過(guò)程中無(wú)法充分使用其他個(gè)體的信息。為增強(qiáng)粒子之間的信息共享度，提高算法的全局搜索能力，對(duì)粒子鄰域結(jié)構(gòu)進(jìn)行擴(kuò)展，擴(kuò)充鄰域半徑，擴(kuò)充鄰域內(nèi)的個(gè)體，由原來(lái)的3個(gè)個(gè)體擴(kuò)大為5個(gè)個(gè)體，其結(jié)構(gòu)如圖3所示。由圖3可知，粒子i同時(shí)與粒子i-2、粒子i-1、粒子i+1、粒子i+2共4個(gè)粒子共享信息，擴(kuò)大了信息交換程度。分析粒子i的鄰域結(jié)構(gòu)可知，其鄰域結(jié)構(gòu)為星型結(jié)構(gòu)，由線性結(jié)構(gòu)連接變成星型結(jié)構(gòu)，當(dāng)前粒子的信息交換對(duì)象由原來(lái)的前后2個(gè)變成4個(gè)，這使得粒子之間的信息交流更充分，全局搜索能力更強(qiáng)。

Figure 3 Star topology with each particle圖3 粒子的星型拓?fù)浣Y(jié)構(gòu)

2.2 PS的均勻度計(jì)算方法

文獻(xiàn)[18]中提出的特殊擁擠距離計(jì)算法(SCD)沒(méi)有很好地控制PS中個(gè)體分布的均勻度，因而針對(duì)該問(wèn)題提出一種評(píng)價(jià)PS中個(gè)體均勻度的新計(jì)算方法NCMIU(New Calculation Method of Individual Uniformity)，通過(guò)個(gè)體均勻度的值更新PS，使求得的Pareto解集中的個(gè)體分布更加均勻，更好地逼近真實(shí)的PS。

圖4給出了在二維情況下粒子i的均勻度新計(jì)算方法所涉及到的相關(guān)個(gè)體。個(gè)體i的均勻度表示為個(gè)體i與其鄰域的個(gè)體i-1,i-2,i+1和i+2在各維度上的距離比值。設(shè)k表示決策空間的第k維；xi,k表示第i個(gè)個(gè)體的第k(k=1,2,…,n)維分量；cdi,k表示決策空間中第i個(gè)個(gè)體在第k維的均勻度；gcdi表示第i個(gè)個(gè)體的綜合均勻度。因此，在決策空間上個(gè)體的均勻度計(jì)算公式如式(1)和式(2)所示：

i=3,4,…,m-2

(1)

(2)

Figure 4 Illustration of new calculation method of individual uniformity圖4 個(gè)體均勻度的新計(jì)算方法示意圖

當(dāng)個(gè)體位于決策空間邊緣時(shí)，其第k維的均勻度無(wú)法按照式(1)和式(2)進(jìn)行計(jì)算，需單獨(dú)計(jì)算。第1個(gè)個(gè)體第k維的均勻度計(jì)算公式為：

第2個(gè)個(gè)體第k維的均勻度計(jì)算公式為：

第m-1個(gè)個(gè)體第k維的均勻度計(jì)算公式為：

第m個(gè)個(gè)體第k維的均勻度計(jì)算公式為:

通過(guò)上述計(jì)算公式計(jì)算個(gè)體的均勻度，按值升序排序。將該計(jì)算方法應(yīng)用到非支配解集的排序函數(shù)中，在決策空間上得到一組分布相對(duì)均勻的外部存儲(chǔ)集。以下描述新的均勻度計(jì)算方法與粒子群算法結(jié)合求解多模態(tài)多目標(biāo)優(yōu)化問(wèn)題(STMOPSONCMIU)的算法過(guò)程。

2.3 STMOPSONCMIU算法過(guò)程

在STMOPSONCMIU算法中，pbestA表示個(gè)體最優(yōu)外部存儲(chǔ)集；nbestA表示鄰近最優(yōu)外部存儲(chǔ)集；pop表示整個(gè)種群；popi(t)表示第t代的第i個(gè)粒子；pbestA{i}表示前i個(gè)粒子發(fā)現(xiàn)的最優(yōu)位置，nbestA{i}表示第i個(gè)粒子鄰域內(nèi)最佳位置。每個(gè)鄰域中有5個(gè)粒子，每個(gè)粒子與其直接鄰近的左右側(cè)粒子相互作用，使得每個(gè)粒子與其鄰域最佳位置上的粒子進(jìn)行信息交互，以避免粒子群體收斂到某個(gè)局部最優(yōu)點(diǎn)。nbestA的引入限制了群體之間的整體信息交流，因此在搜索期間可以形成多個(gè)穩(wěn)定的外部存儲(chǔ)集，偽代碼如算法1所示。

算法1STMOPSONCMIU

// 初始化種群pop(0)

Evaluation(pop(0));

// 初始化pbestA和nbestA

fori=1→mdo

pbestA(i)?pop(0);

nbestA(i)?pop(0);

endfor

fori=1→Max_Gendo

// 更新pbestA

forj=1 →mdo

ifj==1then

temp_nbestA? [pbestA{m-1,:};pbestA{m,:}];

temp_nbestA?[temp_nbestA;pbestA{1,:};pbestA{2,:};pbestA{3,:}];

elseifj==2then

temp_nbestA?[pbestA{m,:};pbestA{1,:}];

temp_nbestA? [temp_nbestA;pbestA{2,:};pbestA{3,:};pbestA{4,:}];

elseifj==m-1then

temp_nbestA?[pbestA{m-3,:};pbestA{m-2,:}];

temp_nbestA?[temp_nbestA;pbestA{m-1,:}];

temp_nbestA?[temp_nbestA;pbestA{m,:};pbestA{1,:}];

elseifj==mthen

temp_nbestA?[pbestA{m-2,:};pbestA{m-1,:}];

temp_nbestA?[temp_nbestA;pbestA{m,:};pbestA{1,:};pbestA{2,:}];

else

temp_nbestA?[pbestA{j-2,:};pbestA{j-1,:};pbestA{j,:}];

temp_nbestA?[temp_nbestA;pbestA{j+1,:};pbestA{j+2,:}];

endif

// 個(gè)體均勻度計(jì)算

nbestA{j}?NCMIU(temp_NBA(:,1:k+n),k,n);

endfor

forj=1→mdo

Sort particles inpbestAandnbestA;

Selectpbestandnbest;

Upadatepop;

Evalutionpop;

UpadatepbestA;

endfor

endfor

returnthe non_dominated particles innbestA;

2.4 STMOPSONCMIU性能分析

STMOPSONCMIU是基于MO_Ring_PSO_SCD改進(jìn)的，主要做了以下的改進(jìn):一是將環(huán)形的2個(gè)粒子擴(kuò)展到星型的5個(gè)粒子，增加粒子之間選擇區(qū)域和信息交流；二是針對(duì)粒子之間的擁擠度距離提出新的計(jì)算方法，根據(jù)粒子之間的鄰域關(guān)系和均勻度的排序選擇全局最優(yōu)和局部最優(yōu)。文獻(xiàn)[18]用多模態(tài)多目標(biāo)測(cè)試函數(shù)4(MMF4)對(duì)MO_Ring_PSO_SCD、Omni-optimizer和DN-NSGAII進(jìn)行收斂性分析，本文對(duì)STMOPSONCMIU與MO_Ring_PSO_SCD、Omni-optimizer和DN-NSGAII進(jìn)行對(duì)比分析。

為了更好地對(duì)比測(cè)試，本文選擇測(cè)試函數(shù)MMF4，設(shè)置種群數(shù)量為800，最大迭代次數(shù)為100，累計(jì)運(yùn)行30次取平均值，所有的其他參數(shù)與第3節(jié)實(shí)驗(yàn)參數(shù)一致。測(cè)試函數(shù)MMF4有4個(gè)可行解，將MMF4的可行域劃分為4個(gè)子區(qū)域，每個(gè)區(qū)域是1個(gè)PS解集，分別為Region1{x1∈[-1,0],x2∈[1,2]},Region2{x1∈[0,1],x2∈[1,2]},Region3 {x1∈[-1,0],x2∈(0,1]}和Region4 {x1∈(0,1],x2∈[0,1)}，在測(cè)試函數(shù)MMF4上，算法的收斂性體現(xiàn)為每次迭代在每個(gè)區(qū)域中得到解的比例情況，越趨近于25%說(shuō)明該算法的收斂性越好。理想情況下，算法在4個(gè)區(qū)域中解的比例各為25%。

如圖5所示為測(cè)試函數(shù)MMF4從1到100次迭代得到的每個(gè)區(qū)域解的占比。針對(duì)4種算法，STMOPSONCMIU算法得到的解的可行區(qū)域占比差距(即縱坐標(biāo)到0.25的距離)為0.37%，MO_Ring_PSO_SCD算法差距為0.45%，STMOPSONCMIU算法優(yōu)于MO_Ring_PSO_SCD算法。整體看來(lái)， STMOPSONCMIU算法迭代20次后在24.6%～25.3%的小范圍內(nèi)波動(dòng)，而MO_Ring_PSO_SCD算法則在50代之后才能達(dá)到24.6%～25.3%，說(shuō)明STMOPSONCMIU算法在收斂時(shí)間上占優(yōu)。但是，Omni-optimizer算法和DN-NSGAII算法波動(dòng)范圍一直很大，沒(méi)有均勻收斂到25%的小范圍內(nèi)(25%±0.5%)。因此， STMOPSONCMIU算法的收斂性相對(duì)優(yōu)于其他3種算法的。

通過(guò)以上分析可知，STMOPSONCMIU主要通過(guò)擴(kuò)大粒子信息交流的范圍，來(lái)增強(qiáng)粒子之間的信息轉(zhuǎn)移；新的擁擠度計(jì)算方法可更好地引導(dǎo)粒子收斂到全局最優(yōu)和局部最優(yōu)，能有效地解決多模態(tài)多目標(biāo)優(yōu)化問(wèn)題。由圖5可知，STMOPSONCMIU的收斂速度比算法MO_Ring_PSO_SCD、Omni-optimizer、DN-NSGAII的快。

Figure 5 Converging behavior of four algorithms on MMF4圖5 MMF4上4個(gè)算法的收斂性

3 實(shí)驗(yàn)結(jié)論分析

為了評(píng)估算法獲得的近似PF的收斂性和均勻性，通過(guò)Pareto解集的近似度PSP(Pareto Sets Proximity)[18]和反轉(zhuǎn)世代距離IGD(Inverted Generational Distance)[12]性能指標(biāo)進(jìn)行評(píng)比。設(shè)P為真實(shí) Pareto最優(yōu)解集，P*是得到的Pareto最優(yōu)解集，反轉(zhuǎn)世代距離IGD的計(jì)算如下所示:

Pareto解集的近似度PSP的計(jì)算公式為：

其中,IGDx表示決策空間中的反轉(zhuǎn)世代距離，CR表示Pareto前沿最大差值的覆蓋率。PSP可以很好地反映算法求得的Pareto解集與真實(shí)的PS之間的相似度，PSP值越大，說(shuō)明Pareto解集相似度越高，同時(shí)滿足Pareto前沿的分布。其中，IGDx和覆蓋率CR的計(jì)算方法參考文獻(xiàn)[18]。同時(shí)，超體積值hv(hyper-volume)也可以作為評(píng)估算法獲得的近似PF的收斂性和均勻性的性能指標(biāo)。實(shí)驗(yàn)分析中，用IGDx和hv的值來(lái)衡量種群的收斂性和均勻度，IGDx值越小(hv值越大)，得到的PS越好，越接近真實(shí)的PS。在STMOPSONCMIU中，ω=0.7298，c1=c2=2.05，其他參數(shù)設(shè)置參考文獻(xiàn)[4,5,17,19,24,25]。

為了說(shuō)明本文算法的有效性，通過(guò)文獻(xiàn)[18]中的測(cè)試函數(shù)進(jìn)行求解，所有的測(cè)試函數(shù)均獨(dú)立運(yùn)行30次，再與算法MOPSONCMIU、STMOPSO、MOPSO和算法MO_Ring_PSO_SCD[18]求得的PSP值進(jìn)行比較。表1列出了以上5種算法在11個(gè)多目標(biāo)測(cè)試函數(shù)上的PSP性能指標(biāo)。表1中的數(shù)值表示同一個(gè)算法在同一個(gè)測(cè)試函數(shù)上獨(dú)立運(yùn)行30次的平均值，粗體數(shù)值表示所有對(duì)比算法在每一個(gè)測(cè)試函數(shù)上最大的PSP值。表2給出了測(cè)試函數(shù)上性能指標(biāo)hv、IGDx、IGDf、CR和PSP的值。IGDf表示在目標(biāo)空間中的反轉(zhuǎn)世代距離，IGDf的值越小，表示得到的PF越好，越接近真實(shí)的PF，且能最大程度覆蓋真實(shí)的PF。另外，TTS表示各算法在求解11個(gè)測(cè)試函數(shù)時(shí)，對(duì)應(yīng)性能參數(shù)獲得最佳的次數(shù)。

由表1可知， 除了在函數(shù)MMF1和Omni_test 上STMOPSONCMIU算法的PSP平均值比MO_Ring_PSO_SCD算法的低之外，其他9個(gè)測(cè)試函數(shù)上STMOPSONCMIU算法的PSP平均值均為最優(yōu)。因此，STMOPSONCMIU算法對(duì)求解多模態(tài)多目標(biāo)優(yōu)化問(wèn)題是有效的。

Table 1 PSPs (mean) of different algorithms 表1 不同算法的PSP值(均值)

通過(guò)表2可以看出，由TTS值可知，STMOPSONCMIU算法計(jì)算得到的性能指標(biāo)hv、IGDx、PSP優(yōu)于其他算法的；測(cè)試函數(shù)SYM_PART_simple上，算法STMOPSO的CR優(yōu)于其他算法的，其他的測(cè)試函數(shù)均是STMOPSONCMIU算法的計(jì)算結(jié)果占優(yōu)；在測(cè)試函數(shù)Omni_test上，STMOPSO算法的性能指標(biāo)IGDf優(yōu)于其他算法的，其他的測(cè)試函數(shù)上，STMOPSONCMIU算法的性能指標(biāo)占優(yōu)。為了更好地對(duì)比各個(gè)算法的性能，將各個(gè)測(cè)試函數(shù)的IGDf、IGDx以及PSP指標(biāo)取對(duì)數(shù)分別作折線圖，如圖6所示。由圖6a可知，測(cè)試函數(shù)MMF1、MMF2上是MOPSO算法占優(yōu)，其他9個(gè)測(cè)試函數(shù)上都是STMOPSONCMIU算法占優(yōu)；由圖6b可知，測(cè)試函數(shù)Omni_test上的IGDf值是STMOPSO算法占優(yōu)；而由圖7和圖8可知，所有的測(cè)試函數(shù)中，改進(jìn)的算法STMOPSONCMIU的性能指標(biāo)IGDx的PSP值均占優(yōu)。由此可以說(shuō)明，STMOPSONCMIU算法可以兼顧PF，從而找到所有的Pareto解集。為更好地體現(xiàn)STMOPSONCMIU算法求解多模態(tài)多目標(biāo)問(wèn)題的效果，圖9給出了其某一次計(jì)算11個(gè)測(cè)試函數(shù)獲得PS與真實(shí)PS之間的逼近程度圖，圖9中橫坐標(biāo)為x1，縱坐標(biāo)為x2。由圖9可以看出，STMOPSONCMIU算法與MO_Ring_PSO_SCD差距比較小，說(shuō)明STMOPSONCMIU有效可行，性能上是占優(yōu)的。

Table 2 Relevant performance index (mean) of each algorithm on each test function表2 各算法在各測(cè)試函數(shù)上相關(guān)性能指標(biāo)(均值)

Figure 6 Each test function corresponds to IGDf performance value of different algorithms and takes logarithmic polyline graph圖6 各個(gè)測(cè)試函數(shù)對(duì)應(yīng)不同算法的IGDf性能值取對(duì)數(shù)折線圖

Figure 7 Logarithmic polyline graph was taken for each test function corresponding to IGDx performance values of different algorithms圖7 各個(gè)測(cè)試函數(shù)對(duì)應(yīng)不同算法的IGDx性能值取對(duì)數(shù)折線圖

Figure 8 Logarithmic polyline graph was taken for each test function corresponding to PSP performance values of different algorithms圖8 各個(gè)測(cè)試函數(shù)對(duì)應(yīng)不同算法的PSP性能值折線圖

Figure 9 PSs obtained by STMOPSONCMIU圖9 STMOPSONCMIU算法在計(jì)算各測(cè)試函數(shù)時(shí)得到的PS

4 結(jié)束語(yǔ)

本文通過(guò)多目標(biāo)優(yōu)化問(wèn)題的Pareto解集多樣性和粒子之間的拓?fù)浣Y(jié)構(gòu)關(guān)系，對(duì)其鄰域結(jié)構(gòu)進(jìn)行擴(kuò)展，提出一種基于星型拓?fù)浣Y(jié)構(gòu)的多目標(biāo)粒子群優(yōu)化算法STMOPSONCMIU。為更好地確定粒子群算法中鄰域內(nèi)的最優(yōu)個(gè)體，設(shè)計(jì)出一種個(gè)體均勻度計(jì)算方法計(jì)算PS中個(gè)體的均勻度，通過(guò)均勻度來(lái)選擇最優(yōu)個(gè)體。將該算法用于求解多模態(tài)多目標(biāo)優(yōu)化問(wèn)題，得到的PS分布均勻且與真實(shí)的Pareto前沿的逼近程度達(dá)到95%以上，表明該算法能較好地解決多模態(tài)多目標(biāo)優(yōu)化問(wèn)題。