一種基于自適應(yīng)模糊支配的高維多目標(biāo)粒子群算法

余偉偉 謝承旺 閉應(yīng)洲 夏學(xué)文 李雄 任柯燕 趙懷瑞 王少鋒

科學(xué)研究與工程實(shí)踐中不斷涌現(xiàn)出要求同時(shí)優(yōu)化4個(gè)或4個(gè)以上目標(biāo)的問題,研究者一般將這類優(yōu)化問題稱為高維多目標(biāo)優(yōu)化問題(Many-objective optimization problem,MAOP),與優(yōu)化目標(biāo)數(shù)為2至3個(gè)的多目標(biāo)優(yōu)化問題(Multi-objective optimization problem,MOP)相比,MAOP問題的目標(biāo)空間更大,搜索的難度也更大.其原因在于:隨著目標(biāo)空間維度的增加,種群中非被占優(yōu)個(gè)體的數(shù)量將呈指數(shù)級增長,運(yùn)用Pareto支配關(guān)系擇優(yōu)個(gè)體的方法面臨失效的窘地,算法的搜索能力被極大地削弱;另外,由于Pareto支配關(guān)系在高維空間中效果變差,使得分布性保持機(jī)制成為算法選擇個(gè)體的主導(dǎo)因素,但是由個(gè)體密度信息主導(dǎo)的選擇機(jī)制不一定能有效地驅(qū)動(dòng)近似Pareto前沿向真實(shí)Pareto前沿逼近,甚至可能對優(yōu)化過程有負(fù)面影響[1?3].為解決高維多目標(biāo)優(yōu)化問題帶來的挑戰(zhàn),各國學(xué)者從不同的視角提出了解決方法.陳振興等[4]融合張角擁擠控制策略解決MAOP問題.鞏敦衛(wèi)等[5]基于目標(biāo)分解的策略提出高維多目標(biāo)并行優(yōu)化方法.Drechsler等[6]提出了目標(biāo)優(yōu)勝關(guān)系的寬松Pareto支配關(guān)系:Favor關(guān)系,但該關(guān)系易受到目標(biāo)函數(shù)量綱差別的影響.Di Pierro等[7]提出K-占優(yōu)機(jī)制,但其只考慮了一個(gè)目標(biāo)向量相對于另一個(gè)目標(biāo)向量的改善目標(biāo)數(shù).Sato等[8]提出對解個(gè)體的支配區(qū)域進(jìn)行縮放以改變解個(gè)體在目標(biāo)空間中的位置,從而達(dá)到改變解個(gè)體支配關(guān)系的目的.需要指出,這種方法需要用戶為每一個(gè)目標(biāo)函數(shù)指定修正參數(shù).Hernandez-diaz等[9]通過引入評判目標(biāo)間優(yōu)劣關(guān)系的閾值提出了ε-占優(yōu)機(jī)制,但該策略依賴閾值的選取方法.Kang等[10]在總結(jié)新型占優(yōu)機(jī)制優(yōu)劣的基礎(chǔ)上提出了E-占優(yōu),但E-占優(yōu)方法在求解MAOP問題中的性能如何,文獻(xiàn)中并未討論.Zou等[11]提出了一種L-最優(yōu)性,該占優(yōu)方法不僅考慮了目標(biāo)值得到改善的目標(biāo)個(gè)數(shù)而且在所有目標(biāo)具有同等重要性的情況下,改善的目標(biāo)函數(shù)也考慮其中,但該方法隨著目標(biāo)個(gè)數(shù)的持續(xù)增加,仍面臨著選擇壓力退化的問題.Farina等[12]將模糊理論引入到多目標(biāo)優(yōu)化算法中,但該策略亦存在產(chǎn)生循環(huán)支配之缺陷.畢曉君等[13]將模糊理論引入高維多目標(biāo)進(jìn)化算法模型,并結(jié)合模糊理論α-截集提出了新的環(huán)境選擇策略.

粒子群優(yōu)化(Particle swarm optimization,PSO)是Kennedy等[14]受到飛鳥集群活動(dòng)的啟發(fā)而提出的一種群體智能優(yōu)化算法,其具有易于實(shí)現(xiàn)和收斂速度快等優(yōu)勢.近年來,PSO算法在多目標(biāo)優(yōu)化領(lǐng)域的研究取得了很大的進(jìn)展,涌現(xiàn)出了不少的多目標(biāo)粒子群算法(Multi-objective particle swarm optimization algorithm,MOPSO),但將其用于高維多目標(biāo)優(yōu)化問題求解的理論和方法還很少.

本文在已有多目標(biāo)粒子群算法和寬松支配關(guān)系等研究的基礎(chǔ)上,提出一種基于自適應(yīng)模糊支配的高維多目標(biāo)粒子群優(yōu)化(Many-objective particle swarm optimization based on adaptive fuzzy dominance,MAPSOAF)算法,以求解復(fù)雜的MAOP問題.算法的創(chuàng)新點(diǎn)主要包括:1)以步長幅度自適應(yīng)地調(diào)整模糊隸屬度支配的閾值來改進(jìn)模糊支配關(guān)系,在加強(qiáng)個(gè)體間支配能力的同時(shí)實(shí)現(xiàn)對種群選擇壓力的精細(xì)化調(diào)控,以改善算法的收斂性;2)增加擾動(dòng)粒子改造基本PSO算法的速度更新公式,在克服種群早熟收斂的同時(shí)改善個(gè)體分布的均勻性;3)利用簡化的Harmonic歸一化距離評估個(gè)體的密度,在改善種群分布性的同時(shí)降低算法的計(jì)算代價(jià).上述三種策略有機(jī)結(jié)合,形成了MAPSOAF算法的主要特點(diǎn),這些策略在算法的不同階段實(shí)施,以協(xié)同地提高M(jìn)APSOAF算法的總體性能.

