基于粒子群與聚類的多目標(biāo)優(yōu)化算法

熊志堅, 王曉晶, 楊景明, 王偉芳, 趙志偉

(1.唐山學(xué)院 人工智能學(xué)院 河北省智能數(shù)據(jù)信息處理與控制重點實驗室,河北 唐山 063000;2.燕山大學(xué) 電氣工程學(xué)院,河北 秦皇島 066004; 3.開灤總醫(yī)院 信息科, 河北 唐山 063000; 4.唐山師范學(xué)院 數(shù)學(xué)與計算科學(xué)學(xué)院,河北 唐山 063000)

1 引 言

現(xiàn)實生活中的許多優(yōu)化問題包含多個需要優(yōu)化的相互沖突的目標(biāo)[1]，這些問題被稱為多目標(biāo)優(yōu)化問題(multi-objective optimization problems,MOPs),如數(shù)學(xué)、工業(yè)和商業(yè)等方面[2～4]。因此,多目標(biāo)優(yōu)化領(lǐng)域吸引了許多研究人員利用群算法開發(fā)一種高效、有效的優(yōu)化算法,以期解決各種復(fù)雜問題[5]。粒子群算法收斂速度較快,但對于多目標(biāo)優(yōu)化而言,保持群中粒子的多樣性一直是一個挑戰(zhàn)。[6]。最優(yōu)解的選擇對于任何多目標(biāo)粒子群優(yōu)化(particle swarm optimization,PSO)都是至關(guān)重要的,需要加強個體非支配性的同時,并保持它們之間的多樣性[7]。當(dāng)處理MOPs時,因為幾個目標(biāo)相互沖突,無法使用關(guān)系運算符來比較解的優(yōu)劣[8]。最終目標(biāo)不是尋找一個單一的解,而是尋找一組均勻分布靠近帕累托前沿(pareto-optimal front,POF)的最優(yōu)解[9]。PSO算法在處理MOPs時是通過探索和開發(fā)來實施。算法面臨的主要挑戰(zhàn)是需要在探索和開發(fā)之間取得平衡[10]。研究人員試圖用當(dāng)前優(yōu)化代數(shù)與最大優(yōu)化代數(shù)的比例來控制優(yōu)化過程[11]。在優(yōu)化過程中,種群成員的多樣性減少了,因為PSO算法將引導(dǎo)當(dāng)前的粒子移向目前為止找到的最佳解的位置[12]。因此,當(dāng)前粒子越接近最優(yōu)解,多樣性越小。然而,解決MOPs需要種群的高度多樣性,直到涵蓋所有可行解[13]。

為多樣化優(yōu)選全局最優(yōu)解,提出1種基于粒子群和分解聚類相結(jié)合的多目標(biāo)優(yōu)化算法(CDPSO)。種群與參考向量進行關(guān)聯(lián),對每個參考向量附近的解進行聚類,并使用聚合函數(shù)從每個聚類中只選擇1個最優(yōu)解。對于參考向量沒有關(guān)聯(lián)個體時,將從附近聚類中選擇1個尚未選擇的具有最小聚合函數(shù)值的解。優(yōu)選個體被用來更新全局最優(yōu)解。

2 相關(guān)理論

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

粒子群算法由1個隨機初始化的種群組成。尋找優(yōu)化問題的每個解被當(dāng)做粒子,所有粒子在目標(biāo)空間中搜索。每個粒子有適應(yīng)度函數(shù)值來判斷自身位置的優(yōu)劣。粒子能記錄自身在搜索過程中的位置信息。粒子的速度決定自身的方向。粒子之間的位置信息共享,粒子不斷調(diào)整本身的速度和位置往最佳的地方搜索。隨著搜索的進行,種群生成全局最優(yōu)解和個體最優(yōu)解。最優(yōu)解可以用于粒子速度和位置的更新。這些最優(yōu)解引導(dǎo)粒子群算法探索優(yōu)化問題的搜索空間。

第i個粒子的速度和位置更新公式分別為:

通過評估每個粒子的新位置,更新全球最優(yōu)解和個體最優(yōu)解。

2.2 參考向量

為了保持種群的多樣性,使用基于參考向量的多目標(biāo)優(yōu)化框架,通過參考向量對目標(biāo)空間進行分解,對種群進行聚類,然后利用這些參考向量選擇最優(yōu)解。通過Das和Dennis的系統(tǒng)方法在單位超平面上生成1組參考點,并繪制從原點到這些參考點的直線[14]。這些參考點放置在1個歸一化的超平面上,該平面與所有目標(biāo)軸傾斜,并在每個軸上有1個截距。參照點的數(shù)量為:

