基于文化基因算法的多目標(biāo)優(yōu)化

溫 攀，王社偉，陶 軍，楊尚君

(空軍航空大學(xué)，長春 130022)

在科研和實踐中，經(jīng)常會遇到需要使多個相互沖突的目標(biāo)均盡可能最佳的優(yōu)化問題，這類問題一般被稱為多目標(biāo)優(yōu)化問題(multi-objective optimization problem，MOP)。大多數(shù)工程和科學(xué)問題都是多目標(biāo)優(yōu)化問題，存在多個彼此沖突的目標(biāo)，如何獲取這些問題的最優(yōu)解，一直是學(xué)術(shù)界和工程界關(guān)注的焦點問題［1］。

1989年，Moscato 在Moscato P.On evoltion，search，optimization，genetic algorithms and martial arts:towards Memetic algorithms 中，首次把memetic 這一術(shù)語引入計算機科學(xué)領(lǐng)域。文化基因算法(memetic algorithm)是一種較寬松的優(yōu)化算法框架，采用不同的搜索策略可構(gòu)成不同的Memetic 算法。本文采用粒子群算法為全局搜索策略，模擬退火算法為局部搜索策略，針對粒子群容易陷入局部最優(yōu)而進行改進，保留粒子群算法快速收斂的特點，融入模擬退火算法全局性好的特點。通過將多目標(biāo)優(yōu)化AI-NN--PR 問題的求解仿真結(jié)果進行比較表明，與NSGA-Ⅱ相比，本文提出的Memetic 算法能得到更好的優(yōu)化結(jié)果。

1 多目標(biāo)優(yōu)化問題描述

通常在多目標(biāo)優(yōu)化領(lǐng)域被普遍接受的多目標(biāo)優(yōu)化問題定義如下［5］。

定義1 一般的多目標(biāo)優(yōu)化問題由n 個決策變量、M 個目標(biāo)函數(shù)和K 種約束條件組成，最優(yōu)化目標(biāo)如下:

其中:x=(x1，x2…，xn)T是n維向量，稱x 為決策向量;x 所在的空間為決策空間En;f1(x)，…，fm(x)稱為目標(biāo)函數(shù);m維向量(f1(x)，…，fm(x))所在的空間稱為目標(biāo)空間Em;gi(x)，hk(x)為約束函數(shù)。

在單目標(biāo)優(yōu)化中，可行集中的解可根據(jù)目標(biāo)函數(shù)的優(yōu)劣關(guān)系進行排列，最終得到1 個全局最優(yōu)解。但在MOP 中，可行集中的解對應(yīng)多個目標(biāo)函數(shù)，很難對可行域中的解進行優(yōu)劣關(guān)系排列，因此不能像單目標(biāo)優(yōu)化中一樣得出1 個全局最優(yōu)解。針對該問題，法國經(jīng)濟學(xué)家V.Pareto 提出了Pareto 的最優(yōu)的概念［6］，所有Pareto 最優(yōu)解對應(yīng)的目標(biāo)函數(shù)值所形成的區(qū)域稱為Pareto 最優(yōu)前端，求解多目標(biāo)優(yōu)化問題的目的就是盡可能多地獲取問題的Pareto 最優(yōu)解。

2 基于粒子群的Memetic 算法

2.1 算法的改進策略

Memetic 算法主要根據(jù)待優(yōu)化問題的性質(zhì)來選擇適當(dāng)?shù)娜趾途植克阉鞣椒?。粒子群算法比較適合于連續(xù)問題，而且具有比遺傳算法更高的執(zhí)行效率。模擬退火算法的并行技術(shù)能大幅度改進系統(tǒng)性能，加大信息吞吐量和提高運算速度;求解不同的非線性問題，對不可微甚至不連續(xù)的函數(shù)優(yōu)化，能以較大概率求得全局最優(yōu)解，具有較強的魯棒性、全局收斂性、隱含并行性以及廣泛的適應(yīng)性，并且能處理不同類型的優(yōu)化設(shè)計變量(離散的、連續(xù)的和混合型的)，不需要任何輔助信息，對目標(biāo)函數(shù)和約束函數(shù)沒有任何要求。本文采用改進粒子群作為全局搜索策略，模擬退火作為局部搜索策略，來驗證該組合的Memetic 算法對多無人機任務(wù)分配的有效性。

根據(jù)以上特點對算法做出如下改進。文化基因算法主要進行的是全局搜索和局部搜索2 個步驟，下面將具體說明。

1)采用粒子群算法作為全局搜索策略，以粒子群的更新機制作為進化的機制。

2)以模擬退火算法作為局部搜索策略，在粒子搜尋到極值的同時對極值的周圍進行局部搜索，提高解的精確性。同時對粒子群進化后的適應(yīng)度值按Metropolis 準(zhǔn)則接受優(yōu)化解的同時概率接受惡化解。

3)在全局搜索中引入交叉和變異操作，產(chǎn)生新的粒子，并對新的粒子進行搜索，幫助跳出局部最優(yōu)。

4)借鑒粒子群尋優(yōu)思想，在每一迭代過程中保留粒子個體的歷史最優(yōu)解和種群的全局最優(yōu)解，以便交叉和變異的個體在下1 次搜索中依然朝著最優(yōu)的方向?qū)ふ?，保證算法的快速性。

2.2 算法步驟

綜上所述，文化基因算法的主要步驟如下:

第1 步 初始化算法參數(shù)(包括種群數(shù)量n、粒子位置x和速度v，各粒子的適應(yīng)度d，初始溫度T，迭代次數(shù)L 等)。

