圖的四作色問題的遺傳算法求解研究

胡能發(fā) (韓山師范學(xué)院數(shù)學(xué)與信息技術(shù)系,廣東潮州521041)

唐為萍 (韓山師范學(xué)院生物系,廣東潮州521041)

1852年,英國的繪圖員費(fèi)南西斯·格斯里在為本國地圖著色時(shí),發(fā)現(xiàn)了不論多么復(fù)雜的地圖,只要用4種顏色就可以使相鄰2個(gè)地區(qū)的顏色不同,這就是著名的四色問題[1]。1878年,英國數(shù)學(xué)家凱利正式向倫敦?cái)?shù)學(xué)會(huì)提出了這一問題,從此,“四色問題”立刻引起了數(shù)學(xué)界的興趣。在長達(dá)一個(gè)半世紀(jì)的進(jìn)程中,有眾多知名學(xué)者投身于四色問題的研究中,但四色問題的研究卻進(jìn)展緩慢。1970年,有人提出一個(gè)可行的檢驗(yàn)方案,但即使在計(jì)算機(jī)幫助下,也需要將近11年才能完成。1976年6月,美國數(shù)學(xué)家Appel與Haken利用IBM360超高速計(jì)算機(jī)工作了1200多小時(shí),分析了1萬多個(gè)圖形,作了約200億個(gè)邏輯判定,終于證明了 “四色問題”的正確性,從而從理論上解決了124年之久的世界難題。Appel與Haken的基本思想是基于 “可約構(gòu)形不可避免集合”的檢驗(yàn)[2],具有較堅(jiān)實(shí)的理論依據(jù),但實(shí)際作圖中,計(jì)算時(shí)間與O(n2)成正比 (n為地圖中的地區(qū)數(shù)),所以當(dāng)n值較大時(shí),進(jìn)行實(shí)例驗(yàn)證時(shí)存在一定的困難,正如中國科學(xué)院院士張景中所述:“仍然不容易用簡單通俗的語言說得十分清楚明白,再者,由于傳統(tǒng)的用紙、筆研究數(shù)學(xué)方法的局限,使十來個(gè)點(diǎn)的圖 (十來個(gè)國家的地圖)的完整四著色分析,用手工的辦法難于進(jìn)行”[3]。而現(xiàn)實(shí)的問題是,即使采用高性能的計(jì)算機(jī),在處理大地區(qū)數(shù)且地圖中地區(qū)之間邊界較稠密的地圖四作色問題方面,仍然存在著一定的困難。通常采用的算法主要有回溯法和貪心算法。但回溯法所需時(shí)間為O(n4n)[4],對(duì)于n較大時(shí)算法不可行,貪心算法則僅對(duì)地區(qū)之間邊界較小的情況有效。為解決計(jì)算上的困難,筆者提出了一種新的求解方法,該方法首先將地圖轉(zhuǎn)化為平面圖,然后采用遺傳算法對(duì)其編碼、演化,從而確定地圖的作色方案。數(shù)值試驗(yàn)結(jié)果表明,該方法能夠高效地處理地區(qū)規(guī)模較大且地圖中地區(qū)之間邊界較稠密的地圖四著色問題,而且所得到的解全部為精確解。

1 地圖的無向圖表示

為了對(duì)任意給定的地圖 (包括平面地圖和球面地圖)作色,首先將其轉(zhuǎn)換為不帶權(quán)值的無向圖G=(V,E),其中V為圖G的頂點(diǎn)集,E為圖G的邊集。其轉(zhuǎn)換方法是,圖G的每一個(gè)頂點(diǎn)對(duì)應(yīng)地圖中的某一地區(qū),如果地圖中某2個(gè)地區(qū)之間有共同的邊界 (一條或多條邊界),則在圖G中2個(gè)對(duì)應(yīng)頂點(diǎn)之間畫一條邊 (弧),如圖1所示。在圖1中,左邊的地圖與右邊的無向圖G相對(duì)應(yīng),其中地圖中地區(qū)2與地區(qū)5、地區(qū)3和地區(qū)6只有一個(gè)公共點(diǎn),在對(duì)應(yīng)的無向圖G中沒有邊相連,地區(qū)1與地區(qū)5有2條邊界,但在平面圖中只對(duì)應(yīng)一條邊。

