[發明專利]基于人工蜂群算法的并行優化處理TSP問題的方法及裝置

有效

• 申請號: 201611141293.0
• 申請日: 2016-12-12
• 公開（公告）號: CN106709597B
• 公開（公告）日: 2020-07-03
• 發明（設計）人: 李德波;馮永新;鐘俊;周杰聯;湛志鋼;殷立寶;李建波
• 申請（專利權）人: 廣東電網有限責任公司電力科學研究院
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/00
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 張春水;唐京橋

1.一種基于人工蜂群算法的并行優化處理TSP問題的方法，其特征在于，包括：

通過MPI接口建立多個并行進程，所述并行進程包括主進程和從進程，通過所述主進程將初始蜜源信息分發給所述從進程，人工蜂群算法的所述初始蜜源信息為TSP的路徑序列；

通過所述從進程根據TSP的路徑長度確定人工蜂群算法的跟隨蜂的搜索的蜜源；

通過所述從進程根據TSP的路徑總數及人工蜂群算法的偵察蜂監測到無效蜜源后進行重新隨機搜索蜜源以放棄無效蜜源跳出局部最優解；

通過所述主進程獲取到所述從進程的返回的非放棄的所有所述蜜源為最優蜜源，所述最優蜜源為所述TSP的最短路徑；

通過所述從進程根據TSP的路徑總數及人工蜂群算法的偵察蜂監測到無效蜜源后進行重新隨機搜索蜜源以放棄無效蜜源跳出局部最優解具體包括：

設定所述偵察蜂的搜索最高限制次數LIMIT，當一所述蜜源在搜索次數達到所述最高限制次數LIMIT后仍未找到更好蜜源，則放棄所述蜜源；

偵察蜂放棄當前蜜源的條件為：其中NP為當前路徑總數；

通過所述從進程根據TSP的路徑長度確定人工蜂群算法的跟隨蜂的搜索的蜜源具體包括：

通過所述從進程根據TSP的路徑長度及函數確定人工蜂群算法的跟隨蜂的蜜源的收益度蜂；

通過預置概率ρ對所述蜜源進行選擇，其中，rank是TSP的一所述蜜源對應的路徑的長度排位，path_num則是TSP的路徑總數。

2.根據權利要求1所述的基于人工蜂群算法的并行優化處理TSP問題的方法，其特征在于，通過所述主進程獲取到所述從進程的返回的非放棄的所有所述蜜源為最優蜜源具體包括：

通過所述主進程獲取到所述從進程的返回的非放棄的所有所述蜜源，并同時更新所有從進程的各個所述蜜源信息，收集所有所述蜜源選取所述最優蜜源。

3.根據權利要求1所述的基于人工蜂群算法的并行優化處理TSP問題的方法，其特征在于，通過所述從進程根據TSP的路徑長度確定人工蜂群算法的跟隨蜂的搜索的蜜源之前還包括：

通過所述從進程進行人工蜂群算法的引領蜂的鄰域搜索所述初始蜜源信息。

4.一種基于人工蜂群算法的并行優化處理TSP問題的裝置，其特征在于，包括：

進程建立單元，用于通過MPI接口建立多個并行進程，所述并行進程包括主進程和從進程，通過所述主進程將初始蜜源信息分發給所述從進程，人工蜂群算法的所述初始蜜源信息為TSP的路徑序列；

跟隨蜂單元，用于通過所述從進程根據TSP的路徑長度確定人工蜂群算法的跟隨蜂的搜索的蜜源；

偵察蜂單元，用于通過所述從進程根據TSP的路徑總數及人工蜂群算法的偵察蜂監測到無效蜜源后進行重新隨機搜索蜜源以放棄無效蜜源跳出局部最優解；

返回單元，用于通過所述主進程獲取到所述從進程的返回的非放棄的所有所述蜜源為最優蜜源，所述最優蜜源為所述TSP的最短路徑；

偵察蜂單元，具體用于設定所述偵察蜂的搜索最高限制次數LIMIT，當一所述蜜源在搜索次數達到所述最高限制次數LIMIT后仍未找到更好蜜源，則放棄所述蜜源；

偵察蜂放棄當前蜜源的條件為：其中NP為當前路徑總數；

跟隨蜂單元具體包括：

第一計算子單元，用于通過所述從進程根據TSP的路徑長度及函數確定人工蜂群算法的跟隨蜂的蜜源的收益度蜂；

第二計算子單元，用于通過預置概率ρ對所述蜜源進行選擇，其中，rank是TSP的一所述蜜源對應的路徑的長度排位，path_num則是TSP的路徑總數。

5.根據權利要求4所述的基于人工蜂群算法的并行優化處理TSP問題的裝置，其特征在于，返回單元，具體用于通過所述主進程獲取到所述從進程的返回的非放棄的所有所述蜜源，并同時更新所有從進程的各個所述蜜源信息，收集所有所述蜜源選取所述最優蜜源。

6.根據權利要求4所述的基于人工蜂群算法的并行優化處理TSP問題的裝置，其特征在于，還包括：

引領蜂單元，用于通過所述從進程進行人工蜂群算法的引領蜂的鄰域搜索所述初始蜜源信息。