基于偏好的ε-Pareto支配的多目標(biāo)粒子群算法

李　靜，黃天民，陳尚云(西南交通大學(xué)數(shù)學(xué)學(xué)院， 四川　成都　611756 )

現(xiàn)實(shí)的優(yōu)化問(wèn)題一般涉及對(duì)多個(gè)目標(biāo)的同時(shí)優(yōu)化[1-4]。進(jìn)化算法的思想是將實(shí)際問(wèn)題的需求轉(zhuǎn)化為目標(biāo)函數(shù)，再采用某種機(jī)制來(lái)搜索解，最終解決實(shí)際問(wèn)題。近年來(lái)的算法都有一些類似的特征，在采用進(jìn)化算法進(jìn)行搜索時(shí)，并未嚴(yán)格地模擬生物進(jìn)化，而是采用適當(dāng)?shù)拇胧┻M(jìn)行精英保留，在整體上沿用進(jìn)化的思想。文獻(xiàn)[5-7]采用局部搜索的操作，使計(jì)算復(fù)雜度有所降低，對(duì)檔案集合的過(guò)程進(jìn)行了更新，具有較好的進(jìn)化性能和收斂速度，但是對(duì)歸檔集合的規(guī)模大小并未限制。文獻(xiàn)[8]基于種群多樣度理論，采用排序的自適應(yīng)縮放因子和自適應(yīng)交叉因子相結(jié)合的雙變異策略，提出了一種較穩(wěn)定且收斂速度較快的算法。

Kennedy等模擬鳥(niǎo)群覓食行為得出一種基于種群的解決優(yōu)化問(wèn)題的進(jìn)化算法，并稱之為粒子群進(jìn)化算法[9](particle swarmoptimization,PSO)。該算法的最終目的是得到解決方案使決策者滿意，并不需要在整個(gè)Pareto 前沿上搜尋最優(yōu)解。于是，在解決多目標(biāo)優(yōu)化問(wèn)題時(shí)，可以將決策者的偏好信息加入到搜索過(guò)程中，利用偏好(preference)信息[10-13]引導(dǎo)粒子傾向決策者滿意的區(qū)域就能有效提高算法的運(yùn)行效率。文獻(xiàn)[14]在粒子群算法的基礎(chǔ)上，考慮參考點(diǎn)與參考區(qū)的動(dòng)態(tài)變化，提出了一種綜合偏好引導(dǎo)策略?？紤]到粒子容易陷入局部最優(yōu)的問(wèn)題，本文引入了擁擠度函數(shù)和突變策略，以提高算法的效率，然后在歸檔集的篩選中引入了決策者的偏好信息，這樣在提高算法運(yùn)行速度的同時(shí)也得到了令決策者滿意的Pareto最優(yōu)解。

1　相關(guān)概念

1.1　基本概念

設(shè)有m個(gè)相互沖突的優(yōu)化目標(biāo)

f(X)={f1(X),f2(X),…,fm(X)}，

(1)

給定決策變量X=(x1,x2,…,xn),滿足

R={X|X∈Rn,gi(X)≤0,j(X)=0,

i=1,2,…,k;j=1,2,…,l}。

(2)

多目標(biāo)優(yōu)化問(wèn)題的一般描述為

minf(X)={f1(X),f2(X),…,fm(X)}。

(3)

1.2　擁擠度函數(shù)

對(duì)于Pareto最優(yōu)解前沿上的解Pk,解Pk的擁擠距離[4]為

1.3　角度偏好區(qū)域的設(shè)定

本文采用文獻(xiàn)[15-16]中的設(shè)定方法，預(yù)先設(shè)定偏好角度α及參考點(diǎn)r的分量ri(i=1,2,…,M)，把參考點(diǎn)r與坐標(biāo)原點(diǎn)0的連線作為參考線。偏好角度應(yīng)適當(dāng)取小，在本文實(shí)驗(yàn)中取0.05。參考點(diǎn)是根據(jù)各分量與Pareto邊界的距離來(lái)進(jìn)行調(diào)整。

