李國輝，龍毅＊，周侗，3，許文帥，陳林

（1.南京師范大學地理科學學院，江蘇 南京 210023；2.虛擬地理環(huán)境教育部重點實驗室，江蘇 南京 210023；3.南通大學地理科學學院，江蘇 南通 226007）

0 引言

地圖綜合過程中，需要考慮地圖所包含的4類關鍵信息，即統(tǒng)計信息、專題信息、拓撲信息和度量信息［1］，居民地作為地圖中重要的人工要素，其選取操作的任務之一就是在選取前后能有效地傳遞這些信息［2］，保持空間分布特征?，F(xiàn)有居民地的選取算法主要以點群形式討論［3］，較為典型的算法有空間比率算法、分布系數(shù)算法、重力模型算法、分片算法、鑲嵌約減算法［4］和圓增長算法［5］，這些方式具有思路簡單、實現(xiàn)容易、能夠保證重要居民地被選取等優(yōu)點，但是可能導致居民地的分布密度關系被破壞［6］，導致度量信息無法有效傳遞；利用Voronoi圖對點群進行綜合的算法［7］可以有效保持點群的分布特征，但是沒有考慮到點的屬性意義［1］，導致專題信息沒有有效傳遞；從地圖信息論角度出發(fā)的算法［8］通過反復構造Voronoi圖從而確保不同信息的有效傳輸。這些針對點群形式的居民地選取算法，在應用到大比例尺地圖中的離散面群居民地選取中時存在一定的缺陷：首先，點群選取模型中居民地的面積只是作為屬性條件考慮，而未從多邊形的幾何特性加以考慮；其次，在計算居民地密度時，根據(jù)居民地中心點計算出的密度可能不符合實際情況，例如，大面積的居民地由于占地面積大而導致計算出的分布密度小?？紤]到居民地的選取實質上是多種信息相互影響相互約束的過程，且一個目標性能的改善可能導致另一個目標性能的降低，因此本文結合4類關鍵信息，將居民地選取從對離散點群的選取拓展為對離散面群的選取，利用多目標優(yōu)化的遺傳算法實現(xiàn)居民地的選取操作。實驗結果表明，利用多目標優(yōu)化的遺傳算法有效地傳遞了關鍵信息，選取結果較好。

1 問題描述

1.1 幾個基本概念

（1）離散面群。面群即多邊形群體，離散面群即各多邊形之間是相離關系。規(guī)定居民地之間的相離關系有助于計算其Voronoi圖。

（2）分布范圍。分布范圍即整個居民區(qū)的影響范圍，其計算方式借鑒文獻［7］的思想，并對其進行改進以適應計算需求。改進算法的一般過程為：1）以居民地所有的點作為離散點、居民地的輪廓作為軟斷裂線建立約束Tin；2）以閾值d（通常大于兩倍所有三角形邊長的平均值）進行“剝皮”，由外向內逐步刪除那些邊長大于d的三角形。需要注意的是，如果某Tin邊在多邊形的輪廓上，則不對該邊“剝皮”。

（3）比率［2］。利用比率來描述分布范圍的變化情況，其計算方式為選取前后分布范圍的多邊形面積之差除以選取前的分布范圍的多邊形面積。比率越小，說明分布范圍的變化越小。

1.2 居民地選取的一般原則

為了保持居民地在選取過程中充分保持空間分布特征，在分析點群居民地選取原則的基礎上［9，10］，總結居民地選取的一般性原則如下：1）考慮居民地的面積大小。面積大的居民地比面積小的居民地優(yōu)先級高，在進行選取時，優(yōu)先選取面積大的居民地。2）考慮居民地的屬性意義。居民地的屬性意義通過行政意義、人口數(shù)、交通狀況、經濟地位和政治、軍事價值等標識來判斷，屬性意義高的居民地優(yōu)先選取。3）反映居民地的密度對比。制圖應保持各地區(qū)間的密度對比關系。居民地密度越大，被選取的可能性越高，但是被舍棄目標的絕對數(shù)量越大。4）保持居民地的分布范圍。居民地的選取應該控制居民地的分布范圍，不能使分布范圍的面積變化過大，因此位于邊界地區(qū)的居民地在選取過程中具有較高的優(yōu)先級。

