遺傳算法在GIS中的應用

姚李虎 張元棟 南楠 上官淵

摘要：隨著計算機技術的不斷發展，伴隨其發展起來的GIS技術也不斷提高并為各行各業應用。將數學、計算機科學和信息科學領域知識聯系起來應用于地學研究，可以有效提高GIS空間數據分析和地理空間問題模擬的準確度。遺傳算法是實現地理空間問題決策化工具。

關鍵詞：GIS技術；遺傳算法；地理空間問題

引言

隨著GIS應用水平的不斷提高，人們逐漸開始關注地理數據的模糊性、不確定性及其分析方法，顯然，傳統基于確定型數據分析模型已經不能有效地解答這一問題。同時，越來越多的復雜應用問題也對GIS空間分析功能提出了更高的要求。因此，把數學、計算機科學和信息科學領域的智能計算機技術引入地學研究，將模糊數學、神經網絡、遺傳算法等人工智能技術與GIS相結合，把不確定性的數據處理轉換成可靠的、精確的知識和信息分析，把具有高度復雜性的客觀世界的本質特征加以抽象和建模，以提高GIS空間數據分析和空間問題模擬的準確度。遺傳算法算是其中一種較常用的方法，利用遺傳算法模擬或求解地理空間問題可以解決GIS工程中的許多難題，提高GIS對非線性問題的解決能力，可以對多方面地理問題進行優化決策，最終得出較為可靠的結果。遺傳算法是實現地理空間問題決策自動化的有力工具。

1.遺傳算法介紹

遺傳算法是根據達爾文的進化論模仿自然界生物進化得到的一種全局優化方法。與傳統的搜索方法不同，遺傳 算法是基于自然選擇和種群基因的一種隨機搜索算法[1]。

遺傳算法在實現上有兩種方法：一種是種群雜交，即選擇一定數量的父代，不管王與后，任何兩個個體都可以雜交，任何兩個父代X個體雜交后產生一個相對優生的Y個體，第二代的Y個體再如同其父代一樣進行雜交，一代一代地遺傳下去，直至達到最優解；另一種是一王數后的雜交，在父代個體中，選擇一個最優的父個體X，分別與其他的母個體Y雜交，優生子個體Y1，再在Y1中選擇一個最優的個體X1作為王，丟棄不良的一個個體后，再新娶一個后Z。新王與后Z再進行雜交，一代一代進行下去，直至產生最優解。這兩種方法各有其優缺點，對于選擇范圍較小的優化問題，種群雜交的收斂速度更快些，而對于選擇范圍較大的優化問題，一王數后的雜交更有利于人工控制，并且易于收斂[1]。

2.遺傳算法在GIS中的應用

2.1并行遺傳算法在軟件可靠性優化中的應用

對于軟件的可靠性優化，也就是在完全固定的資源模式之下，找出一種能夠將軟件的各方面性能進行更完善分配的對策，從而使得運行的系統有更高的穩定性和可靠度，為企業在生產過程中提供更高的經濟利益。而遺傳算法在這個過程中，能夠很好地將軟件運用模擬生物化的方法來進行搜索，從而優化使用方案，在解決這個問題上，遺傳算法顯示出了自身強大的優勢[2]。

并行遺傳算法是在傳統遺傳算法的基礎上進行改進以提高其運算速度。一般而言，它通過運用遷移策略和適應度函數可以有效地抑制早熟現象，在接近收斂時能夠繼續優化，并獲得局部最優解。

2.2混合 DNA 遺傳算法在實際應急救援路徑方案設計中的應用

由于 DNA 計算和遺傳算法有著諸多的相似之處，將 DNA 計算引入遺傳算法進行改進，提出幾種新型的交叉算子和幾種新型的變異算子，并通過TSP 問題驗證了該算法的有效性。TSP 問題是目前研究最為廣泛的組合優化問題之一，其問題復雜性方面屬于 NP 難題，對于其近似算法的研究一直是一個世界性的重要課題。遺傳算法解答的有效性和全局最優的概率都明顯高于早期的啟發性算法，因而值得探索和研究，但標準遺傳算法存在收斂速度緩慢，容易早熟的問題，針對這一問題，提出了一類新的混合遺傳求解該類 NP 問題。仿真結果表明，該算法能夠快速收斂到問題的近似最優解，并能很好地維持種群的多樣性。因此，該方法對實際應急救援路徑方案的設計具有一定的參考價[3]值。