圖1 地圖及其相應(yīng)的無向圖G

要使整張地圖中各相鄰地區(qū)所作的顏色不同,只須確定所對(duì)應(yīng)平面圖G中各頂點(diǎn)的顏色,使任意具有相同邊的2個(gè)頂點(diǎn)作不同顏色即可。

一般來說,對(duì)于任意給定的地圖,如果地圖中存在某些地區(qū)與整塊地圖出現(xiàn)分離的情況下,則可任意作色或看成多個(gè)不同地圖分別進(jìn)行作色。例如中華人民共和國地圖中的海南省、臺(tái)灣省等,這種情況下所對(duì)應(yīng)的無向圖為非連通圖[5]。所以,不失一般性,只須討論所對(duì)應(yīng)的無向圖為連通圖的地圖作色問題即可。

2 算法設(shè)計(jì)

2.1 算法原理

遺傳算法是一種模仿生物自然進(jìn)化的概率算法[6],它通過選擇、雜交和變異等算子,按優(yōu)勝劣汰的原則生成下一代個(gè)體。遺傳算法具有高效的特點(diǎn),其關(guān)鍵在于其遺傳算子的設(shè)計(jì)。其一,通過不同母體的雜交,能產(chǎn)生不同于母體的后代,其后代保留了母體的部分優(yōu)良特征。其二,以一定的概率對(duì)個(gè)體的某些基因進(jìn)行變異,增加了群體的多樣性,從而使算法不易陷入局部最優(yōu)解。對(duì)于圖的作色問題,首先要確定個(gè)體 (染色體)的表現(xiàn)形式,將圖G所有頂點(diǎn)的作色排成一列,構(gòu)成一個(gè)個(gè)體,然后對(duì)該個(gè)體進(jìn)行適應(yīng)度評(píng)估,進(jìn)而進(jìn)行相關(guān)遺傳操作,最終得到優(yōu)化后的個(gè)體,即為圖G的一種作色方案。

2.2 編碼

對(duì)給定地圖所對(duì)應(yīng)的無向圖G=(V,E),將圖G中頂點(diǎn)集V中的所有頂點(diǎn)按自然數(shù)順序依次編號(hào),作為圖G所對(duì)應(yīng)鄰接表的數(shù)組的下標(biāo)。例如下標(biāo)為i的數(shù)組表示編號(hào)為i的結(jié)點(diǎn),鄰接表中表頭結(jié)點(diǎn)由數(shù)據(jù)域和鏈域構(gòu)成,其中數(shù)據(jù)域存放結(jié)點(diǎn)i的顏色編碼,鏈域則指向第一個(gè)與i相鄰的結(jié)點(diǎn) (表結(jié)點(diǎn));表結(jié)點(diǎn)由鄰接點(diǎn)域和鏈域構(gòu)成,其中鄰接點(diǎn)域存放與i相鄰的結(jié)點(diǎn)所對(duì)應(yīng)的數(shù)組的下標(biāo),鏈域則指向下一個(gè)與i相鄰的結(jié)點(diǎn) (表結(jié)點(diǎn))。對(duì)于四作色問題,圖1所對(duì)應(yīng)的鄰接表如圖2所示,其中C表示4種顏色的編碼,由表頭結(jié)點(diǎn)數(shù)據(jù)域中的所有C的值,構(gòu)成遺傳算法中的一個(gè)個(gè)體。對(duì)于圖2所示的鄰接表,其存儲(chǔ)結(jié)構(gòu)可形式化描述為:

圖2 圖 G的鄰接表

2.3 適應(yīng)函數(shù)

