幾種改進的分解類多目標進化算法及其應用.pdf

1、 進化算法作為一種群體智能搜索方法在解決多目標優(yōu)化問題方面有著很多優(yōu)勢，研究求解多目標優(yōu)化問題的進化算法已經(jīng)成為進化計算領域的一個研究熱點?；诜纸獾亩嗄繕诉M化算法（MOEA/D）是2007年提出的一類將數(shù)學規(guī)劃方法與進化算法相結合，求解多目標優(yōu)化問題的新穎分解類算法。與其它類多目標進化算法相比，MOEA/D 在解決復雜的多目標優(yōu)化問題時具有明顯的優(yōu)勢，但此類方法在求解目標函數(shù)個數(shù)較多的和 Pareto 最優(yōu)解相對較為復雜的多目標優(yōu)化

2、問題時還存在求解質(zhì)量不夠高、收斂速度慢等問題。因此，改進 MOEA/D，研究更為高效的分解類多目標進化算法具有重要的理論意義和潛在的應用價值。
本文旨在通過對MOEA/D的深入探索和研究，針對其在解決多目標優(yōu)化問題中存在的不足，提出幾種改進策略，設計幾種改進的分解類多目標進化算法，并進行相應的數(shù)值實驗分析。論文的主要研究成果包括以下幾個方面：
1. 為更好地求解目標函數(shù)個數(shù)較多的多目標優(yōu)化問題，將均勻設計的思

3、想應用到MOEA/D所分解的各個子問題的權向量設置中，提出了基于均勻設計的分解類多目標進化算法（UMOEA/D）。采用均勻設計方法設置權向量，相較于MOEA/D中設置權向量所采用的單純形格子點設計，權向量分布更均勻，也減少了其在邊界上的分布，并且種群的規(guī)模不會隨著目標個數(shù)的增加而呈非線性增長，種群大小可以自由彈性設置，這也突破了MOEA/D在解決一些目標函數(shù)個數(shù)較多的多目標優(yōu)化問題時所受到的一些限制。對三組對應目標個數(shù)分別為3、4和5的

4、6個維數(shù)可擴展的多目標優(yōu)化問題進行了測試，實驗結果表明， UMOEA/D 表現(xiàn)優(yōu)于MOEA/D與NSGA-II，尤其是對于目標個數(shù)較多的優(yōu)化問題和具有復雜Pareto最優(yōu)解集（PS）的多目標優(yōu)化問題。實驗結果還表明，UMOEA/D 運行速度要明顯快于NSGA-II。
2. 為加快 MOEA/D 的收斂速度，將簡化二次逼近（SQA）作為局部搜索算子，融入到MOEA/D中，提出了一種基于簡化二次逼近的分解類多目標進化算法（MO

5、EA/D-SQA）。SQA 是一種簡單有效的直接搜索方法，它不需要導數(shù)信息，在優(yōu)化問題中很方便使用。并且作為一種簡化的三點二次逼近，它的模型的建立只需要三個點，計算量小，還有效地利用了已求得的目標函數(shù)信息。因此，SQA很適合作為啟發(fā)式局部搜索算子插入到MOEA/D中，在計算量增加不多的情況下，提高MOEA/D的性能。13個無約束的CEC 2009標準測試函數(shù)的仿真結果表明了該算法的有效性。數(shù)值實驗結果還表明，與MOEA/D和當前其它一些

6、優(yōu)秀的多目標進化算法相比，MOEA/D-SQA收斂速度快，解的質(zhì)量高。
3. 提出了基于均勻設計和簡化二次逼近的分解類多目標進化算法（ UMODE/D ）。UMODE/D 對 MOEA/D 的新版本，即基于 DE 的 MOEA/D （MOEA/D-DE）從兩方面進行了改進：(1)采用均勻設計的方法設置MOEA/D-DE所分解的各個子問題的權向量，使算法在初始階段就可以均勻地搜索所有區(qū)域，提高求得Pareto最優(yōu)解的可能性；

7、(2)采用SQA對MOEA/D-DE所分解的各個單目標子問題進行局部搜索，以加快算法的收斂速度，提高解的精度。對 9 個具有復雜 Pareto 最優(yōu)解集（PS）的多目標優(yōu)化問題進行測試，實驗仿真結果證明了該算法的有效性，數(shù)值實驗結果還表明，UMODE/D表現(xiàn)優(yōu)于MOEA/D-DE和NSGA-II。另外，兩組獨立的實驗分別證明了均勻設計和SQA局部搜索兩種改進策略對解決此類具有復雜PS的多目標優(yōu)化問題的有效性。最后，對13個無約束的CEC

8、 2009標準函數(shù)進行了測試，數(shù)值實驗結果表明UMODE/D表現(xiàn)明顯優(yōu)于其它算法。
4. 將UMOEA/D用于求解多目標0-1背包問題。0-1背包問題是典型的帶非負系數(shù)的0-1線性整數(shù)規(guī)劃問題，它屬于離散優(yōu)化問題的范疇，與連續(xù)多目標優(yōu)化問題相比，離散多目標優(yōu)化問題的求解比較困難。將 UMOEA/D 用于解決 2-4 個包的多目標 0-1 背包問題。仿真結果表明，在解分布的均勻性和寬廣性上， UMOEA/D的表現(xiàn)要明顯優(yōu)于算

9、法NSGA-II、SPEA2和PESA，UMOEA/D在解決此類離散多目標優(yōu)化問題時是有效的。
5. 將 UMODE/D 用于具有多種方向圖的唯相位可重構陣列天線優(yōu)化設計。UMODE/D 將具有多種方向圖的可重構直線陣優(yōu)化設計表示為一個多目標優(yōu)化問題，實現(xiàn)了可重構直線陣優(yōu)化設計的并行化。在實際應用中，決策者可根據(jù)各種狀態(tài)方向圖的權重偏好，在算法輸出的 Pareto 解集中選擇一個與該組權重偏好值相對應的Pareto解（即設