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

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

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

1　相關(guān)概念

1.1　基本概念

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

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)

多目標優(yōu)化問題的一般描述為

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

(3)

1.2　擁擠度函數(shù)

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

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

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

當產(chǎn)生新的子代個體時，通過

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

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

2.1　突變的類型

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

2.2　算法的主要流程

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

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

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

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

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

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

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

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

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

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

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

圖1　算法流程圖

圖2　更新外部歸檔集

2.3　對比評價指標與實驗結(jié)果

2.3.1GD值

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

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

2.3.2SP值

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

式中：

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

(8)

2.3.3實驗結(jié)果

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

表1　測試函數(shù)

表1(續(xù))

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

為驗證算法的分布性與收斂性，對比本算法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測試函數(shù)的參考點分別為(0.3,0.4)、(0.8,0.6)、(0.4,0.6)。三維DTLZ1、DTLZ2、DTLZ3測試函數(shù)的參考點分別為(0.5,0.5,0.5)、(0.4,0.7,0.9)、(0.2,0.3,0.7)。

表3示出各算法的GD值?？梢钥闯?，AP-εPSO算法的GD值整體上小于其他幾種算法，說明收斂性明顯強于其他幾種算法，所求出來的Pareto邊界比較接近真實的Pareto邊界。相比其他算法，利用AP-εPSO得出的Pareto解與真實的Pareto前端的距離也是比較接近的，僅在ZDT2上稍差于光速搜索算法的解。

表3　GD指標統(tǒng)計值

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

表4　SP指標統(tǒng)計值

3　結(jié)束語

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

[1]崔遜學.多目標進化算法及其應(yīng)用[M].北京:國防工業(yè)出版社,2006.

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

[3]鄭向偉,劉弘.多目標進化算法研究進展[J].計算機科學,2007,34(7):187.

[4]李艷麗,黃天民,劉雅雅. 一種新型的帶有小生境技術(shù)和精英集策略的多目標粒子群算法[J]. 西華大學學報(自然科學版),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].運籌學學報,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ū)域的多目標粒子群算法研究[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]李緯，張興華.一種改進的基于Pareto解的多目標粒子群算法[J]. 計算機仿真,2010，27(5):96.

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

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

[16]鄭金華,賴念,郭觀七.多目標進化算法中基于角度偏好的ε-Pareto 支配策略[J].模式識別與人工智能,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.