多目標(biāo)演化算法

摘要：演化算法因其內(nèi)在的并行行，在求解多目標(biāo)優(yōu)化問題時(shí)具有獨(dú)特的優(yōu)勢(shì)。本文介紹多目標(biāo)演化算法的基本原理，并詳細(xì)討論基于Pareto最優(yōu)概念的多目標(biāo)演化算法。

關(guān)鍵詞：多目標(biāo)優(yōu)化；Pareto最優(yōu)解；演化算法

中圖分類號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)20-30262-02

Evolutiaon Algorithm for Multi-Objective Optimization Problems

MO Hai-fang

(Computer and Experiment Center， South-Center University For Nationality， Wuhan 430074， China)

Abstract: Evolut ionary algorithm is especially suitable to solve multi-object ive optimization problems. The basic principle of multi-object ive evolution algorithm is introduced， and the Pareto optimial-based evolutionary approach is discussed.

Key words: multi-objective optimization; Pareto optimal solutions; evolution algorithm

1 引言

多目標(biāo)問題的求解是近年來(lái)優(yōu)化計(jì)算的一個(gè)熱點(diǎn)問題。與單目標(biāo)問題不同，多目標(biāo)問題的解不是單一的解，而是一組相互之間不可比較，甚至是相互沖突的解。因此求解多目標(biāo)問題比求解單目標(biāo)問題要困難得多。

求解多目標(biāo)問題的傳統(tǒng)方法主要有加權(quán)法、層次優(yōu)化法、目標(biāo)規(guī)劃法等，這些方法的主要思想是對(duì)多目標(biāo)進(jìn)行權(quán)重分配，轉(zhuǎn)化為單目標(biāo)問題，然后運(yùn)用單目標(biāo)優(yōu)化技術(shù)進(jìn)行求解。這類方法需要較多的先驗(yàn)知識(shí)，而且計(jì)算效率低。

演化算法（EA）是一類模擬自然界生物進(jìn)化的全局性概率優(yōu)化搜索方法，因?yàn)槠鋬?nèi)在的并行性，特別適合于求解復(fù)雜的多目標(biāo)優(yōu)化問題。

基于向量評(píng)估的VEGA算法是Schaffer于1985年提出的，這是第一個(gè)多目標(biāo)演化算法。該算法的主要思想是在每一代中根據(jù)各目標(biāo)函數(shù)，用適應(yīng)度比例法產(chǎn)生一定數(shù)目的子種群，然后把它們合并成新的一代，繼續(xù)執(zhí)行交叉和變異等遺傳操作。VEGA算法在本質(zhì)上仍然是加權(quán)和的方法。隨后有許多成功的多目標(biāo)演化算法被提出。1993年，F(xiàn)onseca和Fleming提出MOGA算法，Horn和Nafploitis提出NPGA算法，Srinivas和Deb提出NSGA算法。其中MOGA最著名，這是基于Pareto最優(yōu)概念的算法，它統(tǒng)計(jì)出群體中優(yōu)于某個(gè)體的個(gè)體數(shù)量，并依此計(jì)算該個(gè)體的適應(yīng)值。同時(shí)采用自適應(yīng)的小生境技術(shù)和受限雜交技術(shù)來(lái)提高種群多樣性。1999年，Zitzler和Thiele提出了SPEA算法，該算法采用精英保留策略來(lái)提高多目標(biāo)進(jìn)化算法的性能。這些算法都能成功求解多目標(biāo)問題，它們的實(shí)現(xiàn)基于以下基本的策略：Pareto最優(yōu)策略和保持種群多樣性的策略。

2 多目標(biāo)優(yōu)化問題中的一些概念

一般地，一個(gè)多目標(biāo)優(yōu)化問題可以歸結(jié)為多個(gè)目標(biāo)的極小化模型：

定義1：多目標(biāo)優(yōu)化問題

v-min f(x)=[(f1(x)， f2(x)， …，fm(x))]T

subject to x ∈X

X?哿Rm