第2 步 計算各粒子的適應(yīng)度，記錄個體極值pbest和群體極值gbest。

第3 步 應(yīng)用粒子群算法進行全局搜索，將種群中各粒子個體按照粒子群更新機制更新位置。記錄每次迭代產(chǎn)生的個體極值pbest和群體極值gbest。

第4 步 對每次迭代產(chǎn)生的解S1產(chǎn)生隨機擾動生成新解S2，對新解S2進行模擬退火搜索。

第5 步 如果達(dá)到指定迭代次數(shù)，算法繼續(xù)，否則轉(zhuǎn)向第2 步。

第6 步 隨機選取粒子個體與個體極值pbest和群體極值gbest分別進行交叉操作，個體極值和群體極值自身進行變異操作，產(chǎn)生新的粒子ωi，并對新的粒子進行搜索。

第7 步 如果達(dá)到最大迭代次數(shù)或是搜索到滿足要求的解，則算法停止并輸出結(jié)果，否則將返回第3 步。

算法步驟如圖1 所示。

3 仿真實驗

3.1 仿真測試

為了驗證Memetic 算法解決多目標(biāo)優(yōu)化問題的快速性、有效性以及Pareto 解的分布性能，將該算法與多目標(biāo)進化算法SPEA2 和NSGA-Ⅱ算法［5］進行對比分析。

測試實驗中，Memetic 算法主要參數(shù)設(shè)置為:粒子群種群n=50，迭代次數(shù)L=500，產(chǎn)生游蕩者次數(shù)S=4，適應(yīng)度函數(shù)權(quán)值a=0.3，b =0.3，c =0.4。NSGA -Ⅱ算法參數(shù)設(shè)置為:與Memetic 算法迭代次數(shù)相同，n = L* S =500，交叉概率0.9，變異概率0.1，SPEA2 進化代數(shù)為500，每個算法獨立運行20 次，從中選取1 次最好的結(jié)果進行比較，實驗結(jié)果見圖2。

圖1 算法步驟

圖2 仿真結(jié)果比較

3.2 性能評價指標(biāo)［8］

1)收斂性能評價指標(biāo)γ

收斂性能評價指標(biāo)γ 表示所求解與問題的真實Pareto最優(yōu)解的逼近程度，其計算公式為

2)分布性能評價指標(biāo)Δ

分布性能評價指標(biāo)Δ 是通過度量多目標(biāo)優(yōu)化算法求得的Pareto 最優(yōu)解集中的解在目標(biāo)空間中象點分布的均勻程度來評價算法分布性能的。

進行分布均勻程度度量時，首先將這些點按其中1 個目標(biāo)值的大小進行排列，然后分別計算其中的2 個邊界點到全局Pareto 前沿面的2 個邊界點的歐幾里德距離de1和de2，以及每兩相鄰點之間的歐幾里德距離di，i =1，2，…，l -1 和這些距離的平均值ˉd，最后再按下式進行計算

Δ 的值越小表示求得的Pareto 最優(yōu)解集在目標(biāo)空間中的象點集分布越均勻。

從仿真圖可以看出，改進后的多目標(biāo)優(yōu)化文化基因算法具有很好的搜索最優(yōu)解的能力和求解精度。

4 結(jié)束語

本文將粒子群算法進行有效改進作為全局搜索，多目標(biāo)模擬退火作為局部搜索，保持了粒子群算法收斂速度快和模擬退火算法獲取全部最優(yōu)值的能力，并根據(jù)非劣解的擁擠度決定最優(yōu)值的選取，使得求得的非劣解集具有良好的分布性和求解精度。通過與NSGA -Ⅱ算法和SPEA2 算法進行仿真對比表明，本文算法在解決多目標(biāo)優(yōu)化問題上能取得更好的結(jié)果。

［1］申曉寧.基于進化算法的多目標(biāo)優(yōu)化方法研究［D］.南京:南京理工大學(xué)，2008.

［2］Zitzler E，Deb K，Thiele L. Comparison of multi-objective evolutionary algorithms:empirical results［J］. Evolutionary Computation，2000，8(2):173-195.

［3］Deb K，Agrawal S，Pratap A，et al.A fast and elitist multiobjective genetic algorithms:NSGAⅡ［J］.IEEE Transactions on Evolutionary Computation，2002，6(2):182-197.

［4］Deb K.Multi-objective genetic algorithms:Problem difficulties and construction of test problems［J］. Evolutionary Computation，1999，7(3):205-230.

［5］雷德明，嚴(yán)新平.多目標(biāo)智能優(yōu)化算法及其應(yīng)用［M］.北京:科學(xué)出版社，2009.

［6］Pareto V. Cours Deconmie Politique［M］. Lausance:F.Rouge，1986.

［7］梁艷春，吳春國，時小虎，等.群智能優(yōu)化算法理論與應(yīng)用［M］.北京:科學(xué)出版社，2009.

［8］鄭金華.多目標(biāo)進化算法及其應(yīng)用［M］.北京:科學(xué)出版社，2007.

［9］劉漫丹. 文化基因算法(Memetic algorithm)研究進展［J］.自動化技術(shù)與應(yīng)用，2007，26(11):1-4.

［10］郭輝，徐浩軍，谷向東，等. 基于改進粒子群算法的協(xié)同多目標(biāo)攻擊空戰(zhàn)決策［J］.火力與指揮控制，2011(6):49-51.