移位安全區(qū)約束下的建筑物群移位免疫遺傳算法

劉遠(yuǎn)剛，李少華，蔡永香，何貞銘,馬瀟雅，李鵬程，郭慶勝，何宗宜,

1. 長江大學(xué)地球科學(xué)學(xué)院，湖北 武漢 430100； 2. 武漢大學(xué)資源與環(huán)境科學(xué)學(xué)院, 湖北 武漢 430079

地圖綜合是為了適應(yīng)地圖比例尺和制圖目標(biāo)等條件而進(jìn)行的一種地理信息提取與抽象過程[1]。地圖綜合過程中，由于比例尺縮小，不可避免地產(chǎn)生空間沖突。為了保持地圖清晰性，需要采用空間上下文相關(guān)的地圖綜合操作對各種沖突進(jìn)行處理。移位是解決地圖目標(biāo)之間鄰近沖突最常用的操作之一[2]。該操作通過調(diào)整地圖目標(biāo)的位置解決由于地圖符號重疊或靠得太近而導(dǎo)致的圖形沖突。

建筑物是普通地圖和專題地圖中一種重要的人文要素，建筑物群內(nèi)部以及建筑物與鄰近街道之間鄰近沖突解決是移位算法研究的重點(diǎn)[3-5]。針對建筑物群的移位問題，國內(nèi)外學(xué)者提出了兩類最優(yōu)化算法，即函數(shù)最優(yōu)化算法和組合最優(yōu)化算法[6]。前者將物理、數(shù)學(xué)、工程科學(xué)領(lǐng)域已經(jīng)得到廣泛應(yīng)用的各種模型用于模擬地圖綜合中的移位問題的機(jī)理，從而建立能夠考慮多種約束條件的移位數(shù)學(xué)方程式[7-11]；后者借鑒地圖注記自動配置的思路，將建筑物群移位問題視為一種排列組合問題，通過圖中建筑物位置的大量試探尋找最佳的地圖移位方案，在此過程中采用啟發(fā)式或群智能搜索算法求得最優(yōu)解或可行解。本文重點(diǎn)關(guān)注后者。

文獻(xiàn)[12]最早提出組合最優(yōu)化移位算法，分別采用最大梯度下降法和模擬退火算法對地圖上建筑物進(jìn)行迭代式的移位。作為對模擬退火移位算法的改進(jìn)，文獻(xiàn)[13]進(jìn)一步提出了同時采用移位、夸大、縮小和刪除等多算子協(xié)同的沖突處理方法。文獻(xiàn)[14]針對大規(guī)模建筑物群移位提出了一種遵循“社交適宜距離保持”的最優(yōu)化移位算法。文獻(xiàn)[15]將幾何推理和最大梯度下降法相結(jié)合，提出了地圖目標(biāo)沖突探測及其最優(yōu)化處理方法。類似的研究還有基于禁忌搜索的移位算法[16]、基于遺傳算法的移位算法[17]、基于免疫遺傳算法的移位算法[18]、基于粒子群算法的移位算法[19]、基于多種群遺傳算法的移位算法[20]。這類算法借助各種通用最優(yōu)化算法的普適性，將原本復(fù)雜的移位問題模式化，將各制圖約束條件量化為一個目標(biāo)函數(shù)，降低了算法設(shè)計(jì)和求解的難度。然而，與地圖要素空間關(guān)系和空間分布特征相關(guān)的更高層次的制圖約束的形式化與計(jì)算異常復(fù)雜[21]，難以在算法的目標(biāo)函數(shù)中準(zhǔn)確而充分地體現(xiàn)，但它們卻是地圖綜合尤其是移位操作須重點(diǎn)關(guān)注的空間特征[22]。例如，文獻(xiàn)[3,23]利用Voronoi圖構(gòu)建移位場模型，較好地保持了目標(biāo)群的相對空間關(guān)系，同時采用局部群組整體移位的方式保持建筑物群的分布模式；文獻(xiàn)[24]將建筑物群的鄰近圖作為移位幾何模型，保持建筑物群的鄰近關(guān)系和整體結(jié)構(gòu)，并將局部群組聚合為鄰近圖中的一個結(jié)點(diǎn)參與移位，以保持建筑物局部模式。因此，有必要針對移位過程中地圖目標(biāo)的空間關(guān)系和空間分布特征保持問題，采用相應(yīng)的輔助模型或移位策略對最優(yōu)化算法的約束條件加以補(bǔ)充，以提高算法對移位問題的適用性。