論文的第1節(jié)簡要介紹高維多目標(biāo)優(yōu)化問題相關(guān)概念.第2節(jié)描述構(gòu)成MAPSOAF算法的若干重要組件和算法的流程,它是本文的重點(diǎn)章節(jié).第3節(jié)是論文的仿真實(shí)驗(yàn)與結(jié)果分析.最后是本文的結(jié)論部分.

1 高維多目標(biāo)優(yōu)化問題相關(guān)概念

不失一般性,一個(gè)具有n個(gè)決策變量、m個(gè)目標(biāo)函數(shù)的多目標(biāo)優(yōu)化問題,以最小化為例,可表述為式(1)的形式.

式中,x稱為決策向量,X是n維的決策空間;y稱為目標(biāo)函數(shù),Y是m維的目標(biāo)空間;目標(biāo)函數(shù)F定義了映射函數(shù)和需要同時(shí)優(yōu)化的m個(gè)目標(biāo).當(dāng)m≥4時(shí),稱式(1)為高維多目標(biāo)優(yōu)化問題.對于決策空間任意的兩點(diǎn)x1,x2∈X,當(dāng)x1的目標(biāo)函數(shù)都不大于并且至少存在一個(gè)小于x2的目標(biāo)函數(shù)時(shí),稱x1Pareto支配x2,記為x1?x2.若x?∈X不受種群中其他個(gè)體支配,則稱x?為Pareto非支配解,種群中所有非支配解組成的集合成為Pareto解集,其對應(yīng)的目標(biāo)函數(shù)構(gòu)成的集合為Pareto前沿.

2 基于自適應(yīng)模糊支配的高維多目標(biāo)粒子群優(yōu)化算法

2.1 自適應(yīng)模糊支配關(guān)系

目前基于寬松支配關(guān)系的多目標(biāo)/高維多目標(biāo)進(jìn)化算法大多采用變換目標(biāo)函數(shù)值的方法,鑒于目標(biāo)函數(shù)值是不可預(yù)測的,這就使得算法參數(shù)難以設(shè)定,而且目標(biāo)函數(shù)值的改變,尤其在高維多目標(biāo)優(yōu)化中,會(huì)使尋優(yōu)偏離真實(shí)的Pareto前沿.Farina等[12]將模糊理論引入高維多目標(biāo)優(yōu)化中,通過計(jì)算個(gè)體間目標(biāo)優(yōu)劣的數(shù)量來衡量個(gè)體的支配關(guān)系,提出(1?kF)支配策略.這種模糊支配關(guān)系的優(yōu)點(diǎn)在于個(gè)體間的支配關(guān)系不再受到目標(biāo)函數(shù)量綱和數(shù)值差異大小的影響,并使支配關(guān)系的復(fù)雜程度不受到目標(biāo)數(shù)量的影響.但是該支配策略存在一個(gè)重要缺陷,即種群中的個(gè)體可能會(huì)陷入循環(huán)支配,從而使得種群中不存在非支配的解,導(dǎo)致算法各種擇優(yōu)策略無法實(shí)施,迫使算法停止.基于此,這里提出一種自適應(yīng)的模糊支配關(guān)系,這種支配關(guān)系以步長幅度自適應(yīng)地調(diào)整模糊隸屬度支配閾值,在提高個(gè)體之間支配概率的同時(shí),實(shí)現(xiàn)對高維多目標(biāo)進(jìn)化算法種群選擇壓力的精細(xì)化調(diào)控,以更好地促進(jìn)算法收斂.

假設(shè)F(xi)和F(xj)分別表示種群中任兩個(gè)個(gè)體xi和xj的目標(biāo)向量,Bt(xi,xj)、Ws(xi,xj)和Eq(xi,xj)分別表示F(xi)中優(yōu)于、劣于和等于F(xj)的目標(biāo)個(gè)數(shù),據(jù)此,xi和xj的模糊支配隸屬度C(xi,xj)則可用式(2)表示,而模糊集CS可用式(3)表示.此外,為避免種群個(gè)體發(fā)生循環(huán)支配,借鑒文獻(xiàn)[13]的做法,這里為種群中的個(gè)體xi賦予目標(biāo)質(zhì)量屬性Q(xi),以刻畫xi目標(biāo)值的總體表現(xiàn),其計(jì)算方法如式(4)所示.

其中,N表示種群的規(guī)模,zj為第j(j∈[1,m])個(gè)目標(biāo)函數(shù)的最小值.當(dāng)目標(biāo)函數(shù)最小值已知時(shí),zj取第j個(gè)目標(biāo)函數(shù)真正的最小值;而當(dāng)目標(biāo)函數(shù)真正的最小值難以獲得時(shí),zj的值取當(dāng)前種群對應(yīng)的第j個(gè)目標(biāo)函數(shù)的最小值.

由于目標(biāo)質(zhì)量屬性Q是一個(gè)標(biāo)量,滿足傳遞性,即當(dāng)Q(xi)

在高維多目標(biāo)優(yōu)化問題中,隨著迭代次數(shù)的增加,種群中非支配解的數(shù)目急劇增多,導(dǎo)致種群的選擇壓力不斷降低,嚴(yán)重地影響了算法的收斂性能,因而需要在進(jìn)化過程中逐漸放寬個(gè)體的支配條件,減少群體中非支配解的數(shù)目,以增大種群的選擇壓力.基于此,這里嘗試自適應(yīng)地調(diào)整模糊隸屬度的支配閾值來控制支配條件.