R=C(m+b-1,b)

式中:m為目標(biāo)數(shù)量;b1和b2分別為目標(biāo)軸上外層和內(nèi)層等分截距數(shù)量。圖1展示了當(dāng)b=4時，在三目標(biāo)(f1,f2,f3)空間總共生成了15個參考點。

圖1 參考點示例Fig.1 Reference point example

3 CDPSO

3.1 總體框架

CDPSO的總體框架算法如下:

1)p←初始化粒子群

2)V←初始化參考向量

3)p←歸一化

4) whilet≤tmaxdo

5)p←聚類

6)gb,i,gb,i←p

7)更新粒子群中每個粒子的速度和位置

8)Q←對種群p實施交叉和變異操作

9)p←p∪Q

10)t=t+1

11) end while

12) returnp

首先,確定算法最大迭代次數(shù),隨機初始化N個粒子的種群,根據(jù)第2.2節(jié)內(nèi)容在目標(biāo)空間中產(chǎn)生均勻的參考向量。對種群歸一化:

進行迭代,直到迭代次數(shù)達到規(guī)定的最大次數(shù)為止。把粒子中的全局最優(yōu)解和個體最優(yōu)解放入2個外部存檔中,并更新粒子群中每個粒子的速度和位置。為了避免算法陷入局部最優(yōu),使全局最優(yōu)解引導(dǎo)種群均勻分布在POF附近,需對當(dāng)前種群P中粒子進行交叉[15]和多項式變異[16]操作,產(chǎn)生新的子代Q和父代種群相結(jié)合在一起。然后第t代的計數(shù)器增加1。最后,返回種群。

3.2 聚類

CDPSO中采用了基于參考向量的多樣性策略。該方法的主要任務(wù)是更新全局最優(yōu)解,并分配給每一代種群中的粒子,引導(dǎo)種群多樣化均勻分布。聚類過程以參考向量為中心,通過計算粒子與參考向量的距離,具有最小D(p,V)值的粒子聚類到一起。參考向量與粒子之間的距離為:

生成聚類后,在每個聚類中選取1個具有最小聚合函數(shù)值F(p)的粒子,聚合函數(shù)表示如下:

F(p)=d(p,V)+λD(p,V)

圖2所示為聚類過程。在兩維目標(biāo)空間中分布著5個參考向量(V1,V2,…,V5)和10個粒子(P1,P2,…P10),生成5個聚類,選取5個最優(yōu)解。以參考向量V1為中心的聚類由粒子(P1,P2)構(gòu)成,(P3,P4,P5)形成聚類V2,(P6,P7,P8)形成聚類,V4,(P9,P10)形成聚類V5。一旦形成了這些聚類,使用聚合函數(shù)從每個聚類中只選擇一個優(yōu)秀粒子,聚類V1中選擇粒子P1,同理,粒子(P4,P7,P10)被選中。因為以上粒子分別在自己的聚類中具有最小的F(p)值。

參考向量V3并沒有粒子與它關(guān)聯(lián),需要通過計算附近粒子與V3的聚合函數(shù),找到具有F(P)最小值的個體完成聚類。最終聚類結(jié)果如圖3所示,5個聚類通過聚合函數(shù)分別優(yōu)選出5個最優(yōu)解。

圖2 聚類過程Fig.2 Clustering process

圖3 最優(yōu)解生成Fig.3 Optimal solutions generation

3.3 粒子更新

CDPSO充分利用了基于參考向量的算法所具有的高收斂性和高多樣性的優(yōu)點。

在優(yōu)化過程中,從gb,i的存檔中為群中的每個粒子分配一個全局最優(yōu)解。由于CDPSO采用了多樣性方法來分配全局最優(yōu)解,因此將任務(wù)劃分為兩種情況。如果以每個參考向量為中心的聚類中,有一個粒子被優(yōu)選,它將作為全局最優(yōu)解分配給種群中屬于這個參考向量的聚類中的粒子。為了避免下次重復(fù)選擇,并將這個粒子在這個聚類中刪除。如果參考向量沒有粒子與它關(guān)聯(lián),將從它附近其它聚類中通過聚合函數(shù)選擇一個最優(yōu)粒子作為這個聚類的全局最優(yōu)解,并從其它聚類中刪除這個粒子。

gb,i的存檔使用聚合函數(shù)來更新,如果粒子群中粒子本身的適應(yīng)度值優(yōu)于其個體最優(yōu)解,則更新它為該粒子的個體最優(yōu)解。

