微粒群進化估值策略在多目標優(yōu)化中的應(yīng)用

微粒群進化估值策略在多目標優(yōu)化中的應(yīng)用

劉彤，孫超利，曾建潮

(太原科技大學工業(yè)與系統(tǒng)工程研究所，太原 030024)

摘要：作為群智能算法，微粒群算法由于在獲得最優(yōu)解集之前需要大量的適應(yīng)值評價，從而阻礙了其在復(fù)雜的多目標優(yōu)化優(yōu)化問題中的應(yīng)用。為了解決該問題，本文將進化估值策略引入到多目標微粒群算法中，用適應(yīng)值估計代替適應(yīng)值實際評價，以減少適應(yīng)值實際計算次數(shù)，從而節(jié)省計算花費。實驗結(jié)果表明引入進化估值策略的多目標微粒群算法可以大大減少適應(yīng)值的評價次數(shù)，而相似度的評價控制機制可提高估值的準確性，從而在減少評價次數(shù)的同時提高算法的優(yōu)化性能。

關(guān)鍵詞：多目標微粒群算法；進化估值策略；相似度；適應(yīng)值評價

收稿日期：2015-03-18

基金項目：國家自然科學基金(61403272)

作者簡介：劉彤(1989-)，女，碩士研究生，主要研究方向為計算智能。

中圖分類號：TP311文獻標志碼：A

多目標優(yōu)化問題(MOP)廣泛存在于科學實踐、工程系統(tǒng)設(shè)計及社會生產(chǎn)的各個領(lǐng)域，其一般形式為：

MinF(X)=[f1(X),f2(X),…,fk(X)]

(1)

其中，X=[x1,x2，…,xn]T為D維決策向量，fi∶RD→R,i=1,2,…,k為第k個目標函數(shù)。多目標優(yōu)化問題的多個目標間往往存在沖突，不同于單目標優(yōu)化問題的單個最優(yōu)解，多目標優(yōu)化問題的最優(yōu)解不唯一，得到的通常為一組均衡解，稱之為Pareto解集。解集中的每個解稱為Pareto解或非劣解，沒有一個解的所有目標好于另一個解，由所有Pareto解的目標函數(shù)值構(gòu)成的目標空間內(nèi)的曲面稱為Pareto前沿或Pareto面。在實際應(yīng)用中，Pareto面使得決策者能夠權(quán)衡不同的目標，從而選擇出其所需的最終解。為此，尋找一種有效的方法以找出盡可能多的目標解受到了學者們越來越多的關(guān)注。

近年來，進化算法和群智能算法的提出為多目標優(yōu)化問題提供了一種新的求解方式。由于他們實現(xiàn)簡單，具有較好的收斂性，且這些算法基于群體優(yōu)化，所獲的是一組非劣解，從而越來越多的應(yīng)用于多目標優(yōu)化問題的求解[1-7]。然而，隨著多目標優(yōu)化問題應(yīng)用領(lǐng)域的擴大，其目標函數(shù)越來越復(fù)雜，導致對解的一次評價需要大量的時間花費，大大阻礙了進化算法和群智能算法在多目標優(yōu)化問題中的應(yīng)用，這是因為無論是進化算法還是群智能算法，它們都是基于種群的迭代優(yōu)化算法，任意一代都需要大量的適應(yīng)值評價。為了進一步擴大進化算法和群智能優(yōu)化算法的應(yīng)用范圍，學者們提出了使用適應(yīng)值計算廉價的估值模型來替代適應(yīng)值計算費事的實際目標函數(shù)計算，從而減少算法的運行時間。Lius VSantana-Quintero等[2]提出了將支持向量機(SVM)引入到多目標微粒群算法中；Zenghui Wang和Yanxia Sun[3]將多目標微粒群算法與BP神經(jīng)網(wǎng)絡(luò)進行結(jié)合；Bryan Glaze[4]等用多個代理模型相結(jié)合有效的解決了直升飛機旋翼的葉片減震問題。適應(yīng)值繼承是一類特殊的估值模型，1995年Smith等[5]第一次提出將適應(yīng)值繼承策略引入遺傳算法中，其概念簡單，實現(xiàn)方便，且保持了結(jié)果的較優(yōu)性。2005年，Margarita Reyes-sierra和 Coello CoelloCarlos A[6]將適應(yīng)值繼承的概念引入到了多目標微粒群算法。2013年，Sun等[7]利用微粒群算法本身進化公式提出了一種進化估值策略，與一般的適應(yīng)值繼承策略不同，該估值策略除使用父代個體信息外，還使用同一代其它個體適應(yīng)值信息來估計當前個體的適應(yīng)值，單目標函數(shù)中的測試結(jié)果表明進化估值策略可以在較少適應(yīng)值評價次數(shù)下獲得問題的較好最優(yōu)解。因此本文將進化估值策略進行擴展，使其能夠應(yīng)用于復(fù)雜多目標優(yōu)化問題的求解中，以減少多目標微粒群算法優(yōu)化的計算花費。

