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

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

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

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

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

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

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

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

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