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

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

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