本文首先對一般進化估值策略輔助的微粒群算法進行了簡單介紹。然后對其進行擴展，并引入相似度控制機制以確定估值的個體。隨后，通過對多目標測試函數(shù)的仿真實驗驗證本文提出的估值策略在多目標優(yōu)化問題中的有效性。最后對本文進行總結(jié)和展望。

1進化估值策略輔助的微粒群算法

微粒群算法(Particle Swarm Optimization，PSO)是1995年由美國心理學家KennedyJ與電氣工程師EberhartRC受鳥類的群智能行為啟發(fā)，模擬鳥類覓食過程提出的一種典型的群智能優(yōu)化算法[8-9]。由于其概念簡單、控制參數(shù)少、易于實現(xiàn)且有一定的并行性等優(yōu)點，微粒群算法自提出以來就受到廣泛關(guān)注。

其基本更新公式可表示如下：

vi(t+1)=Vi(t)+c1r1(Pi(t)-Xi(t))+

c2r2(Pg(t)-Xi(t))

(2)

Xi(t+1)=Xi(t)+Vi(t+1)

(3)

其中，c1和c2為兩個常量，分別表示認知系數(shù)和社會系數(shù)。r1和r2是兩個由[0,1]均勻分布的隨機數(shù)組成的對角陣。Pi=(pi1,pi2，…,piD)為粒子i的歷史最優(yōu)位置，Pg=(pi1,pi2，…,piD)為種群歷史最優(yōu)位置。

為解決復(fù)雜單目標優(yōu)化問題，基于式(3)和(4)，Sun等提出了一種新的繼承策略，新個體的適應(yīng)值通過以下公式進行計算：

(4)

其中，

(5)

2進化估值策略輔助的多目標微粒群算法

本文擬將進化估值策略輔助的微粒群算法應(yīng)用于復(fù)雜的多目標優(yōu)化問題中，以進一步擴大微粒群算法的應(yīng)用范圍。

2.1多目標進化估值策略

不同于單目標優(yōu)化問題，多目標優(yōu)化問題得到是一組解，所以在個體進化過程中，其學習的群體最優(yōu)位置往往不一樣，因此，本文在引入虛擬位置時保留了群體歷史最優(yōu)位置，表示為：

Xv(t+1)=Xj(t+1)+(1+χ-χφ1-χφ2)Xi(t)+

(1+χ-χφ1′-χφ2′)Xj(t)+χXi(t-1)+

(6)

相應(yīng)的，目標函數(shù)的估值公式修改為：

k=1,2,…,m

(7)

其中，

(8)

算法1給出了多目標進化估值策略的偽代碼：

Begin

For 當前種群中每個粒子i

fitness(Xi(t+1)).evaluation=0;

fitness(Xi(t+1)).estimation=0;

End For

For 當前種群中每個粒子i

If fitness(Xi(t+1)).evaluation=0 and

