一種顧及道路影響的點要素注記配置遺傳禁忌搜索算法

李 娟，朱勤東

(福州大學省空間信息工程研究中心,福建 福州 350002)

注記配置的合理性會直接影響地圖上文本信息表達的清晰程度[1]，點要素注記配置是國內(nèi)外學者研究最多、最深入的注記配置問題[2]，研究方法多為啟發(fā)式搜索算法[3]，如遺傳算法[2]、禁忌搜索算法[4]和蟻群算法[5]等。當前研究將智能化方法改進，或?qū)煞N或多種方法結(jié)合。如文獻[6]為解決遺傳算法的早熟問題，利用最小生成樹聚類對遺傳算法進行改進；文獻[7]將粒子群優(yōu)化算法和遺傳算法結(jié)合，利用變異算子對粒子進行變異操作；文獻[8]將點要素注記配置問題看成獨立離散問題，結(jié)合數(shù)學方法改進遺傳算法；文獻[9]利用整數(shù)線性規(guī)劃，提出了最大獨立集擴展模型；文獻[10]提出了一種聚類分組的蟻群算法，實現(xiàn)大規(guī)模點要素的快速注記；文獻[11]提出了基于圖論的點要素注記配置模型，將道路周邊點要素注記分布的同一性作為附加影響因子;文獻[12]將遺傳算法和禁忌算法結(jié)合，提出了帶有自適應機制的改進遺傳禁忌混合算法；文獻[13]提出了基于分散集中策略的遺傳禁忌搜索算法解決TSP路徑優(yōu)化問題；文獻[14]利用改進遺傳禁忌搜索算法對電力系統(tǒng)的穩(wěn)定性進行無功化改善。

本文提出利用綜合具有全局尋優(yōu)能力的遺傳算法、具有記憶功能和“爬山能力”的禁忌搜索算法的遺傳禁忌搜索算法(genetic taboo search algorithm，GTSA)解決點要素注記自動配置問題，利用遺傳算法進行前期搜索，利用選擇、交叉、變異等操作構(gòu)造鄰域，保證算法的全局搜索能力，再利用禁忌搜索算法的“爬山能力”進行后期尋優(yōu)，既可提高算法的收斂速度，又可避免陷入局部最優(yōu)。另外，點要素注記配置的約束條件多為單一地圖要素，但在制圖過程中，多為兩種或兩種以上的地圖要素，且沿道路分布的點要素數(shù)量相對較多，雖然文獻[11]中提到道路要素，并未將道路與周邊點要素的空間關(guān)系納入注記配置的約束條件中。因此本文在尋找點要素最佳注記位置時，加入道路對點要素注記的影響作為約束條件來尋找最佳注記配置方案，以增強點要素注記配置的合理性與地圖的可讀性。

1 遺傳禁忌搜索算法主要內(nèi)容

(1) 編碼規(guī)則：若每個點要素有m個候選注記位置，用0～m-1指代每個候選位置[15]，用二進制對每個位置的指代值進行編碼，生成一組染色體。

(2) 遺傳算法(GA)操作方法：包括交叉和變異方法[16]。交叉方法采用單點交叉，即隨機選擇交叉位置，進行染色體交叉變換；變異操作采用沖突位變異，即選擇沖突注記點位，隨機生成一個注記點位編碼，代替原有點位編碼[15]。

(3) 選擇方法：一般采用輪盤法，但該方法會導致過早收斂和停滯[16]。本文選用錦標賽方法[15]，即從交叉和變異后的群體中選擇適配值排名前兩位的作為下一代父代染色體。

(4) 禁忌算法(TS)操作方法：主要操作是確定鄰域、禁忌表長度和規(guī)模、候選解及藐視準則[17]。鄰域是在GA選擇后的群體中選擇定量最優(yōu)個體；禁忌表存放使搜索出現(xiàn)循環(huán)或陷入局部最優(yōu)的禁忌對象，禁忌長度動態(tài)更新；候選解是從當前解的鄰域中選擇定量最優(yōu)個體構(gòu)成；藐視準則是若當前候選解的最優(yōu)對象位于禁忌表中，其適配值比歷史最優(yōu)解大，則該禁忌對象可代替歷史最優(yōu)解，作為下一次迭代的初始解，并更新禁忌表。

