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

(湖南理工學院 信息與通信工程學院, 湖南 岳陽 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個目標函數(shù), k個約束條件. 假設優(yōu)化目標之間是相互沖突的, 則一個最小MOP問題可以表示為:

定義 1 設 P為一個集合, 其大小為n, P中每一個個體均有r個屬性,是每個屬性的評價函數(shù)(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 設置參數(shù), 初始化種群, 把已知最優(yōu)個體加入到初始種群中(種群中個體數(shù)目popsize、運算代數(shù)Maxgen、變量個數(shù)fnvar=2、已知最優(yōu)個體集合KnowClass; 創(chuàng)建初始種群pop, 合并KnowClass與pop, 并置代數(shù)gen=0);

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

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

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

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

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

4 實驗與仿真比較

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

ZDT1函數(shù)的兩種算法仿真結果如下:

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

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

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

圖2 第5代結果

圖3 第15代結果

圖4 第20代結果

圖5 第20代結果

圖6 第100代結果

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

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

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

圖8 NSGA-Ⅱ算法(ZDT2)

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

圖10 NSGA-Ⅱ算法(ZDT3)

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