混合遺傳算法自適應策略研究

陳雄峰，曾霞霞，徐 戈1,

(1.福建省信息處理與智能控制重點實驗室(閩江學院)， 福建 福州 350108；2.閩江學院計算機與控制工程學院， 福建 福州 350108)

0 引言

混合遺傳算法因其結合了全局探索與局部搜索，可折中平衡二者的搜索能力，非常利于搜索復雜的解空間，能有效處理大規模NP難組合優化問題[1]。然而，混合遺傳算法必須進行大量的適應值估算，且種群容易失去多樣性，影響進化效率，所需的計算時間較長[1-2]。問題針對性設計和自適應策略是改進混合遺傳算法性能的兩個主要措施。它是利用問題領域先驗知識增強算法的整體性能，然而人們對NP難問題內部結構的先驗領域知識總是有限的，通過人工實驗設置的參數往往無法使混合遺傳算法達到滿意的搜索效率，因此需要自適應策略。自適應策略利用搜索過程中獲得的信息，通過自適應的機制和參數來控制算法的多個方面，如搜索強度、種群多樣性等，使得搜索過程可動態適應問題解空間的適應值地貌特征，從而提高算法搜索效率。近十來年，自適應策略逐漸成為了混合遺傳等啟發式算法研究的最新趨勢，其中參數和算子自適應策略是具有很好前景的重要研究方向[3]。

自適應策略主要包括局部搜索概率、局部搜索個體選擇與強度和模因(meme)選擇與搜索過程等方面[1-3]。局部搜索概率自適應旨在更好地分配基于種群的全局探索與基于個體的局部搜索的計算時間。局部搜索個體選擇自適應則可增強獲得高質量問題解的整體效率[1,4]?！?br>