宋中山，陳建國，鄭波盡

(中南民族大學 計算機科學學院，武漢 430074)

演化算法是建立在自然選擇和遺傳變異理論之上的一種隨機搜索技術[1].雖然用演化算法來解決最優(yōu)化問題有較長的歷史，但是多目標優(yōu)化演化算法(MOEAs)的歷史并不是很長，近年來，關于MOEAs的研究正在不斷地升溫.

目前，在MOEAs的研究中，基于Pareto和精英策略的演化算法占據(jù)了主流位置，其基本模式為：個體生成器策略+文檔策略.在個體生成器策略中本文采用粒子群優(yōu)化算法(PSO)，PSO沒有使用遺傳算法中的交叉及變異操作，而是粒子根據(jù)自己和同伴的歷史行為來動態(tài)的調(diào)整自己的搜索位置.具有簡單，容易實現(xiàn)；需要調(diào)整的參數(shù)少；收斂快速等優(yōu)點.但是其收斂速度快，又容易出現(xiàn)早熟現(xiàn)象.在文檔策略中本文采用快速文檔處理算法----幾何Pareto選擇算法(GPS)[2]，大部分的文檔算法都存在Pareto前沿點個數(shù)和算法時間復雜度之間的沖突問題，這樣很難在有限時間內(nèi)取得足夠多的近似Pareto前沿點，而采用GPS的MOEAs具有以下優(yōu)點：能以概率1收斂到射線Pareto前沿[3]；前沿點分布均勻；前沿點個數(shù)足夠；時間復雜度僅為O(M)(M為目標數(shù)).鑒于以上兩個算法的優(yōu)越性，本文將PSO和GPS相結合來解決多目標優(yōu)化問題，并且將針對多目標優(yōu)化問題中的難點對PSO進行改進.

1 演化算法的特點

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

PSO是一種基于群智能的演化計算技術，該算法于1995年由Eberhart博士和kennedy博士提出[4].

算法的基本思想：初始化一群隨機解作為隨機粒子，然后通過迭代找到最優(yōu)解.在每一次迭代中，粒子通過跟蹤兩個“極值”來更新自己，第一個是粒子本身所找到的最優(yōu)解，稱為個體極值pBest，另一個極值是整個種群目前找到的最優(yōu)解，稱為全局極值gBest.

PSO每次迭代過程中只根據(jù)gBest和pBest來生成新的粒子，這是一個單向流動的過程，即整個的搜索更新過程是跟隨當前最優(yōu)解的過程，而遺傳算法是通過染色體互相共享信息，使整個種群均勻地向最優(yōu)區(qū)域移動.

1.2 幾何Pareto選擇算法

GPS算法是一種基于采樣模式的文檔算法[5].用文檔來保存最優(yōu)解，即獲得了Pareto前沿點的采樣，GPS算法是目前最先進的保存最優(yōu)解的算法.

在GPS算法中，對于M維目標問題算法的總體時間復雜度為O(GMN)+O(MA2)，對于很多的MOEAs算法的時間復雜度，Jensen在文獻[6]中都進行了討論，對于NSGA2算法改進后的時間復雜度為O(GNlogM-1N)，SPEA2在處理二目標問題時為O((N+A)3/2log(N+A))，所以采用GPS的MOEAs具有較高的速度.在空間復雜度上，GPS算法的空間復雜度為O(NM-1)，在二維目標問題時并不比SPEA2和NSGA2等算法高.

2 多目標優(yōu)化PSGPS算法

2.1 算法的基本思想

1)對于M維目標問題，將整個種群劃分為M+1個子種群，前M個子種群中，每個子種群處理一個目標，而第M+1個用于獲取折中解.

2)每個子種群的粒子采用PSO及一定概率的變異和雜交來生成新的粒子.

3)采用GPS來保存目前最優(yōu)粒子.

4)通過迭代2)、3)來獲得最終的近似Pareto前沿.

2.2 算法的難點及其解決方法

在本文中使用3種策略分別處理MOEAs中的極限點的獲取、折中點的獲取和文檔算法.

1)極限點獲取.所謂極限點，就是在某一個目標值上為最優(yōu)，且該極限點為真實Pareto前沿上的點.極限點的獲取對MOEAs非常重要，在于這些極限點刻畫了真實Pareto前沿的邊界，而且其周圍的點常常也是真實Pareto前沿上的折中點.為了解決極限點的問題，本文在PSO算法中加入變異操作，確保從理論上PSO算法能夠找到極限點.

