遺傳算法及其在地圖自動(dòng)著色中的應(yīng)用研究

摘 要：遺傳算法作為一種全新的和有效的全局優(yōu)化算法，在很多的領(lǐng)域得到了廣泛的應(yīng)用。本文結(jié)合一個(gè)典型的制圖問(wèn)題——地圖自動(dòng)著色，通過(guò)研究學(xué)習(xí)遺傳算法在該問(wèn)題中應(yīng)用的相關(guān)文獻(xiàn)，深入理解了遺傳算法求解問(wèn)題的過(guò)程與思路，并對(duì)遺傳算法應(yīng)用效果和改進(jìn)措施進(jìn)行了探討，最后對(duì)遺傳算法的優(yōu)缺點(diǎn)進(jìn)行了總結(jié)。

關(guān)鍵詞：遺傳算法；混合遺傳算法；地圖著色；四色問(wèn)題；

文章編號(hào)：1674-3520（2015）-12-00-01

一、引言

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

為了深入理解遺傳算法的原理及其求解問(wèn)題的過(guò)程，本文結(jié)合一個(gè)典型的實(shí)際問(wèn)題——地圖四色著色問(wèn)題，對(duì)遺傳算法用于求解地圖四色著色問(wèn)題的具體過(guò)程進(jìn)行了學(xué)習(xí)，在此基礎(chǔ)上，簡(jiǎn)要探討了遺傳算法的改進(jìn)措施，最后總結(jié)了遺傳算法的優(yōu)缺點(diǎn)。

二、遺傳算法在地圖自動(dòng)著色中的應(yīng)用

在對(duì)相關(guān)文獻(xiàn)進(jìn)行研究的基礎(chǔ)上，本文對(duì)遺傳算法用于求解地圖自動(dòng)著色問(wèn)題的過(guò)程重新進(jìn)行了梳理，通過(guò)該實(shí)例詳細(xì)地闡述了遺傳算法的原理及其求解問(wèn)題的過(guò)程。

地圖著色是指在地圖的編制過(guò)程中，為了區(qū)分地圖上不同的屬性區(qū)域，需要用不同的顏色對(duì)每一塊區(qū)域進(jìn)行填涂，同時(shí)要求相鄰的兩塊區(qū)域不能填涂同一種顏色。著名的四色定理提出，不論多么復(fù)雜的地圖，只要用四種顏色就可以使相鄰2個(gè)區(qū)域的顏色不同，四色定理的成功證明為地圖四色著色提供了依據(jù)。尋求一種較合理的優(yōu)化算法來(lái)解決地圖四色著色問(wèn)題就變得十分關(guān)鍵和重要。

地圖著色問(wèn)題可以具體地表述為：用四種顏色（如紅、黃、藍(lán)、綠）對(duì)某幅行政區(qū)地圖實(shí)現(xiàn)計(jì)算機(jī)自動(dòng)著色，要求相互鄰接的任意兩個(gè)行政區(qū)多邊形不能著相同顏色。

用四種不同顏色對(duì)所有結(jié)點(diǎn)進(jìn)行著色，使得相互鄰接的任意兩個(gè)結(jié)點(diǎn)不能著相同顏色。對(duì)地圖進(jìn)行四色著色的問(wèn)題就轉(zhuǎn)換成了對(duì)無(wú)向連通平圖面的結(jié)點(diǎn)進(jìn)行四色著色的問(wèn)題。在遺傳算法中我們可以采用多種形式的條件來(lái)終止算法的執(zhí)行，同時(shí)又總是希望得到滿意的解。常用的終止條件有以下兩個(gè)方面：（1）當(dāng)代群體中最大適應(yīng)度與最小適應(yīng)度之差小于某個(gè)預(yù)先給定的誤差（也稱信度）A，即在A水平下個(gè)體差異已經(jīng)趨于穩(wěn)定，此時(shí)可以終止算法。（2）控制最大遺傳代數(shù)M，即給定正整數(shù)M，最多遺傳到第M代時(shí)，必須終止?？梢钥闯觯簵l件（1）、（2）下算法必然會(huì)終止，終止后，在產(chǎn)生的當(dāng)代群體中選擇適應(yīng)度最大的一個(gè)個(gè)體作為問(wèn)題的解。對(duì)于地圖四色著色問(wèn)題：由于最優(yōu)解存在，我們應(yīng)該將M取得適當(dāng)大，以保證問(wèn)題最終能有答案。

