熊志堅(jiān), 王曉晶, 楊景明, 王偉芳, 趙志偉

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

1 引 言

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

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

2 相關(guān)理論

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

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

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

通過(guò)評(píng)估每個(gè)粒子的新位置,更新全球最優(yōu)解和個(gè)體最優(yōu)解。

2.2 參考向量

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

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

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

圖1 參考點(diǎn)示例Fig.1 Reference point example

3 CDPSO

3.1 總體框架

CDPSO的總體框架算法如下:

1)p←初始化粒子群

2)V←初始化參考向量

3)p←歸一化

4) whilet≤tmaxdo

5)p←聚類(lèi)

6)gb,i,gb,i←p

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

8)Q←對(duì)種群p實(shí)施交叉和變異操作

9)p←p∪Q

10)t=t+1

11) end while

12) returnp

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

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

3.2 聚類(lèi)

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

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

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

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

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

圖2 聚類(lèi)過(guò)程Fig.2 Clustering process

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

3.3 粒子更新

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

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

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

4 實(shí)驗(yàn)研究與分析

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

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

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

4.2 性能指標(biāo)

4.3 實(shí)驗(yàn)分析

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

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

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

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

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

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

5 結(jié) 論

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