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

李 娟，朱勤東

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

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

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

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

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

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

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

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

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

(1)

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

(2)

約束條件

(3)

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

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

2 遺傳禁忌搜索算法的點(diǎn)要素注記自動配置

2.1 點(diǎn)要素注記配置的基本原則

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

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

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

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

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

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

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

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

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

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

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

3.1 點(diǎn)要素預(yù)處理

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

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

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

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

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

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

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

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

(2) 注記框與點(diǎn)要素對應(yīng)關(guān)系函數(shù)M1(i,j)=0.2T+0.4(S-T)，其中S為緩沖區(qū)H內(nèi)的點(diǎn)要素?cái)?shù)目(不含點(diǎn)要素i)，T為被點(diǎn)要素i注記框壓蓋的點(diǎn)要素?cá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) 注記框間對應(yīng)關(guān)系得分值M3(i,j)=0.1T+0.2(S-P)，其中S為緩沖區(qū)H內(nèi)的點(diǎn)要素?cái)?shù)目(不含點(diǎn)要素i)，P為與點(diǎn)要素i注記框相交的注記框數(shù)目。

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

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

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

4 試驗(yàn)與討論

4.1 試驗(yàn)環(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)境下實(shí)現(xiàn)點(diǎn)要素注記配置的遺傳禁忌搜索算法。利用福建省惠安縣的鄉(xiāng)鎮(zhèn)點(diǎn)進(jìn)行試驗(yàn)，包含325個(gè)鄉(xiāng)村點(diǎn)和9條鄉(xiāng)村道路。按照隨機(jī)抽樣的方式設(shè)置點(diǎn)要素的個(gè)數(shù)為50、100、150、200、250、300，將GTSA、禁忌算法、遺傳算法和ArcGIS軟件的結(jié)果對比，判斷本文提出的遺傳禁忌搜索算法的計(jì)算精度、效率及穩(wěn)健性。

4.2 試驗(yàn)參數(shù)確定

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

4.3 試驗(yàn)結(jié)果

4.3.1 算法精度分析

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

(4)

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

表1 算法精度增長率

表2 點(diǎn)要素注記框壓蓋個(gè)數(shù)

表3 點(diǎn)要素注記框壓蓋道路個(gè)數(shù)

4.3.2 算法效率分析

當(dāng)滿足算法終止條件時(shí)，不同算法的運(yùn)行時(shí)間見表4，其中TS的運(yùn)行時(shí)間相對于GTSA和GA的運(yùn)行時(shí)間相對較短，GA算法的運(yùn)行時(shí)間最長。

表4 算法運(yùn)行時(shí)間 s

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

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

(5)

式中，S為同一組數(shù)據(jù)所做試驗(yàn)的總次數(shù)，默認(rèn)為50；Mt(t=0,1,…,49)分別表示TS、GA、GTSA每次獲得的最佳適配值；μi(i=1,2,3)分別為TS、GA、GTSA在S次試驗(yàn)獲得的最佳適配值均值；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)健性，且隨著點(diǎn)要素個(gè)數(shù)的增加，算法的穩(wěn)健性越來越弱；當(dāng)點(diǎn)要素從200到250時(shí)，GA和TS的均方差均從大變小，可能與試驗(yàn)選取的點(diǎn)要素分布位置過于密集且位于道路要素的近鄰范圍內(nèi)有關(guān)，但是GTSA仍舊不被影響，即相對于TS和GA，GTSA更具穩(wěn)健性。

表5 算法均方差

4.4 結(jié)果展示

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

5 結(jié) 語

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