《智能機(jī)器人創(chuàng)新設(shè)計(jì)》 課件 第13章 多機(jī)器人協(xié)同調(diào)度-蟻群算法

第13章多機(jī)器人協(xié)同調(diào)度-蟻群算法智慧物流系統(tǒng)：從設(shè)計(jì)到實(shí)現(xiàn)教學(xué)內(nèi)容CONTENTS1蟻群算法2蟻群算法原理3旅行商問題4蟻群算法評價(jià)3

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

3旅行商問題TSP問題城市分布圖13結(jié)合旅行商問題實(shí)現(xiàn)蟻群算法：

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

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

17結(jié)合旅行商問題實(shí)現(xiàn)蟻群算法：3旅行商問題“轉(zhuǎn)盤抽獎”示意圖

18結(jié)合旅行商問題實(shí)現(xiàn)蟻群算法：3旅行商問題當(dāng)?shù)谝慌膍只螞蟻都經(jīng)過一圈n個(gè)城市后，每只螞蟻的路徑長度value都得到了記錄。19結(jié)合旅行商問題實(shí)現(xiàn)蟻群算法：3旅行商問題關(guān)于其他首批螞蟻?zhàn)哌^的路徑以及路徑長度圖示見教材p148，其中，最小value圖如下：同時(shí)更新記錄：最佳路徑best_route和最短距離best_valuebest_value=12.683best_route:[4,8]->[3,5]->[4,1]->[6,2]->[9,3]->[4,8]接下來對每條城市間路徑的信息素進(jìn)行更新：20結(jié)合旅行商問題實(shí)現(xiàn)蟻群算法：3旅行商問題

21結(jié)合旅行商問題實(shí)現(xiàn)蟻群算法：3旅行商問題

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

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