劉 玉，王海起，侯金亮，陳 冉，桂 麗

（1.中國石油大學(xué)（華東） 地球科學(xué)與技術(shù)學(xué)院，山東 青島 266580；2.中國科學(xué)院寒區(qū)旱區(qū)環(huán)境與工程研究所 遙感與地理信息科學(xué)研究室，甘肅 蘭州 730000）

空間優(yōu)化選址是GIS領(lǐng)域的經(jīng)典問題之一?？臻g選址是指在一定地理區(qū)域內(nèi)為一個(gè)或多個(gè)選址對象選擇或分配位置，使某一指標(biāo)或一組指標(biāo)達(dá)到最優(yōu)的過程。該類問題常常涉及二維或高維的地理空間、大數(shù)據(jù)量、多個(gè)相互沖突的目標(biāo)函數(shù)和多個(gè)限制條件，是NP-hard組合優(yōu)化問題。與單目標(biāo)優(yōu)化問題不同，多目標(biāo)優(yōu)化問題常產(chǎn)生一組折衷解，并把這組折衷解定義為Pareto最優(yōu)解集或非支配解集。因此，傳統(tǒng)的優(yōu)化方法（如brute-force法、盲目搜索法、鄰域搜索法等）難以取得很好的效果。

模擬退火[1]、遺傳算法[2]、粒子群優(yōu)化[3]和蟻群算法[4]等智能啟發(fā)式方法，因其出色的自動(dòng)搜索能力而被用來解決選址問題。盡管這些方法可以搜索到最優(yōu)解或近似最優(yōu)解，但缺點(diǎn)是均通過特定的方式將多目標(biāo)優(yōu)化轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，忽略了多個(gè)目標(biāo)之間的制約關(guān)系，容易漏掉那些實(shí)現(xiàn)了多目標(biāo)最優(yōu)而單目標(biāo)不是最優(yōu)的選址方案[5]；另外，這些方法也沒有考慮GIS對象間的空間關(guān)系對選址的影響。因此，本文以改進(jìn)的非支配排序遺傳算法（NSGA-II）為基本算法，以選址涉及的服務(wù)人口、交通成本、道路可達(dá)性等空間因素定義多個(gè)目標(biāo)函數(shù)，以表達(dá)空間相互作用的權(quán)重矩陣為基本形式，將空間信息融合在NSGA-II算法中，從而形成了GIS空間對象的多目標(biāo)優(yōu)化選址算法流程，并以山東省10個(gè)流行病監(jiān)控點(diǎn)最優(yōu)位置的選址為案例進(jìn)行應(yīng)用分析與對比研究。

1 改進(jìn)的NSGA-II

NSGA是一種基于Pareto支配關(guān)系的多目標(biāo)優(yōu)化算法。它是一個(gè)非常有效的算法，但存在高計(jì)算復(fù)雜度、非精英策略、需設(shè)置共享參數(shù)等明顯缺點(diǎn)。為克服上述缺點(diǎn)，Deb K[6]等提出了改進(jìn)的NSGA- II。在NSGA- II中需確定每個(gè)解的支配解和被支配解，再執(zhí)行快速排序，以確定每個(gè)解的非支配等級。對于具有相同非支配等級的解，定義擁擠距離來估計(jì)某個(gè)解周圍的解密度，以取代適應(yīng)度共享機(jī)制。NSGA- II根據(jù)非支配等級選擇非支配解，當(dāng)兩個(gè)解具有相同的非支配等級時(shí)，優(yōu)先選擇擁擠距離較大的解。NSGA-II利用精英策略來保留最好的父個(gè)體和子個(gè)體，只需MN2（M為目標(biāo)個(gè)數(shù)，N為種群大?。┑挠?jì)算復(fù)雜度。這些策略使得新一代種群比前一代更有效，且解的分布范圍更好，從而收斂到真正的Pareto最優(yōu)前沿。

2 研究方法和流程

將GIS信息與多目標(biāo)遺傳算法相結(jié)合以解決空間選址問題的技術(shù)流程如圖1所示。

圖1 空間優(yōu)化選址的技術(shù)路線圖