(5) 適配值函數(shù)：根據(jù)文中的點要素注記配置準則，主要從注記文本最小外接矩形框間是否交叉、是否壓蓋其他點要素、是否壓蓋線狀要素、注記位置的優(yōu)先級等因素來構(gòu)造適配值函數(shù)

(1)

M(i,j)=β1M1(i,j)+β2M2(i,j)+β3M3(i,j)+β4M4(i,j)

(2)

約束條件

(3)

式中，n為點要素個數(shù)；m表示注記備選位置數(shù)；M(i,j)為點要素i在注記位置j時的適配值；αij為開關(guān)變量，當點要素i的注記框位于j位置時，αij=1，反之αij=0；β1為點要素i的注記框與其他點要素沖突的權(quán)重；β2為點要素注記框位置優(yōu)先級的權(quán)重；β3為點要素i的注記框與其他點要素注記框相交的權(quán)重；β4為點要素i的注記框與道路要素相交的權(quán)重；M1(i,j)為點要素i注記框在j位置時與其他點要素對應關(guān)系的得分值；M2(i,j)為點要素i注記框在j位置對應的得分值；M3(i,j)為點要素i處于j位置的注記框與其他點要素注記框?qū)P(guān)系的得分值；M4(i,j)為點要素i處于j位置的注記框與道路要素對應關(guān)系的得分值。式(3)是為了保證點要素注記配置位置的唯一性。

(6) 終止條件：算法達到預設(shè)的迭代次數(shù)或算法的適配值函數(shù)在一定的范圍內(nèi)最優(yōu)解保持不變，滿足其一即可停止計算過程。

2 遺傳禁忌搜索算法的點要素注記自動配置

2.1 點要素注記配置的基本原則

(1) 點要素注記備選位置如圖1所示，優(yōu)先級排序為正右、正上、正左、正下、右上、左上、左下、右下[7]。

(2) 不與鄰近的其他點要素注記產(chǎn)生沖突，不壓蓋被注記的點要素和其他鄰近點要素。

(3) 不壓蓋境界、鐵路與干線公路等重要線狀地物，并與被注記的點要素位于重要線狀地物的同側(cè)；盡量不壓蓋同顏色的機耕路、鄉(xiāng)村路、小路等[4]。

2.2 GTSA的實現(xiàn)過程

實現(xiàn)過程如圖2所示。

(1) 試驗數(shù)據(jù)預處理。

(2) 給定算法參數(shù)，生成初始種群，置空禁忌表。

(3) 判斷當前最優(yōu)解是否滿足算法的終止條件，若滿足，則終止算法并輸出優(yōu)化結(jié)果，否則繼續(xù)下一步驟。

(4) 利用算法中的選擇、交叉和變異操作產(chǎn)生當前解的若干鄰域解，并從鄰域解中選取當前解的若干候選解。

(5) 判斷當前解的候選解是否滿足藐視準則，若候選解中最佳候選解滿足藐視準則，則替代當前解，成為新的當前最優(yōu)解，并更新禁忌表，轉(zhuǎn)步驟(3)；若不滿足，則判斷候選解集中候選解是否均位于禁忌表中，選擇非禁忌表中的候選解為新的當前最優(yōu)解，并更新禁忌表，再轉(zhuǎn)步驟(3)。

3 試驗數(shù)據(jù)預處理

3.1 點要素預處理

在ArcGIS中，利用ArcToolBox的鄰域分析工具，以2倍對角線長度為搜索半徑，對點要素進行近鄰分析，生成距離值和角度值，為遺傳禁忌搜索分析做準備。

圖3中點要素A的圓形緩沖區(qū)中，僅直線L1、L2間的點要素與中心點A的注記會發(fā)生沖突，稱其為緩沖區(qū)H，故對周圍點要素搜索時不必遍歷除中心點A外的所有點要素，只需遍歷緩沖區(qū)H內(nèi)的點要素即可，極大地減少了算法的搜索時間。

