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

劉彤，孫超利，曾建潮

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

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

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

收稿日期：2015-03-18

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

作者簡介：劉彤(1989-)，女，碩士研究生，主要研究方向?yàn)橛嬎阒悄堋?/p>

中圖分類號：TP311文獻(xiàn)標(biāo)志碼：A

多目標(biāo)優(yōu)化問題(MOP)廣泛存在于科學(xué)實(shí)踐、工程系統(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個目標(biāo)函數(shù)。多目標(biāo)優(yōu)化問題的多個目標(biāo)間往往存在沖突，不同于單目標(biāo)優(yōu)化問題的單個最優(yōu)解，多目標(biāo)優(yōu)化問題的最優(yōu)解不唯一，得到的通常為一組均衡解，稱之為Pareto解集。解集中的每個解稱為Pareto解或非劣解，沒有一個解的所有目標(biāo)好于另一個解，由所有Pareto解的目標(biāo)函數(shù)值構(gòu)成的目標(biāo)空間內(nèi)的曲面稱為Pareto前沿或Pareto面。在實(shí)際應(yīng)用中，Pareto面使得決策者能夠權(quán)衡不同的目標(biāo)，從而選擇出其所需的最終解。為此，尋找一種有效的方法以找出盡可能多的目標(biāo)解受到了學(xué)者們越來越多的關(guān)注。

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

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

1進(jìn)化估值策略輔助的微粒群算法

微粒群算法(Particle Swarm Optimization，PSO)是1995年由美國心理學(xué)家KennedyJ與電氣工程師EberhartRC受鳥類的群智能行為啟發(fā)，模擬鳥類覓食過程提出的一種典型的群智能優(yōu)化算法[8-9]。由于其概念簡單、控制參數(shù)少、易于實(shí)現(xiàn)且有一定的并行性等優(yōu)點(diǎn)，微粒群算法自提出以來就受到廣泛關(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為兩個常量，分別表示認(rèn)知系數(shù)和社會系數(shù)。r1和r2是兩個由[0,1]均勻分布的隨機(jī)數(shù)組成的對角陣。Pi=(pi1,pi2，…,piD)為粒子i的歷史最優(yōu)位置，Pg=(pi1,pi2，…,piD)為種群歷史最優(yōu)位置。

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

(4)

其中，

(5)

2進(jìn)化估值策略輔助的多目標(biāo)微粒群算法

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

2.1多目標(biāo)進(jìn)化估值策略

不同于單目標(biāo)優(yōu)化問題，多目標(biāo)優(yōu)化問題得到是一組解，所以在個體進(jìn)化過程中，其學(xué)習(xí)的群體最優(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)的，目標(biāo)函數(shù)的估值公式修改為：

k=1,2,…,m

(7)

其中，

(8)

算法1給出了多目標(biāo)進(jìn)化估值策略的偽代碼：

Begin

For 當(dāng)前種群中每個粒子i

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

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

End For

For 當(dāng)前種群中每個粒子i

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

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

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

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

End If

For 除i外的其他粒子k

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

將粒子i的適應(yīng)值和評價及估計標(biāo)志信息直接賦值給粒子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)解集中的估計解并實(shí)際計算后與其他解重新比較；

End

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

2.2相似度評價控制機(jī)制

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

(9)

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

2.3算法實(shí)現(xiàn)

算法2給出了本文進(jìn)化估值策略輔助的多目標(biāo)微粒群算法的偽代碼：

Begin

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

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

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

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

While 不滿足停止條件 do

For種群中每個粒子i

從archive1和archive2中分別選出pbesti和gbesti引導(dǎo)粒子i的進(jìn)化；

更新粒子的速度及位置；

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

Ift=1

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

Else

帶有相似度的多目標(biāo)進(jìn)化估值策略；

End If

End For

End While

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

End

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

3仿真與分析

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

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

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

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

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

表2　多目標(biāo)進(jìn)化估值算法的對比實(shí)驗(yàn)結(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個局部極值，而微粒群算法本身存在易早熟收斂的問題，因此在該問題上微粒群算法所求的解集與真實(shí)Pareto解集存在的差異較大。另一方面，具有估值策略的微粒群算法比無估值策略的微粒群算法具有更好的分布性。

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

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

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

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

4結(jié)束語

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

參考文獻(xiàn)：

[1]蘇長慧，夏桂梅.基于改進(jìn)微粒群算法的單點(diǎn)信控交叉口配時優(yōu)化[J].太原科技大學(xué)學(xué)報，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