宋武　陳德祥

摘要：為了解決多目標(biāo)優(yōu)化問題，該文提出了一種改進(jìn)的基于分解的多目標(biāo)進(jìn)化算法，算法非平衡的分配計(jì)算資源給每個(gè)子問題，每個(gè)子問題具有相對較大的密度時(shí)，能夠分配較多的資源，實(shí)驗(yàn)結(jié)果表明改進(jìn)的算法優(yōu)于原有的基于分解的多目標(biāo)優(yōu)化算法。

關(guān)鍵詞：多目標(biāo)優(yōu)化問題；多目標(biāo)進(jìn)化計(jì)算；分解

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2012）34-8316-03

實(shí)際問題一般都是多屬性的，往往需要同時(shí)優(yōu)化多個(gè)目標(biāo)。根據(jù)選擇機(jī)制的不同，可將多目標(biāo)優(yōu)化進(jìn)化算法（MOEAs：MultiobjectiveEvolutionaryAlgorithms）當(dāng)前的主流是基于Pareto的[1]。出現(xiàn)了許多經(jīng)典的算法，如NSGA-II[2]等，但此類算法只能適用于處理低維優(yōu)化問題，隨著目標(biāo)維數(shù)的增加，算法的搜索能力顯著下降，無法找到優(yōu)化問題的近似Pareto最優(yōu)面。

針對基于聚集函數(shù)的多目標(biāo)優(yōu)化算法的不足，Zhang和Li[2]通過預(yù)先產(chǎn)生均勻分布的權(quán)值向量將多目標(biāo)優(yōu)化問題轉(zhuǎn)換為一組單目標(biāo)子問題，并為每個(gè)子問題分配一個(gè)個(gè)體，從而提出了MOEA/D（MultiobjectiveEvolutionaryAlgorithmbasedonDecomposition）[12]。實(shí)驗(yàn)表明，該算法能有效地處理高維問題及決策空間不連續(xù)問題[3]]?；贛OEA/D算法的優(yōu)勢。

由于MOEA/D在進(jìn)化時(shí)，平均的分配給每一個(gè)子問題進(jìn)行進(jìn)化，嚴(yán)重制約了其性能的進(jìn)一步提高。但是由于優(yōu)化的問題在前沿面上，并不是均衡的，對應(yīng)于子問題進(jìn)化時(shí)也不是均衡的。導(dǎo)致了已經(jīng)收斂的子問題，繼續(xù)有進(jìn)化的能力，而沒有收斂的子問題獲得較少的計(jì)算性資源，因此該文考慮了一種，在選擇父親進(jìn)行交叉時(shí)，非平衡的選擇父親個(gè)體，從而完成了非平衡分配的方案，實(shí)驗(yàn)結(jié)果表明該算法具有一定可行性及有效性。

1改進(jìn)的MOEA/D算法

MOEA/D在將多目標(biāo)優(yōu)化問題分解為一組單目標(biāo)子問題并為每個(gè)子問題分配一個(gè)個(gè)體，由各個(gè)子問題上的個(gè)體組成初始種群，通過均勻的并行進(jìn)化各個(gè)子問題而得到一組解集。基于鄰域的進(jìn)化是MOEA/D的有效搜索機(jī)制之一。此外，為了計(jì)算適應(yīng)度，MOEA/D算法成功地將數(shù)學(xué)規(guī)劃中常用的分解方法引入到進(jìn)化多目標(biāo)領(lǐng)域，使用分解方法計(jì)算適應(yīng)度可以直接采用求解單目標(biāo)優(yōu)化問題時(shí)的適應(yīng)度分配和多樣性保持策略[21]。目前最常用的分解方法有：WeightedSum、Tchebycheff和Penalty-basedBoundaryIntersection（PBI）。

1）WeightedSum分解方法