一種基于精英種子策略的多目標遺傳算法

李文彬 , 杜若川, 李雄略, 尹 呈, 郭觀七

(湖南理工學院 信息與通信工程學院, 湖南 岳陽 414006)

引言

多目標優(yōu)化(MO: Multi-objective Optimization)是工程實踐中的常見問題, 其主要特點是各目標之間存在沖突, 目標之間無法同時取得最優(yōu)值, 只能找到一組Pareto非劣解. 但在工程實踐中, 人們往往知道在目標空間中滿足一定條件的一個或幾個最優(yōu)解, 因此這就需要在這一特定的區(qū)域能夠得到比較稠密的Pareto解, 這就對優(yōu)化算法提出了新的問題, 要求在尋優(yōu)過程中必須把已知的最優(yōu)解加到初始種群中去,讓這些最優(yōu)解信息來引導尋優(yōu)方向, 從而在感興趣的區(qū)間內產生能夠滿足人們需要的Pareto解. 針對這個問題, 本文提出了基于精英種子策略的多目標遺傳算法, 把已知的最優(yōu)解信息加到優(yōu)化過程中, 并利用最近鄰方法來識別個體的優(yōu)略, 引導優(yōu)化方向, 通過仿真把該算法和NSGA-Ⅱ[1]進行比較, 結果證明了該算法的可行性和有效性.

1 多目標優(yōu)化問題

一般一個MOP包括n個決策變量, r個目標函數, k個約束條件. 假設優(yōu)化目標之間是相互沖突的, 則一個最小MOP問題可以表示為:

定義 1 設 P為一個集合, 其大小為n, P中每一個個體均有r個屬性,是每個屬性的評價函數(k= 1,2,… ,r), P中個體之間的關系定義為:

定義2 非支配集: 對于給定個體x∈P, 若?y∈P, 使, 則x稱之為集合P的非支配個體. 由所有P的非支配個體組成的集合, 稱之為P的非支配集.

定義3 設Nds是P的非支配集, 則Nds?P, ?x∈P若x是P的非支配個體, 必有, 則稱Nds是P的最大非支配集.

2 基于最近鄰方法的精英選擇

2.1 最近鄰方法

顯然, 兩個模式越相似, 距離d ( · )就越小. 反之亦然.

2.2 精英選擇

在工程實踐的多目標優(yōu)化問題中, 人們往往知道目標空間中的一個或幾個最優(yōu)解, 因此我們把這些已知的最優(yōu)解作為進化尋優(yōu)過程中的精英種子, 引導優(yōu)化方向, 加快pareto最優(yōu)解收斂的速度. 具體做法是: 首先把精英種子加入到初始產生的種群中去, 并對該種群利用擂臺法則[3]產生占優(yōu)類、次優(yōu)類和劣類,那么已知的精英種子一定在占優(yōu)類中; 然后對個體進行選擇、進化, 產生新的個體, 再對新個體利用最近鄰方法進行識別, 使靠近pareto面的精英個體不斷加入到占優(yōu)類中. 這樣占優(yōu)類中既包含了原有的精英個體, 也包含了從進化種群中遷移過來的屬于精英種群的優(yōu)秀個體, 加快了尋找最優(yōu)Pareto 解的速度.

3 基于精英種子策略的多目標遺傳算法

算法采用了精英種子個體保留策略來保證能夠收斂到問題真正的 Pareto 解. 在種群的進化過程中引入已知的最優(yōu)個體信息, 把這些已知的最優(yōu)精英個體加入到占優(yōu)類中, 并利用最近鄰方法把靠近pareto面的個體保留下來, 從而能夠在此區(qū)域內得到足夠多的Pareto 解.

基于精英種子策略的多目標遺傳算法的步驟為:

步驟1 設置參數, 初始化種群, 把已知最優(yōu)個體加入到初始種群中(種群中個體數目popsize、運算代數Maxgen、變量個數fnvar=2、已知最優(yōu)個體集合KnowClass; 創(chuàng)建初始種群pop, 合并KnowClass與pop, 并置代數gen=0);

步驟2 if mod(gen,5)==0 用擂臺法則產生非支配類、支配類和不相關類; 否則轉步驟3;

步驟3 根據rank和擁擠距離選擇個體, 遺傳進化;

步驟4 用最近鄰方法識別個體所屬占優(yōu)類、次優(yōu)類和劣類;

步驟5 gen=gen+1, 如果gen≤Maxgen, 轉到步驟2, 否則終止.