本文基于免疫遺傳算法提出一種顧及空間關(guān)系和空間分布特征的建筑物群最優(yōu)化移位算法。該算法將建筑物群的移位問題定義為一個多目標(biāo)最優(yōu)化問題，然后采用免疫遺傳算法求解。為了盡量保持建筑物群的空間關(guān)系和總體分布特征，采用Voronoi圖和緩沖區(qū)構(gòu)建每個建筑物的移位安全區(qū)，用于限定地圖中建筑物的移位空間；同時，采用建筑物群整體移位策略，保持局部分布模式。并在算法實(shí)現(xiàn)中引入一系列移位策略，以增強(qiáng)算法對移位問題的適用性。

1 建筑物群移位問題的形式化定義

1.1 相關(guān)約束條件

地圖綜合約束條件是地圖綜合目標(biāo)的概念化定義，也是地圖綜合結(jié)果質(zhì)量評價的依據(jù)[25]。建筑物群移位需要考慮的主要約束條件包括“地圖表達(dá)的清晰性、地圖目標(biāo)幾何形狀的相似性、空間關(guān)系與空間分布特征的一致性、地理位置的精確性”等方面。本文僅對建筑物進(jìn)行移位操作，不做縮放、變形處理，也不對地圖中道路做移位處理，因此不考慮“地圖目標(biāo)幾何形狀的相似性”，相關(guān)約束如下。

(1) 地圖表達(dá)的清晰性。地圖目標(biāo)之間的距離應(yīng)該達(dá)到制圖規(guī)范所規(guī)定的最小距離要求。例如，在距離目標(biāo)30 cm時，人眼能分辨的最小間隔距離為0.2 mm[26]。若兩個地圖目標(biāo)之間的距離小于最小距離閾值，就產(chǎn)生鄰近沖突。前人研究一般以鄰近沖突個數(shù)作為地圖表達(dá)的清晰性評價指標(biāo)，而本文采用文獻(xiàn)[27]中定義的沖突嚴(yán)重程度作為其量化指標(biāo)，此處稱之為沖突大小。將整幅地圖上所有沖突大小之和作為評價地圖清晰性的量化指標(biāo)，沖突越嚴(yán)重，清晰性越差。

(2) 地理位置的精確性。移位要改變地圖目標(biāo)的地理位置，從而導(dǎo)致地理位置精度降低。為了保證位置精度，需要根據(jù)制圖需求、制圖規(guī)范、地物類型、要素性質(zhì)等條件，設(shè)定地圖目標(biāo)的移位距離閾值R。例如，在較大比例尺地形圖上，移位距離一般不超過0.5 mm[28]。一般直接采用地圖目標(biāo)的移位距離衡量其位置精度，移位距離越大，位置精度越低。整幅地圖的地理位置精確性評價指標(biāo)可以用所有建筑物的移位距離總和、最大值、最小值、平均值等統(tǒng)計(jì)指標(biāo)來衡量[24]。

(3) 空間關(guān)系一致性。空間關(guān)系一致性主要指移位前后拓?fù)潢P(guān)系、方向關(guān)系和鄰近關(guān)系等需要保持相似性。相關(guān)約束定量化評價計(jì)算量較大，且標(biāo)準(zhǔn)難以統(tǒng)一，很難通過定量化的目標(biāo)函數(shù)來衡量。因此，需要構(gòu)建地圖輔助數(shù)據(jù)模型(例如，三角網(wǎng)、鄰近圖和Voronoi圖等)來幫助人們識別、表達(dá)和保持這些復(fù)雜的空間關(guān)系特征。本文通過構(gòu)建基于Voronoi圖和緩沖區(qū)的移位安全區(qū)限制建筑物的移位范圍，以期盡量保持移位前后空間關(guān)系的一致性，詳見1.3節(jié)。

(4) 空間分布特征一致性?？臻g分布特征一致性主要指地圖目標(biāo)群的空間分布模式的保持，包括建筑物群的局部排列模式和總體分布特征等。相關(guān)的約束指標(biāo)的計(jì)算量很大，也難以在目標(biāo)函數(shù)中表達(dá)，需要采用相關(guān)策略加以約束。對于建筑物群的局部模式需要移位前先識別之，然后移位過程中通過一定的策略加以維護(hù)[23,29]。本文借鑒文獻(xiàn)[23]中的策略，將地圖中呈陣列式、直線式、弧線式等模式分布的建筑物群作為整體移位(圖1)。移位時，將建筑物子群合并，用合并后的整體圖形參與沖突檢測和移位，移位結(jié)束后再分解。但對于建筑物分布密度這種總體空間分布特征，依然借助1.3節(jié)中構(gòu)建的移位安全區(qū)加以控制。

圖1 呈直線排列建筑物群的整體移位示意Fig.1 Schematic diagram of overall displacement of buildings arranged in a straight line

1.2 目標(biāo)函數(shù)定義

