第13章多機器人協同調度-蟻群算法智慧物流系統：從設計到實現教學內容CONTENTS1蟻群算法2蟻群算法原理3旅行商問題4蟻群算法評價3

章節目標了解蟻群算法的起源；理解蟻群算法的原理與機制；掌握蟻群算法的信息素更新與濃度計算；了解蟻群算法的優點、缺點及應用前景。4算法起源：蟻群算法（AntColonyOptimization,ACO）是意大利學者MarcoDorigo于1992年基于蟻群覓食的行為特征提出的一種模型進化算法。該算法在求解旅行商問題（TravelingSalesmanProblem,TSP）、分配問題、圖著色問題等方面均取得了較好的結果。隨著群體智能的研究發展，蟻群算法也被應用于多機器人系統的任務分配及調度協作等方面。1蟻群算法5算法起源：蟻群覓食是一種典型的群體智能行為，蟻群尋找食物時會分散探索，如果一只螞蟻找到食物，它將返回巢中通知同伴并沿途留下“信息量”（Pheromone），作為蟻群前往食物所在地的標記。信息量會隨時間揮發，如果兩只螞蟻同時找到同一食物，又采取不同路線回到巢中，那么比較繞遠的一條路上信息量的氣味會比較淡，蟻群將傾向于選擇另一條更近的路線前往食物所在地。1蟻群算法6算法起源：在旅行商問題中，蟻群算法會設計虛擬的“螞蟻”摸索不同的路線，并留下虛擬“信息量”。虛擬的“信息量”也會揮發，每只螞蟻每次隨機選擇要走的路徑，但是它們傾向于選擇路徑比較短、信息量比較濃的路徑。根據“信息量比較濃的路線更近”原則，即可選擇出最佳路線。由于這個算法利用了正反饋機制，使得較短的路徑能夠有較大的機會得到選擇，并且采用概率算法，所以它能夠不局限于局部最優解。1蟻群算法7算法原理：如圖1所示，螞蟻選路過程中較短路徑上遺留的信息量會在短時間內大于較長路徑，蟻群算法的原理不妨用一個例子來說明：假設A、E兩點是蟻群的巢穴和食物源，從其間有兩條路徑A-B-H-D-E和A-B-C-D-E，其中B-H和H-D間距離為1m，B-C和C-D間距離為0.5m。2蟻群算法原理蟻群選擇路徑圖18算法原理：如圖2所示，在A、E點分別分配30只螞蟻從兩點出發，在t=0時刻，30只螞蟻走到分支路口B點或D點。因為初始時沒有什么線索可供螞蟻們選擇，所以以相同的概率決定選擇哪條路徑，結果是15只螞蟻走左邊路徑D-H、B-H；另外15只螞蟻走右邊的路徑D-C、B-C，這些螞蟻在行進過程中分別留下信息量。2蟻群算法原理蟻群選擇路徑圖29算法原理：如圖3所示，假設螞蟻都具有相同的移動速度（1m/s）和釋放信息量的能力。在經過1s后，從D點出發的螞蟻，有15只螞蟻到達H點，還有15只螞蟻經過C點到達B點（D-H=D-C+C-B）；同樣在經過1s后，從B點出發的螞蟻，有15只螞蟻到達H點，還有15只螞蟻經過C點到達D點（B-H=B-C+C-D）。2蟻群算法原理蟻群選擇路徑圖310算法原理：顯然，在相等時間間隔內，路徑D-H-B上共有15只螞蟻經過并留下信息量，路徑D-C-B上共有30只螞蟻經過并留下信息量，其信息量強度是D-H-B路徑上的2倍。因此，當再有30只螞蟻從A、E點出發選擇路徑時，就會以2倍于D-H-B的概率來選擇D-C-B，從而D-H-B上的螞蟻數目變成了10只，是D-C-B上螞蟻數量的一半，D-C-B路徑上的信息量很快得到了強化。2蟻群算法原理蟻群選擇路徑圖311結合旅行商問題實現蟻群算法：問題：假設有一個旅行商人要拜訪n個城市，要求每個城市都要訪問但只能訪問一次，并且最后要回到原來出發的城市，要求得出訪問所有城市的最短旅行路徑。假定城市分布如右圖所示，共5個城市，即n=5。3旅行商問題TSP問題城市分布圖12結合旅行商問題實現蟻群算法：

