基于三方競(jìng)爭(zhēng)機(jī)制的反向多目標(biāo)粒子群優(yōu)化算法

韓 飛， 鄭明鵬

(1. 江蘇大學(xué) 計(jì)算機(jī)科學(xué)與通信工程學(xué)院, 江蘇 鎮(zhèn)江 212013; 2. 江蘇大學(xué) 江蘇省工業(yè)網(wǎng)絡(luò)空間安全技術(shù)重點(diǎn)實(shí)驗(yàn)室, 江蘇 鎮(zhèn)江 212013)

優(yōu)化問(wèn)題在很多實(shí)際應(yīng)用 (如科學(xué)研究和工程實(shí)踐) 中非常普遍.大多數(shù)的實(shí)際優(yōu)化問(wèn)題通常是由多個(gè)需要同時(shí)優(yōu)化、相互沖突的目標(biāo)構(gòu)成的，這一類優(yōu)化問(wèn)題通常稱為多目標(biāo)優(yōu)化問(wèn)題(multi-objective optimization problems, MOPs).這一類優(yōu)化問(wèn)題通常比單目標(biāo)優(yōu)化問(wèn)題更加棘手，因?yàn)檫m用于1個(gè)函數(shù)的解可能并不適用于其他函數(shù)，即此類問(wèn)題中不存在唯一的最優(yōu)解，只能尋找一組能均衡目標(biāo)之間優(yōu)劣的最佳折中解的集合，使所有目標(biāo)盡可能達(dá)到最優(yōu).

為了獲得MOPs的優(yōu)化解，具有收斂速度快、易于實(shí)現(xiàn)等優(yōu)點(diǎn)的多目標(biāo)粒子群優(yōu)化算法(multi-objective particle swarm optimization, MOPSO)獲得了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注.然而在將MOPSO應(yīng)用于解決多目標(biāo)優(yōu)化問(wèn)題時(shí)，除了需要考慮如外部存檔的維護(hù)等其他進(jìn)化算法所共有的一些策略之外，個(gè)體最優(yōu)解和種群最優(yōu)解的選擇以及多樣性和收斂性的平衡等方面仍然存在著挑戰(zhàn).

不同于傳統(tǒng)的MOPSO更新策略，ZHANG X. Y.等[1]將兩兩競(jìng)爭(zhēng)機(jī)制引入多目標(biāo)優(yōu)化領(lǐng)域，提出了一種基于競(jìng)爭(zhēng)機(jī)制的多目標(biāo)粒子群優(yōu)化算法(competitive mechanism based multi-objective particle swarm optimizer, CMOPSO)，該算法首先選取一部分最優(yōu)粒子作為精英粒子，在每次競(jìng)爭(zhēng)中從這些精英粒子中隨機(jī)挑選2個(gè)精英粒子參與競(jìng)爭(zhēng)，獲勝的精英粒子將用來(lái)引導(dǎo)其他粒子進(jìn)化.該算法能夠有效減少種群進(jìn)化過(guò)程中外部存檔維護(hù)帶來(lái)的計(jì)算成本，并且在很多MOPs上都表現(xiàn)出了較好的性能.基于CMOPSO算法，劉明等[2]提出了一種基于定期競(jìng)爭(zhēng)機(jī)制的MOPSO算法，該算法采用定期競(jìng)爭(zhēng)機(jī)制將全局最優(yōu)粒子選擇策略和競(jìng)爭(zhēng)學(xué)習(xí)機(jī)制結(jié)合起來(lái)，每隔一定代數(shù)便使用競(jìng)爭(zhēng)學(xué)習(xí)機(jī)制對(duì)種群進(jìn)行更新，在防止算法陷入局部最優(yōu)的同時(shí)，提高了種群的多樣性.TIAN Y.等[3]提出了一種求解大規(guī)模MOPs的多目標(biāo)粒子群優(yōu)化算法，該算法基于兩兩競(jìng)爭(zhēng)機(jī)制提出了一種競(jìng)爭(zhēng)失敗者粒子2階段位置更新策略，進(jìn)一步提高了算法跳出局部最優(yōu)的能力.鑒于CMOPSO算法在解決超多目標(biāo)優(yōu)化問(wèn)題方面的不足，YANG W. S.等[4]提出了一種基于競(jìng)爭(zhēng)機(jī)制的超多目標(biāo)粒子群優(yōu)化算法(multi/many-objective particle swarm optimization algorithm based on competition mechanism, CMaPSO)，該算法使用了與CMOPSO算法相同的學(xué)習(xí)方法，但提出了一種新的環(huán)境選擇策略，利用普通個(gè)體和極值點(diǎn)之間的最大角度和最小角度來(lái)選擇最優(yōu)個(gè)體進(jìn)入下一代種群，進(jìn)一步提高了算法的性能.綜上所述，傳統(tǒng)的兩兩競(jìng)爭(zhēng)機(jī)制在多目標(biāo)優(yōu)化領(lǐng)域得到了廣泛的應(yīng)用并取得了較為優(yōu)秀的表現(xiàn)，但算法的多樣性和收斂性仍然有進(jìn)一步提升的空間.

