改進(jìn)的遺傳與模擬退火算法在地圖自動(dòng)著色上的應(yīng)用.pdf

1、四色定理又稱四色猜想或稱四色問(wèn)題,是指任何一幅地圖,只用四種顏色,就可以把每塊區(qū)域染上一種顏色,并使相鄰區(qū)域的顏色不同。四色定理的成功證明使地圖制圖在效率上得到了很大的提升,所以,尋求一種較合理的優(yōu)化算法來(lái)解決地圖四色填充問(wèn)題就變的很有意義。傳統(tǒng)的算法只能應(yīng)用于處理問(wèn)題維度較小的情況,一旦問(wèn)題規(guī)模出現(xiàn)很大的情況,這種算法的耗時(shí)往往呈指數(shù)增長(zhǎng),所以,一種高效的智能優(yōu)化算法的提出就顯得很有必要。本文首先通過(guò)分析地圖四色填充問(wèn)題的研究背景和國(guó)

2、內(nèi)外研究現(xiàn)狀,提出了用一種高效的智能優(yōu)化算法來(lái)解決地圖四色填充問(wèn)題的重要性和實(shí)用性。然后從地圖著色問(wèn)題的數(shù)學(xué)模型入手,提出地圖著色問(wèn)題的解決思路。接著對(duì)現(xiàn)有的搜索算法——遺傳算法和模擬退火算法的原理、思想、特點(diǎn)進(jìn)行了較為詳細(xì)的分析,并分別總結(jié)出這些算法在實(shí)現(xiàn)地圖四色填充過(guò)程中的優(yōu)點(diǎn)與不足之處,通過(guò)對(duì)比分析,提出了利用遺傳算法與模擬退火算法的優(yōu)勢(shì)互補(bǔ),在遺傳算法的運(yùn)行中引入模擬退火算法,找到這兩種算法的結(jié)合點(diǎn),對(duì)遺傳算法進(jìn)行改進(jìn)優(yōu)化。然后