求解圖著色問題的混合遺傳算法.pdf

1、遺傳算法是模擬自然界生物進化過程與機制來求解優(yōu)化問題的一類自組織、自適應的隨機搜索算法，其編碼技術和遺傳操作比較簡單，對優(yōu)化問題的限制性條件要求很低，具有很強的并行性和全局搜索能力。它能解決很多類實際問題，目前已經在機器學習、模式識別、圖像處理、優(yōu)化控制、組合優(yōu)化和管理決策等領域得到了很好的應用。 首先，圖著色問題是一種經典的NP-完全問題。針對圖著色問題對頂點劃分的本質特征，提出了基于度的種群初始化方法和交集雜交算子：為加快算

2、法的收斂速度，設計了新的貪婪局部搜索算子來改進雜交產生的后代個體。在此基礎上，提出了求解圖著色問題的一種新的混合遺傳算法，對10個標準算例的仿真結果表明，新混合遺傳算法可以獲得問題高質量的解，是一種有潛力的算法。 其次，基于頂點分割的特點，提出了圖著色問題的一種新解法。采用概率矩陣表示種群中的解，大大地節(jié)省了存儲空間；為了加快算法的收斂速度，結合了一個局部搜索算子提高雜交產生的后代個體的質量；當概率矩陣中的元素取1或0時，算法停