當(dāng)產(chǎn)生新的子代個(gè)體時(shí)，通過(guò)

計(jì)算新個(gè)體與參考線的夾角θ，從而對(duì)個(gè)體是否位于偏好區(qū)域進(jìn)行判斷。若θ≤α，則該個(gè)體位于偏好區(qū)域；否則，位于非偏好區(qū)域。

2　基于偏好的ε-Pareto支配的多目標(biāo)粒子群算法(AP-εPSO)

2.1　突變的類型

本文的突變[17]是分為2種類型：統(tǒng)一突變和非統(tǒng)一突變。統(tǒng)一突變是指子代中每個(gè)決策變量的變化范圍都是常數(shù)；非統(tǒng)一突變是指子代中每個(gè)決策變量的變化范圍是隨著時(shí)間減少的。定義突變率為1/codesize，codesize指編碼所有決策變量的字符串總長(zhǎng)(在本算法中指的是變量的個(gè)數(shù))。為簡(jiǎn)化數(shù)學(xué)模型，本文采用漸進(jìn)縮小的突變，將決策變量個(gè)數(shù)減少，其次在不改變數(shù)量的基礎(chǔ)上，對(duì)決策變量本身進(jìn)行改變，最終通過(guò)突變使解空間變大。

2.2　算法的主要流程

在AP-εPSO算法中引入突變操作，并且利用ε-Pareto排序、角度偏好來(lái)篩選Pareto前沿上的最優(yōu)解。算法的主要流程如下。

第1步，新個(gè)體new-particle偏好區(qū)域的設(shè)定：

Step1，根據(jù)式(5)計(jì)算角度θ；

Step2，若θ≤α，則new-particle居于偏好區(qū)域，否則，new-particle居于非偏好區(qū)域。

第2步，粒子的初始化和具體迭代：

Step1，設(shè)定最大迭代次數(shù)、參考點(diǎn)及角度值，初始化種群，初始化非支配解，將非支配解歸結(jié)到外部歸檔集；

Step2，計(jì)算外部歸檔集中的非支配解的擁擠度，若擁擠度的個(gè)數(shù)大于可允許的最大值，則僅有擁擠度值大的非支配解被保留下來(lái)；

Step3，將種群細(xì)分為3部分，分別進(jìn)行突變操作，第1個(gè)子部分不發(fā)生突變，第2個(gè)子部分發(fā)生統(tǒng)一突變，第3個(gè)子部分發(fā)生非統(tǒng)一突變；

Step4，更新位置、速度，計(jì)算新個(gè)體是否位于偏好區(qū)域，并且更新外部歸檔集；

Step5，判斷是否達(dá)到算法終止條件，如是，則輸出當(dāng)前歸檔集種群作為最終結(jié)果，否則轉(zhuǎn)Step3。

本算法在更新外部歸檔集中引入決策者的偏好信息，通過(guò)Pareto支配[16]、ε-Pareto支配[10]求得的Pareto最優(yōu)解進(jìn)行篩選，刪除位于非偏好區(qū)域的Pareto最優(yōu)解，使最終得出的Pareto最優(yōu)解的個(gè)數(shù)減少且目標(biāo)函數(shù)值最優(yōu)。它的有效性將通過(guò)實(shí)驗(yàn)進(jìn)行驗(yàn)證。算法的流程如圖1所示，更新外部歸檔集如圖2所示。

圖1　算法流程圖

圖2　更新外部歸檔集

2.3　對(duì)比評(píng)價(jià)指標(biāo)與實(shí)驗(yàn)結(jié)果

2.3.1GD值

當(dāng)代距離(generational distance,GD)指標(biāo)[1]定義為一種表示Pareto最優(yōu)前沿距真實(shí)Pareto前沿的遠(yuǎn)近程度的數(shù)值。其表達(dá)式為

