陳龍

摘 要：多目標(biāo)優(yōu)化問題（MOP）的目標(biāo)函數(shù)有兩個(gè)或兩個(gè)以上，其解通常是一組Pareto最優(yōu)解。采用傳統(tǒng)的優(yōu)化算法處理多目標(biāo)優(yōu)化問題時(shí)不能達(dá)到令人滿意的效果。文字研究基于分解的多目標(biāo)進(jìn)化算法（MOEA/D），該算法將一個(gè)多目標(biāo)優(yōu)化問題分解為一組單目標(biāo)優(yōu)化問題并對它們同時(shí)優(yōu)化，通過利用與每一個(gè)子問題相鄰的子問題的優(yōu)化信息來優(yōu)化它本身，比其他同類的優(yōu)化算法具有更低的計(jì)算復(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)濟(jì)學(xué)家V.Pareto在研究經(jīng)濟(jì)平衡時(shí)提出，并且引進(jìn)和推廣了Pareto最優(yōu)解。多目標(biāo)優(yōu)化問題中的每個(gè)目標(biāo)稱為子目標(biāo)。各個(gè)子目標(biāo)之間的相互影響和作用，使得對多目標(biāo)優(yōu)化時(shí)不僅僅是滿足每個(gè)子目標(biāo)的最優(yōu)化條件，而且要滿足子目標(biāo)間相互關(guān)系的約束條件。因?yàn)樽幽繕?biāo)間的關(guān)系也就是子目標(biāo)約束條件往往是復(fù)雜的，有時(shí)甚至是相互矛盾的，所以多目標(biāo)優(yōu)化問題實(shí)質(zhì)上是處理這種不確定的子目標(biāo)約束條件。Pareto最優(yōu)解，也就是說找不到比這個(gè)更好的解了，使得至少有一個(gè)目標(biāo)函數(shù)有提升。也即找不到一個(gè)解使得每一個(gè)目標(biāo)函數(shù)都比它更不糟糕的解。而弱Pareto最優(yōu)解是指不存在一個(gè)點(diǎn)使得每一個(gè)目標(biāo)函數(shù)相對于現(xiàn)在這個(gè)點(diǎn)都有提升，即找不到一個(gè)解使得每個(gè)目標(biāo)函數(shù)值都比它好。

所謂的目標(biāo)優(yōu)化問題，一般就是指通過一定的優(yōu)化算法獲得目標(biāo)函數(shù)的最優(yōu)化解。當(dāng)優(yōu)化的目標(biāo)函數(shù)為一個(gè)時(shí)稱之為單目標(biāo)優(yōu)化，當(dāng)優(yōu)化的目標(biāo)函數(shù)有兩個(gè)或兩個(gè)以上時(shí)稱為多目標(biāo)優(yōu)化。不同于單目標(biāo)優(yōu)化的解為有限解，多目標(biāo)優(yōu)化的解通常是一組均衡解。顯而易見，多目標(biāo)優(yōu)化問題比單目標(biāo)優(yōu)化問題更接近工程實(shí)踐，同時(shí)更加復(fù)雜。很多工程實(shí)踐中的優(yōu)化問題最后都可以轉(zhuǎn)化為多目標(biāo)優(yōu)化問題，因此，對多目標(biāo)優(yōu)化問題的深入研究對于實(shí)踐應(yīng)用更具價(jià)值。通常，多目標(biāo)優(yōu)化問題都是通過一定的算法實(shí)現(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個(gè)標(biāo)量的子問題。它通過進(jìn)化出一個(gè)解的種群來同時(shí)解決所有子問題。對于每一代種群，種群是從所有代中選出的每一個(gè)子問題的最優(yōu)解的集合。相鄰兩個(gè)子問題鍵的關(guān)聯(lián)程度是由它們的聚合系數(shù)向量間的距離所決定的。對于兩個(gè)相鄰子問題來說，最優(yōu)解應(yīng)該是非常相似的。對于每一個(gè)子問題來說，只是用與其相鄰的子問題的信息來優(yōu)化它。該算法具有以下特性。

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

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

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

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

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

參考文獻(xiàn)：

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

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