文中提出一種基于三方競(jìng)爭(zhēng)機(jī)制的多目標(biāo)粒子群優(yōu)化算法(opposition-based multi-objective particle swarm optimization algorithm based on tripartite competition mechanism, MOPSO-TCOL).在所提出算法中，除了預(yù)選的精英粒子直接進(jìn)入下一代之外，其他粒子均參與競(jìng)爭(zhēng)，其主要思想是允許粒子在空間中進(jìn)行更廣泛的搜索，以保持算法的多樣性.根據(jù)三方競(jìng)爭(zhēng)機(jī)制的特點(diǎn)，提出一種基于反向?qū)W習(xí)的漸進(jìn)式粒子更新策略，部分粒子進(jìn)行反向?qū)W習(xí)以避免算法陷入局部最優(yōu)，其他粒子通過(guò)向指定的更優(yōu)粒子學(xué)習(xí)進(jìn)行更新，借助亞軍粒子良好的反向?qū)W習(xí)能力，避免算法陷入局部最優(yōu).最后，通過(guò)對(duì)比試驗(yàn)驗(yàn)證MOPSO-TCOL算法的性能.

1 基本概念

1.1 多目標(biāo)優(yōu)化

多目標(biāo)優(yōu)化問(wèn)題一般可以描述如下：

minF(x)=(f1(x),f2(x),…,fm(x))T,

s.t.gp(x)≤0,p=1,2,…,P,hq(x)=0,

q=1,2,…,Q,

(1)

式中：x=(x1,x2,…,xn)是一個(gè)n維的決策向量；

fi(x)為第i個(gè)目標(biāo)函數(shù)值；m為目標(biāo)的個(gè)數(shù)；gp(x)≤0表示第p個(gè)不等式約束；hq(x)=0表示第q個(gè)等式約束.

Pareto支配及Pareto最優(yōu)解集定義[5]如下.

定義1(Pareto支配)給定2個(gè)解x和y，稱x支配y(記為xy)，當(dāng)且僅當(dāng)

?i∈{1,2,…,k},fi(x)≤fi(y)∧?i∈{1,2,…,k},fi(x)

(2)

定義2(Pareto最優(yōu)解集)所有Pareto最優(yōu)解的集合稱為Pareto最優(yōu)解集(Pareto optimal set,POS)，即

POS={x|?y∈Ω,yx}.

(3)

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

MOPSO算法的概念來(lái)源于PSO算法.在PSO算法中，設(shè)第k個(gè)粒子的速度屬性為Vk=(vk,1,vk,2,…,vk,D)，位置屬性為Xk=(xk,1,xk,2,…,xk,D)，k=1,2,…,N，其中N為種群規(guī)模大小.則第k個(gè)粒子在第t+1次迭代時(shí)的更新公式如下：

vk,d(t+1)=wvk,d(t)+c1r1(pbestk,d-

xk,d(t))+c2r2(gbestd-xk,d(t)),

(4)

xk,d(t+1)=xk,d(t)+vk,d(t+1),

(5)

式中：d=1,2,…,D，D為決策向量的維度；w為慣性權(quán)重；c1和c2為2個(gè)加速度系數(shù)，也稱為學(xué)習(xí)因子；r1和r2為2個(gè)分布在[0,1]的隨機(jī)數(shù)；pbestk,d和gbestd分別為第k個(gè)粒子的歷史最優(yōu)位置和種群最優(yōu)位置.