3.2 點要素與道路關(guān)系的判斷

對道路進行平滑處理后將道路分段形成滿足多項式插值條件的曲線，并對各段曲線進行編號；再利用Matlab軟件中的樣條插值求出各段道路曲線的樣條曲線函數(shù)；然后利用ArcGIS的ArcToolBox中的鄰域分析工具，以最小外接矩形的對角線TL為搜索半徑，判斷點要素與道路的近鄰關(guān)系。

圖4中道路曲線為l，點要素為A、B、C、D，TL為注記框最小外接矩形的對角線，h為道路曲線l上與點要素最接近的一點的切線垂線與點要素最小外接矩形對角線構(gòu)成直角三角形的一條直邊，其中TL必定大于h，故以TL為搜索半徑來判斷點要素與道路間的關(guān)系，完全可以滿足條件。

可用兩個條件判斷注記框與道路是否壓蓋：①可直接判斷最近點是否位于矩形框內(nèi)；②當最近點不在矩形框內(nèi)時，選取注記框坐標極值，即Xmax、Ymax、Xmin、Ymin，判斷注記極值Ymax、Ymin與鄰近道路曲線函數(shù)在[Xmin,Xmax]區(qū)間上函數(shù)值Y的大小關(guān)系。

3.3 適配值函數(shù)中權(quán)重值與得分值

(1) 編碼確定：點要素備選注記位置有8個，用0—7指代，每個位置的指代值用三位二進制值進行編碼，若假設(shè)種群大小為N，則編碼長度為3N。

(2) 注記框與點要素對應關(guān)系函數(shù)M1(i,j)=0.2T+0.4(S-T)，其中S為緩沖區(qū)H內(nèi)的點要素數(shù)目(不含點要素i)，T為被點要素i注記框壓蓋的點要素數(shù)目。

(3) 要素注記配置位置得分值M2(i,j)，根據(jù)注記備選位置優(yōu)先級從高到低，得分值M2(i,j)取值分別為0.7、0.6、0.5、0.4、0.3、0.2、0.1、0。

(4) 注記框間對應關(guān)系得分值M3(i,j)=0.1T+0.2(S-P)，其中S為緩沖區(qū)H內(nèi)的點要素數(shù)目(不含點要素i)，P為與點要素i注記框相交的注記框數(shù)目。

(5) 注記框與道路要素對應關(guān)系得分值M4(i,j)=0.3L+0.6(F-L)，其中F為緩沖區(qū)H內(nèi)的道路要素數(shù)目，L為被注記框壓蓋的道路要素的數(shù)目。

(6) 經(jīng)過若干試驗的驗證，當點要素i的適配值函數(shù)M(i,j)中的權(quán)重值β1、β2、β3、β4分別為0.2、0.1、0.2、0.5時，試驗所取得的效果最好。

算法的適配值函數(shù)越大，點要素的注記配置效果越好。

4 試驗與討論

4.1 試驗環(huán)境

本文基于ArcGIS 10.2與Python 2.7，在Windows 7(64位)，Pentium(R) Dual-Core CPU E520@2.5 GHz，8 GB內(nèi)存環(huán)境下實現(xiàn)點要素注記配置的遺傳禁忌搜索算法。利用福建省惠安縣的鄉(xiāng)鎮(zhèn)點進行試驗，包含325個鄉(xiāng)村點和9條鄉(xiāng)村道路。按照隨機抽樣的方式設(shè)置點要素的個數(shù)為50、100、150、200、250、300，將GTSA、禁忌算法、遺傳算法和ArcGIS軟件的結(jié)果對比，判斷本文提出的遺傳禁忌搜索算法的計算精度、效率及穩(wěn)健性。

4.2 試驗參數(shù)確定

綜合其他學者研究的參數(shù)設(shè)置[18-19]，并結(jié)合本文試驗驗證，參數(shù)設(shè)置為交叉概率0.8，變異概率0.01，鄰域大小int(0.6N)(N≥30)，候選解大小10，禁忌表長度15，禁忌長度9。

4.3 試驗結(jié)果

4.3.1 算法精度分析

