火善棟

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

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

中圖分類號：TP391 文獻(xiàn)標(biāo)志碼：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種顏色為地圖著色，使得地圖上的每一個區(qū)域著一種顏色，且相鄰區(qū)域顏色不同。圖的著色問題在組合分析和實際生活中有著廣泛的應(yīng)用背景，如任務(wù)調(diào)度、資源分配、考試安排、交通管理和排課表等。

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

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

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

1 遺傳算法在四色圖問題中的具體實現(xiàn)

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

1.2 染色體的編碼

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

1.3 染色體適應(yīng)度的計算

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

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

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

參考文獻(xiàn)：

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

清華大學(xué)出版社，2006.

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

和策略[M].機(jī)械工業(yè)出版社，2010.

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

學(xué)出版社，2002.

[4] 高一凡，編著.《數(shù)據(jù)結(jié)構(gòu)》算法實現(xiàn)及其解析[M].西安電子科技大學(xué)

出版社，2002.

[5] 程杰編著.大話數(shù)據(jù)結(jié)構(gòu)[M].清華大學(xué)出版社，2011.

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