1.3 競(jìng)爭(zhēng)性粒子群優(yōu)化算法

競(jìng)爭(zhēng)性粒子群優(yōu)化算法CSO是CHENG R.等[6]提出的一種元啟發(fā)式算法，其中提出的兩兩競(jìng)爭(zhēng)機(jī)制能夠有效提升算法的性能.該算法本質(zhì)上受到PSO算法的啟發(fā)，但在概念上卻有很大的不同.在每次競(jìng)爭(zhēng)中，從種群中隨機(jī)挑選2個(gè)粒子進(jìn)行比較，贏得競(jìng)爭(zhēng)的粒子將直接進(jìn)入下一代，而競(jìng)爭(zhēng)失敗的粒子則需要通過(guò)向勝利者學(xué)習(xí)來(lái)更新自己的位置和速度，直到種群中一半的粒子被更新為止.在第k輪競(jìng)爭(zhēng)后，競(jìng)爭(zhēng)失敗者粒子的速度及位置更新公式如下：

Vl,k(t+1)=r1Vl,k(t)+r2(Xw,k(t)-

(6)

Xl,k(t+1)=Xl,k(t)+Vl,k(t+1),

(7)

1.4 反向?qū)W習(xí)

反向?qū)W習(xí)(opposition-based learning, OBL)的思想是于2005年提出的，其已被證明能夠有效提升算法的搜索效率和尋優(yōu)速度.一些與反向?qū)W習(xí)策略相關(guān)的概念如下.

(8)

(9)

式中：k為一個(gè)[0,1]內(nèi)的隨機(jī)數(shù)；xj∈[aj,bj]，daj和dbj分別是當(dāng)前代中種群搜索空間中第j維上的最小值和最大值，即

daj=min(Vj),dbj=max(Vj),

(10)

式中：Vj為種群個(gè)體在第j維上所有取值的集合.

2 基于三方競(jìng)爭(zhēng)機(jī)制的反向MOPSO算法

2.1 算法框架

算法1MOPSO-TCOL算法.輸入：種群規(guī)模N，最大迭代次數(shù)tmax.輸出:最終種群Ptmax.算法流程如下：

P0←RandomInitialize(N);

whilet

Pt′=TripartiteCompetitionBasedLearning(Pt);

Pt+1=EnvironmentalSelection(Pt′∪Pt);

t=t+1;

end while

returnPtmax

由算法可見(jiàn)，MOPSO-TCOL擁有一個(gè)非常簡(jiǎn)單的算法框架，主要包含2個(gè)部分：基于三方競(jìng)爭(zhēng)機(jī)制的粒子更新策略和環(huán)境選擇策略.首先初始化一個(gè)大小為N的粒子群Pt，然后使用提出的三方競(jìng)爭(zhēng)機(jī)制來(lái)更新種群中的每個(gè)粒子，再使用多項(xiàng)式變異(polynomial mutation, PM)對(duì)更新后的粒子進(jìn)行擾動(dòng)，最終得到一個(gè)新的種群Pt′，最后利用環(huán)境選擇策略從混合種群(Pt′∪Pt)(規(guī)模為2N)中選出N個(gè)更好的粒子作為下一代種群進(jìn)入下一次迭代直至達(dá)到算法終止條件.為簡(jiǎn)單起見(jiàn)，文中借鑒了NSGA-Ⅲ[7]算法中的環(huán)境選擇策略來(lái)篩選粒子.

2.2 基于三方競(jìng)爭(zhēng)的學(xué)習(xí)機(jī)制

在初始化生成N個(gè)粒子后，MOPSO-TCOL算法使用三方競(jìng)爭(zhēng)機(jī)制來(lái)更新粒子，與CSO算法中采用的兩兩競(jìng)爭(zhēng)機(jī)制不同，除精英粒子直接進(jìn)入下一代之外，種群中其他所有的粒子都有機(jī)會(huì)向更好的粒子學(xué)習(xí)來(lái)更新自己.基于三方競(jìng)爭(zhēng)的學(xué)習(xí)機(jī)制包括3個(gè)部分：精英粒子選擇策略、三方競(jìng)爭(zhēng)策略和粒子更新策略，其詳細(xì)過(guò)程如算法2所示.

