基于分解的多目標(biāo)優(yōu)化算法

陳龍

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

一、多目標(biāo)優(yōu)化問題溯源

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

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

二、基于分解的多目標(biāo)優(yōu)化算法

對多目標(biāo)優(yōu)化問題的研究也更多地集中于對各種算法的研究。目前多目標(biāo)優(yōu)化算法歸結(jié)起來有傳統(tǒng)優(yōu)化算法和智能優(yōu)化算法兩大類?；诜纸獾亩嗄繕?biāo)優(yōu)化算法將MOP分解為N個標(biāo)量的子問題。它通過進化出一個解的種群來同時解決所有子問題。對于每一代種群，種群是從所有代中選出的每一個子問題的最優(yōu)解的集合。相鄰兩個子問題鍵的關(guān)聯(lián)程度是由它們的聚合系數(shù)向量間的距離所決定的。對于兩個相鄰子問題來說，最優(yōu)解應(yīng)該是非常相似的。對于每一個子問題來說，只是用與其相鄰的子問題的信息來優(yōu)化它。該算法具有以下特性。

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

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

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

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

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

參考文獻：

[1]崔遜學(xué).多目標(biāo)進化算法及其應(yīng)用[M].北京：國防工業(yè)出版社，2006.

[2]李紅梅.多目標(biāo)優(yōu)化演化算法研究綜述[J].現(xiàn)代計算機（專業(yè)版），2009（4）：44-46.