適應(yīng)函數(shù)的主要功能是用來判斷群體中所有個(gè)體質(zhì)量的好壞,直接關(guān)系到下一代群體的狀態(tài)。設(shè)計(jì)適應(yīng)函數(shù)時(shí)以鄰接表為依據(jù),如果對(duì)于鄰接表中的表頭結(jié)點(diǎn)i,其對(duì)應(yīng)的表結(jié)點(diǎn)中的所有其他結(jié)點(diǎn)的C值與之不同,則說明該結(jié)點(diǎn)具有較好的適應(yīng)度,可將表頭結(jié)點(diǎn)與表結(jié)點(diǎn)不同C值的數(shù)量記錄下來,作為評(píng)價(jià)個(gè)體中基因i(結(jié)點(diǎn)i)適應(yīng)度的依據(jù),將所有的基因i適應(yīng)度相加,即可得到整個(gè)個(gè)體的適應(yīng)值。在這里對(duì)整個(gè)個(gè)體采用了雙重評(píng)價(jià),除了評(píng)價(jià)個(gè)體的適應(yīng)度以外,還對(duì)個(gè)體中的每個(gè)基因進(jìn)行了評(píng)價(jià),這樣做的目的是為了加快演化的速度,因?yàn)樵谧儺愃阕拥倪x擇時(shí),可以優(yōu)先選擇變異那些適應(yīng)度較差的基因。

由圖G的定義知,圖G所對(duì)應(yīng)的個(gè)體編碼為G.v[1].C,G.v[2].C,…,G.v[G.vexnum].C。

定義1稱圖G的頂點(diǎn)i的適應(yīng)值為fe[i],即fe[i]為圖G的個(gè)體第i個(gè)基因的適應(yīng)值,則fe[i]的值由以下算法得到:

定義2圖G的個(gè)體的適應(yīng)值為f,則。

從以上定義可知,如果同一條邊作色相同,則對(duì)應(yīng)的函數(shù)值加1,函數(shù)值越大,說明具有相同顏色的邊越多,因此,函數(shù)值越小,所對(duì)應(yīng)的個(gè)體越好。在進(jìn)行演化時(shí),可以優(yōu)先選擇具有較小適應(yīng)值的個(gè)體。顯然,如果 f=0,所求得的個(gè)體,就是原問題的一個(gè)解,而且是精確解。

2.4 算法

為了方便算法描述,記圖G的頂點(diǎn)數(shù)G.vexnum的值為n,Gk表示由圖G所生成的第k條染色體(個(gè)體),Gk的第i個(gè)基因的適應(yīng)值記為fe(Gk[i]),則Gk的適應(yīng)值

算法中雜交母體Gk1、Gbest和Gk2分別為數(shù)組:

雜交后所生成的新個(gè)體Gnew為:

算法如下:

3 試 驗(yàn)

筆者選取了2個(gè)實(shí)例進(jìn)行仿真試驗(yàn),試驗(yàn)主機(jī)CPU配置為Intel Pentium 1.5G,內(nèi)存為512M,操作系統(tǒng)為windows2003,采用C#2005編程。

例1 中華人民共和國地圖 (如圖3)。為方便計(jì)算,用數(shù)組下標(biāo)1,2,…,27分別對(duì)應(yīng)地區(qū):新疆、西藏、甘肅、青海、四川、重慶、云南、貴州、廣西、內(nèi)蒙古、寧夏、陜西、山西、河南、湖北、湖南、廣東、遼寧、河北、山東、安徽、江蘇、黑龍江、浙江、江西、福建、吉林。由于北京、上海、天津、海南、香港、澳門、臺(tái)灣等地區(qū)與其他地區(qū)最多只有一條共公邊界,其作色問題很容易在其他27個(gè)地區(qū)作色完成后確定,所以試驗(yàn)中先對(duì)圖中27個(gè)地區(qū)進(jìn)行,再產(chǎn)生上述7個(gè)地區(qū)的作色,從而得到34個(gè)地區(qū)的圖的作色問題。算法所產(chǎn)生的顏色序列在表1中列出,其中顏色序列由1、2、3、4共4個(gè)數(shù)字組成,分別代表4種不同的顏色。