3旅行商問題TSP問題城市分布圖13結合旅行商問題實現蟻群算法：

3旅行商問題TSP問題城市分布圖14結合旅行商問題實現蟻群算法：對于螞蟻個體和蟻群需要定義一些屬性，如表所示：3旅行商問題屬性符號解釋城市open表city_open存放螞蟻個體未經過的城市坐標。城市close表city_close按順序存放螞蟻已經過的城市坐標。路徑長度value螞蟻經過所有城市的總路程長度。螞蟻個體屬性15結合旅行商問題實現蟻群算法：3旅行商問題蟻群屬性屬性蟻群規模符號m解釋蟻群包含的螞蟻數量，通常m=1.5n最短路徑長度best_value歷史解中最短的路徑長度。最佳路徑best_route歷史解中最短路徑長度對應的路徑。信息素揮發因子ρ信息素隨時間揮發，ρ∈[0,1]。信息素啟發因子α信息素的影響程度，通常α∈[1,9]期望啟發因子β某種啟發式搜索的影響程度，通常β∈[1,9]信息素濃度常數Q一只螞蟻攜帶的信息素濃度通常Q∈[10,100]16結合旅行商問題實現蟻群算法：

3旅行商問題TSP問題城市分布圖

17結合旅行商問題實現蟻群算法：3旅行商問題“轉盤抽獎”示意圖

18結合旅行商問題實現蟻群算法：3旅行商問題當第一批的m只螞蟻都經過一圈n個城市后，每只螞蟻的路徑長度value都得到了記錄。19結合旅行商問題實現蟻群算法：3旅行商問題關于其他首批螞蟻走過的路徑以及路徑長度圖示見教材p148，其中，最小value圖如下：同時更新記錄：最佳路徑best_route和最短距離best_valuebest_value=12.683best_route:[4,8]->[3,5]->[4,1]->[6,2]->[9,3]->[4,8]接下來對每條城市間路徑的信息素進行更新：20結合旅行商問題實現蟻群算法：3旅行商問題

21結合旅行商問題實現蟻群算法：3旅行商問題

①圓周系統利用的是整體信息，②③系統模型中利用的是局部信息，因此在解決旅行商問題時我們選擇①模型性能更好。

22結合旅行商問題實現蟻群算法：3旅行商問題停止條件：可以用固定的進化代數或者當進化趨勢不明顯時停止計算。蟻群算法的整體程序框架如圖所示。23算法缺點：4蟻群算法評價蟻群算法與已經發展完備的一些算法（如遺傳算法等）比較起來，計算量比較大，而且效果也不一定好，但是仿生算法如遺傳算法、粒子群算法等的成功應用還是激起了人們對于蟻群算法的極大興趣。蟻群算法還是一種新型的模擬進化算法，其研究剛剛開始。現階段對蟻群算法的研究還停留在仿真階段，有許多問題有待進一步研究，如算法的收斂性、理論依據等。另外該算法也有一些缺陷，例如蟻群在運動過程中，許多個體的運動是隨機的，當群體規模較大時，需要花大量時間才可以尋找到一條最優或者較優路徑。24算法缺點：4蟻群算法評價在多機器人物流系統中，蟻群算法在分配任務的過程時，通過計算螞蟻小隊走過的路徑長度來判斷路徑是否為最優，在物流機器人、貨架、取貨點的分配過程中，將計算路徑規劃算法的執行時間（最后一個機器人執行完成的時間）作為螞蟻小隊走過的路徑長度。時間越短對應路徑就越短，路徑越短對應執行就越快完成，分配的組合就越優。25算法缺點：4蟻群算法評價輸出每一代螞蟻走過的路徑長度(機器人-貨架-取貨點)。下圖表示每一代蟻群中每一隊螞蟻走過的路徑長度。26算法缺點：4