基于隨機擾動的多目標進化算法

郭修豪，陳勇（重慶師范大學，重慶　401331）

基于隨機擾動的多目標進化算法

郭修豪，陳勇
（重慶師范大學，重慶401331）

0　引言

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

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

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

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

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

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

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

定義1非劣解：一個解X非劣于Y當且僅當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)點：如果X'是pareto最優(yōu)點，當且僅當┐X:XX'

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

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

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

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

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

圖1　雜交算子示意圖

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

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

3　基于隨機擾動的多目標進化算法（RD MOGA）

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

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

（2）令i=1。

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

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

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

（2）然后由每個解i，計算由解i+1和i-1構成的立方體的平均邊長idistance。

（3）根據(jù) idistance的大小對解進行排序，idistance越大則排序越靠前。邊界解（其某個目標函數(shù)值最大或最小）的擁擠距離為無窮大。

擁擠距離用來估計一個解周圍其它解的密集程度。設有兩個點i，j，i排在j的前面當且僅當irank＜jrank或者 irank=jrank且 idistance＞jdistance。

圖2　擁擠距離排序示意圖

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

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

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

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

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

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

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

4　RDMOGA算法流程

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

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

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

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

步驟5（結束）當t=Tmax時，算法結束，輸出Pt作為算法最終解。否則轉步驟2。

5　實驗結果對比

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

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

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

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

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

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

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

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

表1　

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

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

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

表2　

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

6　結語

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

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

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

［3］雷德明，嚴新平.多目標智能優(yōu)化算法及其應用［M］.北京：科學出版社，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］鄭金華.多目標進化算法及其應用［M］.北京：社會科學出版社，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）

國家自然科學基金資助項目（60703035）、重慶市教委基金資助項目（No.KJ070801）、重慶市教委科技項目（No.KJ120622）

1007-1423（2015）35-0003-06

10.3969/j.issn.1007-1423.2015.35.001

郭修豪（1990-），男，在讀研究生，研究方向為多目標優(yōu)化、人工智能

2015-11-10

2015-12-10

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

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