本文的自適應(yīng)模糊支配關(guān)系可表述如下:假設(shè)xi和xj是種群中任兩個(gè)個(gè)體,當(dāng)Eq(xi,xj)6=m(m為MAOP問題的目標(biāo)數(shù)),若利用式(5)計(jì)算得到的模糊隸屬度C(xi,xj)滿足大于等于閾值λ(λ∈(0.5,1])且λ隨迭代次數(shù)的增加而遞減時(shí),則稱xi自適應(yīng)模糊支配xj.因此,當(dāng)λ=1時(shí),模糊支配關(guān)系成立需滿足Ws(xi,xj)=0,且Bt(xi,xj)>0,即個(gè)體xi的所有目標(biāo)都不劣于xj,并且至少存在一個(gè)目標(biāo)函數(shù)要優(yōu)于xj,此時(shí)模糊支配關(guān)系等價(jià)于Pareto支配關(guān)系;而當(dāng)λ=0.5時(shí),模糊支配關(guān)系成立需要滿足Bt(xi,xj)>Ws(xi,xj),即xi優(yōu)于xj的目標(biāo)個(gè)數(shù)要大于其劣于xj的目標(biāo)個(gè)數(shù),此時(shí)模糊支配關(guān)系等價(jià)于?-支配;而當(dāng)λ∈(0.5,1)時(shí),此時(shí)的模糊支配關(guān)系實(shí)際上是一種寬松的Pareto支配關(guān)系.閾值λ越小則支配關(guān)系越寬松,這有利于減少種群中非支配解的數(shù)目,以增強(qiáng)群體的選擇壓力,促進(jìn)算法較快收斂.因此,隨著迭代次數(shù)t的增加,閾值λ應(yīng)從1逐漸降至0.5附近,這里規(guī)定λ值依式(6)進(jìn)行非線性遞減.

其中,t為當(dāng)前的進(jìn)化代數(shù),T為算法允許的最大迭代次數(shù).

需要注意的是,現(xiàn)有寬松支配關(guān)系一般需要設(shè)置合理的參數(shù)以達(dá)到放寬支配條件,增大支配概率之目的,但這些支配關(guān)系的參數(shù)值與種群中非支配解的數(shù)量之間僅僅是一種定性關(guān)系,而非定量關(guān)系,因而在進(jìn)化過程中難以精細(xì)化調(diào)整參數(shù)值.鑒于式(5)中分子(Bt(xi,xj))的最小值為1/m,分母(Bt(xi,xj)+Ws(xi,xj))的最大值為m,因此,模糊隸屬度C(xi,xj)的最小值為1/m,閾值λ最小的有效調(diào)整步長可置為1/m.不妨令Bt(xi,xj)+Ws(xi,xj)=Ds,且設(shè)閾值λ的調(diào)整步長為1/Ds,則當(dāng)λ值減少一個(gè)步長1/Ds時(shí),意味著模糊支配關(guān)系降低了對較優(yōu)目標(biāo)個(gè)數(shù)所占比重的要求,使得群體中的個(gè)體更易形成支配關(guān)系,從而可提高支配的概率和種群的選擇壓力,促進(jìn)算法收斂.一般地,在高維多目標(biāo)進(jìn)化算法的后期,Eq(xi,xj)的值會(huì)逐漸增大,種群中更容易產(chǎn)生非支配解,通過對相鄰世代種群的模糊支配,隸屬度閾值變化一個(gè)步長的大小,使得緊鄰的下一代種群非支配解的數(shù)目可量化地減少.因此,這種以步長為幅度自適應(yīng)地調(diào)整支配閾值的方法適于處理一些高維多目標(biāo)優(yōu)化問題.此外,由于黃金分割比例近年來被廣泛應(yīng)用于復(fù)雜系統(tǒng)優(yōu)化中并取得了良好的效果,受此啟發(fā),這里將黃金分割點(diǎn)引入算法以執(zhí)行種群規(guī)模的劃分.

具體地,設(shè)種群規(guī)模為N,利用黃金分割點(diǎn)G將種群分割為規(guī)模不等的兩個(gè)子群,則較小子群的規(guī)模為N?bG·Nc(b·c表示向下取整).當(dāng)規(guī)模為N的種群中非支配解的數(shù)目不超過N?bG·Nc時(shí),以1/Ds為步長降低支配閾值,以放寬支配條件;當(dāng)種群中非支配解數(shù)目超過N?bG·Nc時(shí),則增大支配閾值,以縮緊支配條件.算法1給出了按步長自適應(yīng)調(diào)整支配閾值的流程.

算法1.按步長自適應(yīng)調(diào)整支配閾值

輸入.種群規(guī)模N,最大進(jìn)化代數(shù)Tmax,黃金分割點(diǎn)G,初始支配閾值λ0.

輸出.調(diào)整后的支配閾值.

以上自適應(yīng)模糊支配關(guān)系將MAOP問題中個(gè)體之間m個(gè)目標(biāo)的比較轉(zhuǎn)化成模糊隸屬度和目標(biāo)質(zhì)量屬性兩個(gè)值的比較,使得在目標(biāo)個(gè)數(shù)很多時(shí),也能容易地評價(jià)個(gè)體的優(yōu)劣,并促進(jìn)算法收斂.此過程沒有加入任何的偏好信息,沒有引入額外的參數(shù),沒有改變目標(biāo)函數(shù)的數(shù)值,更沒有對目標(biāo)進(jìn)行刪減,而是利用了個(gè)體目標(biāo)函數(shù)的完整信息.以步長為幅度調(diào)整支配閾值的大小,實(shí)現(xiàn)精細(xì)化調(diào)控支配的松緊程度,可滿足不同情況下的需求,因而自適應(yīng)模糊支配關(guān)系較適合MAOP問題的求解.

