第14章智能算法綜合比較智慧物流系統：從設計到實現教學內容CONTENTS1單路徑規劃算法效果比較2任務分配算法效果比較3

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

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

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

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