2.1 GIS空間數(shù)據(jù)處理

本文以多個(gè)流行病監(jiān)控點(diǎn)的選址為例。疾病監(jiān)控點(diǎn)作為對人類有益的服務(wù)設(shè)施，其最優(yōu)位置的選擇需遵循[7]：①平等性：需要反映公平與公正的理念，所有人都能享受該設(shè)施提供的服務(wù)，因此決策的制定應(yīng)基于人口的分布情況；②成本有效性：確保每個(gè)人可享受服務(wù)的同時(shí)不能造成資源浪費(fèi)；③可到達(dá)性：用戶最大限度地接近服務(wù)點(diǎn)，即最小化交通費(fèi)用或時(shí)間成本?；谝陨显瓌t，流行病監(jiān)控點(diǎn)的選址與總服務(wù)人口、交通成本和道路可達(dá)性等空間因素相關(guān)。

2.2 定義目標(biāo)函數(shù)[8-9]

1）最大化服務(wù)人口。N個(gè)選址點(diǎn)的總服務(wù)人口可定義為：

式中，xi、yi為第i個(gè)選址點(diǎn)的坐標(biāo)；n為選址點(diǎn)總數(shù)；l為統(tǒng)計(jì)覆蓋人口的鄰域窗口；P'den(x, y)為動(dòng)態(tài)人口密度；A0為每個(gè)柵格單元的面積為覆蓋率的衰減函數(shù)；k為衰減函數(shù)的系數(shù)。

動(dòng)態(tài)人口密度是在每確定一個(gè)選址點(diǎn)后將其覆蓋的人口去掉重新計(jì)算獲得的，一個(gè)位置好的選址方案應(yīng)盡量覆蓋最大的人口數(shù)/服務(wù)半徑，即max fpop。

2）最小化交通成本。交通成本的定義為：

一個(gè)位置好的選址方案應(yīng)盡量降低交通出行成本，即minfcost。

3）最小化道路接近度。道路接近度的定義為：

式中，Droad為選址點(diǎn)與道路之間的距離；r為道路因子系數(shù)。

一個(gè)位置好的選址方案應(yīng)盡量接近道路，即minfroad。

2.3 染色體編碼

空間最優(yōu)選址問題，即在M1×M2個(gè)空間單元中找出n個(gè)設(shè)施的最優(yōu)(x, y)坐標(biāo)，故需設(shè)計(jì)染色體為n個(gè)選址設(shè)施的位置組合編碼。染色體可有2n個(gè)基因，每個(gè)基因代表一個(gè)x或y坐標(biāo)：

式中，(xi, yi)為第i個(gè)選址點(diǎn)的坐標(biāo)，i=1, 2,…,n。

2.4 算法流程

融合空間信息的Spatial NSGA-II（SNSGA-II）算法詳細(xì)步驟為：

1）種群初始化：隨機(jī)產(chǎn)生n個(gè)染色體表示n個(gè)個(gè)體（即n個(gè)候選選址方案）。由染色體的編碼形式可知，每個(gè)個(gè)體包含n個(gè)選址點(diǎn)。

2）建立空間權(quán)重矩陣：定義對稱的二進(jìn)制空間權(quán)重矩陣Wn×n，表示n個(gè)選址點(diǎn)之間的相互影響[10]。本文采用兩個(gè)選址點(diǎn)間的歐氏距離作為權(quán)重測度，當(dāng)?shù)趇選址點(diǎn)和第j選址點(diǎn)的距離在給定的范圍（該范圍由實(shí)際問題決定）內(nèi)時(shí)，空間權(quán)重矩陣對應(yīng)的元素Wij=1，說明第i選址點(diǎn)和第j選址點(diǎn)之間存在相互影響；否則，Wij=0說明不存在相互影響。此外，將W所有的主對角元素設(shè)置為0。

3）將空間信息融合到NSGA-II中：加權(quán)平均每個(gè)選址點(diǎn)與鄰域選址點(diǎn)的坐標(biāo)，作為該選址點(diǎn)的新位

