基于隨機(jī)擾動的多目標(biāo)進(jìn)化算法

郭修豪，陳勇（重慶師范大學(xué)，重慶　401331）

基于隨機(jī)擾動的多目標(biāo)進(jìn)化算法

郭修豪，陳勇
（重慶師范大學(xué)，重慶401331）

0　引言

生活中，許多問題都是由相互沖突的多個(gè)目標(biāo)組成，例如在工廠生產(chǎn)成品時(shí)，要求以固定的時(shí)間和固定的成本，生產(chǎn)物品的數(shù)量和質(zhì)量越多/高越好，此時(shí)物品的數(shù)量和質(zhì)量就是需要優(yōu)化的兩個(gè)目標(biāo)。當(dāng)優(yōu)化問題存在的優(yōu)化目標(biāo)如果超過一個(gè)，就成為多目標(biāo)優(yōu)化問題［2］。

多目標(biāo)進(jìn)化算法對解決多目標(biāo)優(yōu)化問題具有重要的意義，在各方研究的不懈努力下，多目標(biāo)進(jìn)化算法取得了顯著成果。多目標(biāo)進(jìn)化算法的發(fā)展主要經(jīng)歷了以下幾個(gè)階段。①1985年～1994年的緩慢發(fā)展期［3］：第一代的算法代表有向量估計(jì)遺傳算法（VEGA），多目標(biāo)遺傳算法［4］（MOGA）、小生境pareto遺傳算法［5］（NPGA）和非劣排序遺傳算法［6］（NSGA）。②1994～2003年的快速發(fā)展期：第二代算法的代表有NSGA2［7］、pareto包絡(luò)選擇算法［8］以及強(qiáng)度pareto進(jìn)化算法（SPEA和SPEA2［10］）。③2003年～現(xiàn)在的全面發(fā)展期。從第三代開始，各種新的概念、機(jī)制和策略開始引入到MOEA，多目標(biāo)進(jìn)化算法進(jìn)入了新的研究階段。

1　多目標(biāo)優(yōu)化問題的基本概念

我們首先給出有關(guān)多目標(biāo)優(yōu)化問題的一般描述［11］。給定決策向量X=（x1，x2，…，xn），它滿足如下約束：

設(shè)有r個(gè)優(yōu)化目標(biāo)，且這r個(gè)優(yōu)化目標(biāo)是相互沖突的，優(yōu)化目標(biāo)可表示為：

f（X）=（f1（X），f2（X），…，ft（X）），尋求 X*=（x1*，x2*，…，xn*）使f（X*）在滿足約束（1）、（2）的情況下達(dá)到最優(yōu)。即：

接下來討論多目標(biāo)優(yōu)化問題的相關(guān)概念。

定義1非劣解：一個(gè)解X非劣于Y當(dāng)且僅當(dāng)fi（X）≤fi（Y）對i=1，2，…，r均成立，并至少在某一維向量的優(yōu)化上存在fj（X）＜fj（Y），j∈｛1，2，…，r｝，我們稱為X非劣于Y，記作XY。

定義2：pareto最優(yōu)點(diǎn)：如果X'是pareto最優(yōu)點(diǎn)，當(dāng)且僅當(dāng)┐X:XX'

定義3：pareto最優(yōu)集：所有pareto最優(yōu)點(diǎn)的集合PS=｛X'|┐XX'｝。

2　NMOGA算法（Novel GA for Multiobjective Optimization Problem）

（3）若父代個(gè)體x和y互不支配，則產(chǎn)生一個(gè)隨機(jī)數(shù)r∈（0，1），當(dāng)r＜0.5時(shí)，令方向d=（y-x）；當(dāng)r≥0.5時(shí)，d=（x-y）。

（4）隨機(jī)產(chǎn)生s（s≥2）個(gè)可行方向d1，d2，…，ds，其中di（i=1，2，…，s）與方向d成銳角。

（5）沿著d1，d2，…，ds方向進(jìn)行步長為R的線性搜索，得到s個(gè)個(gè)體X1，X2，…，XS，基于pareto解的概念從中選取最好的可行個(gè)體作為雜交的后代；若X1，X2，…，XS均為不可行解，令R=R/2，轉(zhuǎn)（5）（其中s=5）。

