基于分解的多目標優化算法

陳龍

摘 要：多目標優化問題（MOP）的目標函數有兩個或兩個以上，其解通常是一組Pareto最優解。采用傳統的優化算法處理多目標優化問題時不能達到令人滿意的效果。文字研究基于分解的多目標進化算法（MOEA/D），該算法將一個多目標優化問題分解為一組單目標優化問題并對它們同時優化，通過利用與每一個子問題相鄰的子問題的優化信息來優化它本身，比其他同類的優化算法具有更低的計算復雜度。在0—1背包問題和連續的多目標優化問題上，利用一些簡單的分解方法本算法就可以比MOGLS和NSGA-Ⅱ表現得更加出色或者表現相近，未來該算法具有較大的發展空間。

一、多目標優化問題溯源

多目標優化問題首先由法國經濟學家V.Pareto在研究經濟平衡時提出，并且引進和推廣了Pareto最優解。多目標優化問題中的每個目標稱為子目標。各個子目標之間的相互影響和作用，使得對多目標優化時不僅僅是滿足每個子目標的最優化條件，而且要滿足子目標間相互關系的約束條件。因為子目標間的關系也就是子目標約束條件往往是復雜的，有時甚至是相互矛盾的，所以多目標優化問題實質上是處理這種不確定的子目標約束條件。Pareto最優解，也就是說找不到比這個更好的解了，使得至少有一個目標函數有提升。也即找不到一個解使得每一個目標函數都比它更不糟糕的解。而弱Pareto最優解是指不存在一個點使得每一個目標函數相對于現在這個點都有提升，即找不到一個解使得每個目標函數值都比它好。

所謂的目標優化問題，一般就是指通過一定的優化算法獲得目標函數的最優化解。當優化的目標函數為一個時稱之為單目標優化，當優化的目標函數有兩個或兩個以上時稱為多目標優化。不同于單目標優化的解為有限解，多目標優化的解通常是一組均衡解。顯而易見，多目標優化問題比單目標優化問題更接近工程實踐，同時更加復雜。很多工程實踐中的優化問題最后都可以轉化為多目標優化問題，因此，對多目標優化問題的深入研究對于實踐應用更具價值。通常，多目標優化問題都是通過一定的算法實現求解的。

二、基于分解的多目標優化算法

對多目標優化問題的研究也更多地集中于對各種算法的研究。目前多目標優化算法歸結起來有傳統優化算法和智能優化算法兩大類。基于分解的多目標優化算法將MOP分解為N個標量的子問題。它通過進化出一個解的種群來同時解決所有子問題。對于每一代種群，種群是從所有代中選出的每一個子問題的最優解的集合。相鄰兩個子問題鍵的關聯程度是由它們的聚合系數向量間的距離所決定的。對于兩個相鄰子問題來說，最優解應該是非常相似的。對于每一個子問題來說，只是用與其相鄰的子問題的信息來優化它。該算法具有以下特性。

（1）該算法提供了一個簡單有效的方法，即將分解的方法引入多目標進化計算中。對于常常在數學規劃領域發展的分解方法，它可以真正并入EA中，通過使用MOEA/D框架來解決MOP問題。

（2）該算法的適應度分配和多樣性控制的難度得到降低。因為MOEA/D算法是同時優化N標量子問題，而不是直接將MOP問題作為一個整體來解決。

（3）與其他優化算法相比有一個較低的計算復雜度。總體來說，在MOGLS和MOEA/D同時解決0—1背包問題測試樣例中，兩者使用相同的分解方法，MOEA/D在解的質量上表現得更為出色，可以產生一組種群數量少的分布均勻的解。

（4）能夠充分利用標量優化算法。因為在MOEA/D中每一個解都和標量優化問題有關，所以使用標量優化方法顯得很自然。

基于分解的多目標優化算法的分解方法有權重求和方法、切比雪夫聚合方法、邊界交叉聚合方法。在MOEA/D中，可將這種只有更好才能取代的策略應用到所有的個體中。這種取代策略可以看做是以一種保優策略。在0—1背包問題和連續的多目標優化問題上，利用一些簡單的分解方法本算法就可以比MOGLS和NSGA-Ⅱ表現得更加出色或者表現相近，多目標優化問題首先是由經濟學領域提出，但其應用范圍已經隨著算法研究的進展推廣到工業實踐的諸多領域。未來如何在算法研究與實際的工程問題結合中實現多目標優化是值得重視的課題，具有較大的發展前景。

參考文獻：

[1]崔遜學.多目標進化算法及其應用[M].北京：國防工業出版社，2006.

[2]李紅梅.多目標優化演化算法研究綜述[J].現代計算機（專業版），2009（4）：44-46.