梁國偉　王社偉　趙雪森

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

關鍵詞：多目標優(yōu)化；遺傳算法；多目標混合進化算法；ZDT測試函數(shù)

中圖分類號：TP18 文獻標識碼：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 算法簡介

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

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

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

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

3 多目標混合進化算法（MHEA）

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

3.1 算法的設計

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

2）交叉操作：

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

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

（1）對選擇操作產生的新種群的個體進行禁忌搜索；

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

（3）如果有，再看是否滿足特赦準則；

（4）如果滿足特赦準則，再看是否滿足收斂準則；

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

（6）如果不滿足特赦準則，禁忌表中也沒有此個體記錄，則放人禁忌表；

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

4）基于濃度的自適應變異算子

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

3.2 外部精英集

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

3.3 多目標混合進化算法的步驟

（如圖1）可描述為：

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

2）計算種群中每個個體的適應度值，并將適應度最高的個體存入精英集1中。

3）將精英集中的部分個體加入到種群中，進行選擇操作得到種群POP1。

4）對POP1進行禁忌搜索同時進行交叉操作得到種群POP2，將POP2中適應度最高的個體存入精英集2中。

5）對POP2進行基于濃度的自適應變異操作得到種群POP3，將POP3中適應度最高的個體存入精英集3中。

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

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

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

4 仿真實驗

4.1 仿真測試

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

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

4.3 實驗結果分析

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

5 結 論

本文有效的結合了遺傳算法、禁忌搜索法和免疫算法的優(yōu)點，提出了一種多目標混合進化算法，提高了收斂性，同時保證了多樣性。通過仿真實驗驗證了算法的有效性。

參考文獻

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

[2] 張勇德，黃莎白.多目標優(yōu)化問題的蟻群算法研究[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] 王娜，向鳳紅，毛劍琳.改進的自適應遺傳算法求解0/1背包問題[J].計算機應用，2012，32（6）：1682-1684.

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

[7] 崔遜學.基于免疫原理的多目標進化算法群體多樣性研究[J].模式識別與人工智能，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] 王潔，高家全.一種新的的免疫遺傳算法及應用[J].計算機應用與軟件，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]鄭金華.多目標進化算法及其應用[M].北京：科學出版社，2007.

[12]王璇.遺傳算法的改進及其應用研究.[R].保定：華北電力大學，2012.