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

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

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

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

1 地圖的無向圖表示

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

圖1 地圖及其相應的無向圖G

要使整張地圖中各相鄰地區所作的顏色不同,只須確定所對應平面圖G中各頂點的顏色,使任意具有相同邊的2個頂點作不同顏色即可。

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

2 算法設計

2.1 算法原理

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

2.2 編碼

對給定地圖所對應的無向圖G=(V,E),將圖G中頂點集V中的所有頂點按自然數順序依次編號,作為圖G所對應鄰接表的數組的下標。例如下標為i的數組表示編號為i的結點,鄰接表中表頭結點由數據域和鏈域構成,其中數據域存放結點i的顏色編碼,鏈域則指向第一個與i相鄰的結點 (表結點);表結點由鄰接點域和鏈域構成,其中鄰接點域存放與i相鄰的結點所對應的數組的下標,鏈域則指向下一個與i相鄰的結點 (表結點)。對于四作色問題,圖1所對應的鄰接表如圖2所示,其中C表示4種顏色的編碼,由表頭結點數據域中的所有C的值,構成遺傳算法中的一個個體。對于圖2所示的鄰接表,其存儲結構可形式化描述為:

圖2 圖 G的鄰接表

2.3 適應函數

適應函數的主要功能是用來判斷群體中所有個體質量的好壞,直接關系到下一代群體的狀態。設計適應函數時以鄰接表為依據,如果對于鄰接表中的表頭結點i,其對應的表結點中的所有其他結點的C值與之不同,則說明該結點具有較好的適應度,可將表頭結點與表結點不同C值的數量記錄下來,作為評價個體中基因i(結點i)適應度的依據,將所有的基因i適應度相加,即可得到整個個體的適應值。在這里對整個個體采用了雙重評價,除了評價個體的適應度以外,還對個體中的每個基因進行了評價,這樣做的目的是為了加快演化的速度,因為在變異算子的選擇時,可以優先選擇變異那些適應度較差的基因。

由圖G的定義知,圖G所對應的個體編碼為G.v[1].C,G.v[2].C,…,G.v[G.vexnum].C。

定義1稱圖G的頂點i的適應值為fe[i],即fe[i]為圖G的個體第i個基因的適應值,則fe[i]的值由以下算法得到:

定義2圖G的個體的適應值為f,則。

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

2.4 算法

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

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

雜交后所生成的新個體Gnew為:

算法如下:

3 試 驗

筆者選取了2個實例進行仿真試驗,試驗主機CPU配置為Intel Pentium 1.5G,內存為512M,操作系統為windows2003,采用C#2005編程。

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

表1 中華人民共和國地圖(27個地區)的四作色試驗結果

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

圖3 中華人民共和國地圖

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

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

四色問題求解算法中的染色體的基因編碼在算子雜交與變異中與傳統的二進制編碼極為相似,試驗發現,如果采用單點雜交方式進行雜交,算法將很快陷入局部解,因此,采用了3條染色體進行雜交,并且為了保持群體的多樣性,在算法中以較大的概率加入變異算子,但發現算法收斂速度明顯下降,算法后期幾乎處于停止狀態,因此引入了對個體基因進行評估的適應函數,從而明顯提高了算法效率。

表2 托特反例圖的四作色試驗結果

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

4 結 語

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

[1]許壽椿.圖說四色問題 [M].北京:北京大學出版社,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].數學進展,2008,37(3):130～130.

[4]王曉東.計算機算法設計與分析[M].北京:電子工業出版社,2007.138～178.

[5]嚴蔚敏,吳偉民.數據結構 [M].北京:清華大學出版社,1997.156～192.

[6]范小勤,胡能發.雙適應函數單親遺傳算法 [J].計算機應用,2009,29(7):1887～1889.

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

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