1.3 基本思路

由居民地選取的一般性原則和需要傳遞的4類關鍵信息，提出離散面群居民地選取的4個指標，包括面積指標、屬性意義指標、密度指標和分布范圍指標。其中度量信息通過居民地面積、密度和分布范圍指標體現(xiàn)，專題信息通過居民地屬性意義指標體現(xiàn)，而統(tǒng)計信息通過居民地選取數(shù)量體現(xiàn)，拓撲信息通過Voronoi圖體現(xiàn)［8］。利用遺傳算法進行離散面群居民地的自動選取就是以上述指標作為約束條件，遺傳迭代逐步優(yōu)化達到全局最優(yōu)解。其一般過程為：1）確定居民地的分布范圍；2）以分布范圍的外輪廓作為邊界，以單個居民地作為計算單元，建立面群Voronoi圖，得到居民地的分布密度；3）利用開根號法則確定選取數(shù)量［11］，計算各約束指標，并利用上述約束指標加權求和進行遺傳算法運算。

2 居民地選取的實現(xiàn)

2.1 編碼方案

對于單個建筑物，只存在選取和刪除兩種情況，因此采用二進制編碼方式，編碼的長度N等于建筑物的個數(shù)，一條染色體代表一種選取方案，等位基因的值表示相應居民地的選取情況：1表示該建筑物被選中，0表示被刪除。

2.2 適應度函數(shù)

按照前文所述，居民地選取應考慮面積、屬性意義、密度和分布范圍等4類指標，適應度函數(shù)作為評價居民地選取好壞的函數(shù)，應該綜合考慮各約束指標。然而分布范圍指標作為密度計算過程的一個步驟通過Voronoi圖體現(xiàn)（詳見后文），因此適應度函數(shù)只考慮其余3類約束指標，各指標量化描述如下。

（1）居民地的面積指標。居民地按照面積指標進行選取，在選取數(shù)量確定的情況下，最優(yōu)的選取結果為選取的居民地的總面積最大，其公式為：

式中：F1為居民地的面積指標，Sj為居民地j的面積，n為居民地的選取數(shù)量。

（2）居民地的密度指標。首先定義居民地j的區(qū)域絕對密度Rj，其公式為：

式中：Nj為居民地j的Voronoi多邊形面積，減去Sj可以消除居民地面積對密度的影響。

居民地密度越大的區(qū)域，其Voronoi多邊形的面積越小，因此Voronoi多邊形面積大的居民地被選取的可能性低于Voronoi多邊形面積小的居民地。居民地被刪除之后，其1階臨近多邊形的面積將增大，如圖1所示，居民地α4被刪除后，其對應的Voronoi多邊形被分攤到α1、α2和α3的Voronoi多邊形中，而為了保持居民地間的密度對比關系，α1、α2和α3被舍棄的概率應該降低［7］。因此，居民地密度指標的計算方式被定義為：

式中：F2為居民地密度指標；ΔNj為居民地j的Voronoi多邊形的變化值，由于Voronoi多邊形面積不可能減少，因此ΔNj恒為非負數(shù)；ω為權重，值越小，選取后的居民地密度的對比度就越大，當ω＝0時，F(xiàn)2簡化為，此時最優(yōu)的選取結果為選取的居民地總密度最大，當ω＝1時，F(xiàn)2簡化為F2＝，此時最優(yōu)的選取結果為選取的居民地總Voronoi變化率總和最大，即被刪除的居民地盡可能均勻分布（通過大量實驗得出ω的取值使ω×max（ΔNj）小于1為宜）。

圖1 居民地Voronoi圖的變化過程示意Fig.1 Changes of settlement Voronoi diagram