本算法在遺傳算法進化過程中用最近鄰方法識別個體, 把與精英種子距離最小的個體都放到了占優(yōu)類中, 然后對個體進行選擇, 并且隨著遺傳尋優(yōu)過程的進行, 占優(yōu)類中的個體也在不斷的進化. 這樣, 既保證了遺傳算法能夠在整個目標空間內進行尋優(yōu)、避免出現早熟現象, 又能夠在特定的區(qū)域內產生比較稠密的Pareto解.

4 實驗與仿真比較

為檢驗所提出的算法的有效性, 對ZDT1、ZDT2和ZDT3這三個有代表的多目標優(yōu)化問題分別以遺傳算法中效果比較好的 NSGA-Ⅱ算法和基于精英種子策略的多目標遺傳算法進行計算和比較. 對NSGA-Ⅱ算法取種群規(guī)模為 100 個, 進化代數為 100 代. 對基于精英種子策略的多目標遺傳算法種群規(guī)模為100 個, 其中精英種子(已知最優(yōu)解個體)3個, 進化代數20代.

ZDT1函數的兩種算法仿真結果如下:

(1)圖1～4為基于精英種子策略的多目標遺傳算法;

(2)圖5、6為NSGA-Ⅱ算法.

圖1 初始精英種子(已知最優(yōu)解個體)3個

圖2 第5代結果

圖3 第15代結果

圖4 第20代結果

圖5 第20代結果

圖6 第100代結果

從ZDT1函數兩種方法的仿真過程可以得出, 在基于精英種子策略的多目標遺傳算法中從第5代就可以很快的得到想要的解, 而在接下來的進化過程中, 僅僅是在某一局部不斷地優(yōu)化; 在分布性上, 初始精英種子所在區(qū)域的解比較稠密, 在沒有初始精英種子所在區(qū)域的解有的地方比較分散, 總體上接近pareto面. 而NSGA-II在前20代的實驗結果看來, 都無法得到想要的結果, 只能得出隨著代數的不斷增大, 慢慢在逼近pareto面, 解的分布在每一處都較均勻.

對于ZDT2、ZDT3函數的2種方法的仿真結果如下:

圖7 基于精英種子策略的的多目標遺傳算法(ZDT2)

圖8 NSGA-Ⅱ算法(ZDT2)

圖9 基于精英種子策略的的多目標遺傳算法(ZDT3)

圖10 NSGA-Ⅱ算法(ZDT3)

從上面的仿真結果可以看出, 引入的已知的最優(yōu)解精英個體發(fā)揮了很好的作用, 它引導了進化過程中的尋優(yōu)方向使得在已知信息的區(qū)域內產生了比較密集的Pareto解; 而且從最終優(yōu)化的結果可以看出, 提出的算法既在已知信息區(qū)域內產生了大量的Pareto 解, 又在整個目標空間的前端產生了一系列分布比較均勻的Pareto解, 這樣的好處是我們的算法能夠以較快的速度收斂和較少的代數得到問題真正的Pareto解.

5 結論

本文提出的基于精英種子策略的多目標遺傳算法既保證了優(yōu)化問題能夠收斂到真正的Pareto解, 又使得在進化過程中由于最優(yōu)解精英個體信息的引入, 能夠在已知信息區(qū)域內產生稠密的Pareto解來滿足用戶的需求. 本文只是利用了區(qū)間這個概念來描述用戶的已知最優(yōu)信息, 這對于比較具體的工程實踐問題是完全可以的.

[1]Deb K, Pratap A, Agrawal S, Meyrivan T. A fast and elitist multi-objective genetic lgorithm: NSGA-II [J]. IEEE Trans. on Evolutionary Computation,2002, 6(2): 182～197

[2]孫即祥. 現代模式識別[ M]. 長沙: 國防科技大學出版社, 2003

[3]鄭金華, 蔣 浩, 鄺 達, 等. 用擂臺賽法則構造多目標Pareto最優(yōu)解集的方法[J]. 軟件學報, 2007, 18(6): 1287～1297

[4]石 川, 李清勇, 史忠植. 一種快速的基于占優(yōu)樹的多目標進化算法[J]. 軟件學報, 2007, 18(3): 505～516

[5]崔遜學, 林 闖. 一種基于偏好的多目標調和遺傳算法[J]. 軟件學報, 2005, 16(05): 761～770

[6]Jensen MT. Reducing the run-time complexity of multi-objective EAs: The NSGA-II and other algorithms [J]. IEEE Trans. on Evolutionary Computation, 2003,7(5): 503～515