幾種改進(jìn)的分解類多目標(biāo)進(jìn)化算法及其應(yīng)用.pdf

1、 進(jìn)化算法作為一種群體智能搜索方法在解決多目標(biāo)優(yōu)化問題方面有著很多優(yōu)勢，研究求解多目標(biāo)優(yōu)化問題的進(jìn)化算法已經(jīng)成為進(jìn)化計(jì)算領(lǐng)域的一個(gè)研究熱點(diǎn)。基于分解的多目標(biāo)進(jìn)化算法（MOEA/D）是2007年提出的一類將數(shù)學(xué)規(guī)劃方法與進(jìn)化算法相結(jié)合，求解多目標(biāo)優(yōu)化問題的新穎分解類算法。與其它類多目標(biāo)進(jìn)化算法相比，MOEA/D 在解決復(fù)雜的多目標(biāo)優(yōu)化問題時(shí)具有明顯的優(yōu)勢，但此類方法在求解目標(biāo)函數(shù)個(gè)數(shù)較多的和 Pareto 最優(yōu)解相對較為復(fù)雜的多目標(biāo)優(yōu)化

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

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

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

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

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

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

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

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