fitness(Xi(t+1)).estimation=0 then

實際計算粒子i的適應(yīng)值；

fitness(Xi(t+1)).evaluation=1;

End If

For 除i外的其他粒子k

IfXk(t+1)=Xi(t+1)then

將粒子i的適應(yīng)值和評價及估計標志信息直接賦值給粒子k；

End If

計算粒子k與粒子i間的歐式距離，搜索粒子i距離最近的粒子j；

If fitness(Xj(t+1)).evaluation=0 then

If 以上10個距離均不為0 then

利用式(7)計算粒子j的適應(yīng)值

fi(Xj(t+1))；

If fitness(Xi(t+1)).estimation=1 and

新解支配原解then；

f(Xj(t+1))=fi(Xj(t+1));

End If

End If

End If

End For

更新群體中粒子i的個體歷史最優(yōu)解集并排序；

End For

更新種群歷史最優(yōu)解集；

搜索種群歷史最優(yōu)解集中的估計解并實際計算后與其他解重新比較；

End

需要注意的是，在基于進化估值策略的多目標微粒群算法中，粒子第一次迭代所得最優(yōu)位置對應(yīng)的適應(yīng)值需全部計算，以獲得粒子在第二代適應(yīng)值估值時所用的祖代信息。

2.2相似度評價控制機制

為了保證估值盡可能準確的前提下進一步減少目標函數(shù)的實際計算次數(shù)，與文獻[10]中類似，本文引入相似度評價。對于任意粒子i與粒子j的相似度可由下式得出：

(9)

評價控制機制的作用是選擇當前種群中可以通過估值公式估計適應(yīng)值的粒子，加入相似度的評價控制機制即將多目標進化估值策略偽代碼步驟“計算粒子k與粒子i間的歐式距離”及“找到與粒子i距離最近的粒子j(距離為0的粒子除外)”進行修改為“計算粒子k與粒子i間的相似度”及“找到滿足相似度閾值的粒子j”.

2.3算法實現(xiàn)

算法2給出了本文進化估值策略輔助的多目標微粒群算法的偽代碼：

Begin

設(shè)置參數(shù)，t=0，超立方體初始化種群；

實際計算種群中各粒子適應(yīng)值；

將個體歷史最優(yōu)解集據(jù)小生境擁擠度排序存儲到archive1；

將群體歷史最優(yōu)解集據(jù)擁擠度距離排序存儲到archive2；

While 不滿足停止條件 do

For種群中每個粒子i

從archive1和archive2中分別選出pbesti和gbesti引導粒子i的進化；

更新粒子的速度及位置；

將范圍外的粒子拉回到搜索空間；

Ift=1

實際計算種群中所有粒子的適應(yīng)值；

Else

帶有相似度的多目標進化估值策略；

End If

End For

End While

選擇外部存儲空間內(nèi)非劣解集作為Pareto最優(yōu)集；

End

可以看出，算法中引入了超立方體初始化以提高算法的搜索性能，并設(shè)定了兩個外部存儲空間分別存儲粒子的局部最優(yōu)解集合種群的全局最優(yōu)解集。在粒子進行位置更新前，對每個粒子的局部非劣解根據(jù)小生境[11]擁擠度排序，全局最優(yōu)解根據(jù)擁擠距離[12]排序，分別選取其中較好解對應(yīng)位置進行粒子的位置更新操作。若新位置超出粒子的搜索范圍則在搜索空間內(nèi)隨機產(chǎn)生一個新位置，以提高種群的多樣性。此外，為了減少算法中外部存儲空間計算復(fù)雜度，本文利用基于擁擠度對存儲空間大小進行了限制。

3仿真與分析

為了驗證進化估值策略輔助的多目標微粒群算法的有效性，本文在5個2目標標準測試函數(shù)(ZDT1，ZDT2，ZDT3，ZDT4和ZDT6)[13]和2個3目標標準測試函數(shù)(DTLZ2以及DTLZ6)[14]上進行了測試，并和多目標遺傳算法，多目標微粒群算法在趨近度(Generation Distance，GD)[15]，分布性(Spacing，SP)[16]和錯誤率(Error Rate，ER)[15]上進行了對比和分析。