2.2 增加擾動(dòng)項(xiàng)的粒子速度更新方式

在粒子群優(yōu)化算法中,一個(gè)無質(zhì)量的粒子i可視為MAOP問題的一個(gè)潛在解,粒子i在搜索空間內(nèi)以一定的速度飛行,并根據(jù)其自身和集體的飛行經(jīng)驗(yàn)來動(dòng)態(tài)調(diào)整飛行速度.在基本PSO算法中粒子i的速度和位置的更新方程分別如式(7)和式(8)所示:

從式(7)可知,粒子i在第t代的移動(dòng)速度的變化受其自身歷史最優(yōu)位置和全局最優(yōu)位置Gbestt的共同影響,圖1以2-目標(biāo)優(yōu)化問題為例,示意在多目標(biāo)粒子群算法中當(dāng)前粒子i速度的變化趨勢.

圖1 多目標(biāo)粒子群算法中粒子的速度更新示意圖Fig.1 Velocity updation of particles in MOPSO

在多目標(biāo)粒子群算法的前期,粒子以較快的速度飛行,且具有較強(qiáng)的全局搜索能力,但在算法后期,若粒子自身的歷史最優(yōu)位置和全局最優(yōu)位置Gbestt比較接近,則容易導(dǎo)致大量粒子的聚集,使得種群中粒子的多樣性變差,可能會(huì)引起算法早熟收斂.基于此,這里考慮對多目標(biāo)粒子群算法中粒子的速度公式進(jìn)行改造,通過增加一擾動(dòng)項(xiàng)來增強(qiáng)種群的多樣性,從而有效避免算法陷入局部最優(yōu).其中的擾動(dòng)粒子從外部檔案(精英解集)中選擇離當(dāng)前粒子i的歐氏距離最近的個(gè)體.改造后的粒子速度更新如式(9)所示.

其中,在式(7)～(9)中,w為慣性權(quán)重,c1、c2和c3為學(xué)習(xí)系數(shù),r1、r2和r3為區(qū)間[0,1]上服從均勻分布的隨機(jī)數(shù),和為第t次迭代時(shí)粒子i在n維搜索空間中的位置和速度,而分別表示第t代的粒子i在搜索空間第j維上的位置和速度.為第t次迭代時(shí)粒子i的自身最佳位置,為第t次迭代時(shí)整個(gè)種群的全局最佳位置,分別表示第t次迭代時(shí)粒子i在第j維上的自身最佳位置和全局最佳位置.表示第t次迭代時(shí)距離當(dāng)前粒子i的歐氏距離最近的精英個(gè)體.在方程(9)的右邊,第1部分為粒子當(dāng)前速度乘以慣性權(quán)重進(jìn)行加速,表示粒子對當(dāng)前自身運(yùn)動(dòng)的信任,依據(jù)自身的速度進(jìn)行慣性運(yùn)動(dòng);第2部分為自我認(rèn)知部分,表示粒子對自身歷史的思考;第3部分為社會(huì)認(rèn)知部分,表示粒子在群體中的信息共享和相互合作;第4部分為擾動(dòng)部分,表示粒子受到檔案精英粒子的影響.圖2為增加一擾動(dòng)項(xiàng)之后粒子i的速度更新示意圖.

圖2 增加擾動(dòng)項(xiàng)之后算法中粒子的速度更新示意圖Fig.2 Velocity updation of particles after adding turbulence item in MOSPO

從式(9)可知,增加擾動(dòng)項(xiàng)后多目標(biāo)粒子群算法中粒子i的速度變化將受其歷史最優(yōu)解、全局最優(yōu)解Gbestt和離粒子i的歐氏距離最近的精英粒子的共同影響.而且從圖2也可看出,加入擾動(dòng)項(xiàng)之后的粒子可較好地逼近Pareto前沿.

從外部檔案中選擇距離當(dāng)前粒子的歐氏距離最近的精英個(gè)體作為擾動(dòng)粒子,原因有二:1)外部檔案中的個(gè)體是算法迄今發(fā)現(xiàn)的較優(yōu)秀的粒子,它們一般更加靠近Pareto前沿,新增精英個(gè)體引導(dǎo)粒子的移動(dòng)將有利于粒子朝Pareto前沿靠近;2)選擇離當(dāng)前粒子的歐氏距離最近的精英個(gè)體作為擾動(dòng)粒子相當(dāng)于對搜索空間進(jìn)行均勻劃分,而且還能較好地引導(dǎo)粒子在多個(gè)子空間內(nèi)進(jìn)行深度搜索,種群中粒子的多樣性和搜索能力都能得以改善,可有效防止算法早熟收斂.

2.3 全局最優(yōu)位置的選取

在多目標(biāo)粒子群算法中,全局最優(yōu)位置在引導(dǎo)粒子群朝Pareto前沿逼近的過程中發(fā)揮著重要的作用.由于MAOP問題的結(jié)果是一個(gè)非劣解集,因此粒子i的全局最優(yōu)位置有若干候選方案,而不像單目標(biāo)優(yōu)化問題那樣可以直接確定.多目標(biāo)粒子群算法中每個(gè)粒子的全局最優(yōu)位置從外部檔案(精英集)中產(chǎn)生,為防止檔案中部分粒子被重復(fù)選取,致使粒子朝相同的方向進(jìn)化而造成聚集,這里給檔案集中的粒子賦予一定的選擇概率,依概率選擇粒子i的全局最優(yōu)位置.如果外部檔案中某個(gè)精英個(gè)體被選為粒子i的全局最優(yōu)位置,則該精英個(gè)體再次被選中的概率將減少,其減少的概率將均勻分配給檔案集中其他的個(gè)體.式(10)給出了檔案個(gè)體被選為全局最優(yōu)位置后其概率的變化方式.

