基于文化基因算法的多目標優化

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

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

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

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

1 多目標優化問題描述

通常在多目標優化領域被普遍接受的多目標優化問題定義如下［5］。

定義1 一般的多目標優化問題由n 個決策變量、M 個目標函數和K 種約束條件組成，最優化目標如下:

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

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

2 基于粒子群的Memetic 算法

2.1 算法的改進策略

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

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

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

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

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

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

2.2 算法步驟

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

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

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

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

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

第5 步 如果達到指定迭代次數，算法繼續，否則轉向第2 步。

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

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

算法步驟如圖1 所示。

3 仿真實驗

3.1 仿真測試

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

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

圖1 算法步驟

圖2 仿真結果比較

3.2 性能評價指標［8］

1)收斂性能評價指標γ

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

2)分布性能評價指標Δ

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

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

Δ 的值越小表示求得的Pareto 最優解集在目標空間中的象點集分布越均勻。

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

4 結束語

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

［1］申曉寧.基于進化算法的多目標優化方法研究［D］.南京:南京理工大學，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］雷德明，嚴新平.多目標智能優化算法及其應用［M］.北京:科學出版社，2009.

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

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

［8］鄭金華.多目標進化算法及其應用［M］.北京:科學出版社，2007.

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

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