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

有效

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

本發明實施例公開了一種基于人工蜂群算法的并行優化處理TSP問題的方法及裝置，解決了目前對于像解空間隨問題規模增大而呈指數增長的NP難題，由于硬件核心的工藝制作已經到達瓶頸，導致的難以通過對單個核心的制造來提高性能的技術問題。本發明實施例方法包括：通過MPI接口建立多個并行進程，通過主進程將初始蜜源信息分發給從進程；通過從進程根據TSP的路徑長度確定人工蜂群算法的跟隨蜂的搜索的蜜源；通過從進程根據TSP的路徑總數及人工蜂群算法的偵察蜂監測到無效蜜源后進行重新隨機搜索蜜源以放棄無效蜜源跳出局部最優解；通過主進程獲取到從進程的返回的非放棄的所有蜜源為最優蜜源，最優蜜源為TSP的最短路徑。

技術領域

本發明涉及計算機技術領域，尤其涉及一種基于人工蜂群算法的并行優化處理TSP問題的方法及裝置。

背景技術

人工蜂群算法是模仿蜜蜂行為提出的一種優化方法，是集群智能思想的一個具體應用，它的主要特點是不需要了解問題的特殊信息，只需要對問題進行優劣的比較，通過各人工蜂個體的局部尋優行為，最終在群體中使全局最優值突現出來，有著較快的收斂速度。為了解決多變量函數優化問題，Karaboga提出了人工蜂群算法ABC模型(artificial beecolony algorithm)。

作為人工蜂群算法應用，討論旅行商問題(Travelling Salesman Problem，TSP)：設有n個城市，用數(1,…,n)代表。城市i和城市j之間的距離為d(i，j)i,j＝1,…,n.TSP問題的目標是要找遍訪每個域市恰好一次，最后回到出發城市，形成一條回路，且其路徑總長度為最短。解空間：解空間S是遍訪每個城市恰好一次的所有回路。

目前對于像解空間隨問題規模增大而呈指數增長的NP難題，在問題規模較小時，通過一些算法可以在一定程度上較好的解決問題，但問題規模持續增大時，由于現階段，硬件核心的工藝制作已經到達瓶頸，導致了難以通過對單個核心的制造來提高性能的技術問題。

發明內容

本發明實施例提供的一種基于人工蜂群算法的并行優化處理TSP問題的方法及裝置，解決了目前對于像解空間隨問題規模增大而呈指數增長的NP難題，在問題規模較小時，通過一些算法可以在一定程度上較好的解決問題，但問題規模持續增大時，由于現階段，硬件核心的工藝制作已經到達瓶頸，導致的難以通過對單個核心的制造來提高性能的技術問題。

本發明實施例提供的一種基于人工蜂群算法的并行優化處理TSP問題的方法，包括：

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

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

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

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

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

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

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

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