用遺傳算法實現四色圖問題

火善棟

摘 要： 遺傳算法是模擬生物進化過程的算法，任何問題只要能用一組合適的編碼來表示其中的一個可行解，那么這個可行解就可以看做是一個生物個體，若干個可行解就可以看做是一個生物種群。將問題的若干個可行解利用生物進化的特點，最終就可以簡單快速地得到問題的一個最優解。利用遺傳算法和四色圖問題的這一特點，通過遺傳算法實現了四色圖問題的求解。實驗證明，用遺傳算法實現類似的四色圖問題，思想簡單，收斂速度快。

關鍵詞： 四色圖問題； 遺傳算法； 染色體編碼； 鄰接矩陣

中圖分類號：TP391 文獻標志碼：A 文章編號：1006-8228（2015）03-56-02

Abstract： Genetic algorithms are algorithms to simulate biological evolution， as long as one of the feasible solution can be represented by a set of suitable code， then the feasible solution can be seen as a biological entity， serveral feasible solutions can be seen as a biological population. By using the characteristics of biological evolution with a number of feasible solutions， the optimal solution can be obtained easily and quickly. This article uses the characteristics of genetic algorithms and the four-color map problem， to solve the four-color map problem with genetic algorithm. Experiments show that， to solve a similar four-color map problem with genetic algorithms can be simply thinking and fast convergence.

Key words： four-color map problem； genetic algorithm； chromosome coding； adjacency matrix

0 引言

圖的著色問題是由地圖的著色問題引申而來的：用m種顏色為地圖著色，使得地圖上的每一個區域著一種顏色，且相鄰區域顏色不同。圖的著色問題在組合分析和實際生活中有著廣泛的應用背景，如任務調度、資源分配、考試安排、交通管理和排課表等。

19世紀50年代，英國學者提出了任何地圖都能以4種顏色來著色的4色猜想問題。過了100多年，這個問題才由美國學者在計算機上予以證明，這就是著名的四色定理。

至于圖的著色問題有很多學者提出了一些相關的算法，如：窮舉法、回溯法、貪心法、蟻群算法等，本文采用遺傳算法實現了四色圖問題。

遺傳算法[3]的工作過程實質上就是模擬生物的進化過程。首先，確定一種編碼方法，使得問題的任何一個潛在的可行解都能表示為一個“數字”染色體，然后，創建一個由隨機染色體組成的初始群體（每條染色體代表一個不同的候選解），再經過優勝劣汰、交差變異、基因突變得到一個新的群體，每個新的群體不斷如此反復，經過若干代以后，只要問題有解，遺傳算法將會收斂到一個解。遺傳算法的最大優點就是，不需要知道怎么去解決一個問題，僅需知道用怎樣的方式對可行解進行編碼，使得它能夠被遺傳機制所利用。通常情況下，代表可行解的染色體采用一系列二進制位編碼，在運行開始時，創建一個染色體群體，每個染色體都是由一組隨機的二進制位所組成，二進制位（即染色體）的長度在整個群體中都是一樣的。實驗證明，用遺傳算法實現類似的四色圖問題，思想簡單，收斂速度快。

1 遺傳算法在四色圖問題中的具體實現

1.1 地圖的簡化表示及其鄰接矩陣[4]

1.2 染色體的編碼

由于四色圖問題中每一個頂點僅限為4種顏色，故編碼后的染色體應該就代表這4種顏色信息的一個字符串，傳統的編碼方法就是把顏色變換成二進制的代碼。

1.3 染色體適應度的計算

設置一個一維數組，該數組中的每一個元素對應相應頂點的顏色信息，該顏色信息分別為0、1、2、3（這個顏色信息可以通過染色體中相應的兩個相鄰的比特位來得到），然后通過簡化圖的鄰接矩陣來計算每條染色體（候選解）的適應度。其方法是：遍歷簡化圖中的每一個頂點，通過其鄰接矩陣找到與當前頂點相連接的所有的頂點，當這個相鄰頂點與當前頂點的顏色值相等時，其適應性分數n就加1。當所有的頂點遍歷完了之后，就可以得到這條染色體的適應度fitness=1/（1+n）。通過這個公式可以看出，當n=0時，這條染色體就是問題的一個解，并且其適應度越大，其個體的適應性就越強，該個體就越有可能產生新的后代個體。

1.4 用遺傳算法求解四色圖問題的詳細求解過程

用遺傳算法實現四色圖問題時，其收斂次數和收斂時間并不與種群的大小成一定的比例關系，當種群為100和80時其收斂次數隨著種群的減少而呈現增加趨勢，收斂時間呈增多趨勢，當種群大小為70、60、50和40時，收斂次數為1，收斂時間很短，近似為0，但當種群大小為20時，迭代次數突然增大，當然迭代時間也突然增大。從這種結果也可以看出，在用遺傳求解相關問題時，種群的大小直接影響到求解問題的迭代次數和迭代時間。從表2的實驗結果也可以看出，只要比較合理地設定初始種群的大小，用遺傳算法就可以快速有效的解決類似的四色圖問題。

參考文獻：

[1] [美]Mat Buckland著，吳祖增，沙鷹譯.游戲編程中的人工智能技術[M].

清華大學出版社，2006.

[2] [美]George E Luger著，郭茂祖等譯.人工智能復雜問題求解的結果

和策略[M].機械工業出版社，2010.

[3] 王小平，曹立明著.遺傳算法：理論、應用與軟件實現[M].西安交通大

學出版社，2002.

[4] 高一凡，編著.《數據結構》算法實現及其解析[M].西安電子科技大學

出版社，2002.

[5] 程杰編著.大話數據結構[M].清華大學出版社，2011.

[6] 呂鳳詟編著.C++語言程序設計[M].清華大學出版社，2003.