實驗中測試函數(shù)的參數(shù)設(shè)置如表1.

微粒群算法中種群大小為100，認知系數(shù)和社會系數(shù)c1=c2=2.05，收斂因子χ=0.798，程序獨立運行30次，外部存儲空間大小設(shè)置為100.ZDT1到ZDT6其每次運行最大迭代數(shù)為100，DTLZ2和DTLZ6的最大迭代次數(shù)為200.

表2給出了不同算法在這些測試函數(shù)上的對比結(jié)果。其中“Evaluated times”表示算法迭代100次適應(yīng)值實際計算次數(shù)即適應(yīng)值的評價次數(shù)。

表1　測試函數(shù)相應(yīng)參數(shù)

表2　多目標進化估值算法的對比實驗結(jié)果

(b)ZDT2結(jié)果對比

(c)ZDT3結(jié)果對比

(d)ZDT4結(jié)果對比

(e)ZDT6結(jié)果對比

(f)DTLZ2結(jié)果對比

(g)DTLZ6結(jié)果對比

由表2可以看出，與NSGAⅡ和MOPSO相比，在相同迭代次數(shù)下，增加了估值策略的EMOPSO和SEMOPSO的適應(yīng)值評價次數(shù)明顯減少。從錯誤率和趨近度來看，本文的SEMOPSO算法除了ZDT4均獲得了比其它算法更好的結(jié)果。分析其原因，ZDT4存在219個局部極值，而微粒群算法本身存在易早熟收斂的問題，因此在該問題上微粒群算法所求的解集與真實Pareto解集存在的差異較大。另一方面，具有估值策略的微粒群算法比無估值策略的微粒群算法具有更好的分布性。

為了更詳細的查看算法優(yōu)化過程中非劣解集的變化，圖1給出了NSGAⅡ，MOPSO，EMOPSO和SEMOPSO四種算法對ZDT函數(shù)和DTLZ函數(shù)優(yōu)化過程中每次迭代所得非劣解集各項評價標準在適應(yīng)值實際計算次數(shù)下的變化曲線，以及評價次數(shù)隨迭代次數(shù)變化曲線。由于各算法對函數(shù)ZDT4和DTLZ2函數(shù)優(yōu)化所得最優(yōu)解集錯誤率均為1，故圖中未給出兩函數(shù)錯誤率變化曲線。

由圖1可知，進化估值策略的引入在算法的運行初期就有效的影響了非劣解集，尤其是當加入相似度的評價控制機制，函數(shù)的收斂曲線均在評價次數(shù)為1 000時即超過其他算法迅速收斂，最終趨于平穩(wěn)。在對搜索空間單一的ZDT1和ZDT2優(yōu)化時，EMOPSO所得非劣解集的分布性隨著適應(yīng)值評價次數(shù)的增加迅速減小，并很快超過其他算法并逐漸趨于平穩(wěn)，然而其收斂性變化相對平緩且最終比SEMOPSO差。說明了在一些多目標優(yōu)化問題中，解集分布性的提高通常會減慢算法的收斂速度造成解的質(zhì)量與收斂速度間的沖突[17]。由圖中各函數(shù)適應(yīng)值評價次數(shù)隨迭代次數(shù)變化曲線可知， 在優(yōu)化初期三種算法的適應(yīng)值估值次數(shù)均隨著迭代次數(shù)以一定比值線性增加，SEMOPSO和MOPSO及NSGAⅡ的稍小一點，而EMOPSO的比值則遠小于其他算法。在隨后的優(yōu)化過程中EMOPSO保持線性增長的趨勢，而SEMOPSO的適應(yīng)值曲線逐漸趨于平緩，甚至如ZDT6的適應(yīng)值評價次數(shù)變化曲線所示，最終超過EMOPSO的變化曲線，得到最少的適應(yīng)值評價次數(shù)。證實了，進化估值策略可以有效減少適應(yīng)值實際評價次數(shù)，相似度可以提高適應(yīng)值估值準確性的推斷。