式中：n為Pareto最優(yōu)前沿解的數(shù)量；通常p=2；di為目標(biāo)空間中真實(shí)Pareto前端的每個(gè)向量與其最鄰近向量之間的歐幾里得距離。

2.3.2SP值

Scott提出一種度量Pareto前沿中鄰居向量的距離方差方案，該方法無(wú)須設(shè)置參數(shù)且已知Pareto面，是目前常用的均勻性評(píng)價(jià)指標(biāo)之一。評(píng)價(jià)函數(shù)[1]定義為

式中：

i=1,2,…,n，j=1,2,…n；

(8)

2.3.3實(shí)驗(yàn)結(jié)果

表1為測(cè)試函數(shù)。表2為測(cè)試函數(shù)的運(yùn)行參數(shù)。在表1中DTLZ1、DTLZ2及DTLZ3的|XM|=K,決策變量的后K(K=(n-M+1))個(gè)變量表示為XM并且g(XM)≥0,在本論文中M=3。

表1　測(cè)試函數(shù)

表1(續(xù))

表2　算法中的運(yùn)行參數(shù)設(shè)置

為驗(yàn)證算法的分布性與收斂性，對(duì)比本算法AP-εPSO與G-NSGA-Ⅱ[5]、R-NSGA-Ⅱ[5]以及光束搜索[18]在ZDT1、ZDT2、ZDT3、DTLZ1、DTLZ2、DTLZ3的GD值；并比較本算法AP-εPSO與SPEA2、NSGA-Ⅱ的SP值。偏好角度值設(shè)為0.05,二維ZDT1、ZDT2、ZDT3測(cè)試函數(shù)的參考點(diǎn)分別為(0.3,0.4)、(0.8,0.6)、(0.4,0.6)。三維DTLZ1、DTLZ2、DTLZ3測(cè)試函數(shù)的參考點(diǎn)分別為(0.5,0.5,0.5)、(0.4,0.7,0.9)、(0.2,0.3,0.7)。

表3示出各算法的GD值。可以看出，AP-εPSO算法的GD值整體上小于其他幾種算法，說(shuō)明收斂性明顯強(qiáng)于其他幾種算法，所求出來(lái)的Pareto邊界比較接近真實(shí)的Pareto邊界。相比其他算法，利用AP-εPSO得出的Pareto解與真實(shí)的Pareto前端的距離也是比較接近的，僅在ZDT2上稍差于光速搜索算法的解。

表3　GD指標(biāo)統(tǒng)計(jì)值

表4示出各種算法的SP值?？梢钥闯?，在ZDT1與DTLZ2 2個(gè)函數(shù)上，AP-εPSO的SP值要劣于SPEA2的。這是因?yàn)楸舅惴ㄔ谇蠼鈫?wèn)題時(shí)引入了決策者的偏好信息，對(duì)Pareto最優(yōu)解進(jìn)行了進(jìn)一步的篩選，使所得出的解都是在決策者的偏好區(qū)域內(nèi)的Pareto最優(yōu)解，最終解的分布會(huì)比較集中。這正是本文所要達(dá)到的一種結(jié)果。

表4　SP指標(biāo)統(tǒng)計(jì)值

3　結(jié)束語(yǔ)

本文將粒子群算法與ε-Pareto支配結(jié)合起來(lái)，采用精英策略將非支配解提出來(lái)組成外部歸檔集，用擁擠度函數(shù)來(lái)控制歸檔集的大小；對(duì)整個(gè)粒子群采取突變操作，增加粒子的多樣性；利用參考點(diǎn)與角度值將決策者提供的偏好信息引入到多目標(biāo)粒子群算法中，根據(jù)與最優(yōu)個(gè)體的角度值大小來(lái)判斷其是位于偏好區(qū)域還是非偏好區(qū)域；最終針對(duì)新個(gè)體與位于歸檔集中個(gè)體所在的不同區(qū)域采取不同的篩選條件來(lái)更新外部歸檔集。與經(jīng)典算法的對(duì)比實(shí)驗(yàn),驗(yàn)證該算法具有可行性。該算法仍存在許多待解決的問(wèn)題，而且在實(shí)際優(yōu)化問(wèn)題中，如何具體確定參考點(diǎn)及角度值仍需要考慮，下一步主要針對(duì)具體的實(shí)際問(wèn)題設(shè)定相應(yīng)的算法。