將地圖定義為由若干分區(qū)構(gòu)成的一個集合M={P1,P2,…,Pm}，其中m是分區(qū)數(shù)。每個分區(qū)是一個二元組Pi(L,O)，其中i∈{1,2,…,m}，L={l1,l2,…,lp}為道路集合，B={b1,b2,…,bq}為建筑物集合,p和q分別是分區(qū)Pi中道路和建筑物的個數(shù)。每個分區(qū)內(nèi)可能存在兩種沖突：建筑物與建筑物之間沖突(BB型沖突)、建筑物與道路之間沖突(BL型沖突)。參考文獻(xiàn)[27]，兩類沖突大小的評價函數(shù)分別定義為

fBB(bi,bj,BBmin)=max[0,(BBmin-BBDij)]

(1)

fBL(bi,lj,BLmin)=max[0,(BLmin-BLDij)]

(2)

式中，BBmin是兩個建筑物之間的最小距離閾值；BBDij是建筑物bi與bj之間的最小距離；BLmin是建筑物與道路之間的最小距離閾值；BLDij是建筑物bi與道路lj之間的最小距離，i∈{1,2,…,q}，j∈{1,2,…,p}。

g(s)=w1×f1+w2×f2+w3×f3

(3)

(4)

(5)

(6)

式中，f1代表所有BL型沖突的大小之和；f2代表所有BB型沖突大小之和，它們的值用于評價地圖清晰性，單個沖突大小采用式(1)、式(2)計(jì)算；f3代表所有建筑物移位距離總和，用于評價位置精度，其中dxi和dyi分別表示建筑物bi在X和Y方向的移位值；w1、w2和w3分別表示以上3項(xiàng)的權(quán)重。顯然，g值越小，對應(yīng)的地圖狀態(tài)越好。

1.3 移位安全區(qū)的建立

以上目標(biāo)函數(shù)中并沒有體現(xiàn)與空間關(guān)系和空間分布特征相關(guān)的約束指標(biāo)，需要補(bǔ)充相關(guān)附加條件。Voronoi圖被廣泛用于地圖中建筑物群的空間關(guān)系、空間結(jié)構(gòu)和空間分布的識別與描述[23,30]。因此，本文采用Voronoi圖進(jìn)一步約束建筑物群的移位范圍。將每個建筑物的半徑為R的緩沖區(qū)多邊形和其Voronoi多邊形疊加求交，構(gòu)建移位安全區(qū)(圖2)。這種移位安全區(qū)既可保證每個建筑物的位置精度，也能較好地保持整個建筑物群的相對空間關(guān)系和總體空間分布特征，防止產(chǎn)生拓?fù)溴e誤。

圖2 移位安全區(qū)構(gòu)建方法Fig.2 The method of constructing displacement safety zones

綜上，一個地圖分區(qū)中建筑物群的移位問題可以定義為在移位安全區(qū)限制下，求目標(biāo)函數(shù)g最小值的最優(yōu)化問題，其數(shù)學(xué)模型為

(7)

式中，g(s)為目標(biāo)函數(shù)，由式(3)給出；posi為地圖分區(qū)中第i個建筑物bi在當(dāng)前狀態(tài)s中的位置；Ωi為建筑物bi的移位安全區(qū)，其中i∈{1,2,…,q}。

2 基于免疫遺傳算法的建筑物群移位算法設(shè)計(jì)

2.1 免疫遺傳算法總體流程

免疫遺傳算法將基本遺傳算法和免疫理論相結(jié)合，有效改善了傳統(tǒng)遺傳算法早熟收斂的缺陷，提高了算法的局部和全局搜索能力[31]。文獻(xiàn)[18]將免疫遺傳算法用于解決建筑物群的移位問題，將移位候選解編碼成抗體基因，每個抗體表示地圖分區(qū)在移位過程中的某個狀態(tài)，N個抗體構(gòu)成一個種群，通過親和力函數(shù)評價單個抗體的質(zhì)量，采用免疫遺傳操作(包括精英保持策略、選擇、交叉和變異等)對種群逐步優(yōu)化，直至達(dá)到算法收斂條件，最后以末代種群中最優(yōu)抗體對應(yīng)的地圖狀態(tài)作為移位結(jié)果。本文引入移位安全區(qū)的概念對該算法加以改進(jìn)，并結(jié)合算法中抗體編碼、種群初始化、親和力函數(shù)、抗體移位空間適宜度和抗體濃度調(diào)節(jié)等環(huán)節(jié)做進(jìn)一步優(yōu)化，算法的主要流程見圖3，具體步驟如下：

圖3 算法流程Fig.3 Flow chart of the algorithm