算法2基于三方競(jìng)爭(zhēng)的學(xué)習(xí)機(jī)制.輸入： 當(dāng)前種群P.輸出：新種群P′.算法流程如下：

P′←?;

/*精英粒子選擇策略 */

L← 根據(jù)非支配排序和擁擠距離排序結(jié)果從當(dāng)前種群P中選出λ個(gè)粒子構(gòu)建精英粒子集L；

P*←CLP；

Fitness← 應(yīng)用式(11)、(12)計(jì)算種群P*中每個(gè)粒子的適應(yīng)度值；

while |P*|>1 do

/* 三方競(jìng)爭(zhēng)策略*/

{p,q,r}←隨機(jī)從種群P*中選擇3個(gè)粒子；

P*←P*-{p,q,r}；

假設(shè)Fitness(p)≥Fitness(q)≥Fitness(r)

Xw(t)←p,Xmw(t)←q,Xl(t)←r；

/* 粒子更新策略 */

Xe←從精英粒子集中隨機(jī)挑選一個(gè)精英粒子；

應(yīng)用式(14)更新粒子X(jué)w(t)；

應(yīng)用式(15)更新粒子X(jué)mw(t)；

應(yīng)用式(19)更新粒子X(jué)l(t)；

利用多項(xiàng)式變異對(duì)粒子X(jué)w(t)、Xmw(t)、Xl(t)進(jìn)行擾動(dòng)；

P′←P′∪{Xw(t),Xmw(t),Xl(t)}；

end while

P′←P′∪L；

returnP′

在某種意義上來(lái)說(shuō)，種群中幾乎所有的粒子都是通過(guò)間接地向精英粒子學(xué)習(xí)來(lái)更新自己的速度和位置，也就是說(shuō)精英粒子間接被用來(lái)引導(dǎo)整個(gè)種群進(jìn)化，因此選擇的精英粒子必須同時(shí)具備良好的收斂性和多樣性，精英粒子的好壞也會(huì)直接影響算法性能的優(yōu)劣.

基于三方競(jìng)爭(zhēng)的學(xué)習(xí)機(jī)制采用了非支配排序和擁擠距離排序[8]相結(jié)合的方式來(lái)挑選精英粒子.在進(jìn)行精英粒子的選擇時(shí)，首先對(duì)當(dāng)前種群P中的所有粒子進(jìn)行非支配排序以獲得種群中每個(gè)粒子的Pareto前沿面編號(hào)F1,F2,…,Fn.當(dāng)需要挑選λ個(gè)精英粒子時(shí)，首先要確定滿足條件的Pareto前沿面編號(hào).假設(shè)前k個(gè)前沿上的粒子數(shù)大于或等于λ，即|F1∪F2∪…∪Fk|≥λ，并且前k-1個(gè)前沿上的粒子數(shù)小于或等于λ，即|F1∪F2∪…∪Fk-1|≤λ.首先將前k-1個(gè)前沿面上的所有粒子加入精英粒子集，剩下的精英粒子在第k個(gè)前沿上基于擁擠距離排序結(jié)果選取.

至于種群中每個(gè)粒子的適應(yīng)度值計(jì)算，不能采用像單目標(biāo)PSO算法中直接將每個(gè)粒子的目標(biāo)函數(shù)值作為其適應(yīng)度值的機(jī)制，因?yàn)樵贛OPSO算法中每個(gè)粒子都有多個(gè)目標(biāo)函數(shù)值.文中引入了一種基于Iε+指標(biāo)和位移密度估計(jì)(shift-based density estimation, SDE)的混合指標(biāo)ISDE+[9]來(lái)計(jì)算每個(gè)粒子的適應(yīng)度值以評(píng)估各個(gè)粒子的優(yōu)劣性.Iε+指標(biāo)可以促進(jìn)收斂性，而SDE則能促進(jìn)種群的多樣性，因此ISDE+混合指標(biāo)能夠幫助算法更好地平衡多樣性和收斂性.一般而言，具有更高ISDE+值的粒子將被認(rèn)定為更優(yōu).種群P中粒子p的適應(yīng)度值定義為p與種群中其他粒子q基于ISDE+的最小距離，表示如下：

Fitness(p)=

