求解圖著色問(wèn)題的混合遺傳算法.pdf

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

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