《智能機(jī)器人創(chuàng)新設(shè)計(jì)》 課件 第14章 智能算法綜合比較

第14章智能算法綜合比較智慧物流系統(tǒng)：從設(shè)計(jì)到實(shí)現(xiàn)教學(xué)內(nèi)容CONTENTS1單路徑規(guī)劃算法效果比較2任務(wù)分配算法效果比較3

章節(jié)目標(biāo)掌握機(jī)器人路徑規(guī)劃三種算法的原理與結(jié)論；掌握三種任務(wù)分配算法的原理與結(jié)論。4單路徑規(guī)劃算法的總結(jié)路徑規(guī)劃是規(guī)劃出一條連接起點(diǎn)到終點(diǎn)的序列點(diǎn)或者曲線。單機(jī)器人路徑規(guī)劃是為單個(gè)機(jī)器人規(guī)劃出一條從起點(diǎn)到終點(diǎn)的通行路線。1單路徑規(guī)劃算法效果比較本書前章共講述了三種單路徑規(guī)劃的方法：廣度優(yōu)先搜索算法(BFS)、深度優(yōu)先搜索算法(DFS)和A*搜索算法，接下來將概述這三種單機(jī)器人路徑規(guī)劃算法的差異。5一、原理比較1.廣度優(yōu)先搜索算法將地圖中所有的節(jié)點(diǎn)系統(tǒng)地展開并檢查，直到找到結(jié)果為止。2.深度優(yōu)先搜索算法“不撞南墻不回頭”，一條路走到黑，走不通掉頭往回走，回到路口之后進(jìn)入另一條路，直到找到結(jié)果為止。3.A*搜索算法根據(jù)F(n)=G(n)+H(n)公式，計(jì)算估值函數(shù)并且選擇函數(shù)值小的方向前進(jìn)，走不通的路，就返回路口重新選擇函數(shù)值小的方向前進(jìn)，直到找到結(jié)果為止。1單路徑規(guī)劃算法效果比較6一、原理比較1.廣度優(yōu)先搜索算法將地圖中所有的節(jié)點(diǎn)系統(tǒng)地展開并檢查，直到找到結(jié)果為止。1單路徑規(guī)劃算法效果比較7一、原理比較2.深度優(yōu)先搜索算法“不撞南墻不回頭”，一條路走到黑，走不通掉頭往回走，回到路口之后進(jìn)入另一條路，直到找到結(jié)果為止。1單路徑規(guī)劃算法效果比較8一、原理比較3.A*搜索算法根據(jù)F(n)=G(n)+H(n)公式，計(jì)算估值函數(shù)并且選擇函數(shù)值小的方向前進(jìn)，走不通的路，就返回路口重新選擇函數(shù)值小的方向前進(jìn)，直到找到結(jié)果為止。1單路徑規(guī)劃算法效果比較9二、效果比較以物流機(jī)器人執(zhí)行下述任務(wù)為例，確保三種算法執(zhí)行任務(wù)條件相同，如下表所示。1單路徑規(guī)劃算法效果比較機(jī)器人數(shù)量1機(jī)器人編號(hào)R00機(jī)器人初始位置R00（0,0）機(jī)器人初始朝向R00右訂單情況（任務(wù)）取C06貨物1個(gè)貨架位置S06（5,6）任務(wù)條件10分別執(zhí)行三種算法，從路徑長度上去分析不同算法的路徑長度。圖1為廣度優(yōu)先搜索算法路徑規(guī)劃效果，圖2為深度優(yōu)先搜索算法路徑規(guī)劃效果，圖3為A*搜索算法路徑規(guī)劃效果。1單路徑規(guī)劃算法效果比較圖1圖2圖311二、效果比較從規(guī)劃效果上分析，在不加入轉(zhuǎn)向時(shí)間等因素的情況下，廣度優(yōu)先搜索算法和A*搜索算法規(guī)劃出的路徑長度是一樣的。廣度優(yōu)先搜索算法的一層層搜索特點(diǎn)，會(huì)將終點(diǎn)之前所有的點(diǎn)都搜索完才能規(guī)劃出路徑；深度優(yōu)先搜索算法“不撞南墻不回頭”的特點(diǎn)，規(guī)劃出的路徑繞了很遠(yuǎn)；A*算法根據(jù)估值函數(shù)較小值選擇前進(jìn)方向的特點(diǎn)規(guī)劃出的路徑會(huì)有較多的轉(zhuǎn)彎。1單路徑規(guī)劃算法效果比較12三、時(shí)間比較分析三種算法各自的①計(jì)算時(shí)間、②預(yù)計(jì)執(zhí)行時(shí)間、③實(shí)際執(zhí)行時(shí)間、從執(zhí)行時(shí)間上分析，廣度優(yōu)先算法的執(zhí)行時(shí)間最短。1單路徑規(guī)劃算法效果比較廣度優(yōu)先搜索算法計(jì)算時(shí)間A*搜索算法計(jì)算時(shí)間深度優(yōu)先搜索算法計(jì)算時(shí)間13一、分配算法的隨機(jī)性分析遺傳算法、粒子群算法與蟻群算法都是隨機(jī)搜索算法。2任務(wù)分配算法效果比較（1）遺傳算法：遺傳算法的隨機(jī)性體現(xiàn)在基因進(jìn)化時(shí)交配和變異會(huì)產(chǎn)生和父代基因不同的基因個(gè)體，也確?；虿粫?huì)很快的收斂到一個(gè)局部最優(yōu)解。（2）粒子群算法：其隨機(jī)性體現(xiàn)在粒子原本的初始速度，每個(gè)粒子在向最優(yōu)粒子靠近時(shí)都有自己原本的速度，這樣可防止粒子群收斂時(shí)出現(xiàn)“自鎖”現(xiàn)象，收斂到局部最優(yōu)解。（3）蟻群算法：其隨機(jī)性體現(xiàn)在選擇路徑中，計(jì)算完每條路徑選擇的概率后，螞蟻會(huì)根據(jù)“轉(zhuǎn)盤抽獎(jiǎng)”的規(guī)則選擇路徑，同樣是為了防止快速收斂到局部最優(yōu)解。14一、分配算法的隨機(jī)性分析遺傳算法：遺傳算法的隨機(jī)性體現(xiàn)在基因進(jìn)化時(shí)交配和變異會(huì)產(chǎn)生和父代基因不同的基因個(gè)體，確保基因不會(huì)很快的收斂到一個(gè)局部最優(yōu)解。2任務(wù)分配算法效果比較計(jì)算機(jī)解釋交配設(shè)置一個(gè)交叉概率，從種群中隨機(jī)選擇兩個(gè)基因個(gè)體，這兩個(gè)基因個(gè)體按照交叉概率進(jìn)行基因交換，基因交換的位置隨機(jī)選取。變異設(shè)置一個(gè)變異概率，從種群中隨機(jī)選擇一個(gè)個(gè)體，該個(gè)體按照變異概率進(jìn)行基因變異，變異的基因位置是隨機(jī)的。15一、分配算法的隨機(jī)性分析粒子群算法：其隨機(jī)性體現(xiàn)在粒子原本的初始速度，每個(gè)粒子在向最優(yōu)粒子靠近時(shí)都有自己原本的速度，可防止粒子群收斂時(shí)出現(xiàn)“自鎖”現(xiàn)象，收斂到局部最優(yōu)解。2任務(wù)分配算法效果比較屬性描述速度當(dāng)前粒子所具有的速度由兩部分組成：由先前速度影響遺留下來的慣性速度w；若當(dāng)前粒子不是粒子群中最接近目標(biāo)的粒子時(shí)，該粒子有向著最優(yōu)方向移動(dòng)的趨勢(shì)速度。位置當(dāng)前粒子所在的位置，用以衡量粒子與目標(biāo)的距離歷史最優(yōu)位置當(dāng)前粒子在搜尋目標(biāo)的過程中，距離目標(biāo)最近時(shí)的位置。16一、分配算法的隨機(jī)性分析蟻群算法：其隨機(jī)性體現(xiàn)在選擇路徑中，計(jì)算完每條路徑選擇的概率后，螞蟻會(huì)根據(jù)“轉(zhuǎn)盤抽獎(jiǎng)”的規(guī)則選擇路徑，同樣是為了防止快速收斂到局部最優(yōu)解。2任務(wù)分配算法效果比較轉(zhuǎn)盤抽獎(jiǎng)示意圖17二、分配算法結(jié)果比較以物流機(jī)器人執(zhí)行下述任務(wù)為例，控制三種算法的輸入值不變，執(zhí)行任務(wù)相同，路徑規(guī)劃算法均選擇D*算法。任務(wù)條件如下表所示。2任務(wù)分配算法效果比較機(jī)器人數(shù)量3機(jī)器人編號(hào)R00、R01、R02機(jī)器人初始位置R00（0,1）、R01（0,0）、R02（7,0）機(jī)器人初始朝向R00右、R01右、R02左訂單情況（任務(wù)）取C02貨物1個(gè)、C04貨物1個(gè)、C07貨物1個(gè)貨架位置S02（1,6）、S04（3,6）、S07（6,6）18（1）遺傳算法結(jié)果：

