一種基于健康度的多目標(biāo)粒子群算法

(長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院,湖北 荊州 434023)

科學(xué)研究和現(xiàn)實(shí)工程設(shè)計(jì)中存在許多涉及多個(gè)數(shù)值目標(biāo)的最優(yōu)化問(wèn)題，即多目標(biāo)優(yōu)化問(wèn)題(multi-objective optimization problem，MOP)。通常情況下，多目標(biāo)優(yōu)化問(wèn)題考慮的各個(gè)子目標(biāo)互不相容，每個(gè)目標(biāo)的物理意義和單位均不一致。一個(gè)解在滿足某個(gè)目標(biāo)的同時(shí)必須以犧牲其他目標(biāo)為代價(jià)，所以多目標(biāo)問(wèn)題的解不是唯一的，而是存在一組既能滿足全部約束條件同時(shí)又可使各個(gè)目標(biāo)函數(shù)盡可能的達(dá)到最優(yōu)的Pareto最優(yōu)解集[1]。求解多目標(biāo)優(yōu)化問(wèn)題的方法主要分為2大類(lèi)[2]：①將多目標(biāo)優(yōu)化問(wèn)題作適當(dāng)?shù)奶幚?，如將多目?biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為一個(gè)單目標(biāo)優(yōu)化問(wèn)題的線性加權(quán)法、將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為一系列單目標(biāo)優(yōu)化問(wèn)題的層次分析法等。這類(lèi)方法思路較為簡(jiǎn)單，發(fā)展較為成熟，計(jì)算量小，能找到多目標(biāo)優(yōu)化問(wèn)題的非支配解，但這些方法也存在一定的局限性，如在優(yōu)化時(shí)要求決策者對(duì)問(wèn)題域有足夠的先驗(yàn)認(rèn)識(shí)才能給出較理想的轉(zhuǎn)化參數(shù)，不適用于求解Pareto前沿為非凸的問(wèn)題。②直接求出非劣解，然后從中選擇較好解，如非支配方法。

粒子群優(yōu)化算法(particle swarm optimization,PSO)是由美國(guó)社會(huì)心理學(xué)家Kennedy 和電氣工程師Eberhart于1995 年提出的一種群體智能算法，該算法源于對(duì)鳥(niǎo)群覓食行為的模擬。PSO算法具有易理解、易實(shí)現(xiàn)、收斂速度快、求解精度高等優(yōu)點(diǎn)，在多目標(biāo)問(wèn)題上得到了廣泛應(yīng)用。自2004年Colleo等[3]提出多目標(biāo)粒子群優(yōu)化算法(multi-objective particle swarm optimization, MOPSO)以來(lái)，許多研究者針對(duì)MOPSO計(jì)算復(fù)雜度高、通用性低、收斂性不好等缺點(diǎn)提出了改進(jìn)的多目標(biāo)粒子群算法。2006年，Sierra和Colleo[4]對(duì)各種多目標(biāo)粒子群算法進(jìn)行了歸納總結(jié)，指出單目標(biāo)PSO擴(kuò)展為MOPSO的3個(gè)關(guān)鍵問(wèn)題：如何找到無(wú)限逼近真實(shí)Pareto解集的非支配解集、如何選擇全局最優(yōu)粒子、如何維護(hù)Pareto前沿上解的多樣性；文獻(xiàn)[5]使用Pareto支配概念來(lái)確定粒子的飛行方向，并采用聚類(lèi)技術(shù)將決策空間中的種群分為幾個(gè)子種群，對(duì)每個(gè)子種群執(zhí)行PSO且子種群之間有信息交換;文獻(xiàn)[6]引入了適應(yīng)度共享概念，根據(jù)外部檔案中的每個(gè)解共享值大小采用輪盤(pán)賭方式為每個(gè)粒子從檔案選擇全局最優(yōu)粒子;文獻(xiàn)[7]引入了一種新的粒子群算法的領(lǐng)導(dǎo)者選擇方案，提出了一種與基于散點(diǎn)搜索的局部搜索方法相結(jié)合的多目標(biāo)粒子群算法；文獻(xiàn)[8]介紹了一種改進(jìn)的粒子群優(yōu)化算法(NSPSO)，通過(guò)使用非支配排序概念和2種無(wú)參數(shù)的小生境技術(shù)，更好地實(shí)現(xiàn)多目標(biāo)優(yōu)化；文獻(xiàn)[9]提出了目標(biāo)空間壓縮和擴(kuò)展策略，利用群體間的知識(shí)共享更新PSO，構(gòu)建了多目標(biāo)粒子群算法中的動(dòng)態(tài)多群算法。