表1 中華人民共和國地圖(27個(gè)地區(qū))的四作色試驗(yàn)結(jié)果

例2 托特反例圖[7](25域3-正則平面圖,見圖4)。用1,2,…,25分別對(duì)應(yīng)字母A,B,…,Y,算法所產(chǎn)生的顏色序列在表2中列出。

圖3 中華人民共和國地圖

圖4 托特反例圖(25域3-正則平面圖)

比較發(fā)現(xiàn),筆者提出的算法與相關(guān)算法相比有較大的優(yōu)勢(shì),對(duì)地圖作色問題,前已知求得最優(yōu)解的平均時(shí)間為1724ms[8],而筆者算法所需平均時(shí)間大約為424ms,而且對(duì)于邊集密圖較高的托特反例圖,筆者算法所處理的平均時(shí)間僅為559ms。

四色問題求解算法中的染色體的基因編碼在算子雜交與變異中與傳統(tǒng)的二進(jìn)制編碼極為相似,試驗(yàn)發(fā)現(xiàn),如果采用單點(diǎn)雜交方式進(jìn)行雜交,算法將很快陷入局部解,因此,采用了3條染色體進(jìn)行雜交,并且為了保持群體的多樣性,在算法中以較大的概率加入變異算子,但發(fā)現(xiàn)算法收斂速度明顯下降,算法后期幾乎處于停止?fàn)顟B(tài),因此引入了對(duì)個(gè)體基因進(jìn)行評(píng)估的適應(yīng)函數(shù),從而明顯提高了算法效率。

表2 托特反例圖的四作色試驗(yàn)結(jié)果

算例中的托特反例圖提出的目的是為了推翻Tait的四色證明而提出來的,因此給人們的印象是不存在四作色方案,但算法在試驗(yàn)中發(fā)現(xiàn)其四作色方案眾多,因此托特反例圖不能否定Tait的四色證明,表2中僅列舉了部分四作色方案。

4 結(jié) 語

四色問題所涉及的理論和實(shí)際問題眾多,筆者僅從圖的四作色方面進(jìn)行了研究,給出了圖的四作色問題的遺傳算法的編碼方案及算法實(shí)現(xiàn)。分析發(fā)現(xiàn),該算法之所以具有較高的效率,其關(guān)鍵在于適應(yīng)函數(shù)的設(shè)計(jì)對(duì)個(gè)體進(jìn)化方向具有良好的方向性,個(gè)體基因適應(yīng)函數(shù)指導(dǎo)最差個(gè)體進(jìn)行變異,加快了算法的進(jìn)化速度。通過對(duì)34個(gè)省市自治區(qū)的中國地圖和托特反例圖的試驗(yàn),驗(yàn)證了算法在求解圖的著色問題方面具有良好的優(yōu)越性。

[1]許壽椿.圖說四色問題 [M].北京:北京大學(xué)出版社,2008.130～130.

[2]Appel k I,Haken W.Every planar map is four-colourable[J].Bull Amer Math Soc,1976,(82):711～712.

[3]張景中.新書簡介—— 《圖說四色問題》[J].數(shù)學(xué)進(jìn)展,2008,37(3):130～130.

[4]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京:電子工業(yè)出版社,2007.138～178.

[5]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu) [M].北京:清華大學(xué)出版社,1997.156～192.

[6]范小勤,胡能發(fā).雙適應(yīng)函數(shù)單親遺傳算法 [J].計(jì)算機(jī)應(yīng)用,2009,29(7):1887～1889.

[7]徐志才.四色問題的探討[J].北京郵電大學(xué)學(xué)報(bào),2003,26(2):105～112.

[8]韓云,郭慶勝,章莉萍,等.行政區(qū)劃圖自動(dòng)著色的混合遺傳算法[J].武漢大學(xué)學(xué)報(bào)·信息科學(xué)版,2007,32(8):948～751.