圖1　NSGAⅡ，MOPSO，EMOPSO，SEMOPSO對測試函數(shù)優(yōu)化所得最優(yōu)解集各評價標準變化曲線

本文所選ZDT函數(shù)包含了一般兩目標優(yōu)化問題的所有特性，兩個三目標DTLZ函數(shù)分別有連續(xù)的最優(yōu)解集前沿和離散的最優(yōu)解集前沿，較全面的測試了本文所提出算法的性能。由以上四種多目標函數(shù)所得最優(yōu)解集的各個性能評價指標的對比實驗結(jié)果可以得到以下結(jié)論：(1)在多目標的微粒群算法中，進化估值策略的引入可以明顯減少適應(yīng)值的評價次數(shù)。在用微粒群算法解決多目標的計算費時問題時，引入進化估值策略可以通過估值代替適應(yīng)值評價，減少適應(yīng)值評價次數(shù)從而減少算法的優(yōu)化計算總花費。(2)相似度的評價控制機制可以提高估值的準確性，明顯的提高算法的優(yōu)化性能。加入相似度的進化估值策略的引入可以使算法在減少評價次數(shù)的同時提高優(yōu)化性能，避免了估值的不準確性帶來的影響。(3)進化估值策略在算法的整個優(yōu)化過程中都發(fā)揮著作用，并且無論對于兩目標的優(yōu)化問題，還是多目標的優(yōu)化問題，進化估值策略的引入都可以有效提高算法的性能減少算法的適應(yīng)值評價次數(shù)。

4結(jié)束語

本文提出了一種多目標微粒群算法的進化估值策略，通過在多目標的微粒群算法中引入進化估值策略，以估值代替適應(yīng)值的評價從而減少適應(yīng)值的評價次數(shù)。進化估值策略中通過微粒群算法的更新公式推導所得估計公式，利用粒子的祖代父代以及同代已知適應(yīng)值的粒子估計其適應(yīng)值，代替目標函數(shù)的適應(yīng)值計算。在進化估值策略中引入相似度的評價控制機制，利用粒子間的相似度選擇所要估計的粒子。仿真實驗表明進化估值策略的引入明顯減少了算法優(yōu)化過程中的適應(yīng)值評價次數(shù)，而且在一定程度上增加了種群的多樣性。相似度的評價控制機制的引入提高了估值的準確性，使進化估值策略在減少算法適應(yīng)值評價次數(shù)的同時提高了算法的性能。多目標微粒群算法中進化估值策略的加入是有效可行的。

參考文獻：

[1]蘇長慧，夏桂梅.基于改進微粒群算法的單點信控交叉口配時優(yōu)化[J].太原科技大學學報，2014，35(3)：198-201.

[2]SANTANA-QUINTEROLUIS V，COELLO COELLO CARLOS A，JESUS MOISES OSORIO VELAZQUEZ，et al.Surrogate-based Multi-objective Particle Swarm Optimization[C]∥Swarm Intelligence Symposium，St.LOuis，MO，2008：1-8.

[3]ZENGHUI WANG，YANXIA SUN.Fully Connected Muti-Objective Particle SwarmOptimizer Based on Neural Network[C]∥ICIC 2011，Springer-Verlag Berlin Heidelberg，2011：170-177.

[4]BRYAN GLAZ，TUSHAR GOEL，LI LIU，et al.Friedmann and Raphael T.Haftka.Multiple-Surrogate Approach to Helicopter Rotor Blade Vibration Reduction[J].Aiaa Journal，2009，47(1)：271-282.

[5]SMITH R E，DIKE B A，STEGMANN S A.Fitness inheritance in genetic algorithm[C]∥ACM Symposium on Applied Computing，NY，USA，1995：345-350.