利用ArcGIS中“使用Maplex標注引擎”功能，規(guī)定標注位置的優(yōu)先級、點要素與道路要素之間的關(guān)系，按照規(guī)定的注記配置規(guī)則計算適配值。將ArcGIS得到注記位置的適配值S作為參考值，按照式(4)計算3種方法得出的最佳適配值Di(i=1,2,3)相對于ArcGIS的精度變化率

(4)

當滿足算法終止條件時，不同算法的求解結(jié)果見表1、表2、表3，當點要素個數(shù)在100以內(nèi)時，GTSA與ArcGIS計算結(jié)果間的精度增長在1%以內(nèi)(GA和TS則是點要素個數(shù)在150以內(nèi))，隨著點要素個數(shù)的增加，GTSA、TS、GA的求解質(zhì)量均優(yōu)于ArcGIS，GTSA平均提高3.83%，TS平均提高2.3%，GA平均提高1.74%。

表1 算法精度增長率

表2 點要素注記框壓蓋個數(shù)

表3 點要素注記框壓蓋道路個數(shù)

4.3.2 算法效率分析

當滿足算法終止條件時，不同算法的運行時間見表4，其中TS的運行時間相對于GTSA和GA的運行時間相對較短，GA算法的運行時間最長。

表4 算法運行時間 s

4.3.3 算法穩(wěn)健性分析

由于GA和TS均為啟發(fā)式算法，同一組數(shù)據(jù)的多次計算結(jié)果不一定相同[11]，故可通過同組數(shù)據(jù)進行多次試驗，利用算法的均方差判斷算法的穩(wěn)健性。均方差公式如下

(5)

式中，S為同一組數(shù)據(jù)所做試驗的總次數(shù)，默認為50；Mt(t=0,1,…,49)分別表示TS、GA、GTSA每次獲得的最佳適配值；μi(i=1,2,3)分別為TS、GA、GTSA在S次試驗獲得的最佳適配值均值；si(i=1,2,3)分別為TS、GA、GTSA的均方差，均方差越小，算法穩(wěn)健性越好。

3種算法求得的均方差見表5，GTSA的穩(wěn)健性高于GA和TS的穩(wěn)健性，GA的穩(wěn)健性高于TS的穩(wěn)健性，且隨著點要素個數(shù)的增加，算法的穩(wěn)健性越來越弱；當點要素從200到250時，GA和TS的均方差均從大變小，可能與試驗選取的點要素分布位置過于密集且位于道路要素的近鄰范圍內(nèi)有關(guān)，但是GTSA仍舊不被影響，即相對于TS和GA，GTSA更具穩(wěn)健性。

表5 算法均方差

4.4 結(jié)果展示

對所有的數(shù)據(jù)進行試驗，其結(jié)果如圖5、圖6所示，矩形框框出是注記有沖突的要素。在ArcGIS結(jié)果中，注記無沖突的點要素為237，注記與道路要素有沖突的點要素為47；在GTSA結(jié)果中，注記無沖突的點要素為261，注記與道路要素有沖突的點要素為26。兩者對比可知，GTSA方法的注記無沖突率比ArcGIS高，與道路的沖突數(shù)目降低，即GTSA的注記效果更好。

5 結(jié) 語

本文提出將綜合遺傳算法和禁忌搜索算法特性的遺傳禁忌搜索算法應用在點要素注記配置中，并將道路對點要素注記配置的影響作為注記配置中的約束條件。與遺傳算法、禁忌搜索算法相比，該算法的算法精度和穩(wěn)健性均有所提高，但是計算效率略低于禁忌算法；與ArcGIS相比，無論是算法精度、運行計算效率還是穩(wěn)健性都有提高。另外，在該算法的配置結(jié)果中點要素注記與點要素、道路的壓蓋量最少，注記與注記間的交叉量最少，在一定程度上提高了地圖的易讀性和美觀性。但本文選擇的僅為單一等級的點、道路要素，在后續(xù)的工作中，將進一步把點、道路要素的多等級屬性納入到研究中；同時，對該算法進行并行化改造，以提升算法的運行效率。