其中,Pk表示外部檔案集中的個(gè)體k被選中的概率,size(pop)和size(archive)分別表示粒子群和外部檔案的規(guī)模,初始時(shí)外部檔案中所有的非劣解的選擇概率取值為1/size(archive).

2.4 改進(jìn)的鄰域擁擠密度估計(jì)方法

高維多目標(biāo)優(yōu)化問題的求解目標(biāo)之一是要求獲得的近似Pareto解集中的解個(gè)體不僅能均勻分布在Pareto前沿面上,而且要求它們的分布盡量廣泛.實(shí)現(xiàn)該目標(biāo)需要體現(xiàn)出種群個(gè)體在目標(biāo)空間的分布情況,而個(gè)體之間的結(jié)構(gòu)和聯(lián)系主要表現(xiàn)為個(gè)體在目標(biāo)空間中的疏密遠(yuǎn)近.這里采用一種簡化的Harmonic歸一化距離方法計(jì)算個(gè)體的擁擠密度,一方面可克服Harmonic平均距離存在的缺陷[15],另一方面可高效地維持群體的分布性.具體描述如下:

對于種群中的第i個(gè)個(gè)體,假設(shè)在目標(biāo)空間中與個(gè)體i的距離由近及遠(yuǎn)的個(gè)體距離依次為di,1,di,2,···,di,N?1,則個(gè)體i的 Harmonic 平均距離如式(11)所示.

式(11)中的N為種群規(guī)模,即個(gè)體Harmonic平均距離的計(jì)算考慮了種群其他所有個(gè)體的距離,計(jì)算量很大.種群中相對距離較遠(yuǎn)的個(gè)體對所要計(jì)算鄰域密度的個(gè)體的影響不應(yīng)考慮在內(nèi),會(huì)引入不必要的偏差,造成資源浪費(fèi),這種情況在高維多目標(biāo)優(yōu)化問題中尤為明顯.在不影響精度的情況下,這里提出減少參與計(jì)算平均距離的個(gè)體數(shù)量,即計(jì)算的數(shù)目由N?1降為k,并取k=blog2Nc,可得到式(12):

鑒于種群個(gè)體之間的距離d可能為任意的正數(shù),為方便計(jì)算,對di,j(j=1,2,···,k)用歸一化方法進(jìn)行規(guī)范,可得相對距離為((di,k?dmin)/(dmax?dmin)),dmin和dmax分別為種群中個(gè)體之間的最小距離和最大距離,分布越好的個(gè)體其擁擠度應(yīng)該越大.為了保持di和di,k的一致性,可得[1?(di,k?dmin)/(dmax?dmin)],而且一般距離越近的個(gè)體對該個(gè)體的擁擠度的影響越大,反之距離越遠(yuǎn)影響會(huì)越小.為了擴(kuò)大這種差異,現(xiàn)對相對距離進(jìn)行平方,即((di,k?dmin)/(dmax?dmin))2,由此可得個(gè)體擁擠距離的計(jì)算公式:

分析式(13)可以發(fā)現(xiàn),該擁擠密度的計(jì)算方法只考慮了個(gè)體在局部鄰域內(nèi)相鄰的blog2Nc個(gè)個(gè)體之間的距離,這種簡化的Harmonic歸一化距離方法相比于Harmonic平均距離減少了計(jì)算量.具體分析如下:設(shè)種群規(guī)模為N,搜索空間的維度為n,目標(biāo)數(shù)為m.由于簡化后的擁擠密度計(jì)算方法僅考慮了bNc個(gè)相鄰的個(gè)體,其數(shù)量要少于Harmonic平均距離方法,所以時(shí)間復(fù)雜度要小于Harmonic平均距離的復(fù)雜度O(mnlog2n),減少量為O(N(N?1?blog2Nc)),其總復(fù)雜度為O(mnlog2n)?O(N(N?1?blog2Nc)).相比于循環(huán)擁擠排序方法,這里使用簡化的Harmonic歸一化距離無需反復(fù)計(jì)算個(gè)體的擁擠密度,僅需計(jì)算一次,大大降低了算法的計(jì)算復(fù)雜度.

種群中的個(gè)體由于具有共同的相鄰個(gè)體而聯(lián)系在一起,因此能在一定程度上反映出該個(gè)體在種群中的整體分布;同時(shí),采取在該局部鄰域內(nèi)距離不同的個(gè)體對其擁擠度的影響不同的放大策略和歸一化方法,保證了個(gè)體具有較好的鄰域分布.由此可見,簡化的擁擠密度估計(jì)方法能夠從局部和全局兩方面來維持種群的分布性.

2.5 高維多目標(biāo)優(yōu)化的環(huán)境選擇策略

在高維多目標(biāo)優(yōu)化問題中,決策空間和目標(biāo)空間的搜索范圍極大擴(kuò)張,自適應(yīng)模糊支配關(guān)系雖然能在一定程度上增強(qiáng)選擇壓力,提高收斂性能,但如果環(huán)境選擇策略設(shè)計(jì)不當(dāng),則可能導(dǎo)致種群陷入局部最優(yōu)甚至收斂停滯.針對這一問題,本文利用文獻(xiàn)[13]中改進(jìn)的環(huán)境選擇策略更新種群和外部檔案,而且引入兩個(gè)參數(shù)w1和w2分別表示支配度權(quán)重和擁擠距離權(quán)重,以協(xié)調(diào)收斂性和分布性.因此,粒子i的適應(yīng)度計(jì)算方法變化如下:

