用遺傳算法實(shí)現(xiàn)四色圖問題

火善棟

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

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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

圖的著色問題是由地圖的著色問題引申而來(lái)的：用m種顏色為地圖著色，使得地圖上的每一個(gè)區(qū)域著一種顏色，且相鄰區(qū)域顏色不同。圖的著色問題在組合分析和實(shí)際生活中有著廣泛的應(yīng)用背景，如任務(wù)調(diào)度、資源分配、考試安排、交通管理和排課表等。

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

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

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

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

1.1 地圖的簡(jiǎn)化表示及其鄰接矩陣[4]

1.2 染色體的編碼

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

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

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

學(xué)出版社，2002.

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

出版社，2002.

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

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