[發(fā)明專利]使用基于MapReduce的蟻群優(yōu)化技術求解組合優(yōu)化問題的方法

無效

• 申請?zhí)枺?/td>: 201210433343.8
• 申請日: 2012-11-02
• 公開（公告）號: CN102982389A
• 公開（公告）日: 2013-03-20
• 發(fā)明（設計）人: 吳剛;吳碧晗;王巖冰;楊夢東;劉翔宇;漆桂林
• 申請（專利權）人: 東南大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 柏尚春

技術領域

本發(fā)明涉及的是組合優(yōu)化問題求解技術領域的方法，具體的說，涉及的是使用基于MapReduce的蟻群優(yōu)化技術求解組合優(yōu)化問題的方法。

背景技術

蟻群算法（Ant?Colony?Optimization,ACO）是一種仿生的元啟發(fā)式算法，源自于蟻群尋找食物的自然過程，具有可分布性、魯棒性等優(yōu)點，是元啟發(fā)式算法中較優(yōu)的一種，并被廣泛應用于解決各種組合優(yōu)化問題，例如具有NP難度的旅行商（TSP）問題的最優(yōu)解答，Job?Shop調度問題、二次指派問題以及多維背包問題等。在實際工程應用中蟻群算法被大量應用于數(shù)據(jù)分析、機器人協(xié)作問題求解、電力、通信、水利、采礦、化工、建筑、交通等領域。然而，經典蟻群算法時間空間開銷巨大，性能隨著問題規(guī)模的擴大而下降的嚴重問題。在計算機領域，可以通過采用分布式并行處理技術提高系統(tǒng)的可伸縮性（scalability）。

經對現(xiàn)有技術的文獻檢索發(fā)現(xiàn)，文章Parallel?Multicolony?ACO?Algorithm?WithExchange?of?Solutions，Proceedings?of?the18th?Belgium-Netherlands?Conference?onArtificial?Intelligence,2006:409-410（基于解交換的并行多群ACO算法）提出了采用MPI（Message?Passing?Interface）并行編程技術在多機環(huán)境下實現(xiàn)蟻群算法并解決TSP問題的方法,該方法具有一定的優(yōu)點，但是該方法由于基于MPI技術，一方面無法保證系統(tǒng)的魯棒性，另一方面復雜的MPI編程模型增加了開發(fā)難度。文章Scaling?Populations?of?a?Genetic?Algorithm?for?Job?Shop?Scheduling?Problemsusing?MapReduce，Proceedings?of?the2010IEEE?Second?International?Conference?onCloud?Computing?Technology?and?Science,2010：780-785（使用MapReduce擴大Job?Shop調度問題的遺傳算法種群）提出了采用MapReduce技術實現(xiàn)遺傳算法解決一定規(guī)模Job?Shop調度問題的方法，該方法也具有一定的優(yōu)點，但該方法需要多次MapReduce迭代，限制了算法性能的提高。

發(fā)明內容

本發(fā)明針對現(xiàn)有技術的不足，提供使用基于MapReduce的蟻群優(yōu)化技術求解組合優(yōu)化問題的方法，通過對組合優(yōu)化問題的解空間進行劃分，并充分利用MapReduce技術所具有的簡單、可伸縮性強的特點，提高蟻群算法的并行化程度，改善其性能。本發(fā)明將有助于提高求解大規(guī)模組合優(yōu)化問題的效率。

本發(fā)明是通過以下技術方案實現(xiàn)的：使用基于MapReduce的蟻群優(yōu)化技術求解組合優(yōu)化問題的方法，包括以下步驟：

1）根據(jù)設定的mapper的數(shù)量劃分指定組合優(yōu)化問題的解空間；

2）Map階段，每個mapper獨立并行地在步驟1)劃分得到的子問題解空間中執(zhí)行改進的蟻群算法，搜索局部最優(yōu)解；

3）Reduce階段，reducer接受所有mapper在不同解空間搜索到的局部最優(yōu)解，根據(jù)步驟1)中采用的解空間劃分情況綜合得到全局最優(yōu)解；

4）輸出reducer當前得到的全局最優(yōu)解，結束。

步驟1），具體為：分析指定組合優(yōu)化問題的解空間類型，并根據(jù)設定的mapper數(shù)量劃分解空間，令每個mapper分別在不同的子空間內搜索局部問題的解；其中，所述的問題的解空間是指：設問題的解向量為x=(x₁，x₂，…,x_i…,x_n)，x_i的取值范圍為有窮集S,把x的所有可能取值組合稱為問題的解空間，i、n均為自然數(shù)；每一個組合是問題的一個可能解；可行解是滿足約束條件的解，是解空間中的一個子集；最優(yōu)解是使目標函數(shù)取極值的可行解；解空間組織成子集樹或排列樹形式。

步驟2），即MapReduce的Map函數(shù)，其中，所述的改進的蟻群算法，具體包括如下步驟：

①根據(jù)步驟1)劃分得到的子問題規(guī)模選擇螞蟻數(shù)和迭代次數(shù)，初始化個體的信息素值和待選個體集，具體設置如下：