(1) 構(gòu)建移位安全區(qū)，整個算法中抗體初始化、選擇、交叉、變異等各個環(huán)節(jié)均受移位安全區(qū)的約束。

(2) 初始化抗體種群。

(3) 對每個抗體進(jìn)行沖突檢測，并計(jì)算它們的親和力。

(4) 根據(jù)親和力挑選最優(yōu)抗體，判斷是否滿足收斂條件，即達(dá)到設(shè)定的閾值或達(dá)到最大迭代次數(shù)，若滿足則算法結(jié)束，輸出最優(yōu)抗體，否則進(jìn)入步驟(5)。

(5) 按照親和力對種群中的抗體進(jìn)行排序，并選出其中的優(yōu)秀抗體復(fù)制到免疫記憶庫。

(6) 計(jì)算抗體濃度、抗體移位空間適宜度，根據(jù)抗體親和力、抗體濃度、抗體移位空間適宜度計(jì)算抗體選擇概率。

(7) 執(zhí)行選擇、交叉和變異3項(xiàng)遺傳操作，即根據(jù)選擇概率選擇抗體，然后在選中的抗體中根據(jù)親和力大小挑選一部分進(jìn)行交叉，交叉得到的抗體再以較小的概率進(jìn)行變異。

(8) 將免疫記憶庫中的優(yōu)秀抗體和經(jīng)遺傳操作得到的新抗體合并構(gòu)成新一代抗體，然后轉(zhuǎn)入步驟(3)。

2.2 抗體編碼和種群初始化

地圖中每個建筑物移位時的試探位置所在范圍被稱為移位向量模板，主要包括離散空間移位向量模板[12-13,16]和連續(xù)空間移位向量模板[17]兩種。采用連續(xù)空間的移位向量模板，理論上可獲得更大的搜索空間，因此本文采用后者，并采用實(shí)數(shù)編碼方式表示抗體[18]。對于一個包含n個建筑物的地圖分區(qū)，以每個建筑物在X和Y方向的移位值進(jìn)行編碼，其抗體編碼長度為2n。設(shè)u為實(shí)數(shù)編碼對應(yīng)的一個抗體，表示為u={u1x,u1y,u2x,u2y,…,unx,uny}，其中uix，uiy(i=1,2,…,n)分別為第i個建筑物X方向和Y方向的移位值。

編碼時，對于每個建筑物，還需要考慮移位安全區(qū)的限制，將位于移位安全區(qū)之外的候選位置剔除。首先，對每個建筑物，生成一定數(shù)量的[-R，R]之間的隨機(jī)數(shù)對，作為其X和Y方向的初始移位量。按照初始移位量移位后，建筑物不一定保持在移位安全區(qū)之內(nèi)，需要做進(jìn)一步篩選，將移位距離大于R或移位之后建筑物超出Voronoi范圍的候選點(diǎn)剔除。如圖4所示，以某一建筑物為例說明確定建筑物候選點(diǎn)的過程。圖4(a)中虛線包圍區(qū)域?yàn)樵摻ㄖ飳?yīng)的Voronoi區(qū)域，圓形區(qū)域?yàn)橐栽摻ㄖ镏行臑閳A心，以R為半徑的緩沖區(qū)，其中包含了所有落在精度范圍內(nèi)的候選點(diǎn)。圖4(b)放大顯示了初始候選點(diǎn)；圖4(c)中為最終滿足移位安全區(qū)約束的候選點(diǎn)。為每個建筑物確定了滿足條件且足夠數(shù)量的候選點(diǎn)后，即可在此基礎(chǔ)上按照種群規(guī)模產(chǎn)生抗體的初始種群。在后續(xù)種群進(jìn)化過程中，新產(chǎn)生的抗體中每個建筑物對應(yīng)的位置也需要符合以上條件。

圖4 確定建筑物移位候選點(diǎn)的過程Fig.4 The process of determining the candidate points of building displacement

2.3 抗體親和力函數(shù)

親和力函數(shù)由目標(biāo)函數(shù)變換而來。在免疫遺傳算法中，親和力越大，對抗體的評價越好。因此，親和力函數(shù)定義為

Fit(g)=1/(1+g)

(8)

式中，F(xiàn)it(g)是關(guān)于目標(biāo)函數(shù)g的親和力函數(shù)，目標(biāo)函數(shù)定義見1.2節(jié)。g的值越小，F(xiàn)it(g)的值越大，建筑物群移位的效果越好。目標(biāo)函數(shù)g是恒大于0的，因此親和力函數(shù)Fit(g)不會出現(xiàn)小于或等于0的情況，可保證算法正常運(yùn)行。由抗體親和力確定的抗體選擇概率為

(9)