(11)

(12)

式中：PSB(p)∈P,且q∈PSB(p)，SB(q)

在計(jì)算完每個(gè)粒子的適應(yīng)度值之后，利用三方競(jìng)爭(zhēng)學(xué)習(xí)機(jī)制對(duì)種群中除精英粒子之外的所有粒子進(jìn)行比較.在每次競(jìng)爭(zhēng)中，從種群中隨機(jī)挑選3個(gè)粒子進(jìn)行比較，適應(yīng)度值最大、次之、最小的分別定義為冠軍粒子、亞軍粒子、季軍粒子，它們對(duì)應(yīng)不同的更新策略.

2.3 粒子更新策略

不同于兩兩競(jìng)爭(zhēng)機(jī)制中的粒子更新方式，文中針對(duì)三方競(jìng)爭(zhēng)機(jī)制的特點(diǎn)提出了一種基于反向?qū)W習(xí)的漸進(jìn)式粒子更新策略.在改進(jìn)的粒子更新策略中，每次更新時(shí)，首先從精英粒子集L中隨機(jī)挑選一個(gè)精英粒子，冠軍粒子首先向預(yù)選的精英粒子學(xué)習(xí)進(jìn)行更新，然后亞軍粒子通過(guò)反向?qū)W習(xí)策略來(lái)更新自己，最后季軍粒子則向更新后的冠軍粒子學(xué)習(xí)來(lái)更新自己的速度和位置，這有利于增強(qiáng)算法的全局搜索能力，并且讓粒子更快地逼近真實(shí)的Pareto前沿.

假設(shè)第t次迭代時(shí)，在第k輪競(jìng)爭(zhēng)后冠軍粒子、亞軍粒子和季軍粒子的位置分別表示為Xw,k、Xmw,k和Xl,k，其速度分別表示為Vw,k、Vmw,k和Vl,k，其中k=1,2,…,(N-λ)/3.則在第t次迭代第k輪競(jìng)爭(zhēng)后，冠軍粒子的更新公式如下：

Vw,k(t+1)=r1Vw,k(t)+r2(Xe,k(t)-Xw,k(t)),

(13)

Xw,k(t+1)=Xw,k(t)+Vw,k(t+1).

(14)

亞軍粒子不更新速度，直接基于動(dòng)態(tài)廣義反向?qū)W習(xí)策略來(lái)更新自己的位置，即

Xmw,k(t+1)=k(daj+dbj)-Xmw,k(t),

(15)

式中：[daj,dbj]為第j維搜索空間的動(dòng)態(tài)范圍，下限、上限分別取值為亞軍粒子X(jué)mw,k=(xmw,k1,xmw,k2,…,xmw,kD)在第j維上的最小值和最大值，即

daj=min(xmw,kj),dbj=max(xmw,kj).

(16)

此時(shí)需要注意的是，亞軍粒子在某代進(jìn)化中可能會(huì)跳出可行解的邊界，此時(shí)對(duì)其在[daj,dbj]內(nèi)采用隨機(jī)生成的方法進(jìn)行重置，即

(17)

季軍粒子通過(guò)向更新后的冠軍粒子學(xué)習(xí)來(lái)更新自己的速度和位置，即

Vl,k(t+1)=r3Vl,k(t)+r4(Xw,k(t+1)-Xl,k(t)),

(18)

Xl,k(t+1)=Xl,k(t)+Vl,k(t+1).

(19)

式(13)-(19)中Xe,k是精英粒子的位置，參數(shù)r1-r4均為[0,1]D內(nèi)的隨機(jī)向量.值得注意的是，種群中1/3的亞軍粒子通過(guò)反向?qū)W習(xí)策略更新自己，有利于引導(dǎo)算法跳出局部最優(yōu)，而冠軍粒子向精英粒子學(xué)習(xí)，季軍粒子又通過(guò)向更新后的冠軍粒子學(xué)習(xí)來(lái)進(jìn)行更新，也能夠有效避免算法多樣性的喪失.

最后，為了進(jìn)一步增強(qiáng)算法跳出局部最優(yōu)的能力并提升種群多樣性，使用在遺傳算法中廣泛應(yīng)用的多項(xiàng)式變異來(lái)對(duì)更新后的所有粒子施加輕微變異，再將變異后的粒子加入新種群P′，重復(fù)上述操作直到種群P中所有的粒子都已被更新.