圖1　雜交算子示意圖

設(shè)X=（x1，x2，…，xn）T是參加變異的后代個(gè)體，對其每個(gè)分量xi（i=1，2，…，n），隨機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù)r∈（0，1），則：

式中，λ∈（0，1）為隨機(jī)數(shù)。對每個(gè)分量個(gè)體xi進(jìn)行如上的操作，得到的個(gè)體X'=（x1'，x2'，…，xn'）為變異產(chǎn)生的新的后代個(gè)體。

3　基于隨機(jī)擾動的多目標(biāo)進(jìn)化算法（RD MOGA）

在介紹RDMOGA算法之前，我們先介紹兩種關(guān)于非劣解的排序方法。

（1）令每個(gè)解x∈P對應(yīng)的支配解x的所有個(gè)體的數(shù)量nX=0，P為多目標(biāo)問題可行解的范圍，對于除x外的任何解q，q∈P，如果有qx，則nX=nX+1。最終得到每個(gè)解所對應(yīng)的nX，將nX的點(diǎn)放入到前端F1中，且Xrank=1。

（2）令i=1。

（3）除去所有Xrank=i的點(diǎn)，設(shè)剩下的解的集合為Q，對于每個(gè)x∈Q，找出其中nX=0的點(diǎn)，將nX=0的點(diǎn)放入到前端F（i+1）中，且Xrank=i+1。

（4）如果Fi+1不為空集，i=i+1，轉(zhuǎn)到（3），否則，停止迭代。

（1）對于每個(gè)目標(biāo)函數(shù)f1，f2，…，fr，先對非劣解集i中的解根據(jù)該目標(biāo)函數(shù)值的大小進(jìn)行排序。

（2）然后由每個(gè)解i，計(jì)算由解i+1和i-1構(gòu)成的立方體的平均邊長idistance。

（3）根據(jù) idistance的大小對解進(jìn)行排序，idistance越大則排序越靠前。邊界解（其某個(gè)目標(biāo)函數(shù)值最大或最?。┑膿頂D距離為無窮大。

擁擠距離用來估計(jì)一個(gè)解周圍其它解的密集程度。設(shè)有兩個(gè)點(diǎn)i，j，i排在j的前面當(dāng)且僅當(dāng)irank＜jrank或者 irank=jrank且 idistance＞jdistance。

圖2　擁擠距離排序示意圖

我們假定需要優(yōu)化的目標(biāo)函數(shù)在自變量所約束的范圍內(nèi)為有界函數(shù)，即這些函數(shù)存在最大最小值，我們將這些目標(biāo)函數(shù)記為f1，f2，…，fr。我們在這些函數(shù)前乘以一個(gè)不為零的常數(shù)，將新產(chǎn)生的函數(shù)相加得到一個(gè)單目標(biāo)函數(shù)F（X），我們記為：F（X）=af1（X）+bf2（X）+…rfr（X），由前面的定義可知，F(xiàn)（X）在規(guī)定的自變量范圍內(nèi)也存在最大最小值，我們將函數(shù)F的最小值點(diǎn)記為（X'，F(xiàn)（X'）），即：Fmin（X）=af1（X'）+bf2（X'）+…rfr（X'）。

推論1：基于有界多目標(biāo)函數(shù)，其隨機(jī)分配權(quán)重后求得的最小值點(diǎn)一定是該多目標(biāo)函數(shù)的pareto最優(yōu)點(diǎn)。

（1）選取參加交叉過程的父代個(gè)體X1和X2，隨機(jī)產(chǎn)生兩組擾動因子其中r為目標(biāo)函數(shù)的個(gè)數(shù)，我們假定

（2）將C1，C2分別分配到各個(gè)目標(biāo)函數(shù)中形成2個(gè)單目標(biāo)函數(shù)，如下所示：，求出兩個(gè)函數(shù)的最小值，最小值點(diǎn)記作和

圖4　新算法雜交算子示意圖

（1）根據(jù)變異概率Pm選取參加變異的個(gè)體Xa，隨機(jī)產(chǎn)生一組擾動因子（r為目標(biāo)函數(shù)的個(gè)數(shù)），令

圖4　新算法變異算子示意圖