其中,ri和di分別表示粒子i的支配度和擁擠距離,詳情參見文獻(xiàn)[13].

2.6 MAPSOAF算法流程

在前面第2.1～第2.5節(jié)的基礎(chǔ)上,算法2給出了自適應(yīng)模糊支配的高維多目標(biāo)粒子群算法的流程.

算法2.MAPSOAF算法流程

輸入.種群規(guī)模N,外部檔案最大容量N0,黃金分割點(diǎn)G,初始支配閾值λ0,最大迭代次數(shù)Tmax,支配度權(quán)重w1,擁擠距離權(quán)重w2.

輸出.外部檔案集.

1.初始化規(guī)模為N的粒子群,對每個(gè)粒子,確定其初始位置和初始速度,粒子的自身歷史最好位置Pbest設(shè)置為粒子本身,置外部檔案集為空,令迭代器t=1.

2.WHILE(t≤Tmax)

3.計(jì)算粒子群中各粒子的目標(biāo)向量,根據(jù)第2.1節(jié)的自適應(yīng)模糊支配關(guān)系,將較好的N0個(gè)個(gè)體拷貝至外部檔案中.

4.根據(jù)第2.2節(jié)和第2.3節(jié)為種群粒子選擇擾動(dòng)粒子和全局最優(yōu)位置,并依式(9)更新粒子速度.

5.利用第2.4節(jié)中改進(jìn)的擁擠密度方法為種群中的粒子計(jì)算擁擠距離.

6.利用第2.5節(jié)的方法更新粒子群和外部檔案集.

7.t=t+1

8.END WHILE

9.輸出外部檔案集.

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

3.1 實(shí)驗(yàn)設(shè)置

3.1.1 對等比較算法

為檢驗(yàn)MAPSOAF算法的性能,這里選取5個(gè)代表性的多目標(biāo)進(jìn)化算法作為對比算法,它們分別是:1)Deb等[16]提出的改進(jìn)型非劣分類遺傳算法NSGA-II;2)Nebro等[17]提出的基于檔案的混合分散搜索算法AbYSS;3)Zitzler等[18]提出的改進(jìn)型強(qiáng)度Pareto進(jìn)化算法SPEA2;4)Nebro等[19]提出的限制速度的多目標(biāo)粒子群算法SMPSO;以及5)Wang等[20]提出的自適應(yīng)調(diào)整約束子問題MOEA/D算法,即MOEA/D-ACD算法.

3.1.2 高維多目標(biāo)測試函數(shù)集

為檢驗(yàn)本文算法的有效性,這里將MAPSOAF算法與上述5種對比算法一同在4,10,30目標(biāo)的DTLZ測試函數(shù)集[21]上進(jìn)行實(shí)驗(yàn)比較.選用可擴(kuò)展為任意目標(biāo)維數(shù)和自變量維數(shù)的通用測試函數(shù)DTLZ{1,2,4,5}.所有實(shí)驗(yàn)在硬件配置AMDA10-8700P CPU 1.8GHz主頻8.0GB內(nèi)存,Windows 7 64位操作系統(tǒng)的ThinkPad E565計(jì)算機(jī)上運(yùn)行.1)當(dāng)目標(biāo)個(gè)數(shù)為4時(shí),DTLZ函數(shù)集參數(shù)設(shè)置為:目標(biāo)個(gè)數(shù)為4,決策空間的維度為10,算法的迭代次數(shù)為2000;2)當(dāng)目標(biāo)個(gè)數(shù)為10時(shí),DTLZ函數(shù)集參數(shù)設(shè)置為:目標(biāo)個(gè)數(shù)為10,決策空間的維度為20,算法迭代次數(shù)為5000;3)當(dāng)目標(biāo)個(gè)數(shù)為30時(shí),DTLZ函數(shù)集參數(shù)設(shè)置為:目標(biāo)個(gè)數(shù)為30,決策空間維度為50,算法的迭代次數(shù)為10000.

3.1.3 性能指標(biāo)

反轉(zhuǎn)世代距離(Inverted generational distance,IGD)[22]度量了真實(shí)的Pareto前沿到算法獲得的近似Pareto前沿之間的距離.由于DTLZ函數(shù)集的真實(shí)Pareto解集是已知的,通過對真實(shí)Pareto解集進(jìn)行多樣性采樣,計(jì)算這些采樣點(diǎn)到近似Pareto解點(diǎn)之間的距離既反映了算法的收斂性又能反映出算法所獲解集的多樣性.一般而言,IGD指標(biāo)值越小則說明近似Pareto前沿的收斂性和多樣性越好.設(shè)P是多目標(biāo)優(yōu)化問題的真實(shí)Pareto解集,則IGD性能指標(biāo)值可通過式(15)進(jìn)行計(jì)算.

3.1.4 實(shí)驗(yàn)參數(shù)

5種對比算法的主要參數(shù)均采用對應(yīng)參考文獻(xiàn)中的建議值,如表1所示.