同時由圖1可知，邊界上居民地由于外邊界被“剝皮”的原因，其Voronoi多邊形面積小于相同情況下的內部居民地的Voronoi多邊形面積，導致Rj大于相同情況下的內部居民地。因此，在選取過程中，邊界上的居民地被選取的可能性較大，可以保持居民地的分布范圍，體現(xiàn)分布范圍指標。

（3）居民地的屬性意義指標。居民地的屬性意義I的取值為｛0，1｝，其中1表示居民地的意義重大，而0表示居民地的意義一般。居民地按照屬性意義進行選取，在選取數(shù)量確定的情況下，最優(yōu)的選取結果為選取居民地的I總和最大，其公式為：

式中：F3為居民地的屬性意義指標，Ij為居民地j的屬性意義值，其余符號含義同上。

居民地的選取實質上是多目標優(yōu)化的問題，根據(jù)上述約束指標，適應度函數(shù)可以設計為：

式中：Fit（L）為染色體L的適應度值，ω1、ω2和ω3分別為相應約束指標的權重。

在實際操作過程中，約束指標的權重值往往難以確定，而采用自適應權重方法可以使權重隨著遺傳操作的進行而不斷變化，從而獲得朝正理想點的搜索壓力［12］，其公式為：

式中：ωi表示約束指標i的權重：Fmaxi、Fmini分別表示在種群中所有染色體的Fi的最大值、最小值。

2.3 局部搜索策略與終止條件

為降低計算復雜度，本文采用遺傳算法和局部搜索策略相結合的方式，將居民地選取的次要目標（居民地選取數(shù)量、強制保留的居民地）放在局部搜索策略中，使得所有將要進行下一步操作的備選方案均是可行解。其執(zhí)行過程如下：1）根據(jù)居民地的屬性信息和空間信息獲取居民地的強制保留信息表L，對具有重要行政意義、位于重要道路旁或道路交叉口、具有重要政治或軍事意義的居民地，將其加入L；2）對有待進行局部搜索策略的染色體進行解碼，獲取居民地的選取和刪除情況；3）根據(jù)L對染色體進行修正，將需要強制保留的居民地對應的等位基因強制設為1；4）統(tǒng)計居民地的選取數(shù)量，若選取數(shù)量大于先前給定的選取程度，則從已選取居民地中選出部分非強制保留的居民地，將其等位基因設為0，反之，從已刪除居民地中選出部分居民地，將其等位基因設為1；5）用修正后的染色體代替原來的染色體。無論是初始產生的還是通過交叉、變異產生的新生染色體，在加入種群之前都必須首先執(zhí)行局部搜索策略，采用該方式可以有效避免在非可行解上浪費時間，提高系統(tǒng)執(zhí)行效率。

采用兩種終止條件：遺傳代數(shù)到達一定的值以及種群的最大適應度連續(xù)若干代沒有變化。這兩個條件滿足任意一個則停止運算。

3 實驗分析

在Eclipse 3.7環(huán)境下利用Java語言對提出的方案進行實驗和分析。實驗數(shù)據(jù)選取廬山地區(qū)部分居民地數(shù)據(jù)，如圖2a所示，面狀目標56個，初始比例尺為1∶10 000，目標比例尺為1∶25 000，根據(jù)開根號法則確定待選取的數(shù)量為36個。由實驗對比分析，確定最大迭代次數(shù)為150，種群大小為50，交叉概率為0.9，變異概率為0.1。算出的居民地Voronoi圖如圖2b所示，外邊界的粗實線為居民地分布范圍，利用遺傳算法算出的居民地選取結果如圖2c所示。

圖2 居民地的選取Fig.2 Selection of settlements

居民地的區(qū)域相對密度為該居民地的區(qū)域絕對密度占整個區(qū)域居民地絕對密度的比重，其變化如表1所示，其中Rs、Rt分別為原圖、目標圖中居民地的區(qū)域相對密度值。表1以Rs由小到大排序，并做出Rs和Rt變化曲線（圖3），其中虛線為Rs的最小二乘擬合曲線；原圖居民地平均面積為516.11m2，選取后的值為588.58m2＞516.11m2；原圖居民地屬性意義的平均值為67÷55≈1.2182，選取后的值為43÷36≈1.25＞1.2182；選取前后居民地分布范圍的比率為8 850.5÷78 474.25＝11.28%。