式中，F(xiàn)iti為第i個抗體的親和力值；N為種群大小。

2.4 抗體移位空間適宜度調(diào)節(jié)

移位安全區(qū)不僅限定了每個建筑物的移位范圍，其面積也可作為對應(yīng)建筑物附近區(qū)域開闊程度的量化指標(biāo)。移位操作中，筆者更希望處于開闊區(qū)域的目標(biāo)優(yōu)先移動，為其他沖突的建筑物釋放更多的移位空間。因此提出抗體移位空間適宜度的概念及其量化指標(biāo)，對那些在開闊區(qū)域具有較大移位量的抗體賦予更大的選擇概率，從而在選擇抗體時引入地圖空間格局相關(guān)干預(yù)，吸引移位向開闊區(qū)域傳播?？贵w移位空間適宜度的計(jì)算公式定義如下

(10)

式中，SFiti為第i個抗體的移位空間適宜度；ri為第i個抗體中每個建筑物的移位距離平方值與可移位面積的相關(guān)系數(shù)，可通過式(11)計(jì)算，rmin與rmax是整個種群中相關(guān)系數(shù)的最小值與最大值。

(11)

式中，Di為第i個抗體所表示的移位方案中，所有建筑物的移位距離的平方構(gòu)成的向量；Ai為所有建筑物的安全區(qū)面積構(gòu)成的向量；Var[Di]為Di的方差；Var[Ai]為Ai的方差；Cov(Di,Ai)為兩者的協(xié)方差。對應(yīng)的抗體移位空間適宜度選擇概率計(jì)算公式為

(12)

2.5 抗體濃度調(diào)節(jié)

算法中抗體的選擇概率還采用了抗體濃度進(jìn)行調(diào)節(jié)。在傳統(tǒng)的遺傳算法中，如果相似的和非最優(yōu)的抗體占了太大的比例，就需要降低它們的選擇概率，否則就很容易過早收斂。在選擇時通過適當(dāng)抑制高濃度抗體，可以有效提升種群的多樣性，從而防止早收斂。抗體濃度的計(jì)算公式為

(13)

式中，N為種群大?。籒i為與第i個抗體相似的抗體數(shù)量；Ci為第i個抗體對應(yīng)的濃度。對應(yīng)的第i個抗體的抗體濃度選擇概率的為

(14)

最后，由抗體親和力、抗體移位空間適宜度和抗體濃度共同確定的抗體的選擇概率為

Pi=αPfi+βPsi+γPdi(i=1,2,…,N)

(15)

式中，α、β和γ為3種選擇概率的權(quán)重，且滿足α+β+γ=1。

3 試驗(yàn)與討論

3.1 數(shù)據(jù)準(zhǔn)備和算法參數(shù)設(shè)置

采用C#編程語言實(shí)現(xiàn)免疫遺傳算法、沖突檢測和Voronoi圖生成等算法。基于CDT三角網(wǎng)提供的鄰近關(guān)系，對每個建筑物周圍的對象進(jìn)行距離量測，若距離小于設(shè)定的閾值，則判定為沖突，并計(jì)算沖突大小[18]。進(jìn)行移位之前先進(jìn)行初始沖突探測，若不存在沖突，則算法結(jié)束，若存在沖突，則調(diào)用免疫遺傳算法進(jìn)行移位。

試驗(yàn)數(shù)據(jù)選擇北京市中心城區(qū)部分街區(qū)的建筑物群(圖5)。地圖目標(biāo)比例尺為1∶10 000，街道符號寬1.2 mm，建筑物輪廓線寬0.1 mm，因此地圖上街道與建筑物之間最小距離閾值為0.85 mm(BLmin=0.85 mm)，建筑物之間最小距離閾值為0.3 mm(BBmin=0.5 mm)，最大移位距離設(shè)為0.5 mm(R=0.5 mm)。目標(biāo)比例尺下，由于符號擁擠產(chǎn)生了建筑物與街道、建筑物與建筑物的鄰近沖突。首先采用分治策略，以街道為邊界將地圖分為8個區(qū)，然后分別對每個分區(qū)調(diào)用算法解決沖突。

