一種多目標(biāo)混合進(jìn)化算法的研究

梁國(guó)偉　王社偉　趙雪森

摘 要：針對(duì)遺傳算法的不足，提出將禁忌搜索方法、免疫算法、遺傳算法融和的多目標(biāo)混合進(jìn)化算法。該算法引入禁忌搜索法，避免了傳統(tǒng)遺傳算法早熟現(xiàn)象的發(fā)生；引入基于濃度的自適應(yīng)變異操作，克服算法由于變異概率不變導(dǎo)致的求解過(guò)程長(zhǎng)，解的多樣性差的缺陷；引入外部精英集，避免最優(yōu)解的丟失，通過(guò)ZDT系列測(cè)試函數(shù)的仿真實(shí)驗(yàn)并與NSGA-Ⅱ算法進(jìn)行比較，驗(yàn)證了算法的有效性。

關(guān)鍵詞：多目標(biāo)優(yōu)化；遺傳算法；多目標(biāo)混合進(jìn)化算法；ZDT測(cè)試函數(shù)

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract：A multiobjective hybrid evolutionary algorithm （MHEA） was put forward aiming at the shortcomings of the traditional genetic algorithm， which combines taboo search algorithm， immune algorithm and genetic algorithm. This algorithm avoids the premature phenomenon of the traditional genetic algorithm through importing the taboo search algorithm. The operator of adaptive mutation based on the density overcomes the problem of long solving process caused by the constant mutation probability and bad diversity of the solution. Then external elite set was introduced to avoid the loss of the optimal solution. Finally the simulation of ZDT series test functions and the comparison with NSGA-Ⅱ algorithm verifies the effectiveness of the algorithm.

Key words：Multiobjective optimization；genetic algorithm； MHEA； ZDT test functions

2.3 算法簡(jiǎn)介

遺傳算法[4，5]因其高度的并行處理能力、強(qiáng)魯棒性和全局搜索能力而被廣泛地應(yīng)用于諸多領(lǐng)域。理論上遺傳算法依“概率1”收斂于問(wèn)題的最優(yōu)解，然而實(shí)踐應(yīng)用中，遺傳算法會(huì)表現(xiàn)出早熟現(xiàn)象、局部尋優(yōu)能力較差等不足，所以一些常規(guī)遺傳算法并不一定是針對(duì)某一問(wèn)題的最佳求解方法。

禁忌搜索法[6]具有靈活的記憶功能和藐視原則，并且在搜索過(guò)程中可以接受劣解，因而具有較強(qiáng)的爬山能力，搜索時(shí)能夠跳出局部最優(yōu)解，從而增強(qiáng)獲得更好的全局最優(yōu)解的概率。但其搜索性能完全依賴于鄰域結(jié)構(gòu)和初始解。

免疫算法[7]可以通過(guò)細(xì)胞的分裂和分化作用，對(duì)抗體的產(chǎn)生進(jìn)行促進(jìn)或者抑制，體現(xiàn)了自我調(diào)節(jié)功能，保證了個(gè)體的多樣性。

由于遺傳算法、禁忌搜索法、免疫算法各有優(yōu)缺點(diǎn)，因此將三種算法相結(jié)合，互相取長(zhǎng)補(bǔ)短，則可能設(shè)計(jì)出性能優(yōu)良的新的全局搜索算法，可以加快算法的收斂性同時(shí)提高算法的多樣性。

3 多目標(biāo)混合進(jìn)化算法（MHEA）

本文引入禁忌搜索法[8]，避免早熟現(xiàn)象的發(fā)生，提高了局部搜索能力；采用基于濃度的自適應(yīng)變異操作，克服了算法由于變異概率不變導(dǎo)致的求解過(guò)程長(zhǎng)，解的多樣性差的缺陷；引入外部精英集，避免了最優(yōu)解的丟失，下面介紹算法的實(shí)現(xiàn)：