2.4 時(shí)間復(fù)雜度分析

由算法1和算法2可知，MOPSO-TCOL算法主要由種群初始化、精英粒子選擇、三方競(jìng)爭(zhēng)學(xué)習(xí)、速度與位置更新、環(huán)境選擇策略5個(gè)部分組成.對(duì)于一個(gè)大小為N的種群和一個(gè)含有m個(gè)目標(biāo)的多目標(biāo)優(yōu)化問(wèn)題，隨機(jī)初始化種群的時(shí)間復(fù)雜度為O(N)，而精英粒子是由非支配排序和擁擠距離排序機(jī)制選擇的，其最壞情況下的時(shí)間復(fù)雜度為O(mN2).對(duì)于采取的三方競(jìng)爭(zhēng)機(jī)制，在每次競(jìng)爭(zhēng)中首先從種群中隨機(jī)挑選3個(gè)粒子，然后進(jìn)行適應(yīng)度值比較，所需要的時(shí)間復(fù)雜度為O(3N×log(3N))；然后每個(gè)粒子向更優(yōu)粒子學(xué)習(xí)或基于反向?qū)W習(xí)策略來(lái)進(jìn)行更新，這個(gè)過(guò)程需要的時(shí)間復(fù)雜度均為O(N).至于環(huán)境選擇策略，文中借鑒了NSGA-Ⅲ算法中的相關(guān)策略從混合種群Pt′∪Pt(大小為2N)篩選出下一代的新種群Pt+1(大小為N)，這在最壞情況下需要的時(shí)間復(fù)雜度為O(mN2)或O(N2logm-2N).綜上所述，MOPSO-TCOL算法在最壞情況下的總的時(shí)間復(fù)雜度為max{O(N2logm-2N),O(mN2)}，這與NSGA-Ⅲ算法的時(shí)間復(fù)雜度是一致的.

3 性能測(cè)試與試驗(yàn)結(jié)果分析

3.1 試驗(yàn)設(shè)置

為了綜合評(píng)估MOPSO-TCOL的性能，進(jìn)行了一系列全面且多樣化的對(duì)比試驗(yàn).首先，將MOPSO-TCOL與4種目前主流的多目標(biāo)粒子群優(yōu)化算法進(jìn)行了比較，包括MPSO/D、MMOPSO、NMPSO和CMOPSO[1]；然后，將MOPSO-TCOL與4種經(jīng)典的多目標(biāo)進(jìn)化算法進(jìn)行了對(duì)比，包括MOEA/D-M2M、RPEA、NSLS和OSP-NSDE.這些算法都是近幾年發(fā)表在高質(zhì)量期刊上的算法，因此對(duì)比試驗(yàn)?zāi)軌虺浞肿C明所提出算法在性能上的優(yōu)勢(shì).對(duì)比算法的參數(shù)設(shè)置見(jiàn)表1.

表1 對(duì)比算法的參數(shù)設(shè)置

從2種被廣泛應(yīng)用的測(cè)試套件中挑選的14個(gè)基準(zhǔn)測(cè)試函數(shù)將被用來(lái)測(cè)試MOPSO-TCOL的性能，包括ZDT(ZDT1- 4, ZDT6)和WFG(WFG1- 9)，其中ZDT測(cè)試函數(shù)均為2目標(biāo)函數(shù)，而WFG測(cè)試函數(shù)為3目標(biāo)函數(shù).將ZDT1-3、ZDT4和ZDT6的決策變量數(shù)設(shè)置為30、10和10，將所有WFG測(cè)試函數(shù)的決策變量數(shù)設(shè)置為12.

在試驗(yàn)中，所有算法的種群大小設(shè)置為100.由于MOPSO-TCOL算法使用了三方競(jìng)爭(zhēng)機(jī)制，因此涉及到進(jìn)化的粒子數(shù)需為3的倍數(shù).文中采用CMOPSO算法中的建議值，將參數(shù)λ設(shè)置為10.所有的對(duì)比算法使用迭代次數(shù)作為算法終止條件，在2目標(biāo)、3目標(biāo)測(cè)試函數(shù)上的最大迭代次數(shù)分別設(shè)置為300、500.所有的對(duì)比算法均是在平臺(tái)PlatEMO[10]上運(yùn)行，并且每個(gè)對(duì)比算法在每個(gè)測(cè)試函數(shù)上均獨(dú)立運(yùn)行30次.