移位時，為了保持建筑物的局部模式，位于相同模式中的建筑物被作為一個整體處理[23]，即將同一模式的多個建筑物合成一個目標(biāo)，用合并后的整體圖形參與沖突檢測和移位，完成移位后再分解。因此，首先需識別各分區(qū)內(nèi)建筑物的典型模式，包括線性模式、陣列模式等。關(guān)于建筑物群的模式識別超出了本文的研究范圍，這里主要借鑒文獻(xiàn)[29]提出的識別方法。其主要思路是在構(gòu)建建筑物群鄰近圖的基礎(chǔ)上，依據(jù)格式塔完形原則，將具有相似的形狀、尺寸和方位等特征的多個建筑物劃分為模式子群。其中線性模式是最基本的模式，多個相互交錯的線性模式又可以組成更復(fù)雜的陣列模式。采用該方法從試驗(yàn)數(shù)據(jù)識別出的模式及其合并圖形，在圖5中以紅色半透明多邊形標(biāo)繪。在分區(qū)3、7、8中識別出7組建筑物線性排列。其中分區(qū)3中存在一個特大的網(wǎng)格狀建筑物群，可看作一個由4行7列線性模式復(fù)合而成的陣列模式，本可作為一個整理處理，但由于此網(wǎng)格模式內(nèi)部各列之間存在沖突(各行間無沖突)，為了解決這些沖突，將其拆分為4組縱向的線性排列分別參與移位。

結(jié)合前人經(jīng)驗(yàn)[17-18]，試驗(yàn)中將免疫遺傳算法的種群大小設(shè)為分區(qū)中初始沖突數(shù)的4倍，最大迭代次數(shù)設(shè)為分區(qū)中建筑物個數(shù)的15倍，目標(biāo)函數(shù)中各項(xiàng)權(quán)值分別為w1=100、w2=50和w3=1,交叉率、變異率分別為0.75和0.1，抗體相似度閾值為0.8，計(jì)算選擇概率時3種選擇概率的權(quán)重分別為0.5，0.25和0.25(α=0.5,β=0.25,γ=0.25)，免疫記憶庫中的優(yōu)秀抗體占種群大小的10%。

3.2 初步試驗(yàn)

調(diào)用算法對圖5中的建筑物移位，得到結(jié)果如圖6所示。表1列出了各個分區(qū)中建筑物的個數(shù)、初始沖突大小、初始沖突個數(shù)、剩余沖突大小和剩余沖突個數(shù)。總體上，初步移位后剩余沖突大小和個數(shù)仍較多，主要集中在分區(qū)3、7和8中，剩余沖突大小分別為5.14 mm,1.4 mm和2.75 mm。其他分區(qū)的剩余沖突較小，其中最大為分區(qū)6中的0.43 mm。

圖5 移位前地圖及其分區(qū)(1∶10 000放大至1∶5000)Fig.5 The map and its segments before displacement (enlarged from 1∶10 000 to 1∶5000)

圖6 初步移位結(jié)果圖(1∶10 000放大至1∶5000顯示)Fig.6 The result of preliminary displacement (enlarged from 1∶10 000 to 1∶5000)

表1顯示移位后沖突個數(shù)沒有沖突大小減少得明顯，BB沖突沒有BL沖突減少得多，這與本文所采用的目標(biāo)函數(shù)及其相關(guān)權(quán)值有關(guān)。目標(biāo)函數(shù)中將沖突大小作為地圖清晰性評價指標(biāo)，而非沖突個數(shù)。沖突大小是一種連續(xù)變量，與移位距離的單位一致，這可保持目標(biāo)函數(shù)中各項(xiàng)指標(biāo)量綱達(dá)到統(tǒng)一，并且采用這種連續(xù)變量作為地圖清晰性評價指標(biāo)可提高評價結(jié)果與視覺感受的一致性。例如分區(qū)2中剩余沖突個數(shù)雖高達(dá)4個，但對應(yīng)的沖突大小僅為0.2 mm，顯然沖突大小更符合視覺感受。目標(biāo)函數(shù)中，BL沖突比BB沖突具有更大的權(quán)值，可促進(jìn)BL沖突優(yōu)先被解決，甚至?xí)榱私鉀QBL沖突而引起新的BB沖突，這種策略是符合實(shí)際的移位操作邏輯的，因?yàn)榻ㄖ锶旱囊莆煌怯捎诮值婪枖U(kuò)寬而觸發(fā)，在移位過程中逐步傳播到遠(yuǎn)離道路的建筑物[3,23]。

表1 各個分區(qū)移位前后沖突對比

3.3 分階段漸進(jìn)式優(yōu)化試驗(yàn)

初步試驗(yàn)結(jié)果中存在不少剩余沖突。尤其在分區(qū)3、7和8中，由于建筑物較多，且在多處形成局部聚集模式，導(dǎo)致其中的移位安全區(qū)非常狹小，沖突的建筑物無法通過足夠的移位解決沖突。圖7以分區(qū)3為例標(biāo)記了存在剩余沖突的建筑物(或群組)，這些建筑物(或群組)已經(jīng)移動到安全區(qū)的邊界，已沒有進(jìn)一步移位的可能。其他分區(qū)中也存在類似情況。可見，本文提出的移位安全區(qū)對于建筑物比較擁擠區(qū)域的限制太嚴(yán)苛，需要適當(dāng)放寬條件。

