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

有效

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

1.一種基于并行模擬退火算法的劃界線生成方法，其特征在于，所述方法包括：

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

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

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

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

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

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

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

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

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

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

S64、計算該新解的目標函數值，并在該線程中判斷是否接受該新解，若不接受，則返回執行步驟S63；若接受，從各線程對應的新解中選擇最快被接受的新解作為當前解，并進行降溫后執行步驟S65；

S65、判斷當前解是否滿足終止條件，若是，則輸出當前解并結束搜索，所述當前解為從劃界線起點到劃界線終點的最優點串，若不是，則返回執行步驟S63；

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

2.如權利要求1所述的基于并行模擬退火算法的劃界線生成方法，其特征在于，所述步驟S3中：

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

3.如權利要求2所述的基于并行模擬退火算法的劃界線生成方法，其特征在于，所述步驟S5進一步包括：

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

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

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

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

4.如權利要求1所述的基于并行模擬退火算法的劃界線生成方法，其特征在于，所述步驟S64中：

根據Metropolis抽樣準則判斷是否接受新解，所述Metropolis抽樣準則為：

min{1，exp(-Δf/T_k)}＞random(0，1)；

其中，Δf為新解目標函數值與當前解目標函數值的差值，T_k為當前溫度，random(0，1)表示0-1之間的隨機小數。

5.如權利要求1所述的基于并行模擬退火算法的劃界線生成方法，其特征在于，所述步驟S64中：

從各線程對應的新解中選擇最快被接受的新解作為當前解后，利用該當前解對應線程的降溫方式進行降溫；其中，所述三個線程的降溫方式不同，且對于每一個線程，采用以下任一種降溫方式進行降溫：

T₁(k)＝T₀/lg(1+k)

T₂(k)＝T₀/(1+k)

T₃(k)＝[T₀/lg(1+k)+T₀/(1+k)]/2

T₀為預設的初始溫度值，k為降溫次數。