遺傳算法及其在地圖自動著色中的應用研究

摘 要：遺傳算法作為一種全新的和有效的全局優化算法，在很多的領域得到了廣泛的應用。本文結合一個典型的制圖問題——地圖自動著色，通過研究學習遺傳算法在該問題中應用的相關文獻，深入理解了遺傳算法求解問題的過程與思路，并對遺傳算法應用效果和改進措施進行了探討，最后對遺傳算法的優缺點進行了總結。

關鍵詞：遺傳算法；混合遺傳算法；地圖著色；四色問題；

文章編號：1674-3520（2015）-12-00-01

一、引言

遺傳算法（Genetic Algorithm， GA）是由美國J.H.Holland博士于1975年提出的，建立在自然選擇原理和自然遺傳機制上的一種啟發式搜索方法，它根據適者生存和優勝劣汰的自然法則，模擬自然界物種的繁殖、交配和變異現象，具有廣泛的適用性和強大的全局搜索能力。遺傳算法利用簡單的編碼技術和自然選擇原理來表達復雜的現象，用于解決非常困難的優化問題。遺傳算法的求解過程類似于生物進化，它將問題的求解表示成染色體的適者生存過程，通過染色體的一代代進化，最終收斂到最適合環境的個體（問題的最優解）。GA為許多傳統優化方法難以解決的優化問題提供了嶄新的途徑，遺傳算法逐步成熟，應用日漸增多，已廣泛應用于自動控制、模式識別、智能故障診斷等諸多領域，取得了令人矚目的應用成果。

為了深入理解遺傳算法的原理及其求解問題的過程，本文結合一個典型的實際問題——地圖四色著色問題，對遺傳算法用于求解地圖四色著色問題的具體過程進行了學習，在此基礎上，簡要探討了遺傳算法的改進措施，最后總結了遺傳算法的優缺點。

二、遺傳算法在地圖自動著色中的應用

在對相關文獻進行研究的基礎上，本文對遺傳算法用于求解地圖自動著色問題的過程重新進行了梳理，通過該實例詳細地闡述了遺傳算法的原理及其求解問題的過程。

地圖著色是指在地圖的編制過程中，為了區分地圖上不同的屬性區域，需要用不同的顏色對每一塊區域進行填涂，同時要求相鄰的兩塊區域不能填涂同一種顏色。著名的四色定理提出，不論多么復雜的地圖，只要用四種顏色就可以使相鄰2個區域的顏色不同，四色定理的成功證明為地圖四色著色提供了依據。尋求一種較合理的優化算法來解決地圖四色著色問題就變得十分關鍵和重要。

地圖著色問題可以具體地表述為：用四種顏色（如紅、黃、藍、綠）對某幅行政區地圖實現計算機自動著色，要求相互鄰接的任意兩個行政區多邊形不能著相同顏色。

用四種不同顏色對所有結點進行著色，使得相互鄰接的任意兩個結點不能著相同顏色。對地圖進行四色著色的問題就轉換成了對無向連通平圖面的結點進行四色著色的問題。在遺傳算法中我們可以采用多種形式的條件來終止算法的執行，同時又總是希望得到滿意的解。常用的終止條件有以下兩個方面：（1）當代群體中最大適應度與最小適應度之差小于某個預先給定的誤差（也稱信度）A，即在A水平下個體差異已經趨于穩定，此時可以終止算法。（2）控制最大遺傳代數M，即給定正整數M，最多遺傳到第M代時，必須終止。可以看出：條件（1）、（2）下算法必然會終止，終止后，在產生的當代群體中選擇適應度最大的一個個體作為問題的解。對于地圖四色著色問題：由于最優解存在，我們應該將M取得適當大，以保證問題最終能有答案。

三、遺傳算法在地圖自動著色中的應用結果分析及改進

目前，地圖四色自動著色的實現算法有很多，如遞歸算法、回溯算法、貪心算法等，但隨著區域數目的增加和鄰接關系的復雜化，以上算法就會效率低下，顯得難以勝任了。作為一種擅長自適應全局優化的智能優化算法，遺傳算法已經成功地應用到了地圖自動著色問題中。相關的文獻說明遺傳算法可以有效解決地圖自動著色問題，相對于傳統的優化算法來說，它具有相當大的優勢，它可以避免陷入局部單峰極值點，具有良好的全局搜索性能。但是由于遺傳算法會表現出早熟現象、局部尋優能力較差等不足，遺傳算法有時不是最成功的優化算法。因此，需要對遺傳算法進行相應的改進來進一步提高遺傳算法求解問題的效率。

在地圖自動著色問題中，一些學者針對遺傳算法局部搜索能力不足的缺點，提出了將具有較優的局部搜索能力的優化算法引入遺傳算法，建立混合遺傳算法，遺傳算法與現有優化算法相結合可以互相取長補短，取得更優的效果。在地圖自動著色問題中，李曉年等將模擬退火算法引入遺傳算法，使它們結合起來解決地圖四色填充問題，從而形成相對優化的算法，改進算法的收斂速度更平穩，整個搜索過程朝著全局最優的方向發展。韓云等研究了結合貪心算法的混合遺傳算法求解行政區劃圖四色問題，遺傳算法的全局搜索能力保證了搜索過程向全局最優解搜索， 同時保留了貪心算法局部搜索的高效性。

四、總結

遺傳算法是人工智能的重要分支，它是建立在自然選擇原理和自然遺傳機制上的迭代式自適應概率性搜索方法，它能夠高效、并行的且在全局范圍內搜索最優解。與其他優化算法相比，它主要具有以下特點：1、遺傳算法對可行解的表示具有廣泛性，它不對處理對象直接操作，而是處理由編碼得到的基因個體，可以方便地應用到各種問題的求解中；2、遺傳算法對群體進行搜索，易于并行化，可同時評估搜索空間中的多個解，避免陷入局部單峰極值點，具有良好的全局搜索性能；3、遺傳算法不需輔助信息，不采用確定性規則，僅用適應度函數來評估基因個體，靠概率的變遷規則來指導搜索方向，內在啟發式隨機搜索特性和較少的限制條件，使其應用范圍得以擴大；4、遺傳算法采用自然進化機制，能有效表示復雜現象，可靠而快速地解決難題。

遺傳算法是解決復雜問題的有力工具，具有諸多優點，但是由于受其本身一些特性的限制，遺傳算法也存在早熟收斂、進化時間長、參數選擇困難、計算效率問題等一些不足。因此，在選擇使用遺傳算法求解問題時，需要結合待優化的問題進行全面地考慮，以合理適當地應用遺傳算法，達到最優的效果。

參考文獻（References）：

[1]郭慶勝，任曉燕著. 智能化地理信息處理：武漢大學出版社，2002.

[2]韓云，郭慶勝，章莉萍，孫艷.行政區劃圖自動著色的混合遺傳算法[J].武漢大學學報（信息科學版），2007，32（8）： 748-751.

[3]李曉年，張國合，朱翊，劉曉東.地圖自動著色算法研究與實踐[J].地理信息世界，2011，6： 53-59.

[4]宇亞衛.基于遺傳算法的圖著色的研究與實現[J].西安文理學院學報：自然科學版，2007，10（3）： 91-94.

[5]Gwee， B. H.， Lim， M. H.， Ho， J. S.， Solving Four-Coloring Map Problem using Genetic Algorithm[C]. The First New Zealand International Two-Stream Conference on Artificial Neural Networks and Expert Systems， New Zealand， 1993.