2)折中點的獲取.當PSO算法尋找極限點的時候，由于演化算法在局部最優(yōu)點或者全局最優(yōu)點附近常常會有重復的搜索，而這些點，很可能就是折中點，因此，算法不需要特意去尋找極限點附近的折中點.該假設成立的前提是：PSO所優(yōu)化的各個目標比較復雜.當比較簡單的時候，PSO可能直接就找到最優(yōu)點，而不會在最優(yōu)點附近做密集搜索.在PSO中，加入變異算子，也可以達到在目標值簡單的情形下，獲得較多折中解的目的.此外，為了獲得更好的折中解，算法中加入一個跨子種群的仿射雜交算子.這一算子由于在各個極限點之間進行仿射雜交，因此，多數(shù)情況下，都能得到極限點中間的點，即折中解.在算法中，PSO除搜索M個目標外，還需要搜索一個折中的目標以發(fā)現(xiàn)更好的折中解.

3)文檔算法.以上2個問題都屬于搜索問題.文檔算法則屬于解的保存問題.本文使用GPS算法進行處理.

2.3 算法中各算子的介紹

(1)

2) 變異算子.使用Delta變異算子，假設父體為X1=(x11,x12…,x1n)，隨機選擇一個基因x1j，β為一個小常數(shù)，令：

(2)

種群的劃分策略.本算法中將種群劃分為M+1個子種群，M為目標函數(shù)的個數(shù).每個目標函數(shù)優(yōu)化1個子種群，自定義第M+1個目標優(yōu)化函數(shù)，用其來優(yōu)化所有目標的平均值，并將這個函數(shù)取名為折中函數(shù).用公式(3)表示：

Gi(x)=Fi(x),
Gi+1(x)=(F1(x)+F2(x)+…+Fi(x))/M.

(3)

better()函數(shù)用來比較2個個體的優(yōu)劣.在優(yōu)化最小化問題時，同一個種群中的個體在同一個目標函數(shù)下，如果新個體比舊個體在的函數(shù)值小，則返回true；如果函數(shù)值相同則使用比較兩個點的占優(yōu)關系以防止取得錯誤的極限點；如果優(yōu)化目標為第M+1個目標，則根據(jù)折中函數(shù)進行比較，如果新個體的折中函數(shù)值小于舊個體的折中函數(shù)值，則返回true.

2.4 算法的總體流程

算法的總體流程如下.

算法PSGPS

初始化種群和文檔

While (! Terminate ())

For i=1 to PopSize

采用PSO生成策略生成新的個體tmp

試著采用GPS算法將個體tmp加入到文檔中

If Better (tmp,Indiv[i])then Indiv[i]:=tmp

else以概率為0.5的變異操作生成新的個體tmp2

試著采用GPS算法將個體tmp加入到文檔中

If Better (tmp2,Indiv[i])then Indiv[i]:=tmp2

else 通過子種群的雜交操作生成新個體tmp3

試著采用GPS算法將個體tmp3加入到文檔中

If Better(tmp3,Indiv[i])then Indiv[i]:=tmp3

End for

End While

消除文檔中被占優(yōu)的解

輸出文檔中的非占優(yōu)解

3 實驗及結果分析

為了驗證算法的性能，我們選取了ZDT1、ZDT6、SPH2、KURS(KUR有2個函數(shù)，這里選擇的是其中較難的，為與另一個區(qū)分，在本文中改寫為KURS)、QV這些測試函數(shù)，并將實驗數(shù)據(jù)跟SPEA2、NSGA2、PESA所得的數(shù)據(jù)進行比較，這些對比的數(shù)據(jù)可以從Zitzler的網(wǎng)址上下載到.

為了比較算法的優(yōu)越性，我們引入2個指標S和D來度量超體積的多樣性和近似度.超體積即解構成的空間，它是融合了算法解收斂性、均勻性、和解的個數(shù)的度量尺度，顯然，占優(yōu)的超體積越大，則算法的性能越好.S為超體積的大小，D用來度量超體積的差異.假設要度量算法A和B，S(A)為算法A所得到的解的超體積，D(A+B)為A算法所得解的超體積占優(yōu)B算法所得解的超體積的大小，則D(A+B)=S(A+B)-S(B)，如果要比較D(A+B)和D(B+A)的質(zhì)量則還需要定義一個指標Q，Q用來度量算法A，B所得解之間的占優(yōu)比率，Q(A)表示A算法得到的解在A,B兩個算法共同最優(yōu)解中的占優(yōu)比率.

(4)

(5)

下面列出對于各問題PSGPS算法一次運行及對比算法30次運行的結果.