其中的v-min表示向量極小化，即向量目標(biāo)函數(shù)f(x)=[(f1(x)，f2(x)，…，fm(x))]T中的各子目標(biāo)函數(shù)都盡可能地極小化。

然而在很多情況下，多目標(biāo)優(yōu)化問題中的各個(gè)子目標(biāo)是相互沖突的，一個(gè)子目標(biāo)性能的改善可能會(huì)引起另一個(gè)子目標(biāo)性能的降低，也就是說(shuō)，一個(gè)能夠同時(shí)使所有目標(biāo)函數(shù)達(dá)到最優(yōu)的解很可能是不存在的，只能在它們之間進(jìn)行協(xié)調(diào)和折衷處理，使各個(gè)子目標(biāo)函數(shù)都盡可能地達(dá)到最優(yōu)。為了對(duì)多目標(biāo)問題的解進(jìn)行比較， 先給出Pareto最優(yōu)解的定義。

定義2：Pareto占優(yōu)

任何兩個(gè)決策向量a∈X和b∈X，如果f(a)o占優(yōu)于b的。

定義3：Pareto最優(yōu)解

如果不存在y∈X，使fi(y)≤fi(x)， i=1，2，…，m，且至少有一個(gè)嚴(yán)格不等式成立，則稱x∈X是多目標(biāo)優(yōu)化問題的Pareto最優(yōu)解，或稱為非劣解。

通常的多目標(biāo)問題的Pareto最優(yōu)解都有很多，把Pareto最優(yōu)解的集合稱為Pareto前沿。由定義3可知，Pareto最優(yōu)解集中的解是彼此不可比較的，解集中的解數(shù)量越多，分布越廣泛， 決策者的選擇空間越大，越能對(duì)實(shí)際多目標(biāo)問題進(jìn)行合理求解。

3 多目標(biāo)演化算法

多目標(biāo)演化算法的大致流程如下：

1) 初始化：產(chǎn)生初始群體P(0)；

2) 計(jì)算個(gè)體的適應(yīng)值；

3) 在群體P(t)中執(zhí)行選擇、交叉和變異等進(jìn)化操作產(chǎn)生下一代種群P(t+1)；

4) 若滿足結(jié)束條件則將退出，否則轉(zhuǎn)到步驟3)。

3.1 基于Pareto非劣概念的排名

用Pareto非劣解的概念計(jì)算個(gè)體適應(yīng)值的方法首先是由Goldberg于1989年提出的。他提出排序方法（Ranking）和基于序的適應(yīng)度函數(shù)形式。先將多目標(biāo)函數(shù)值組成一個(gè)向量代表一個(gè)個(gè)體，假設(shè)個(gè)體xi在t代群體中有n個(gè)個(gè)體優(yōu)于它，則它在群體中的序?yàn)椋簉ank(xi)=1+n。如圖1所示，當(dāng)前群體中所有非劣最優(yōu)解的序都為1。

圖1 群體中個(gè)體的Pareto序

排序僅僅體現(xiàn)了各個(gè)個(gè)體之間的優(yōu)越次序，沒有體現(xiàn)各個(gè)個(gè)體的分散程度，所以容易導(dǎo)致最終得到很多個(gè)相似的Pareto最優(yōu)解，而難于獲得分布均勻的Pareto最優(yōu)解。

3.2 群體多樣性

為了逼近Pareto最優(yōu)解集，就要得到多個(gè)不同的解，因此，群體多樣性極其重要。為了提高群體多樣性，多目標(biāo)演化算法已經(jīng)提出了多種小生境與共享技術(shù)，以求獲得均勻分布得Pareto最優(yōu)解集。已有的保持群體多樣性的方法有：適應(yīng)值共享、受限雜交、孤島模型、重新初始化、擁擠機(jī)制等。比較適合多目標(biāo)演化算法的是適應(yīng)值共享。

適應(yīng)值共享的思路是：同一個(gè)小生境中（Niche）的個(gè)體必須共享資源。一個(gè)個(gè)體有越多的鄰居（neighborhood），那么該個(gè)體的適應(yīng)值越小。