4　RDMOGA算法流程

步驟1（初始化）給定一定規(guī)模的種群數(shù)量N，交叉概率PC，變異概率Pm，最大進(jìn)化代數(shù)T，和初始種群A0，將A0中的非劣解存入精英檔案檔案P0中，t=0。

步驟2（交叉）按交叉概率Pc從At中選定參與交叉的個(gè)體，按新算法交叉算子對選中個(gè)體進(jìn)行交叉操作，產(chǎn)生的后代存入檔案O1中。

步驟3（變異）按變異概率Pm從At中選定參與變異的個(gè)體，用新算法變異算子對選中個(gè)體進(jìn)行變異操作，產(chǎn)生的后代存入檔案O2中。

步驟4（精英保留）從At∪Pt∪O1∪O2中選取非劣解保存到下一代精英檔案P（t+1）中，我們設(shè)定非劣檔案P中的最大個(gè)數(shù)容納數(shù)為M，若非劣解個(gè)數(shù)超過M，則根據(jù)非劣解的擁擠距離排序規(guī)則排除擁擠距離最小的個(gè)體。

步驟5（結(jié)束）當(dāng)t=Tmax時(shí)，算法結(jié)束，輸出Pt作為算法最終解。否則轉(zhuǎn)步驟2。

5　實(shí)驗(yàn)結(jié)果對比

從文獻(xiàn)［12］中選取ZDT1，ZDT2，ZDT3，ZDT6函數(shù)作為測試函數(shù)。將NMOGA算法的測試結(jié)果與RDMOGA算法的測試結(jié)果進(jìn)行對比。我們規(guī)定，N=100，Pc=0.9，Pm=0.05，Tmax=20，M=50，圖5到圖8分別表示對T1，T2，T3，T6函數(shù)的搜索結(jié)果，RDMOGA算法和NMOGA算法的搜索結(jié)果用○和*表示）。

圖5　兩種算法對T1求得的pareto前沿面

圖6　兩種算法對T2求得的pareto前沿面

圖7　兩種算法對T3求得的pareto前沿面

圖8　兩種算法對T6求得的pareto前沿面

由圖可以看出，RDMOGA算法的搜索結(jié)果要好于NMOGA算法。我們選用C-measure［3］和U-measure［13］對搜索結(jié)果進(jìn)行驗(yàn)證。

C-measure描述了兩個(gè)集合間的覆蓋關(guān)系，它表示集合B中的解被集合A中解支配的個(gè)數(shù)與集合B總數(shù)之比。公式如下：

表1根據(jù)兩種算法的pareto前沿面得出的C值。

表1　

由表1可以看出，NOMOGA算法所求得的pareto前沿面基本上被RDMOGA算法求得的pareto前沿面覆蓋。

U-measure用于評價(jià)多目標(biāo)優(yōu)化問題均勻性和寬廣性的。其公式如下：

表2為根據(jù)兩種算法的pareto前沿面得出的U值。

表2　

由表2可知，RDMOGA算法的 U值要小于NOMOGA算法，這表明RDMOGA算法求得的pareto前沿面在均勻性和寬廣性方面要優(yōu)于NOMOGA算法。我們采用擁擠距離排序保證了pareto前沿面的均勻性，引入隨機(jī)擾動因子使求得的pareto前沿面的范圍更加寬廣。

6　結(jié)語

RWMOGA算法在搜索高維多目標(biāo)問題的最優(yōu)前沿面時(shí)，表現(xiàn)出了優(yōu)秀的搜索性能。在其與其他算法的比較中，顯示出了該算法在搜索方面的優(yōu)越性。智能算法一直處于發(fā)展中，將智能算法與一些數(shù)學(xué)方法相結(jié)合，在解決多目標(biāo)優(yōu)化問題時(shí)具有其獨(dú)特的優(yōu)勢。探索pareto最優(yōu)解的其他數(shù)學(xué)特征，是我們今后努力的方向。

［1］韓麗霞.求解多目標(biāo)優(yōu)化問題的新遺傳算法［M］.計(jì)算機(jī)科學(xué)，2013，40（6A）：64-66.

［2］肖曉偉，肖迪，林錦國等.多目標(biāo)優(yōu)化問題的研究概述［J］.計(jì)算機(jī)應(yīng)用研究，2011，28（3）:805-808.