三、遺傳算法在地圖自動(dòng)著色中的應(yīng)用結(jié)果分析及改進(jìn)

目前，地圖四色自動(dòng)著色的實(shí)現(xiàn)算法有很多，如遞歸算法、回溯算法、貪心算法等，但隨著區(qū)域數(shù)目的增加和鄰接關(guān)系的復(fù)雜化，以上算法就會(huì)效率低下，顯得難以勝任了。作為一種擅長(zhǎng)自適應(yīng)全局優(yōu)化的智能優(yōu)化算法，遺傳算法已經(jīng)成功地應(yīng)用到了地圖自動(dòng)著色問(wèn)題中。相關(guān)的文獻(xiàn)說(shuō)明遺傳算法可以有效解決地圖自動(dòng)著色問(wèn)題，相對(duì)于傳統(tǒng)的優(yōu)化算法來(lái)說(shuō)，它具有相當(dāng)大的優(yōu)勢(shì)，它可以避免陷入局部單峰極值點(diǎn)，具有良好的全局搜索性能。但是由于遺傳算法會(huì)表現(xiàn)出早熟現(xiàn)象、局部尋優(yōu)能力較差等不足，遺傳算法有時(shí)不是最成功的優(yōu)化算法。因此，需要對(duì)遺傳算法進(jìn)行相應(yīng)的改進(jìn)來(lái)進(jìn)一步提高遺傳算法求解問(wèn)題的效率。

在地圖自動(dòng)著色問(wèn)題中，一些學(xué)者針對(duì)遺傳算法局部搜索能力不足的缺點(diǎn)，提出了將具有較優(yōu)的局部搜索能力的優(yōu)化算法引入遺傳算法，建立混合遺傳算法，遺傳算法與現(xiàn)有優(yōu)化算法相結(jié)合可以互相取長(zhǎng)補(bǔ)短，取得更優(yōu)的效果。在地圖自動(dòng)著色問(wèn)題中，李曉年等將模擬退火算法引入遺傳算法，使它們結(jié)合起來(lái)解決地圖四色填充問(wèn)題，從而形成相對(duì)優(yōu)化的算法，改進(jìn)算法的收斂速度更平穩(wěn)，整個(gè)搜索過(guò)程朝著全局最優(yōu)的方向發(fā)展。韓云等研究了結(jié)合貪心算法的混合遺傳算法求解行政區(qū)劃圖四色問(wèn)題，遺傳算法的全局搜索能力保證了搜索過(guò)程向全局最優(yōu)解搜索， 同時(shí)保留了貪心算法局部搜索的高效性。

四、總結(jié)

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

遺傳算法是解決復(fù)雜問(wèn)題的有力工具，具有諸多優(yōu)點(diǎn)，但是由于受其本身一些特性的限制，遺傳算法也存在早熟收斂、進(jìn)化時(shí)間長(zhǎng)、參數(shù)選擇困難、計(jì)算效率問(wèn)題等一些不足。因此，在選擇使用遺傳算法求解問(wèn)題時(shí)，需要結(jié)合待優(yōu)化的問(wèn)題進(jìn)行全面地考慮，以合理適當(dāng)?shù)貞?yīng)用遺傳算法，達(dá)到最優(yōu)的效果。

參考文獻(xiàn)（References）：

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

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

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

[4]宇亞衛(wèi).基于遺傳算法的圖著色的研究與實(shí)現(xiàn)[J].西安文理學(xué)院學(xué)報(bào)：自然科學(xué)版，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.