圖7 分區(qū)3的初步移位結(jié)果及其移位安全區(qū)Fig.7 The preliminary displacement result of segment-3 and its displacement safety zones

為了放寬移位安全區(qū)的限制，試驗(yàn)中采用了多階段漸進(jìn)式移位策略，即分階段調(diào)用算法若干次，每次調(diào)用時，將上一次的移位結(jié)果作為輸入，這樣移位安全區(qū)也會在上一階段的基礎(chǔ)上重新生成，從而逐漸地放松移位范圍的限制。經(jīng)試探，分2～3個階段移位可得到較好的結(jié)果。因此在優(yōu)化試驗(yàn)中對每個分區(qū)分別進(jìn)行2次移位，每次的最大移位距離設(shè)為R/2(R=0.5 mm),經(jīng)2次調(diào)用算法后，移位效果明顯改善(圖8)。在優(yōu)化試驗(yàn)中，第1階段移位后，總沖突大小從36.32 mm減少到21.53 mm，再經(jīng)過第2階段處理，總沖突大小最終減少到4.61 mm，這比初步試驗(yàn)中的10.49 mm降低了不少(表2)。分區(qū)1、2、4和5中的沖突大小和沖突個數(shù)幾乎全降到了0。然而，在比較擁擠的分區(qū)3、6、7和8中，沖突大小盡管也有明顯減小，但最終無法解決所有沖突。說明當(dāng)?shù)貓D上符號密度不大，存在足夠移位空間的時，通過本文算法是能解決所有沖突的；但當(dāng)?shù)貓D上符號比較密集，沒有足夠的空間移位時，剩余的沖突無法僅通過移位解決，還需要配合采用典型化、刪除、合并等降低圖幅密度的地圖綜合操作。篇幅所限，此處不對移位之外的綜合算子做進(jìn)一步討論。

圖8 兩階段漸進(jìn)式移位結(jié)果(1∶10 000放大至1∶5000顯示)Fig.8 The result of 2-stage progressive displacement (enlarged from 1∶10 000 to 1∶5000)

表2 對各分區(qū)分別采用2階段漸進(jìn)式移位的剩余沖突變化情況

為了定量評價移位前后建筑物群的空間分布變化情況，借助Voronoi圖計(jì)算移位前后每個建筑物的空間分布密度，其公式為

(16)

式中，ai是第i個建筑物的面積；Ai是其對應(yīng)Voronoi多邊形的面積。圖9(a)是移位前后建筑物及其Voronoi圖的對比效果。在圖9(b)中橫、縱坐標(biāo)分別為移位前、后各建筑物的分布密度，通過直線擬合得到橫縱坐標(biāo)的關(guān)系為：y=0.899 8x+0.05，其確定系數(shù)(R2)為0.928 3，說明移位前后建筑物的分布密度高度相關(guān)；另外通過統(tǒng)計(jì)計(jì)算得到每個建筑物移位前后分布密度比值的平均值為0.979、標(biāo)準(zhǔn)差為0.078，說明位移前后建筑物分布密度比值集中分布于0.979附近(圖9(c))，從定量角度說明本算法良好地保持了建筑物群相對位置關(guān)系和空間分布特征。

圖9 移位前后建筑物的分布密度對比Fig.9 Comparison of distribution densities before and after displacement

3.4 對比試驗(yàn)

為了進(jìn)一步證明本文相對于以往算法的改進(jìn)是有效的，筆者模擬了文獻(xiàn)[18]的算法，并將試驗(yàn)結(jié)果與3.3節(jié)中的優(yōu)化試驗(yàn)結(jié)果作對比。文獻(xiàn)[18]中采用半徑為R的矩形區(qū)域作為建筑物的移位范圍，采用沖突個數(shù)作為地圖清晰性評價指標(biāo)。因此，該算法中目標(biāo)函數(shù)(式(3))的前兩項(xiàng)f1和f2分別是BL沖突個數(shù)和BB沖突個數(shù)，f3仍然是總移位距離，對應(yīng)的權(quán)值w1、w2和w3分別設(shè)置為100、50和10。為了具有可比性，其他參數(shù)與3.1節(jié)中的設(shè)置保持一致。對比試驗(yàn)結(jié)果如圖10所示，從視覺效果看，結(jié)果并不理想，在建筑物分布比較稠密的分區(qū)3中甚至出現(xiàn)了多處拓?fù)溴e誤，即建筑物與建筑物、建筑物與街道中心線的重疊。

