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

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