3.2 算法性能評(píng)估指標(biāo)

文中使用inverted generational distance (IGD)[11]作為算法性能評(píng)估指標(biāo)，該指標(biāo)能夠同時(shí)評(píng)估算法的收斂性和多樣性.算法所獲得的IGD值越小，就代表算法的綜合性能包括收斂性和多樣性越好.IGD

值計(jì)算公式如下：

(20)

dist(x*,S)=

(21)

3.3 IGD值比較

表2、3分別列出了4種MOPSO算法和4種MOEA算法與MOPSO-TCOL算法在14個(gè)基準(zhǔn)測(cè)試函數(shù)上獲得IGD值的平均值和標(biāo)準(zhǔn)差(括號(hào)中的是標(biāo)準(zhǔn)差)，其中最優(yōu)值用黑體標(biāo)出.此外，還采用了顯著性水平α=0.05的Wilcoxon秩和檢驗(yàn)來(lái)確定對(duì)比算法的性能在統(tǒng)計(jì)意義上的差異，采用符號(hào)“+”、“-”和“=”表示對(duì)比算法在統(tǒng)計(jì)意義上比MOPSO-TCOL算法更好、更差和相當(dāng).

表2 MOPSO-TCOL和其他MOPSO算法在測(cè)試函數(shù)上的IGD值

由表2可見(jiàn)，MOPSO-TCOL與其他4個(gè)對(duì)比的MOPSO算法相比在性能上具有明顯優(yōu)勢(shì).在所有14個(gè)測(cè)試函數(shù)中，MOPSO-TCOL算法在其中9個(gè)基準(zhǔn)測(cè)試函數(shù)上獲得了最好的平均值和標(biāo)準(zhǔn)差，而MMOPSO、NMPSO和CMOPSO則分別只在其中1、1、3個(gè)測(cè)試函數(shù)上獲得了最好的IGD值，而MPSO/D算法則未獲得任何最佳的IGD值.根據(jù)Wilcoxon秩和檢驗(yàn)統(tǒng)計(jì)結(jié)果，在14個(gè)基準(zhǔn)測(cè)試函數(shù)中，MOPSO-TCOL算法的性能分別在統(tǒng)計(jì)意義上在12、11、12、10個(gè)函數(shù)上優(yōu)于4個(gè)MOPSO算法，這說(shuō)明MOPSO-TCOL算法相比其他4個(gè)MOPSO算法擁有更好的多樣性和收斂性.

由表3可見(jiàn)，在與4個(gè)最近提出的MOEA算法的對(duì)比試驗(yàn)中，MOPSO-TCOL在性能上也具有競(jìng)爭(zhēng)性的優(yōu)勢(shì).在所有14個(gè)測(cè)試函數(shù)中，MOPSO-TCOL算法在其中11個(gè)基準(zhǔn)測(cè)試函數(shù)上獲得了最好的IGD值，而RPEA則在其中3個(gè)測(cè)試函數(shù)上獲得了最好的IGD值，并且MOEA/D-M2M、NSLS和OSP-NSDE算法在所有14個(gè)測(cè)試函數(shù)中均沒(méi)有取得任何最佳的IGD值.根據(jù)Wilcoxon秩和檢驗(yàn)統(tǒng)計(jì)結(jié)果，在14個(gè)基準(zhǔn)測(cè)試函數(shù)中，MOPSO-TCOL算法的性能在統(tǒng)計(jì)意義上分別在13、11、14、13個(gè)函數(shù)上優(yōu)于4個(gè)MOEA算法，這說(shuō)明MOPSO-TCOL算法相比其他4個(gè)MOEA算法也擁有更好的性能.

表3 MOPSO-TCOL和其他MOEA算法在測(cè)試函數(shù)上的IGD值

續(xù)表

3.4 Pareto前沿比較和收斂速度比較