兩個(gè)個(gè)體之間的空間距離小于某個(gè)伐值（Niche radius）時(shí)，就成為鄰居（neighborhood），一個(gè)個(gè)體的鄰居數(shù)量稱為小生境數(shù)（Niche Count）。某個(gè)個(gè)體的適應(yīng)值除以它的小生境數(shù)就得到它調(diào)整后的適應(yīng)值，從而使有多個(gè)相似的個(gè)體降低了適應(yīng)值，減少了它們遺傳到下一代群體的機(jī)會(huì)。

3.3 精英策略

SPEA算法采用精英保留策略來(lái)提高多目標(biāo)進(jìn)化算法的性能。精英是指一代群體中適應(yīng)值較高的個(gè)體。在多目標(biāo)演化算法中，在每一代群體中都有多個(gè)精英，把這些精英保存到一個(gè)精英集合中，然后按照概率從這個(gè)集合中再選擇優(yōu)秀個(gè)體進(jìn)入下一代群體，從而加快了算法的收斂速度，提高算法的性能。

4 測(cè)試函數(shù)

minimize T(x)=(f1(x1)，f2(x2)

subject to f2(x)=g(x2，…， xm)h(f1(x1)，g(x2，…，xm))

where x=(x1，x2，…，xm)

測(cè)試函數(shù)1：

f1(x1)=x1

(m=30并且xi∈[0，1]。當(dāng)達(dá)到Pareto前沿時(shí)g(x)=1)

5 結(jié)束語(yǔ)

多目標(biāo)演化算法具有廣泛的應(yīng)用前景，目前已經(jīng)被成功應(yīng)用到自動(dòng)控制、機(jī)械設(shè)計(jì)、航空航天、網(wǎng)絡(luò)通信、作業(yè)調(diào)度、圖像處理、生命科學(xué)等多個(gè)領(lǐng)域。隨著多目標(biāo)演化算法在理論上的深入探索，必將在更多領(lǐng)域得到應(yīng)用。

多目標(biāo)演化算法的研究在近年來(lái)取得了許多成果，進(jìn)一步值得研究的問題包括：加強(qiáng)多目標(biāo)演化算法的基礎(chǔ)理論研究，從理論上證明算法的收斂性，設(shè)計(jì)能反映多目標(biāo)演化算法基本特征的測(cè)試函數(shù)；對(duì)于高維多目標(biāo)優(yōu)化問題，研究新的非基于Pareto 最優(yōu)概念的群體排序方法；結(jié)合領(lǐng)域知識(shí)，設(shè)計(jì)專門的多目標(biāo)演化算法。

參考文獻(xiàn)：

[1] 謝濤， 陳火旺， 康立山. 多目標(biāo)優(yōu)化的演化算法[J]. 計(jì)算機(jī)學(xué)報(bào)， 2003，26(8):997-1007.

[2] 馬清亮， 胡昌華. 多目標(biāo)進(jìn)化算法及其在控制領(lǐng)域中的應(yīng)用綜述[J].控制與決策， 2006，21(5):481-486.

[3] 祁榮賓， 錢鋒， 杜文莉， 等. 基于精英選擇和個(gè)體遷移的多目標(biāo)遺傳算法[J]. 控制與決策， 2007，22(2):164-168.

[4] 陳柳， 周偉， 張國(guó)平. 一種基于樹結(jié)構(gòu)排序的多目標(biāo)優(yōu)化演化算法[J]. 計(jì)算機(jī)工程與應(yīng)用. 2005，(2):90-93.

[5] 陳國(guó)良， 王熙法， 莊鎮(zhèn)泉， 等. 遺傳算法及其應(yīng)用[M]. 北京：人民郵電出版社，2001.

[6] 王小平， 曹立明. 遺傳算法理論、應(yīng)用與軟件實(shí)現(xiàn)[M]. 西安：西安交通大學(xué)出版社，2002.