以上提到的多目標(biāo)粒子群算法是粒子群算法應(yīng)用于多目標(biāo)問(wèn)題的重要研究成果，但還存在著收斂速度慢的問(wèn)題，且在粒子維數(shù)較高的情況下，很容易過(guò)早陷入局部最優(yōu)(早熟)。為此，筆者提出了一種基于健康度[10]的多目標(biāo)粒子群算法(HMOPSO)。

1 模型與基本概念

假設(shè)x∈Rn,f:Rn→Rm,g:Rn→Rq，則多目標(biāo)規(guī)劃問(wèn)題可表述為：

(1)

式中：x=[x1,x2,…,xn]T為決策變量；f(x)表示目標(biāo)函數(shù)；g(x)為不等式約束；S={x∈Rn|gi(x)≤0}表示問(wèn)題(1)的可行域。

定義1(Pareto支配)對(duì)于任意2個(gè)可行解x和y，如果對(duì)?i∈{1,2,…,m}滿足fi(x)≤fi(y)，且?i∈{1,2,…,m}使fi(x)

定義2(Pareto最優(yōu)解)如果x*是問(wèn)題(1)的可行解, 并且不存在x∈S, 使得xx*, 則x*為問(wèn)題(1)的一個(gè)Pareto最優(yōu)解。

定義3(Pareto最優(yōu)解集)所有問(wèn)題(1)的Pareto最優(yōu)解構(gòu)成Pareto最優(yōu)解集(Pareto-optimal set)，記作:

P*={x*∈S|?x∈S,x*x}

定義4(Pareto前沿)對(duì)于給定問(wèn)題(1)的所有Pareto最優(yōu)解所對(duì)應(yīng)的目標(biāo)向量構(gòu)成該多目標(biāo)問(wèn)題的Pareto前沿(Pareto Front)，記作：