3.1 算法的設(shè)計(jì)

1）將部分精英集中的個(gè)體加入到種群POP0中并進(jìn)行選擇操作，可以提高種群的收斂速度。

2）交叉操作：

由于交叉算子在搜索最優(yōu)解的進(jìn)程中是一個(gè)破壞性同時(shí)也是產(chǎn)生新解的過(guò)程，因此遺傳算法常常很快收斂到比較好的解，但是往往不能收斂到最優(yōu)解，本文采用單點(diǎn)交叉算子。

3）禁忌搜索法：利用遺傳算法與禁忌搜索法相結(jié)合，克服遺傳算法早熟和收斂慢的缺點(diǎn)，具體步驟如下：

（1）對(duì)選擇操作產(chǎn)生的新種群的個(gè)體進(jìn)行禁忌搜索；

（2）查找禁忌表中是否有此個(gè)體記錄；

（3）如果有，再看是否滿足特赦準(zhǔn)則；

（4）如果滿足特赦準(zhǔn)則，再看是否滿足收斂準(zhǔn)則；

（5）滿足收斂準(zhǔn)則，繼續(xù)進(jìn)行交叉操作，產(chǎn)生新種群，然后轉(zhuǎn)到1）；

（6）如果不滿足特赦準(zhǔn)則，禁忌表中也沒(méi)有此個(gè)體記錄，則放人禁忌表；

（7）繼續(xù)查看是否滿足收斂準(zhǔn)則，滿足后輸出結(jié)果，否則進(jìn)行上述的交叉操作。

4）基于濃度的自適應(yīng)變異算子

相比變異概率不變情況下，自適應(yīng)變異更加符合生物遺傳規(guī)律，有利于提高種群多樣性。借用免疫算法中對(duì)抗體產(chǎn)生進(jìn)行促進(jìn)或者抑制，可以自我調(diào)節(jié)，從而保證個(gè)體多樣性的思想，本文提出了一種基于濃度的自適應(yīng)變異算子。

3.2 外部精英集

由圖1可知，最初的精英集由初始群體中適應(yīng)度最高的個(gè)體填充，隨后由交叉和變異操作產(chǎn)生的最優(yōu)個(gè)體對(duì)精英集進(jìn)行更新，如果個(gè)體的數(shù)量超過(guò)檔案規(guī)模，則依據(jù)適應(yīng)度值大小對(duì)精英集進(jìn)行修剪。在種群外設(shè)置一個(gè)精英集合用于保存種群進(jìn)化每一步搜索到的非支配解。精英集合的使用將有效防止算法在搜索過(guò)程中由于隨機(jī)因素而丟失最優(yōu)解，并且能加快算法收斂速度。

3.3 多目標(biāo)混合進(jìn)化算法的步驟

（如圖1）可描述為：

1）初始化算法的參數(shù)（包括種群規(guī)模POP、禁忌表及其長(zhǎng)度、迭代次數(shù)等），隨機(jī)產(chǎn)生初始群體POP0。

2）計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度值，并將適應(yīng)度最高的個(gè)體存入精英集1中。

3）將精英集中的部分個(gè)體加入到種群中，進(jìn)行選擇操作得到種群POP1。

4）對(duì)POP1進(jìn)行禁忌搜索同時(shí)進(jìn)行交叉操作得到種群POP2，將POP2中適應(yīng)度最高的個(gè)體存入精英集2中。

5）對(duì)POP2進(jìn)行基于濃度的自適應(yīng)變異操作得到種群POP3，將POP3中適應(yīng)度最高的個(gè)體存入精英集3中。

6）更新精英集，如果個(gè)體數(shù)量超過(guò)檔案規(guī)模，則對(duì)精英集進(jìn)行修剪。

7）如果滿足終止條件，執(zhí)行步驟8，否則，轉(zhuǎn)到步驟3。

8）輸出最優(yōu)解。

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

4.1 仿真測(cè)試

