一種求解圖頂點著色問題的遺傳算法.pdf

1、圖頂點著色問題是經(jīng)典的組合優(yōu)化問題之一,屬于NP難問題,它不論在理論研究還是現(xiàn)實生活中均有重要的價值。在理論方面,圖頂點著色是圖論的一個重要研究方向,在圖論中占有重要的地位,廣大學(xué)者對它的不斷研究與探索極大的推動了現(xiàn)代圖論的發(fā)展。另一方面,該問題有著廣泛的應(yīng)用背景,如資源分配、超大規(guī)模集成電路布線、頻率分配等,許多領(lǐng)域的問題都可歸結(jié)為圖頂點著色問題來求解。
　　尋求高效的算法對圖著色問題進(jìn)行求解成為圖論工作者及從事工程技術(shù)方面的學(xué)

2、者研究的一個主要課題。當(dāng)問題規(guī)模較大時,不存在多項式時間內(nèi)的精確算法,因此在現(xiàn)實應(yīng)用中,啟發(fā)式算法的研究成為一個重要的方面。
　　遺傳算法作為一種全局隨機(jī)搜索和優(yōu)化的啟發(fā)式算法成為求解該問題的重要分支,它是一種利用自然選擇和進(jìn)化思想在高維空間中尋優(yōu)的方法,它不一定找到最優(yōu)點,但能在可接受的時間內(nèi)找到較優(yōu)解,而找到的解往往已能滿足實際應(yīng)用的要求。
　　在算法的設(shè)計過程中多處采取了貪心策略,每一步貪心選擇都能得到局部最優(yōu)解,實驗