問題1：QV(維數(shù)為100)，比較結果如圖1所示.

圖1 QV的比較圖

問題2：ZDT1，比較結果如圖2所示.

圖2 ZDT1的比較圖

問題3：ZDT6，比較結果如圖3所示.

圖3 ZDT6的比較圖

問題4：SPH2 (維數(shù)為100)，比較結果如圖4所示.

圖4 SPH2的比較圖

問題5：KURS，比較結果如圖5所示.

圖5 KURS的比較圖

從以上各個問題的對比圖形可以看出本文算法所得的解非常好.經(jīng)過統(tǒng)計分析可知，該算法在求解ZDT1、SPH2問題時所得到的解完全占優(yōu)于其它對比算法的解，即占優(yōu)比為100%，只在求解KURS、QV和ZDT6問題時不能完全占優(yōu).以下將這3個不能夠完全占優(yōu)的問題的各個指標列舉出來，分別為表1，表2，表3.P、C分別表示PSGPS算法和對比算法，其中S(P)、S(C)分別表示本算和對比算法的S指標，D(PC)、D(CP)分別表示D(P+C)和D(C+P).

表1 QV問題的各個對比結果

表2 KURS問題的各個對比結果

表3 ZDT6問題的各個對比結果

經(jīng)計算，上述3個問題的占優(yōu)比(Q測度值)都高于99%.這證明了該算法在結果的近似程度上遠優(yōu)于對比算法.

由于本文算法中的生成策略將種群分為M+1個子種群，自定義了1個目標函數(shù)，即折中函數(shù).在二目標下，對于KURS這類簡單問題，算法收斂速度過快，粒子很快可以收斂到兩個函數(shù)極值點和折中函數(shù)的極值點.雖說種群更新中引入了一定概率的雜交和變異，仍可能出現(xiàn)兩個鄰近目標之間的區(qū)域不能夠充分收斂到Pareto前沿的現(xiàn)象，如圖5中橫坐標為120～140的區(qū)域.經(jīng)過分析，如果我們在原有的M個目標下引入更多的折中函數(shù)，上述現(xiàn)象就會得到解決.

該算法在速度方面也具有良好的性能，在Intel雙核處理器主頻1.86GHz的機器上以單線程運行，時間單位為ms.各個問題的運行時間如表4.

表4 各個問題的運行時間

4 結語

本文受PSO算法和GPS算法的啟發(fā)，提出了一種高效的PSGPS算法.選取5個有代表性的多目標問題進行實驗，結果表明：這個算法比當前的著名SPEA2，PESA，NSGA2等算法都要優(yōu)越.在實驗中，該算法的一次運行生成的解，無論是在數(shù)量上還是在均勻性上，都要比對比算法運行30次生成的解之和要好；在覆蓋完整性上，其它算法在處理QV和KURS問題時都無法實現(xiàn)解的完全覆蓋，而本算法做到了這一點；此外，本算法在時間復雜度上比其它算法要低.

算法在處理二目標時表現(xiàn)了良好的效果，在以后的工作中將希望實現(xiàn)三目標以上問題的解決；算法中采用的是數(shù)組存儲精英解，但是當維數(shù)增加時，該算法需要更多的存儲空間，如果采用其它的一些數(shù)據(jù)結構來存儲精英解，有可能降低存儲的空間；算法在處理QV、KURS和ZDT6問題時存在不能占優(yōu)的解，如何采用更多的折中函數(shù)來使所得解能夠完全占優(yōu)，以上這些問題都有待進一步研究.

[1] Michalewicz.Genetic algorithm + Data structure =evolutionary programs [M].3rd rev and extended.Berlin: Springer-Verlag,1997:372-373.

[2] Zheng B.A highly efficient multi-objective optimization evolutionary algorithm [C]//ICNC.Proceedings-Third International Conference on Natural Computation.Jinan: ICNC,2007: 549-554.

[3] 周育人,閔華清.多目標演化算法的收斂性研究[J].計算機學報,2004,27(10): 1415-1421.

[4] Eberhart R ,Kennedy J.A new optimizer using particle swarm theory[C]//ISMMHS.Proceedings of the Sixth International Symposium on Micro Machine and Human Science.Nagoya:ISMMHS,1995: 39-43.

[5] 鄭波盡.演化優(yōu)化方法研究[D].武漢:武漢大學，2006.

[6] Jensen M T.Reducing the run-time complexity of multi-objective EAs: the NSGA-II and other algorithms[J].Evolutionary Computation,2003,7(5): 503-515.