應急物資配送問題的研究是一項復雜的系統工程，通過研究多個配送點和多個需求點之間配送一次即可滿足需求的情形，將應急物資指揮中心的物資發放問題轉換成為了多旅行商的問題，并應用了混合 DNA 遺傳算法和新提出的交叉算子和變異算子，最后通過計算機的 Matlab 軟件進行仿真求出應急物資配送的最優解，同時印證本算法的合理性和可行性。但是不考慮道路約束以及應急點的時間限制性等，有待進步加強研究[3]。

2.3基于改進的遺傳算法的航空運輸系統的設計與實現

研究國內外航空運輸業的發展歷程，尤其是航空運輸系統的發展歷程，對主流航空運輸系統的設計模式有一定的了解后重點研究配送過程中飛行路線的優化問題。飛行路線的優化是航空運輸業最需要解決、優化的問題，為了有效解決飛行路線的優化，使系統適合國內用戶使用習慣及行業現狀。

對遺傳算法進行改進，設計并實現了一個基于 B/S 結構的航空運輸系統。該系統包含了前臺登錄、后臺管理、航班信息管理、客戶信息管理、發貨管理、報表管理等功能。其中發貨管理部分將遺傳算法應用并實現到本系統上，最終給出一個合理、有效的基于遺傳算法的航空運輸系統。這樣一個系統對于減少企業運營成本、改善經營狀況有著很大的幫助[4]。

2.4基于遺傳算法的動態路徑優化

隨著我國社會的不斷發展，交通環境不斷惡化，這都成為影響社會發展的消極因素。路徑優化可以幫助出行者尋找出合適的行駛路徑，實現交通流在整個城市路網中各路段上的最優分配，這對于解決城市交通擁擠、提高運行效率和行車安全系數、減少能源消耗以及改善交通環境等來說都具有非常積極的意義。

對路網的建立和動態路徑優化算法進行了深入研究，將道路上的實時交通流信息轉化為路權，并用改進的遺傳算法動態地進行路徑優化，建立動態路網模型。改進的遺傳算法避免了車輛在行駛中進入擁擠區域，減少了車輛的排隊等候時間，提高了路徑優化的動態性和實時性[5]。

2.5優化遺傳算法的模糊聚類在圖像分割算法中的應用

圖像分割是需要進度對多種像素進行對比分割，將圖形中的像素進行歸類分布，采用聚類的方法分析得出圖形的分割閾值，這種模糊類聚的計算方法在圖形分割中是一種常用的算法。將遺傳算法應用到各種圖形的分割計算中，對于模糊C均值 （FCM） 迭代計算，運用遺傳算法，能夠有效的解決這一問題。在一般的圖形分割中，運用遺傳算法能夠提高 FCM 算法的計算速度，圖形分割的有效性，但不能有效的對變異率 Pm 和交叉率Pc進行控制，不能夠自行調節像素搜索和分割的結果，影響分割的準確性和結果的正確性，需要遺傳算法進行優化，改變計算的約束條件，提高算法的準確性[6]。

在圖像分割時，采用優化遺傳算法，能夠有效的對圖像分割的約束條件和相關的交叉參數進行設置，通過對對 FCM圖像分割算法的分析，最終得出函數的優化條件，說明了遺傳算法的模糊聚類在圖像分割有效性[6]。

3.總結

通過對遺傳算法的研究，發現遺傳算法與傳統的搜索算法不同，主要表現在以下幾個方面：（1）遺傳算法作用于一個參數集的編碼而不是參數本身，二進制和十進制是兩種廣泛采用的遺傳算法編碼方式；（2）遺傳算法是一種多解并行搜索機制，使其能以較大的概率找到整體最優解；（3）遺傳算法用一個適應度函數來引導搜索，因而能應用到不同的問題中而不要求該問題受到某些特殊約束，入系統的連續性和可微性等；（4）遺傳算法使用隨即轉移規則而不是確定性的轉移規則。因此，遺產算法被應用于各行各業，尤其是地理問題的空間分析中，可以解決很多傳統算法無法解決的問題。

參考文獻

[1] 王平劉湘南黃方. GIS空間分析原理與方法， 科學出版社， 284-323.

[2] 周政. 并行遺傳算法在軟件可靠性優化中的應用[J]. 華章. 2013（19）： 323.

[3] 聞玉剛. 混合DNA遺傳算法及其在組合優化中的應用[D]. 遼寧科技大學， 2013.

[4] 高慶. 基于改進的遺傳算法的航空運輸系統的設計與實現[D]. 吉林大學， 2013.

[5] 李云. 基于遺傳算法的動態路徑優化[D]. 太原理工大學， 2013.

[6] 范瑜. 論優化遺傳算法的模糊聚類在圖像分割算法應用[J]. 電子測試. 2013（05）： 279-281.