多目標進化算法研究.pdf

1、現實世界的很多優(yōu)化問題都是由多個互相作用且互相沖突的目標組成的，它的最優(yōu)解不是一個解，而是一組均衡解，這組解被稱為Pareto最優(yōu)解集。進化算法作為一種群體智能搜索方法十分適合用來求解多目標優(yōu)化問題。從20世紀80年代中期開始，進化算法就被應用于求解多目標優(yōu)化問題。近年來涌現出大量的多目標進化算法，其中一些已成功應用到工程實踐中，進化多目標優(yōu)化也因此成為目前進化計算和多目標優(yōu)化領域的一個研究熱點。多目標0/l背包問題是經典的組合優(yōu)化問題

2、，具有重要的理論研究和工程應用價值，并且常常被用來測試多目標進化算法的性能。
　　 本文旨在通過對多目標進化算法進行深入的探索和研究，針對多目標0/1背包問題設計高效的求解策略，并進行相應的實驗和理論分析。本論文的研究內容主要包括以下幾個方面：
　　 (1)針對多目標0/1背包問題，提出了兩種新的加權修復策略。自Zitzler等人提出SPEA算法以來，多目標進化算法被廣泛地用于求解多目標0/1背包問題。多目標0/1背包問

3、題必須滿足容量約束，然而進化算法在求解過程中會產生超出容量的不可行解。最直接最有效的方法之一是通過修復操作將不可行解變成可行解，而目前最常用的基于最大化利率的修復策略并沒有全面考慮物品對各個包的影響。因此，本文提出了兩種新的加權修復策略，分別基于背包容量和個體約束違反程度。將這兩種新的修復策略分別應用到經典算法SPEA2中來求解多目標0/1背包問題，實驗結果表明新的修復策略不僅在2到4個目標的樣本上收斂性有較大提高，并且分布性也有一定的

4、改善。與此同時，在目標數超過4個的高維多目標0/1背包問題上性能也有明顯提高。
　　 (2)針對多目標優(yōu)化問題，基于Minkowski距離和對各個目標值進行加權，提出了多種新的密度評估策略。多目標優(yōu)化的目標就是找到一個解集。這個解集要滿足兩個要求，即收斂性和分布性。收斂性就是要使得到的解集在目標空間上與真正Pareto最優(yōu)前沿的距離盡可能小，而分布性則是要使這個解集在目標空間盡可能均勻分布。當前多目標進化算法的設計正是圍繞著這兩

5、個要求來進行的。引入Pareto支配關系是為了盡可能保證算法的收斂性，而密度函數的引入則主要是為了盡可能保證算法有更好的分布性。當然，這兩方面是相互關聯、相互影響的。當非支配解的數目超過歸檔群體大小時，就需要根據密度函數刪除一部分個體。而在遺傳選擇時，大量支配關系相同的個體就要根據密度函數來決定其優(yōu)劣。因此，密度評估策略對多目標進化算法的性能是很重要的，但對于高維多目標問題，現有密度評估策略的可擴展性卻存在一定問題。為此，本文更全面地考

6、慮目標空間上各個子目標的影響，基于Minkowski距離和對各個子目標值進行加權，提出了幾種新的密度評估策略。在4到9個目標的多目標0/1背包問題樣本上的實驗結果表明，使用新的密度評估策略的多目標進化算法能更有效的收斂到Pareto前沿。然后，將其與本文提出的修復策略相結合，實驗結果表明二者結合后使得算法收斂性有更大提高。此外，進一步將已有的基于歐氏距離與隨機距離的密度評估策略相結合提出了混合密度評估策略，并用實驗驗證了它的有效性。

7、r>　　 (3)針對多目標進化算法，提出了多種新的遺傳選擇策略。遺傳選擇是多目標進化算法的一個重要步驟?，F有的多目標進化算法在進行遺傳選擇時，大都是從外部群體中來選擇父代個體，并且基本是采用基于局部競爭的選擇方法，如錦標賽選擇等。競爭獲勝的標準一般是根據適應度的大小來判斷，而適應度的大小通常由個體間的Pareto支配關系和個體信息（比如密度函數）來共同決定。當目標數增多時，非支配解的數目急劇增加，外部群體中的大多數個體均為非支配解，此

8、時哪個個體獲勝完全依賴于密度函數的值，偏向于保持解集的分布性，這顯然不夠合理。因此，通過在錦標賽選擇時加入考慮兩個體間各子目標值的具體對比情況，本文提出了多種新的遺傳選擇策略。實驗結果表明，使用新的遺傳選擇策略的多目標進化算法在求解超過4個目標的多目標0/1背包問題時性能有很大提高。然后，將其與本文提出的修復策略相結合，實驗結果表明二者結合后對于算法收斂性有更大提高，對于算法的分布性也并沒有不利的影響。
　　 本論文以多目標優(yōu)化