置[11]。具體方法為：令為鄰域選址點(diǎn)x、y坐標(biāo)的平均值，即為選址點(diǎn)(xi, yi)唯一的

虛擬鄰居，(xi, yi)與(xi, yi)之間相關(guān)系數(shù)的計(jì)算公式為：

則選址點(diǎn)新的位置(x'i, y'i)為：

用新坐標(biāo)表示每個(gè)個(gè)體，形成原始種群。

4）非支配排序：以前述的3個(gè)目標(biāo)函數(shù)fpop、fcost、froad為適應(yīng)度評價(jià)函數(shù)，按非支配次序和擁擠距離將個(gè)體分類。

5）遺傳操作：定義匹配池（大小為n/2），采用錦標(biāo)賽法選擇父種群個(gè)體，對父種群個(gè)體進(jìn)行交叉和變異操作，得到子種群。

6）合并父種群和子種群，通過精英機(jī)制選擇最好的n個(gè)個(gè)體形成新一代的父種群。

7）判斷迭代終止條件，若滿足，則可視化輸出選址結(jié)果；否則，轉(zhuǎn)至步驟3）。

2.5 可視化輸出結(jié)果

利用GIS平臺提取上述算法得到的柵格數(shù)據(jù)選址結(jié)果，將柵格數(shù)據(jù)轉(zhuǎn)化為點(diǎn)數(shù)據(jù)，并顯示在地圖上。

3 應(yīng)用實(shí)例

3.1 研究區(qū)和空間數(shù)據(jù)

以山東省作為不規(guī)則的大尺度區(qū)域，給出10個(gè)流行病監(jiān)控點(diǎn)的最優(yōu)位置。選取山東省人口密度數(shù)據(jù)，并在選址過程中排除無效柵格單元，并以山東省內(nèi)鐵路網(wǎng)為道路數(shù)據(jù)，計(jì)算各柵格單元到鐵路的距離，從而獲取道路接近度（圖2）。

圖2 道路接近度圖

3.2 參數(shù)設(shè)置

算法采用Matlab 實(shí)現(xiàn)，在Intel DUO CPU 2.66GHz環(huán)境下運(yùn)行程序，選擇的種群大小為200，最大迭代次數(shù)為500，交叉率為0.98，變異率為0.01，衰減函數(shù)的系數(shù)為0.05，道路因子為0.05，鄰域窗口的大小為15。迭代終止條件是達(dá)到最大迭代次數(shù)或非支配等級最高的個(gè)體不再發(fā)生變化。另外，算法還采用了謝菲爾德大學(xué)Matlab遺傳算法工具箱中的一些函數(shù)。

3.3 實(shí)驗(yàn)結(jié)果與分析

比較標(biāo)準(zhǔn)遺傳算法（GA）、融合空間信息的遺傳算法（SGA）、NSGA-II和SNSGA-II的效果，重復(fù)運(yùn)行3 次，4種算法的實(shí)驗(yàn)結(jié)果見表1和圖3～6。

表1 4種算法的運(yùn)行時(shí)間、解的集中趨勢（均值）和離中趨勢（標(biāo)準(zhǔn)差）

使用GA的過程、參數(shù)設(shè)置等與黎夏[8]等提出的方法完全相同，采用相同的權(quán)重系數(shù)將3個(gè)目標(biāo)函數(shù)組合為單一的目標(biāo)函數(shù)，并將該目標(biāo)函數(shù)作為適應(yīng)度評價(jià)函數(shù)。圖3a表明迭代次數(shù)達(dá)到180次后，標(biāo)準(zhǔn)適應(yīng)度達(dá)到了峰值0.853 8；迭代次數(shù)達(dá)到260次時(shí)迭代過程終止。

SGA使用與GA相同的設(shè)置，并采用空間信息融合方法。圖4a表明迭代次數(shù)達(dá)到230次后，標(biāo)準(zhǔn)適應(yīng)度達(dá)到了峰值0.861 7；迭代次數(shù)達(dá)到300次時(shí)迭代過程終止。