PF*={f=(f1(x),f2(x),…,fm(x)|x∈P}

2 健康度

文獻(xiàn)[10]提出了健康度的概念，用于衡量粒子在尋求最優(yōu)解過(guò)程中的狀態(tài)。在每一次迭代進(jìn)程中，記錄當(dāng)前粒子的振蕩數(shù)Nosc和停滯數(shù)Ns，越來(lái)越接近最優(yōu)解的粒子健康度上升，反之下降。粒子健康度計(jì)算公式如下：

H=100-min(wsNs+woscNosc,100)

(2)

式中：ws和wosc分別是粒子的停滯次數(shù)和振蕩次數(shù)的權(quán)值系數(shù)。測(cè)試時(shí)選擇ws=0.8，wosc=3。

2.1 粒子的振蕩數(shù)Nosc

在粒子的運(yùn)動(dòng)過(guò)程中，如果粒子當(dāng)前迭代與上一次迭代運(yùn)行方向相異，則該粒子在此維度上出現(xiàn)振蕩，粒子振蕩狀態(tài)的判定公式如下：

(3)

式中：xi表示粒子在i狀態(tài)下的位置。

在迭代過(guò)程中，若連續(xù)2代均滿足式(3)，則判定該粒子第1次出現(xiàn)振蕩趨勢(shì)。自第3代開(kāi)始，只要滿足式(3)，則粒子振蕩數(shù)加1，直至粒子被迫變異或者不滿足式(3)時(shí)，Nosc重置為0。

2.2 粒子的停滯數(shù)Ns

粒子的運(yùn)動(dòng)軌跡可以表示為圖1所示的3種狀態(tài)，當(dāng)粒子的運(yùn)動(dòng)軌跡表現(xiàn)為振蕩狀態(tài)，即粒子在某個(gè)維度上重復(fù)出現(xiàn)圖1中(b)和(c)所示的2種狀態(tài)時(shí)，通常會(huì)出現(xiàn)尋優(yōu)停滯。粒子停滯數(shù)的確定如下：

(i) 若當(dāng)前粒子支配個(gè)體歷史最優(yōu)值時(shí)，粒子停滯數(shù)Ns記為0；

(ii) 若個(gè)體歷史最優(yōu)值支配當(dāng)前粒子時(shí)，粒子停滯數(shù)Ns加1；

(iii) 若當(dāng)前粒子與個(gè)體歷史最優(yōu)值不存在支配關(guān)系時(shí)，粒子停滯數(shù)Ns以0.5的概率加1。

圖1 粒子運(yùn)動(dòng)軌跡示意圖

2.3 異常粒子的變異

在粒子維數(shù)較高時(shí)，粒子極易陷入早熟收斂，筆者引入的健康度體現(xiàn)了粒子向最優(yōu)解的飛行狀態(tài)，當(dāng)粒子健康度下降至試驗(yàn)前設(shè)定的閾值時(shí)，則判定該粒子為異常粒子。對(duì)健康度過(guò)低的異常粒子，利用引導(dǎo)因子qi引導(dǎo)更新異常粒子的歷史最優(yōu)位置，改變粒子的運(yùn)動(dòng)軌跡，促使粒子跳出局部最優(yōu)，在每一次迭代中減少異常粒子的數(shù)量，增強(qiáng)種群的整體健康度，保證種群的多樣性。異常粒子位置更新為：

xw=xw+rand(0,1)×(qi-xw)

(4)

式中：qi為引導(dǎo)因子，即每次迭代的全局最優(yōu)值。

3 HMOPSO

3.1 外部歸檔集的更新策略

整個(gè)搜索過(guò)程中，外部歸檔集的更新策略是獲得一組好的Pareto最優(yōu)解的關(guān)鍵。Deb等[11]使用了非支配排序方法解決多目標(biāo)優(yōu)化問(wèn)題。Zitzler等[12]于1999年正式提出了具有精英保留機(jī)制的強(qiáng)度帕累托進(jìn)化算法(SPEA)。Deb等[13]提出了更有效的非主導(dǎo)排序方法稱(chēng)為快速非支配排序。筆者利用給定最大容量的外部歸檔集來(lái)存儲(chǔ)和更新每個(gè)迭代中的非支配解。最初，非支配解存儲(chǔ)在空的外部歸檔集中。粒子X(jué)是否加入到當(dāng)前外部歸檔集有3條規(guī)則：如果X被外部歸檔集中某個(gè)解支配，則X不加入；如果X支配外部歸檔集中某一個(gè)或多個(gè)解，則X加入外部歸檔集中并刪除掉外部歸檔集中被X支配的解；如果X不支配外部歸檔集中任何解且外部歸檔集中沒(méi)有解支配X，則X加入到外部歸檔集中。

3.2 動(dòng)態(tài)擁擠排序的外部歸檔集維護(hù)策略

當(dāng)外部歸檔集中解的個(gè)數(shù)超出預(yù)先給定的范圍時(shí)需要?jiǎng)h除多余的部分。文獻(xiàn)[13]通過(guò)計(jì)算每個(gè)粒子的擁擠距離刪除擁擠距離小的粒子。針對(duì)m個(gè)目標(biāo)的多目標(biāo)問(wèn)題，非支配解集為I，粒子擁擠度距離的計(jì)算方法步驟如下：

根據(jù)商務(wù)英語(yǔ)專(zhuān)業(yè)跨境電商方向人才培養(yǎng)目標(biāo)和對(duì)行業(yè)企業(yè)的調(diào)研，在全面分析跨境電商崗位所需知識(shí)結(jié)構(gòu)和崗位技能的基礎(chǔ)上，我們提出基于職業(yè)素養(yǎng)的崗位基本能力、崗位核心能力和拓展能力構(gòu)建跨境電商方向的課程體系。

Step1初始化距離，對(duì)每個(gè)I中的粒子i，令I(lǐng)[i]distance=0；

Step2對(duì)目標(biāo)j∈m，根據(jù)目標(biāo)函數(shù)值對(duì)l個(gè)粒子進(jìn)行升序排列(l=|I|為解集中粒子個(gè)數(shù))；

Step3令I(lǐng)[1]distance=I[l]distance=∞，以保證邊界點(diǎn)始終被選中；

Step4第2個(gè)至第l-1個(gè)粒子的擁擠度計(jì)算公式如下：

(5)

式中:cj(i)為第i個(gè)粒子在目標(biāo)j的目標(biāo)函數(shù)值。

