[發明專利]路徑生成的方法及裝置

在審

• 申請號: 201611132745.9
• 申請日: 2016-12-09
• 公開（公告）號: CN106600049A
• 公開（公告）日: 2017-04-26
• 發明（設計）人: 趙廣懷;高嵩;焦陽;張洪濤;張小亞
• 申請（專利權）人: 國網北京市電力公司;國家電網公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/00
• 代理公司: 北京康信知識產權代理有限責任公司11240
• 代理人: 韓建偉,張永明

1.一種路徑生成的方法，其特征在于，包括：

獲取電力通信網絡的拓撲圖，其中，所述拓撲圖包括多個節點和鏈路，其中，一條鏈路至少用于連接兩個節點；

獲取多個待處理業務的路徑起點和路徑終點，并配置各個待處理業務的螞蟻集群；

控制所述多個螞蟻集群中的所有螞蟻從對應的待處理業務的路徑起點移動至所述待處理業務的路徑終點，并記錄所有螞蟻在移動過程中的移動信息，以得到所述拓撲圖中各個鏈路的節點信息素；

基于所述各個鏈路的節點信息素確定各個待處理業務的路徑。

2.根據權利要求1所述的方法，其特征在于，控制所述多個螞蟻集群中的所有螞蟻從對應的待處理業務的路徑起點移動至所述待處理業務的路徑終點包括：

控制每個所述螞蟻集群中的每一個螞蟻從對應的待處理業務的路徑起點移動至所述待處理業務的路徑終點，其中，控制每個所述螞蟻集群中的每一個螞蟻從對應的待處理業務的路徑起點移動至所述待處理業務的路徑終點包括：

將所述螞蟻集群中的螞蟻放置在對應的待處理業務的路徑起點，將所述路徑起點作為當前節點，對所述螞蟻執行下述操作，直至所述螞蟻移動至所述路徑終點，更新所述螞蟻在移動過程中所經過的各個鏈路的節點信息素，所述操作包括：

確定所述當前節點的相鄰鏈路，其中，在所述拓撲圖上所述相鄰鏈路用于連接所述當前節點與其他節點；

基于所述相鄰鏈路的節點信息素，確定所述螞蟻的移動方向；

控制所述螞蟻按照移動方向移動至下一個節點，將所述下一個節點作為當前節點。

3.根據權利要求2所述的方法，其特征在于，基于所述相鄰鏈路的節點信息素，確定所述螞蟻的移動方向包括：

利用轉移概率公式確定所述螞蟻的移動方向，其中，所述轉移概率公式為，

其中，表示循環代數t時螞蟻k從v_i節點移動到v_j節點的轉移概率，v_i節點與v_j節點之間的鏈路被記錄為鏈路e_ij，v_j與v_s屬于所有v_i節點可連通節點集合Viallowed；表示鏈路e_ij在循環代數t時的蟻群As_k的節點信息素，表示鏈路e_ij的期望值；α表示信息素濃度的重要程度，β代表期望值的重要程度，循環代數t表示所述螞蟻從對應的待處理業務的路徑起點移動至所述待處理業務的路徑終點的當前循環執行所述操作的次數。

4.根據權利要求2所述的方法，其特征在于，更新所述螞蟻在移動過程中所經過的各個節點的節點信息素包括：

若更新后的節點信息素超過預定范圍，則按照預定比例調整更新后的節點信息素，以使該更新后的節點信息素在所述預定范圍內。

5.根據權利要求1所述的方法，其特征在于，基于所述各個鏈路的節點信息素確定各個待處理業務的路徑包括：

從所述待處理業務對應的多個鏈路中，選取節點信息素值最高的鏈路，作為所述待處理業務的路徑。

6.根據權利要求1至5中任意一項所述的方法，其特征在于，所述節點信息素用通道壓力來表示。

7.一種路徑生成的裝置，其特征在于，包括：

第一獲取單元，用于獲取電力通信網絡的拓撲圖，其中，所述拓撲圖包括多個節點和鏈路，其中，一條鏈路至少用于連接兩個節點；

第二獲取單元，用于獲取多個待處理業務的路徑起點和路徑終點，并配置各個待處理業務的螞蟻集群；

控制單元，用于控制所述多個螞蟻集群中的所有螞蟻從對應的待處理業務的路徑起點移動至所述待處理業務的路徑終點，并記錄所有螞蟻在移動過程中的移動信息，以得到所述拓撲圖中各個鏈路的節點信息素；

確定單元，用于基于所述各個鏈路的節點信息素確定各個待處理業務的路徑。