多目標(biāo)進化算法研究.pdf

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

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

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

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

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

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

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

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