圖1、2分別展示了MOPSO-TCOL算法和其他8個(gè)對(duì)比算法在ZDT3和WFG6測(cè)試函數(shù)上獨(dú)立運(yùn)行30次上獲得IGD均值相關(guān)的非支配解集在目標(biāo)空間中的分布.圖3給出了IGD值的收斂曲線.

圖1 所有算法在ZDT3測(cè)試函數(shù)上的近似帕累托前沿

圖2 所有算法在WFG6測(cè)試函數(shù)上的近似帕累托前沿

圖3 所有算法在ZDT3和WFG6測(cè)試函數(shù)上所獲得IGD值的收斂曲線

ZDT3是一個(gè)2目標(biāo)測(cè)試函數(shù)，其Pareto前沿是不連通的，從圖1可見(jiàn)，只有MMOPSO、CMOPSO和MOPSO-TCOL能完整地收斂到真實(shí)的Pareto前沿.WFG6為3目標(biāo)測(cè)試函數(shù)且具有球形的Pareto前沿.從圖2可見(jiàn)，相比于其他8種對(duì)比算法，MOPSO-TCOL算法所得到的非支配解均能更整齊且均勻地分布在真實(shí)的Pareto前沿上，這充分說(shuō)明了三方競(jìng)爭(zhēng)機(jī)制能夠有效提升算法的多樣性和收斂性，并且能在多樣性和收斂性之間保持很好的平衡.而其他算法則無(wú)法取得令人滿意的效果，例如：MOEA/DM2M、RPEA、NSLS和OSP-NSDE算法均只有少量的解能收斂到真實(shí)的Pareto前沿，而MMOPSO、NMPSO雖然也能收斂到真實(shí)的Pareto前沿，但分布不是很均勻；MPSO/D算法明顯陷入了局部最優(yōu)；只有CMOPSO和MOPSO-TCOL能取得較好的表現(xiàn)，并且MOPSO-TCOL所獲得的非支配解集的分布性明顯要比CMOPSO算法更好一些.這也間接說(shuō)明三方競(jìng)爭(zhēng)機(jī)制能夠引導(dǎo)算法較好地跳出局部最優(yōu).

為了充分衡量算法的性能，另一個(gè)重要的評(píng)估指標(biāo)是收斂速度.圖3給出了所有算法在ZDT3和WFG6測(cè)試函數(shù)上所獲得IGD值的收斂曲線.

從圖3可見(jiàn)，MOPSO-TCOL在ZDT3和WFG6上均具有最快的收斂速度，它能以很小的IGD值快速收斂到真實(shí)的Pareto前沿，即使迭代次數(shù)還不夠多，而此時(shí)其他的對(duì)比算法可能還沒(méi)有完全收斂.這也表明三方競(jìng)爭(zhēng)機(jī)制可以很好地提升算法的收斂速度.

基于以上分析和統(tǒng)計(jì)結(jié)果可見(jiàn)，所提出的MOPSO-TCOL算法的總體性能要優(yōu)于其他8種比較算法，這充分證明了三方競(jìng)爭(zhēng)機(jī)制和粒子更新策略的有效性.三方競(jìng)爭(zhēng)機(jī)制可以幫助MOPSO-TCOL獲得具有更好多樣性的非支配解，而基于反向?qū)W習(xí)的漸進(jìn)式粒子更新策略則可以在具有較優(yōu)多樣性的進(jìn)化環(huán)境中充分提升算法的收斂速度和求解精度.

4 結(jié) 論

1) 提出了一種基于三方競(jìng)爭(zhēng)機(jī)制的學(xué)習(xí)策略.該策略能夠有效減少算法維護(hù)外部存檔時(shí)的計(jì)算成本.同時(shí)，允許粒子在空間中進(jìn)行更廣泛的搜索，并有效提升算法的多樣性和收斂性.

2) 所提出的基于反向?qū)W習(xí)的漸進(jìn)式粒子更新策略可以進(jìn)一步提升算法的搜索效率、收斂速度和求解精度，同時(shí)借助較優(yōu)粒子良好的反向?qū)W習(xí)能力，能夠有效避免算法陷入局部最優(yōu).

3) 試驗(yàn)結(jié)果表明，所提出的MOPSO-TCOL算法在基準(zhǔn)測(cè)試函數(shù)上能夠產(chǎn)生精度更高且分布更好的非支配解集，且擁有更快的收斂速度.