((0,0),(3,6),(2,0))：機(jī)器人(0,0)—>貨架(3,6)—>取貨點(diǎn)(2,0)；((0,1),(1,6),(2,0))：機(jī)器人(0,1)—>貨架(1,6)—>取貨點(diǎn)(2,0)；((7,0),(6,6),(5,0))：機(jī)器人(7,0)—>貨架(6,6)—>取貨點(diǎn)(5,0)。2任務(wù)分配算法效果比較GA-機(jī)器人分配到貨架GA-貨架分配到取貨點(diǎn)19（2）粒子群算法結(jié)果：

((0,0),(1,6),(2,0))：機(jī)器人(0,0)—>貨架(1,6)—>取貨點(diǎn)(2,0)；((0,1),(6,6),(5,0))：機(jī)器人(0,1)—>貨架(1,6)—>取貨點(diǎn)(5,0)；((7,0),(3,6),(2,0))：機(jī)器人(7,0)—>貨架(3,6)—>取貨點(diǎn)(2,0)。2任務(wù)分配算法效果比較PSO-機(jī)器人分配到貨架PSO-貨架分配到取貨點(diǎn)20（3）蟻群算法結(jié)果：

((0,0),(3,6),(2,0))：機(jī)器人(0,0)—>貨架(3,6)—>取貨點(diǎn)(2,0)；((1,0),(1,6),(2,0))：機(jī)器人(1,0)—>貨架(1,6)—>取貨點(diǎn)(2,0)；((7,0),(6,6),(5,0))：機(jī)器人(7,0)—>貨架(6,6)—>取貨點(diǎn)(5,0)。2任務(wù)分配算法效果比較ACO-機(jī)器人分配到貨架ACO-貨架分配到取貨點(diǎn)21二、分配算法結(jié)果比較從分配效果來看，遺傳算法和蟻群算法本次的分配方案是相同的，也是最優(yōu)的分配方案。而粒子群本次的分配方案相對(duì)于遺傳算法和蟻群算法來說就不是最優(yōu)的，機(jī)器人行進(jìn)的路徑長度也不是最短。當(dāng)然，算法是存在隨機(jī)概率的，可能下一次規(guī)劃出的路徑就會(huì)是最優(yōu)或者較優(yōu)的解。2任務(wù)分配算法效果比較22三、分配算法的時(shí)間對(duì)比遺傳算法：算法的平均計(jì)算時(shí)間976.36ms，實(shí)際平均執(zhí)行時(shí)間82s；粒子群算法：算法平均計(jì)算時(shí)間501.96ms，實(shí)際平均執(zhí)行時(shí)間82.05s；蟻群算法：算法平均計(jì)算時(shí)間491.49ms，實(shí)際平均執(zhí)行時(shí)間79.34s2任務(wù)分配算法效果比較粒子群算法時(shí)