一種多目標混合進化算法的研究

梁國偉　王社偉　趙雪森

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

關鍵詞：多目標優化；遺傳算法；多目標混合進化算法；ZDT測試函數

中圖分類號：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”收斂于問題的最優解，然而實踐應用中，遺傳算法會表現出早熟現象、局部尋優能力較差等不足，所以一些常規遺傳算法并不一定是針對某一問題的最佳求解方法。

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

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

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

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

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

3.1 算法的設計

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

2）交叉操作：

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

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

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

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

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

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

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

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

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

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

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

3.2 外部精英集

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

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

（如圖1）可描述為：

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

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

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

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

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

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

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

8）輸出最優解。

4 仿真實驗

4.1 仿真測試

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

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

4.3 實驗結果分析

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

5 結 論

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

參考文獻

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

[2] 張勇德，黃莎白.多目標優化問題的蟻群算法研究[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.