［3］雷德明，嚴(yán)新平.多目標(biāo)智能優(yōu)化算法及其應(yīng)用［M］.北京：科學(xué)出版社，2009.

［4］Fonseca C M，F(xiàn)leming P J.Genetiic Algorithms for Multi-Objective Optimization:Formulation，Discussion and Generalization.Proceedings of Fifth International Conference on Genetic Algorithms.San Mateo and California，1993:416-423

［5］Horn J，Nafpliotis N，Goldberg D E.A Niched Pareto Genetic Algorithm for Mutiobjectives Optimization.Proceedings of the First IEEE Conference on Evolutionary Computation，1994:82-87.，

［6］Srinivas N，Deb K.Muti-Objective Optimization Using Non-Domimated in Genetic Algorithms.Evolutionary Computation，1994，2（3）: 221-248.

［7］Deb K，Pratap A，Agarwal S，et al.A Fast and Elitist Multi-Objective Genetic Algorithms:NSGA2.IEEE Transactions on Evolutionary Computation，2002，6（2）:182-197.

［8］Knowles J D，Corne D W.Approximating the Non-Dominated Front Using the Pareto Archive Evolutionary Strategy.Evolutionary Computation，2000，8（2）:149-172

［9］Corne D W，Knowles J D，Oates M J.The Pareto Envelope-Based Selection Algorithm for Muti-Objective Optimization.Proseedings of the Parallel Problem Solving from Nature VI Conference，2000:839-848.

［10］Zitzler E，Laumanns M，Thiele L.SPEA2:Improving the Strength Pareto Evolutionary Algorithm.Swiss Federal Institute of Technology，Lausanne，Switzerl，Tech.Rep.，2001:103

［11］鄭金華.多目標(biāo)進(jìn)化算法及其應(yīng)用［M］.北京：社會科學(xué)出版社，2007.

［12］Zitzler E，Deb，K.Multiobjective Function Optimization Using Momdominated Sorting Genetic Algorithm［J］.Evolutionary Computation，1995，2（2）:221-248.

［13］leung Y W，Wang Y P.A Quality Measure for Muti-Objective Programming［J］.IEEE Transactions on System，Man and Cybernetics-Part A:System and Human，2003，33（2）:337-343.

Uses genetic algorithm to solve multi-objective problem，the result is often trapped in local optimum.Introduces the external population of the traditional algorithm，and proposes a genetic algorithm based on random perturbation of the RDMOGA.The new algorithm is tested by using the standard multi objective test functions，and compared with the NMOGA algorithm proposed by Han Lixia.The test results show that the new algorithm shows good performance.

Keyswords：

Multi-Objective Optimization；Random Disturbance；Evolutionary Algorithm；Crowding Distance Sorting；C-measure；U-measure

An Evolutionary Algorithm for Multi-Objective Optimization Problem Based on Random Distuibance

GUO Xiu-hao，CHEN Yong
（Chongqing Normal University，Chongqing 401331）

國家自然科學(xué)基金資助項(xiàng)目（60703035）、重慶市教委基金資助項(xiàng)目（No.KJ070801）、重慶市教委科技項(xiàng)目（No.KJ120622）

1007-1423（2015）35-0003-06

10.3969/j.issn.1007-1423.2015.35.001

郭修豪（1990-），男，在讀研究生，研究方向?yàn)槎嗄繕?biāo)優(yōu)化、人工智能

2015-11-10

2015-12-10

運(yùn)用遺傳算法解多目標(biāo)問題，結(jié)果往往會陷入局部最優(yōu)。引入傳統(tǒng)算法求得的外部種群，提出基于隨機(jī)擾動的RDMOGA遺傳算法。將新算法用標(biāo)準(zhǔn)多目標(biāo)測試函數(shù)進(jìn)行測驗(yàn)，并與韓麗霞提出的NMOGA算法進(jìn)行對比，實(shí)驗(yàn)結(jié)果表明，新算法表現(xiàn)出良好的搜索性能。

多目標(biāo)優(yōu)化；隨機(jī)擾動；進(jìn)化算法；擁擠距離排序；C-measure；U-measure