在表1中,N表示種群規(guī)模;Pc表示雜交概率;Pm表示變異概率;ηc=20和ηm=20分別是SBX和多項(xiàng)式變異的分布指數(shù).對于AbYSS算法而言,NRefSet1和NRefSet2分別是RefSet1和RefSet2的規(guī)模.在MOEA/D-ACD算法中,T定義了在加權(quán)系數(shù)中鄰域的規(guī)模,η為控制從T個(gè)鄰域解中選擇父本的概率,而nr表示父代個(gè)體被子代個(gè)體取代的最大數(shù)目.C1和C2是SMPSO算法中兩個(gè)從區(qū)間[1.5,2.5]的范圍內(nèi)隨機(jī)選取的控制參數(shù).需要指出,對比算法的參數(shù)是經(jīng)過適當(dāng)調(diào)參后為解決本文實(shí)驗(yàn)中絕大多數(shù)的MAOP問題而設(shè)定的.為公平比較起見,本文MAPSOAF算法的主要參數(shù)參照其他對比算法進(jìn)行設(shè)置,例如MAPSOAF種群規(guī)模為100,外部檔案的最大容量為100,而計(jì)算個(gè)體適應(yīng)度的支配度和擁擠距離的權(quán)重系數(shù)則參考文獻(xiàn)[15]的研究,分別取w1=1.5,w1=0.5.

為減少隨機(jī)誤差對統(tǒng)計(jì)結(jié)果的影響,這里所有的實(shí)驗(yàn)各執(zhí)行30次,每次使用不同的隨機(jī)數(shù)種子,以統(tǒng)計(jì)IGD的均值和方差.此外,為了使獲得的結(jié)論在統(tǒng)計(jì)上合理、可靠,這里采用Wilcoxon0s rank sum test來檢驗(yàn)MAPSOAF算法和其他對比算法所獲得的結(jié)果具有水平為α=0.5的顯著性差異.

3.2 實(shí)驗(yàn)結(jié)果與分析

表2～表5分別統(tǒng)計(jì)了函數(shù)DTLZ{1,2,4,5}具有4、10和 30個(gè)目標(biāo)時(shí)獲得的IGD 均值(mean)和標(biāo)準(zhǔn)差(std),其中采用粗體顯示不同算法在同一測試函數(shù)上獲得的最好的IGD均值,表中的“+”,“?”和“≈”分別表示算法獲得的結(jié)果要顯著地優(yōu)于、劣于和相似于MAPSOAF算法獲得的水平為α=0.05的Wilcoxon秩和檢驗(yàn)的結(jié)果.

從表2可以看出,MAPSOAF算法在10-目標(biāo)和30-目標(biāo)的DTLZ1問題上分別獲得了最優(yōu)的IGD均值,SMPSO算法在4-目標(biāo)的DTLZ1問題上獲得了最好的IGD均值,但本文的算法在該問題上獲得的IGD值與SMPSO算法獲得的IGD值具有相同的數(shù)量級(10?2),表明MAPSOAF算法在4-目標(biāo)的DTLZ1問題上的表現(xiàn)僅稍遜于SMPSO 算法,而要優(yōu)于AbYSS、SPEA2、NSGAII和MOEA/D-ACD算法.其次,通過統(tǒng)計(jì)各算法在DTLZ1(4,10,30)三個(gè)測試?yán)汐@得的IGD值的最終排序,表現(xiàn)最好的是MAPSOAF,然后依次是 SMPSO、AbYSS、SPEA2、NSGA-II和MOEA/D-ACD.從表2 的 “better/worst/similar”結(jié)果來看,各算法在DTLZ1(4,10,30)三個(gè)測試函數(shù)上只有SMPSO的結(jié)果是“1/1/1”,而其他4種對比算法的結(jié)果均是“0/3/0”,這表明MAPSOAF算法在這3個(gè)高維多目標(biāo)的DTLZ1問題上較之其他對比算法具有顯著的IGD性能優(yōu)勢.由于DTLZ1問題的Pareto前沿具有線性、多模態(tài)的特征,說明MAPSOAF算法在求解此類問題特征的MAOP問題時(shí)較其他算法更具優(yōu)勢.

表3給出了各算法在 4、10和 30目標(biāo)的DTLZ2問題上獲得的IGD值.MAPSOAF算法

分別在10-目標(biāo)和30-目標(biāo)的DTLZ2問題上獲得了最好的IGD均值結(jié)果,而NSGA-II算法則在4-目標(biāo)的DTLZ2問題上獲得了最佳的IGD均值.需要指出的是,MAPSOAF算法在4-目標(biāo)的DTLZ2問題上獲得的IGD值僅略差于NSGAII算法 (二者處于相同的數(shù)量級 10?2),而要優(yōu)于 SMPSO、AbYSS、SPEA2和 MOEA/D-ACD算法.此外,通過統(tǒng)計(jì)各算法在DTLZ2(4,10,30)三個(gè)測試?yán)汐@得的IGD值的最終排序,表現(xiàn)最好的是MAPSOAF,然后依次是NSGAII、SMPSO、AbYSS、SPEA2和MOEA/D-ACD.從表3的“better/worst/similar”來看,各算法在DTLZ2(4,10,30)三個(gè)測試函數(shù)上只有NSGA-II的結(jié)果是“1/1/1”,而其他4種對比算法的結(jié)果均是“0/3/0”,這表明本文算法在這3個(gè)高維多目標(biāo)的DTLZ2問題上較其他對比算法而言具有顯著的IGD性能優(yōu)勢.由于DTLZ2問題具有凹狀Pareto前沿,表明MAPSOAF算法能夠較好地求解具有這類問題特征的MAOP問題.

表1 5種對比算法的參數(shù)設(shè)置Table 1 Parameter settings of all the algorithms compared

表2 各算法在DTLZ1函數(shù)上獲得IGD值的比較Table 2 Results of IGD for algorithms compared based on DTLZ1

表3 各算法在DTLZ2函數(shù)上獲得IGD值的比較Table 3 Results of IGD for algorithms compared based on DTLZ2