4 實驗研究與分析

為了評估CDPSO算法的有效性,使用WFG[17]測試函數(shù)上對CDPSO算法與4種PSO算法(MMOPSO[18],MOPSO[19],SMPSO[20],dMOPSO[21])進行仿真實驗。

4.1 參數(shù)設(shè)置

4個對比算法的參數(shù)值按照其原文的建議進行設(shè)置值。其它參數(shù)設(shè)置為:1) 種群總體大小為100,即隨機產(chǎn)生的解的數(shù)量。2) 所有算法的迭代次數(shù)設(shè)置為10 000次。3) 每個算法都經(jīng)過20次獨立運行進行評估。4) 所有算法根據(jù)Wilcoxon符號秩檢驗對其評價結(jié)果進行了5%顯著性水平檢驗。5) 在實驗過程中,各算法在目標(biāo)數(shù)量為(3,6,9)上分別測試。

4.2 性能指標(biāo)

4.3 實驗分析

所有算法在9個WFG測試問題中所獲得的結(jié)果分別展示在表1中。表1包含了每個算法在20次獨立運行中獲得的IGD值的平均值和標(biāo)準(zhǔn)差,最優(yōu)值加粗突出顯示,括號內(nèi)數(shù)據(jù)為標(biāo)準(zhǔn)差。Wilcoxon檢驗結(jié)果用符號(+,-,=)表示。符號“+”表明對比算法的性能明顯優(yōu)于CDPSO算法,符號“-”表示對比算法性能明顯差于CDPSO算法,“=”表示2種算法性能相當(dāng)。

表1 5個PSO算法獲得的IGD平均值和標(biāo)準(zhǔn)差值Tab.1 The IGD average and standard deviation obtained by five PSO algorithms

由表1可以看出,CDPSO性能出色,在27個測試結(jié)果中,CDPSO獲得的最佳IGD值達到20個,勝過MMOPSO達20項,全部優(yōu)于MOPSO,勝過SMPSO和dMOPSO多達22項。IGD指標(biāo)用來衡量每個算法獲得的最優(yōu)解與POF的距離,因此CDPSO是最接近POF的算法。

WFG1問題是1個混合和有偏差的問題,MMOPSO獲得了所有目標(biāo)的最佳IGD值。WFG2是1個凸的、不連接的、多模態(tài)的、不可分離的問題,在這個問題上,CDPSO獲得了3目標(biāo)和6目標(biāo)上的最優(yōu)值,MMOPSO獲得了9目標(biāo)上的最佳IGD值。WFG3問題是1個線性、退化和不可分離的問題,SMPSO獲得了6目標(biāo)和9目標(biāo)上測試的最佳IGD值。WFG4問題是1個凹的多模態(tài)問題;WFG5問題是1個凹的欺騙問題;WFG6問題是1個凹的不可分離問題;WFG7是1個凹的、偏向的問題;WFG8是1個凹的、偏向的、不可分離的問題;WFG9是1個凹的、偏向的、多模態(tài)的、欺騙性的、不可分離的問題。CDPSO在WFG4-WFG9多個目標(biāo)測試中,全部獲得了最優(yōu)值。

為了更加直觀地展示CDPSO算法的優(yōu)勢,5種PSO算法在3目標(biāo)WFG6測試問題上獲得的最優(yōu)解展示在圖4中。從圖4可以看出,MMOPSO,MOPSO和SMPSO三個算法的最優(yōu)解并沒有收斂到POF附近,并且分布不均勻。dMOPSO算法陷入了局部最優(yōu),最優(yōu)解集中到1個角落中。CDPSO算法的最優(yōu)解均勻的收斂在POF附近,表明聚類更新全局最優(yōu)解的策略產(chǎn)生了良好的作用。

圖4 5個PSO算法在3目標(biāo)WFG6測試問題上獲得的最優(yōu)解Fig.4 The optimal solution obtained by five PSO algorithms on the 3-objective WFG6 test problem

5 結(jié) 論

利用參考向量分解聚類,結(jié)合多目標(biāo)粒子群優(yōu)化算法,提出了基于粒子群的多目標(biāo)優(yōu)化算法。該算法主要目標(biāo)是增加最優(yōu)粒子的多樣性選擇,用于更新全局最優(yōu)解。在WFG測試問題上對CDPSO算法和4個PSO算法進行了性能比較,實驗結(jié)果表明CDPSO算法具有絕對的優(yōu)勢,提出的方法和策略提升了算法的性能。在未來的工作中,將對CDPSO進一步改進,解決到約束MOPs和實際問題。