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

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

引言

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

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

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

定義 1 設(shè) P為一個(gè)集合, 其大小為n, P中每一個(gè)個(gè)體均有r個(gè)屬性,是每個(gè)屬性的評(píng)價(jià)函數(shù)(k= 1,2,… ,r), P中個(gè)體之間的關(guān)系定義為:

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

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

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

2.1 最近鄰方法

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

2.2 精英選擇

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

3 基于精英種子策略的多目標(biāo)遺傳算法

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

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

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

步驟2 if mod(gen,5)==0 用擂臺(tái)法則產(chǎn)生非支配類、支配類和不相關(guān)類; 否則轉(zhuǎn)步驟3;

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

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

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

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

4 實(shí)驗(yàn)與仿真比較

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

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

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

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

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

圖2 第5代結(jié)果

圖3 第15代結(jié)果

圖4 第20代結(jié)果

圖5 第20代結(jié)果

圖6 第100代結(jié)果

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

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

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

圖8 NSGA-Ⅱ算法(ZDT2)

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

圖10 NSGA-Ⅱ算法(ZDT3)

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

5 結(jié)論

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

[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)代模式識(shí)別[ M]. 長沙: 國防科技大學(xué)出版社, 2003

[3]鄭金華, 蔣 浩, 鄺 達(dá), 等. 用擂臺(tái)賽法則構(gòu)造多目標(biāo)Pareto最優(yōu)解集的方法[J]. 軟件學(xué)報(bào), 2007, 18(6): 1287～1297

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

[5]崔遜學(xué), 林 闖. 一種基于偏好的多目標(biāo)調(diào)和遺傳算法[J]. 軟件學(xué)報(bào), 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