從表4可知:MOEA/D-ACD算法在DTLZ4(4,10,30)三個(gè)高維目標(biāo)測試問題上均獲得了最優(yōu)的IGD均值,而MAPSOAF算法在4-目標(biāo)的DTLZ4問題上排名第2,在10-目標(biāo)和30-目標(biāo)的DTLZ4問題上均排名第3.通過統(tǒng)計(jì)各算法在DTLZ4(4,10,30)三個(gè)測試?yán)汐@得的IGD值的最終排名,表現(xiàn)最好的是MOEA/D-ACD,然后依次是NSGA-II、MAPSOAF、SMPSO、AbYSS和SPEA2.從表4的“better/worst/similar”來看,MOEA/D-ACD獲得的結(jié)果是“3/0/0”,而NSGAII獲得的結(jié)果是“0/2/1”,而其他兩種對比算法的結(jié)果均是“0/3/0”.由此可見,在DTLZ4(4,10,30)三個(gè)測試函數(shù)上,MOEA/D-ACD算法的IGD性能是最佳的,而MAPSOAF算法的表現(xiàn)只能處于中游位置.DTLZ4問題的Pareto前沿為凹形、有偏的特點(diǎn),說明本文算法在求解具有這類問題特征的MAOP問題時(shí)性能尚待提高.

從表5可以看出,MAPSOAF算法在DTLZ5(4,10,30)三個(gè)測試函數(shù)上均獲得了最優(yōu)的IGD均值.通過統(tǒng)計(jì)各算法在DTLZ5(4,10,30)三個(gè)測試?yán)汐@得的IGD值的最終排序,表現(xiàn)最好的是MAPSOAF,然后依次是SMPSO、NSGAII、SPEA2、AbYSS和MOEA/D-ACD.從表5最末一行的“better/worst/similar”來看,各算法在DTLZ1(4,10,30)三個(gè)測試函數(shù)上只有NSGA-II的結(jié)果是“0/2/1”以及SMPSO的結(jié)果是“0/3/1”,而其他兩種對比算法的結(jié)果均是“0/3/0”.表5的結(jié)果表明MAPSOAF算法在DTLZ5(4,10,30)三個(gè)測試問題上較之其他幾種對比算法具有顯著的性能優(yōu)勢.DTLZ5問題具有凹形且退化的Pareto前沿,而MAPSOAF算法能在該MAOP問題上獲得較好的結(jié)果.

綜觀表2～表5的實(shí)驗(yàn)結(jié)果,MAPSOAF算法相對其他5種代表性MOEA算法總體上具有顯著的收斂性和多樣性上的優(yōu)勢.究其原因,MAPSOAF算法通過定義步長幅度自適應(yīng)地調(diào)整模糊隸屬度支配的閾值,實(shí)現(xiàn)了對種群選擇壓力的精細(xì)化控制,能較好地改善算法的收斂性能;其次,MAPSOAF算法在粒子飛行速度的更新公式中新增了一擾動(dòng)項(xiàng),而且擾動(dòng)粒子來源于外部檔案中不重復(fù)的精英解,這種策略一方面能克服種群早熟收斂的缺點(diǎn),另一方面也能改善群體分布的均勻性;此外,MAPSOAF算法采用簡化的Harmonic歸一化距離方法評估個(gè)體的擁擠密度,既改善了種群的分布性,同時(shí)減小了計(jì)算代價(jià),提高了算法的效率.這三種策略相同協(xié)同,有效地提高了算法在求解高維多目標(biāo)優(yōu)化問題時(shí)的總體性能.

表4 各算法在DTLZ4函數(shù)上獲得IGD值的比較Table 4 Results of IGD for algorithms compared based on DTLZ4

表5 各算法在DTLZ5函數(shù)上獲得IGD值的比較Table 5 Results of IGD for algorithms compared based on DTLZ5

4 結(jié)論

高維多目標(biāo)優(yōu)化問題巨大的目標(biāo)空間使得一些經(jīng)典的多目標(biāo)優(yōu)化算法面臨困境,迫切需要發(fā)展新型高維多目標(biāo)優(yōu)化算法應(yīng)對挑戰(zhàn).論文提出一種基于自適應(yīng)模糊支配的高維多目標(biāo)粒子群算法MAPSOAF,該算法以步長為幅度,自適應(yīng)地調(diào)整模糊隸屬度支配閾值,實(shí)現(xiàn)對種群選擇壓力的精細(xì)化控制;其次算法在粒子速度更新公式中新增一擾動(dòng)項(xiàng),實(shí)現(xiàn)在克服種群早熟收斂的同時(shí)改善群體的分布性;最后,算法采用簡化的Harmonic歸一化距離評估個(gè)體的密度,實(shí)現(xiàn)改善群體分布性的同時(shí)降低算法的計(jì)算代價(jià).MAPSOAF算法與其他5種代表性的MOEA算法在12個(gè)基準(zhǔn)高維多目標(biāo)測試函數(shù)上進(jìn)行IGD性能實(shí)驗(yàn),結(jié)果表明本文的算法具有較顯著的收斂性和多樣性的性能優(yōu)勢.

未來將利用MAPSOAF算法求解實(shí)踐中如雷達(dá)優(yōu)化問題、水資源優(yōu)化問題、翼行設(shè)計(jì)問題和護(hù)士排班等典型高維多目標(biāo)優(yōu)化問題,以進(jìn)一步測試和改善算法的性能;另外,考慮將一些新近提出的進(jìn)化范例引入到高維多目標(biāo)優(yōu)化算法的框架中,以不斷提高解決復(fù)雜MAOP問題的能力.