表3列舉了本文算法和文獻(xiàn)[18]算法的剩余沖突對比情況。文獻(xiàn)[18]算法剩余沖突大小為17.65 mm遠(yuǎn)大于本文算法的4.61 mm，說明本文算法更優(yōu)。而文獻(xiàn)[18]算法的剩余沖突個數(shù)卻僅為31個，比本文算法的51個少很多，這與圖8和圖10中的視覺感受并不一致。與之前的試驗(yàn)結(jié)果類似，剩余沖突基本集中在分區(qū)3、6、7和8中，尤其是分區(qū)3中甚至產(chǎn)生了7個嚴(yán)重的拓?fù)溴e誤。證明本文提出的移位安全區(qū)對于保持建筑物群的空間關(guān)系和分布特征、防止移位中產(chǎn)生嚴(yán)重的拓?fù)溴e誤是有十分有效的。當(dāng)?shù)貓D上建筑物比較密集，且沒有移位安全區(qū)的限制時，算法可能會為了減少沖突個數(shù)而容忍非常嚴(yán)重鄰近沖突或拓?fù)溴e誤產(chǎn)生。因?yàn)檫@種沖突可以為周圍的地圖目標(biāo)騰出更多的空白區(qū)域，從而有效減少沖突個數(shù)，而這種情況在實(shí)際地圖綜合過程中是不可接受的。這也說明從提高算法穩(wěn)定性角度考慮，采用“沖突大小”代替“沖突個數(shù)”作為地圖清晰性評價指標(biāo)更合理。

圖10 文獻(xiàn)[18]算法移位結(jié)果圖(1∶10 000放大至1∶5000)Fig.10 The result of the algorithm in reference [18] (enlarged from 1∶10 000 to 1∶5000)

表3 本文算法與文獻(xiàn)[18]算法剩余沖突對比

表4分別給出了兩組試驗(yàn)的移位量統(tǒng)計(jì)值?？梢钥闯?，本文算法的移位距離被嚴(yán)格控制在距離閾值0.5 mm之內(nèi)，說明采用移位安全區(qū)對保證建筑物的位置精度是可靠的。兩者的總移位量分別為50.32 mm和39.87 mm，雖然本文算法的總移位量略大，但這些移位對于解決沖突更有效。為說明其有效性，此處提出移位效率的概念，用于定量評價移位總距離對解決沖突的有效程度，其計(jì)算公式為

表4 本文算法與文獻(xiàn)[18]算法移位距離對比

(17)

式中，τ為移位效率；initalCtotal和remainderCtotal分別為初始總沖突大小和剩余總沖突大??；displacementtotal表示總的移位量。經(jīng)計(jì)算，本文算法移位效率為63.0%，而文獻(xiàn)[18]算法移位效率僅為46.8%。

4 結(jié) 論

將免疫遺傳算法用于建筑物群移位問題，對相關(guān)約束指標(biāo)進(jìn)行定量化評價，建立通用的目標(biāo)函數(shù)，再借助智能優(yōu)化算法從全局角度解決沖突，降低了移位算法的設(shè)計(jì)難度，但仍需要在算法中引入更多與制圖綜合相關(guān)的補(bǔ)充條件和后繼策略。針對移位過程中地圖目標(biāo)群的空間關(guān)系和空間分布特征一致性保持問題，本文提出移位安全區(qū)約束下的建筑物群移位免疫遺傳算法，將建筑物群的緩沖區(qū)和Voronoi圖疊加，構(gòu)建每個建筑物的移位安全區(qū)，可有效保持移位前后的空間關(guān)系和全局空間分布特征的一致性，避免了嚴(yán)重拓?fù)溴e誤的產(chǎn)生；同時，采用建筑物模式整體移位策略，可有效保持建筑物群的局部模式。

在算法的目標(biāo)函數(shù)中，采用沖突大小(連續(xù)變量)作為地圖清晰性的評價指標(biāo)，比沖突個數(shù)(離散變量)更符合人類視覺感受。對于高密度區(qū)域，構(gòu)建的移位安全區(qū)過于狹窄，導(dǎo)致較多剩余沖突無法解決，實(shí)際應(yīng)用中可采用分階段漸進(jìn)式移位策略，適當(dāng)放松移位安全區(qū)的限制，從而更充分地解決沖突。

本文所采用的免疫遺傳算法比較耗時，且相關(guān)參數(shù)的設(shè)置對移位效果和算法的收斂性有一定影響，其選擇缺少普適方法，還需依靠經(jīng)驗(yàn)。下一步將針對算法效率的提高、算法參數(shù)設(shè)置等問題進(jìn)行更深入的研究。試驗(yàn)結(jié)果也表明，僅僅采用移位并不能解決所有沖突，還需將移位操作與其他地圖綜合算子結(jié)合，協(xié)同處理各類沖突。