[1]崔遜學(xué).多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京:國(guó)防工業(yè)出版社,2006.

[2]鄭金華.多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京:科學(xué)出版社, 2007.

[3]鄭向偉,劉弘.多目標(biāo)進(jìn)化算法研究進(jìn)展[J].計(jì)算機(jī)科學(xué),2007,34(7):187.

[4]李艷麗,黃天民,劉雅雅. 一種新型的帶有小生境技術(shù)和精英集策略的多目標(biāo)粒子群算法[J]. 西華大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,35(1):73.

[5]DEB K,PRATAP A,AGARWAL S,et al. A fast and elitist multi-objective genetic algorithm: NSGA-II[J].IEEE Trans on Evolutionary Computation,2002,6(2):182.

[6]KNOWLES J,CORNE D.The pareto archived evolution strategy: a new base line algorithm formulti-objective optimization[C]//Proceedings of the 1999 Congress on Evolutionary Computation Piscataway. NJ:IEEE Press,1999: 98-105.

[7]ZITZLER E, LAUMANNS M, THIELE L. SPEA2: improving the strength pareto evolutionary algorithm[R]. Technical Report,Zurich,Swiss: Swiss Federal Institute of Technology, 2001.

[8]李榮雨,陳慶倩,陳菲爾.改變種群多樣性的雙差異差分進(jìn)化算法[J].運(yùn)籌學(xué)學(xué)報(bào),2017,21(1):444.

[9]KENNEDY J,EBERHART R. Particle swarm optimization[C]//Proceedings of the 1995 IEEE International Conference Oil Neural Networks. Piscataway，NY：IEEE Service Center，1995:1942.

[10]DEB K,MOHAN M,MISHRA S. Evaluating the ε-domination based multi-objective evolutionary algorithm for a quick computation of pareto-optimal solutions[J]. Evolutionary Computation, 2005, 13(4): 501.

[11]麥雄發(fā)，李玲.基于決策者偏好區(qū)域的多目標(biāo)粒子群算法研究[J]．計(jì)算機(jī)應(yīng)用研究，2010，27(4):1301.

[12]DEB K,SUNDAR J,BHASKARA U,et al. Reference point based multi objective optimization using evolutionary algorithm[J]. International Journal of Computational Intelligence Research,2006,2(3):273.

[13]李緯，張興華.一種改進(jìn)的基于Pareto解的多目標(biāo)粒子群算法[J]. 計(jì)算機(jī)仿真,2010，27(5):96.

[14]戴永彬.一種基于綜合引導(dǎo)的偏好多目標(biāo)優(yōu)化算法[J].中南大學(xué)學(xué)報(bào)(自然科學(xué)版),2016，47(9):3072.

[15]鄭金華,謝諄志.關(guān)于如何用角度信息引入決策者偏好的研究[J].電子學(xué)報(bào),2014,42(11):2239.

[16]鄭金華,賴念,郭觀七.多目標(biāo)進(jìn)化算法中基于角度偏好的ε-Pareto 支配策略[J].模式識(shí)別與人工智能,2014，27(6):569.

[17]LAUMANNS M, THIELE L, DEB K, et al.Combining convergence anddiversity in evolutionary multi-objective optimization[J].Evolutionary Computation,2002,10(3):263.

[18]DEB K,KUMAR A.Light beam search based multi-objective optimization using evolutionary algorithms [C]// Proc of the IEEE Congress on Evolutionary Computation. Singapor：IEEE, 2007: 2125-2132.