由表1可知，GA、SGA的效率相對較低，尤其是SGA算法，其平均運(yùn)行時(shí)間為57 711 s。NSGA- II、SNSGA-II的效率有顯著提升，平均運(yùn)行時(shí)間約為20 000 s，得到的中心位置也更接近研究區(qū)域的中心（研究區(qū)域的中心坐標(biāo)為（236, 328））；但SNSGA-II算法具有更大的離中趨勢，說明解集的分布范圍更廣、多樣性更好。

比較圖3～6的b圖可知，4種選址結(jié)果中有6個(gè)選址位置接近或重合，這說明本文提出方法的穩(wěn)定性是可以接受的。另外，圖3、圖5的一些選址點(diǎn)彼此非?？拷赡苁窍萑肓司植孔顑?yōu)，而這種現(xiàn)象在融合空間信息的SGA、SNSGA-II算法中是不存在的。

綜上所述，多目標(biāo)遺傳算法可得到更加可靠的結(jié)果，空間結(jié)構(gòu)對選址結(jié)果也有較大影響。在GIS空間優(yōu)化選址過程中，采用多目標(biāo)優(yōu)化算法并考慮地理空間信息可得到更優(yōu)的結(jié)果。

圖3 GA迭代情況和選址結(jié)果

4 結(jié) 語

在考慮空間因素的基礎(chǔ)上，將GIS選址問題作為多目標(biāo)優(yōu)化問題，可獲取協(xié)調(diào)多個(gè)目標(biāo)準(zhǔn)則的一組均衡解。實(shí)際應(yīng)用表明，融合空間知識的多目標(biāo)遺傳算法可有效解決復(fù)雜的空間優(yōu)化選址問題，不僅可收斂到Pareto最優(yōu)集，而且解集的分布性更好，算法也具有很好的穩(wěn)定性。然而，本文案例僅選擇了10個(gè)，選址點(diǎn)就運(yùn)行了數(shù)小時(shí)，這將限制算法的實(shí)用性；另外，如何在多目標(biāo)優(yōu)化算法中更好地融合空間特征和約束信息也是需重點(diǎn)研究的問題之一。

圖4 SGA迭代情況和選址結(jié)果

圖5 NSGA-II迭代和選址結(jié)果

圖6 SNSGA-II迭代和選址結(jié)果

[1] Aerts J C J H, Heuvelink G B M. Using Simulated Annealing for Resource Allocation[J]. International Journal of Geographical Information Science,2002,16(6):571-587

[2] 黎夏,葉嘉安.遺傳算法和GIS結(jié)合進(jìn)行空間優(yōu)化決策[J].地理學(xué)報(bào),2004,59(5):745-753

[3] 杜國明,陳曉翔,黎夏.基于微粒群優(yōu)化算法的空間優(yōu)化決策[J].地理學(xué)報(bào),2006,61(12):1 290-1 298

[4] 何晉強(qiáng),黎夏,劉小平,等.蟻群智能及其在大區(qū)域基礎(chǔ)設(shè)施選址中的應(yīng)用[J].遙感學(xué)報(bào),2009,13(2):246-256

[5] 公茂果,焦李成,楊咚咚,等.進(jìn)化多目標(biāo)優(yōu)化算法研究[J].軟件學(xué)報(bào),2009,20(2):271-289

[6] Deb K, Pratap A, Agarwal S, et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation,2002,6(2):182-197

[7] 宋廣飛.GIS在購物中心選址中的應(yīng)用研究[D].大連:大連理工大學(xué),2008

[8] LI X, Yeh A G O. Integration of Genetic Algorithms and GIS for Optimal Location Search[J]. International Journal of Geographical Information Science,2005,19(5):581-601

[9] LI X, HE J Q, LIU X P. Intelligent GIS for Solving Highdimensional Site Selection Problems Using ant Colony Optimization Techniques[J]. International Journal of Geographical Information Science,2009,23(4):399-416

[10] 王海起,王勁峰.一種基于空間鄰接關(guān)系的k-means聚類改進(jìn)算法[J].計(jì)算機(jī)工程,2006,32(21):50-51

[11] HU T M, Sung S Y. Data Fusion in Radial Basis Function Networks for Spatial Regression[J]. Neural Processing Letters,2005,21(2):81-93