在算法中，通常種群距離越小的粒子，分布度就越差，當(dāng)非支配解集中粒子個(gè)數(shù)超過(guò)種群規(guī)模時(shí)，則需根據(jù)擁擠距離大小的排序，淘汰多余的粒子。傳統(tǒng)的淘汰機(jī)制是直接淘汰擁擠距離較小的k個(gè)粒子，顯然，這種方法較為粗糙，可能會(huì)導(dǎo)致個(gè)體的缺失，使得解的分布性較差。鑒于此，筆者采用動(dòng)態(tài)的擁擠排序的方法來(lái)控制外部存檔的規(guī)模[14]，每計(jì)算一次擁擠距離，就刪除掉擁擠距離最小的一個(gè)粒子，重復(fù)下去，直至淘汰所有多余的粒子。

3.3 HMOPSO具體計(jì)算步驟

對(duì)于PSO算法，粒子的速度和位置更新公式為：

(6)

式中：pij(t)表示第i個(gè)粒子的歷史最優(yōu)位置；gj(t)表示全局最優(yōu)位置；w為慣性權(quán)重；c1和c2為學(xué)習(xí)因子；r1和r2為[0，1]間隨機(jī)數(shù)。HMOPSO的具體計(jì)算步驟如下：

Step1初始化粒子群：設(shè)定種群規(guī)模N、外部歸檔集大小Ne、最大迭代次數(shù)M、隨機(jī)產(chǎn)生粒子初始的位置Xi、初始速度Vi、個(gè)體極值pbest[i]、全局極值gbest。

Step2計(jì)算每個(gè)粒子的適應(yīng)度函數(shù)值，并根據(jù)粒子適應(yīng)度確定粒子間的支配關(guān)系，將非支配解放入外部歸檔集中。

Step3根據(jù)式(6)更新粒子的速度與位置，并重新計(jì)算適應(yīng)度值。

Step4基于健康度更新個(gè)體最優(yōu)粒子：

(i) 計(jì)算粒子停滯數(shù)和振蕩數(shù)；

(ii) 更新粒子健康度；

(iii) 若粒子健康度小于給定閾值H，執(zhí)行變異操作，改變其局部最優(yōu)位置，變異后，粒子健康度重新恢復(fù)到100。

Step5更新外部歸檔集。

Step6更新全局極值。

Step7判斷是否滿足終止條件，若滿足，退出，否則返回Step 3。

4 仿真試驗(yàn)

為測(cè)試HMOPSO算法的效果，筆者對(duì)FON、ZDT6和ZDT1這3個(gè)不同維度的典型函數(shù)進(jìn)行測(cè)試：

s.t.-4≤xi≤4,i=1,2,3

ZDT6:minf1(x)=1-exp(-4x1)sin6(6πx1)

s.t.0≤xi≤1,i=1,2,…,10

ZDT1:minf1(x1)=x1

s.t.0≤xi≤1,i=1,2,…,30

試驗(yàn)中給定MOPSO和HMOPSO的參數(shù)：學(xué)習(xí)因子c1=1，c2=2,慣性權(quán)重w=0.5,粒子群規(guī)模N=100,最大迭代次數(shù)M=400，最低健康度H=88。由MOPSO和HMOPSO分別所得3個(gè)測(cè)試函數(shù)的Pareto解繪制的Pareto前沿如圖2、圖3、圖4所示。從圖2～圖4可以看出，MOPSO和HMOPSO均能得到有效的Pareto前沿， HMOPAO得到的Pareto前沿更加均勻，且更接近真實(shí)Pareto前沿。試驗(yàn)結(jié)果表明了HMOPSO能保證種群的多樣性和Pareto前沿分布上的均勻性，對(duì)解決多目標(biāo)問(wèn)題具有重要的借鑒意義。

圖2 測(cè)試函數(shù)FON的Pareto曲線

圖3 測(cè)試函數(shù)ZDT6的Pareto曲線

圖4 測(cè)試函數(shù)ZDT1的Pareto曲線

5 結(jié)語(yǔ)

提出了一種基于健康度的多目標(biāo)粒子群算法HMOPSO。該算法采用了健康度的概念來(lái)使粒子跳出局部最優(yōu),并在擁擠距離基礎(chǔ)上，使用了動(dòng)態(tài)擁擠排序的外部歸檔集維護(hù)策略。試驗(yàn)結(jié)果證明，該算法具有較強(qiáng)的全局搜索能力和獲得好的Pareto最優(yōu)解的能力。相比于MOPSO，HMOPSO的Pareto解集在多樣性和分布均勻性上具有明顯的優(yōu)勢(shì)。