[發明專利]基于并行模擬退火算法的劃界線生成方法

有效

• 申請號: 201410528857.0
• 申請日: 2014-09-26
• 公開（公告）號: CN104484490B
• 公開（公告）日: 2017-08-08
• 發明（設計）人: 華一新;馮長強;江南;趙軍喜;李響;武麗麗;曹一冰
• 申請（專利權）人: 中國人民解放軍信息工程大學
• 主分類號: G06F17/50
• 分類號: G06F17/50;G06T11/20
• 代理公司: 國防專利服務中心11043
• 代理人: 張友春

技術領域

本發明涉及劃界談判領域，特別涉及一種基于并行模擬退火算法的劃界線生成方法。

背景技術

當前，我國是世界上最后一個國界線還沒有完全確定的大國，這直接影響到我國的領土主權、民族團結及邊界地區的繁榮穩定，是我國走向繁榮富強及民族復興的重要障礙。

劃界談判是一種解決邊界領土爭端的有效手段。傳統的爭議區劃界方法主要是基于紙質地圖的手工劃界，隨著計算機、GIS及空間決策支持等技術的發展，出現了計算機輔助劃界方法，大大提高了劃界的進程及透明度。但是，劃界工作涉及多種因素，包括面積、資源、地形以及由于歷史、民族、宗教和戰略目的等所形成的必爭區域及不可分割區域，傳統的方法往往很難將其全部考慮在內，要么沒有考慮資源，要么忽略了地形的影響。

實際地形不僅具有天然的區域分割作用，而且容易管理以及阻擋攻擊。因此，如何利用實際地形中的特征線生成劃界線成為業內研究的主要課題。

發明內容

本發明需解決的技術問題是提供一種利用實際地形中的特征線生成劃界線的方法，使得劃界線與實際地形相吻合，并提高最優劃界線的生成速度。

為了解決上述問題，本發明提供一種基于并行模擬退火算法的劃界線生成方法，其采用的技術方案如下：

S1、建立實際地形的數字高程模型，并從該數字高程模型中分別提取柵格形式的山脊線和山谷線，所述柵格形式的山脊線和山谷線存儲在兩個圖層中；

S2、將所述兩個圖層中的柵格形式的山脊線和山谷線融合到同一圖層中，得到特征圖層，獲取該特征圖層中的所有特征柵格，所述特征柵格包括懸掛特征柵格和非懸掛特征柵格；

S3、對所述特征圖層中的懸掛特征柵格進行反向追蹤，使得特征圖層中的山脊線與山谷線相連，形成特征柵格網絡；并對所述特征柵格網絡進行柵格轉矢量操作，得到矢量地形特征網絡，該矢量地形特征網絡中的各連線為地形特征線；

S4、遍歷所述各地形特征線，并對每一地形特征線的首末端點進行編號；根據矢量地形特征網絡，建立各地形特征線首末端點的點-點拓撲關系；

S5、根據所述各地形特征線首末端點的點-點拓撲關系，隨機搜索從劃界線起點到劃界線終點的點串作為初始點串，所述初始點串為各端點編號的集合；

S6、預設初始溫度值，將所述初始點串作為初始解，開啟并行模擬退火線程，以完成從劃界線起點到劃界線終點的最優點串的搜索；

S7、對所述最優點串進行解碼，得到從劃界線起點到劃界線終點的地形特征線的集合，將該集合中的各地形特征線首尾相連，得到劃界線。

優選的，所述步驟S3中：利用基于地形梯度方向的斷面極值法對所述特征圖層中的懸掛特征柵格進行反向追蹤。

優選的，所述步驟S5進一步包括：

S51、根據所述各地形特征線首末端點的點-點拓撲關系，構造主棧與多個分棧，其中，所述主棧用于存儲分棧，所述分棧用于存儲與其前一個分棧棧頂相關聯的所有拓撲點的編號；基于劃界線起點構造新的分棧，并將該分棧插入到主棧中；

S52、判斷主棧棧頂對應的分棧是否為空，若為空，則彈出前一個分棧棧頂，并將主棧棧頂彈出，并重復執行步驟S52；若不為空，則執行步驟S53；

S53、判斷與主棧棧頂對應的分棧棧頂相關聯的拓撲點集中是否存在劃界線終點，若存在，則將主棧中各分棧的棧頂以及該劃界線終點依次輸出作為初始點串，并結束搜索；若不存在，則執行步驟S54；

S54、從與主棧棧頂對應的分棧棧頂相關聯的拓撲點集中，將懸掛拓撲點與主棧中所有分棧棧頂去除，然后對該拓撲點集中的拓撲點進行隨機排列，以構造新的分棧，將該新的分棧插入主棧中，并返回執行步驟S52。

優選的，所述步驟S6進一步包括：

S61、預設目標函數的先決條件并構造目標函數；所述目標函數為

f(l)為劃界線L對應的目標函數值，r_s為實際所得面積比例，r₀為談判約定的面積比例，ω_i為實際獲得的第i種資源的重要性權值，R_i為實際獲得的第i種資源的占有量歸一化值，n為實際獲得的所有資源的數量；

S62、預設初始溫度值，將初始點串作為初始解，并將該初始解作為當前解，開啟并行模擬退火線程，所述并行模擬退火線程包括三個線程，所述三個線程的降溫方式不同；

S63、計算當前解的目標函數值，針對每一個線程，由當前解生成新解，并判斷所述新解是否滿足目標函數的先決條件，若是，則執行步驟S64；若不是，則繼續執行步驟S63；