[6]MARGARITA REYES-SIERRA ，COELLO COELLOCARLOS A.Fitness inheritance inmulti-objective particle swarm optimization[C]∥Swarm Intelligence Symposium，SIS 2005，Palathingal，USA，2005：116-123.

[7]SUN C，ZENG J，PAN J，et al.A new fitness estimation strategy for particle swarm optimization[J].Information Sciences，2013，221：355-370.

[8]KENNEDY J，EBERHARD R C.Particle Swarm Optimization[C]∥Proceeding of the IEEE International Conference on Neural Networks，Perth，Australia，1995：1942-1948.

[9]EBERHART R，KENNEDY J.A new optimizer using particle swarm theory[C]∥Proceeding of the Sixth International Symposium on Micro Machine and HumanScience，Nagoya，Japan，1995：39-43.

[10]SUN C，ZENG J，PAN J，et al.Similarity-based evolution control for fitness estimation in particle swarm optimization[C].IEEE Symposium on Computational Intelligence in Dynamic and Uncertain Environment(CIDUE)，2013：1-8.

[11]MARGARITA REYES-SIERRA，COELLO COELLOCARLOS A.Multi-objective Particle SwarmOptimizes：A Survey of the State-of- the-Art [J].International Journal of Computational Intelligence Research，2006，2(3)：287-308.

[12]DEB K，AGRAWAL S，MEYARIVAN T.A Fast Elitist NonDominatedSorting Genetic Algorithm for Multi-Objective Optimization：NSGA-II[C]∥Proceedings of Parallel Problem Solving from Nature - PPSN VI，Paris，England，2000：849-858.

[13]ECKART ZITZLER，KALYANMOY DEB，LOTHAR THIELE.Comparison of MultiobjectiveEvolutionary Algorithms：Empirical Results[C]//Evolutionary Computation，SanDiego，USA，2000，8(2)：173-195.

[14]DEB K，THIELE L，LAUMANNS M，et al.Scalable multi-objective optimization test problems[C]∥Proceedings of the Congress on Evolutionary Computation，Honolulu，USA，2002：825-830.

[15]VAN VELDHUIZEN DA，LAMONT G B.Multiobjective evolutionary algorithm testsuites[C]∥Proceedings of the 1999 ACM Symposium on Applied Computing，Texas，USA，1999：351-357.

[16]TAO ZHANG，TIESONG HU，YUE ZHENG，et al.An Improved Particle Swarm Optimization for Solving Bilevel Multiobjective Programming Problem[J].Journal of Applied Mathematics，2012，30：1-13.

[17]YEN G G，LU H.Dynamic multiobjective evolutionary algorithm：Adaptive cell-based rank and density estimation[J].IEEE Transaction on Evolutionary Computation，2003，7(3)：253-274.

Fitness Estimation Strategy Assisted with Particle Swarm Optimization for

Complicated Multi-objective Optimization Problem

LIU Tong，SUN Chao-li，ZENG Jian-chao

(Complex System and Computational Intelligence Laboratory，Taiyuan University of Science and Technology，

Taiyuan 030024，China)

Abstract：As a swarm intelligence algorithm，particle swarm optimization needs a lot of fitness evaluation before locating near to global optima， which impedes it to be applied in the complex multi-objective problems. In order to

solve the problem，an evolutionary fitness estimation strategy is proposed，in which the real fitness evaluation will be replaced by fitness approximation，so that the number of real computationally expensive fitness evaluation will be reduced and the computation expense will be correspondingly saved.The experimental results showed that evolutionary fitness estimation strategy assisted with multi-objective particle swarm optimization can reduce the times of fitness evaluation，and evolutionary fitness estimation strategy with similarity can improve the correctness of fitness approximation so as to improve the optimization performance and reduce the times of fitness evaluation.

Key words：multi-objective particle swarm optimization，fitness estimation strategy，similarity，fitness evaluation