表1 綜合前后居民地的相對密度比較Table 1 Comparison of relative settlement density before and after merging

圖3 綜合前后居民地的相對密度比較Fig.3 Comparison of relative settlement density before and after merging

根據(jù)上述實驗數(shù)據(jù)得出如下結論：1）Rt的變化趨勢與Rs相似，且其擬合曲線屬于單調遞增類型，說明居民地在綜合前后較好地保持了區(qū)域相對密度；2）居民地選取前后的平均面積和平均屬性意義值均有不同程度的提高，說明選取前后居民地較好地保持了面積指標和屬性意義指標；3）在一定程度上可以保證居民地的分布范圍，但是比率偏大，是因為該指標沒有作為適應度函數(shù)的指標之一造成的，可行的解決辦法是將邊界地區(qū)的居民地屬性意義值設為1，以提高被選取的可能性。

4 結論

本文提出的離散面群居民地自動選取模型不僅考慮了居民地的密度和分布范圍，還考慮了居民地的面積和屬性意義，從實驗結果看，該模型在一定程度上能夠保持地圖的4類關鍵信息，但是部分指標的保持不太理想。該模型具有一定的可擴展性，只要適當修改適應度函數(shù)，就可以添加居民地選取的其它約束指標。本文的難點在于居民地知識的獲取，一方面居民地的某些空間知識很難通過計算機識別，另一方面還有很多知識該模型中沒有考慮到，比如建筑物的方向性、線性排列特性以及與其他地理要素的協(xié)同特性等，這將在以后的研究中進一步探討。在計算性能方面，由于遺傳算法是從全局優(yōu)化的角度進行迭代的，計算速度較慢，但是遺傳算法具有很好的并行特性［13］，因此可以利用多線程并行計算的方式來提高運行效率。

［1］ 閆浩文，王家耀.基于Voronoi圖的點群目標普適綜合算法［J］.中國圖象圖形學報，2005，10（5）：633－636.

［2］ 閆浩文，王家耀.地圖群（組）目標描述與自動綜合［M］.北京：科學出版社，2009.15－29.

［3］ 王家耀，姚杰.模糊綜合評判在制圖綜合中的應用（以居民地選取為例）［J］.解放軍測繪學院學報，1985（2）：45－52.

［4］ LANGRAN G E，POIKER T K.Integration of name selection and name placement［A］.2nd Int.Symp.on Spatial Data Handling［C］.1986.50－64.

［5］ MARC V K，RENE V O.Efficient settlement selection for interactive display［A］.Auto－Carto 13：ACSM／ASPRS Annual Convention Technical Papers［C］.1997.287－296.

［6］ SADAHIRO Y.Cluster perception in the distribution of point objects［J］.Cartographica：The International Journal for Geographic Information and Geovisualization，1997，34（1）：49－62.

［7］ 艾廷華，劉耀林.保持空間分布特征的群點化簡方法［J］.測繪學報，2002，31（2）：175－181.

［8］ YAN H，WEIBEL R.An algorithm for point cluster generalization based on the Voronoi diagram［J］.Computers ＆ Geosciences，2008，34（8）：939－954.

［9］ 祝國瑞，郭禮珍，尹貢白，等.地圖設計與編繪［M］.武漢：武漢大學出版社，2001.166.

［10］ 王輝連.居民地自動綜合的智能方法研究［D］.鄭州：信息工程大學，2005.

［11］ TOPFER F T，PILLEWIZER W.The principles of selection［J］.Cartographic Journal，1966，3（1）：10－16.

［12］ CHENT R，GEN M.An adaptive superplane approach for multiple objective optimization problems［R］.Ashikaga Institute of Technology，1998.

［13］ 武金瑛，王希誠.一種粗粒度并行遺傳算法及其應用［J］.計算力學學報，2002，19（2）：148－153.