遺傳算法在GIS中的應(yīng)用

姚李虎 張?jiān)獥? 南楠 上官淵

摘要：隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，伴隨其發(fā)展起來的GIS技術(shù)也不斷提高并為各行各業(yè)應(yīng)用。將數(shù)學(xué)、計(jì)算機(jī)科學(xué)和信息科學(xué)領(lǐng)域知識(shí)聯(lián)系起來應(yīng)用于地學(xué)研究，可以有效提高GIS空間數(shù)據(jù)分析和地理空間問題模擬的準(zhǔn)確度。遺傳算法是實(shí)現(xiàn)地理空間問題決策化工具。

關(guān)鍵詞：GIS技術(shù)；遺傳算法；地理空間問題

引言

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

1.遺傳算法介紹

遺傳算法是根據(jù)達(dá)爾文的進(jìn)化論模仿自然界生物進(jìn)化得到的一種全局優(yōu)化方法。與傳統(tǒng)的搜索方法不同，遺傳 算法是基于自然選擇和種群基因的一種隨機(jī)搜索算法[1]。

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

2.遺傳算法在GIS中的應(yīng)用

2.1并行遺傳算法在軟件可靠性優(yōu)化中的應(yīng)用

對(duì)于軟件的可靠性優(yōu)化，也就是在完全固定的資源模式之下，找出一種能夠?qū)④浖母鞣矫嫘阅苓M(jìn)行更完善分配的對(duì)策，從而使得運(yùn)行的系統(tǒng)有更高的穩(wěn)定性和可靠度，為企業(yè)在生產(chǎn)過程中提供更高的經(jīng)濟(jì)利益。而遺傳算法在這個(gè)過程中，能夠很好地將軟件運(yùn)用模擬生物化的方法來進(jìn)行搜索，從而優(yōu)化使用方案，在解決這個(gè)問題上，遺傳算法顯示出了自身強(qiáng)大的優(yōu)勢(shì)[2]。

并行遺傳算法是在傳統(tǒng)遺傳算法的基礎(chǔ)上進(jìn)行改進(jìn)以提高其運(yùn)算速度。一般而言，它通過運(yùn)用遷移策略和適應(yīng)度函數(shù)可以有效地抑制早熟現(xiàn)象，在接近收斂時(shí)能夠繼續(xù)優(yōu)化，并獲得局部最優(yōu)解。

2.2混合 DNA 遺傳算法在實(shí)際應(yīng)急救援路徑方案設(shè)計(jì)中的應(yīng)用

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

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

2.3基于改進(jìn)的遺傳算法的航空運(yùn)輸系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

研究國內(nèi)外航空運(yùn)輸業(yè)的發(fā)展歷程，尤其是航空運(yùn)輸系統(tǒng)的發(fā)展歷程，對(duì)主流航空運(yùn)輸系統(tǒng)的設(shè)計(jì)模式有一定的了解后重點(diǎn)研究配送過程中飛行路線的優(yōu)化問題。飛行路線的優(yōu)化是航空運(yùn)輸業(yè)最需要解決、優(yōu)化的問題，為了有效解決飛行路線的優(yōu)化，使系統(tǒng)適合國內(nèi)用戶使用習(xí)慣及行業(yè)現(xiàn)狀。

對(duì)遺傳算法進(jìn)行改進(jìn)，設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于 B/S 結(jié)構(gòu)的航空運(yùn)輸系統(tǒng)。該系統(tǒng)包含了前臺(tái)登錄、后臺(tái)管理、航班信息管理、客戶信息管理、發(fā)貨管理、報(bào)表管理等功能。其中發(fā)貨管理部分將遺傳算法應(yīng)用并實(shí)現(xiàn)到本系統(tǒng)上，最終給出一個(gè)合理、有效的基于遺傳算法的航空運(yùn)輸系統(tǒng)。這樣一個(gè)系統(tǒng)對(duì)于減少企業(yè)運(yùn)營成本、改善經(jīng)營狀況有著很大的幫助[4]。

2.4基于遺傳算法的動(dòng)態(tài)路徑優(yōu)化

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

對(duì)路網(wǎng)的建立和動(dòng)態(tài)路徑優(yōu)化算法進(jìn)行了深入研究，將道路上的實(shí)時(shí)交通流信息轉(zhuǎn)化為路權(quán)，并用改進(jìn)的遺傳算法動(dòng)態(tài)地進(jìn)行路徑優(yōu)化，建立動(dòng)態(tài)路網(wǎng)模型。改進(jìn)的遺傳算法避免了車輛在行駛中進(jìn)入擁擠區(qū)域，減少了車輛的排隊(duì)等候時(shí)間，提高了路徑優(yōu)化的動(dòng)態(tài)性和實(shí)時(shí)性[5]。

2.5優(yōu)化遺傳算法的模糊聚類在圖像分割算法中的應(yīng)用

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

在圖像分割時(shí)，采用優(yōu)化遺傳算法，能夠有效的對(duì)圖像分割的約束條件和相關(guān)的交叉參數(shù)進(jìn)行設(shè)置，通過對(duì)對(duì) FCM圖像分割算法的分析，最終得出函數(shù)的優(yōu)化條件，說明了遺傳算法的模糊聚類在圖像分割有效性[6]。

3.總結(jié)

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

參考文獻(xiàn)

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

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

[3] 聞?dòng)駝? 混合DNA遺傳算法及其在組合優(yōu)化中的應(yīng)用[D]. 遼寧科技大學(xué)， 2013.

[4] 高慶. 基于改進(jìn)的遺傳算法的航空運(yùn)輸系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D]. 吉林大學(xué)， 2013.

[5] 李云. 基于遺傳算法的動(dòng)態(tài)路徑優(yōu)化[D]. 太原理工大學(xué)， 2013.

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