為了驗(yàn)證MHEA算法解決多目標(biāo)優(yōu)化問(wèn)題的性能優(yōu)劣，將該算法與目前解決多目標(biāo)問(wèn)題較好的NSGA-Ⅱ[10]算法進(jìn)行比較分析。本文選取一組具有不同特征的benchmark問(wèn)題ZDT1、ZDT3和ZDT6作為測(cè)試函數(shù)，其中ZDT1具有Pareto最優(yōu)前沿，ZDT3具有非連續(xù)Pareto最優(yōu)前沿，ZDT6具有非凸性且非均勻Pareto最優(yōu)前沿。

測(cè)試過(guò)程中，MHEA算法和NSGA-Ⅱ算法均采用實(shí)數(shù)編碼，濃度閾值γ=0.7，交叉概率pm=0.9，變異概率pc=1/n（n為變量個(gè)數(shù)），種群規(guī)模M=200，迭代次數(shù)gen=300。在同一臺(tái)計(jì)算機(jī)上分別獨(dú)立運(yùn)行20次，從中選取最優(yōu)結(jié)果進(jìn)行比較，試驗(yàn)結(jié)果如圖所示。

4.3 實(shí)驗(yàn)結(jié)果分析

由表1可知，所提算法MHEA在優(yōu)化測(cè)試函數(shù)ZDT中的收斂性能、分布性能及多樣性均優(yōu)于算法NSGA-Ⅱ，說(shuō)明算法引用禁忌搜索法及基于濃度的自適應(yīng)變異算子是可行有效的，它能夠提高收斂性，增加群體的多樣性，但MHEA的平均運(yùn)行時(shí)間卻較長(zhǎng)，這是它在提高算法搜索性能的同時(shí)所付出的代價(jià)。

5 結(jié) 論

本文有效的結(jié)合了遺傳算法、禁忌搜索法和免疫算法的優(yōu)點(diǎn)，提出了一種多目標(biāo)混合進(jìn)化算法，提高了收斂性，同時(shí)保證了多樣性。通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性。

參考文獻(xiàn)

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

[2] 張勇德，黃莎白.多目標(biāo)優(yōu)化問(wèn)題的蟻群算法研究[J].控制與決策，2005，20（2）：170-173.

[3] COELLO COELLO C A，PULIDO G T.Handing multiple objectives with particle swarm optimization[J].IEEE Transactions on Evolutionary Computation， 2004， 8（3）： 256-279.

[4] GOLDBERG D E.Genetic Algorithm in Search， Optimization and Machine Learning[J].NJ： Addtion Wesley，1989.

[5] 王娜，向鳳紅，毛劍琳.改進(jìn)的自適應(yīng)遺傳算法求解0/1背包問(wèn)題[J].計(jì)算機(jī)應(yīng)用，2012，32（6）：1682-1684.

[6] 張文化，劉素華，侯惠芳.一種用于特征選擇的禁忌搜索算法[J].計(jì)算機(jī)應(yīng)用于軟件，2010，27（5）：125-127.

[7] 崔遜學(xué).基于免疫原理的多目標(biāo)進(jìn)化算法群體多樣性研究[J].模式識(shí)別與人工智能，2001，14（3）：291-296.

[8] B T G TAN，S M LIM.Automated Parameter Optimization for Double Frequency Modulation Synthesis Using the Genetic Annealing Algorithm[J].J Audio Eng Soc.1996，44（1）.

[9] 王潔，高家全.一種新的的免疫遺傳算法及應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件，2010，27（12）：89-91

[10]Deb K，Prata A，Agarwal S，Meyarivan T.A fast and elitist multiobjective geneticalgorithm： NSGAⅡ[C].IEEE Transactions on Evolutionary Computation， 2002， 6 （2）：182-197.

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

[12]王璇.遺傳算法的改進(jìn)及其應(yīng)用研究.[R].保定：華北電力大學(xué)，2012.