項目二學習智能鼠迷宮搜索優化算法1學習目標（1）學習智能鼠行走迷宮最優路徑規劃方法——蟻群算法。在綜合篇中已經介紹了智能鼠走迷宮的基礎算法，相信讀者已經對此有了基本的認知和掌握。現在介紹走迷宮競賽中會應用到的較常見的幾種高級算法。2任務一學習基于蟻群算法的最優路徑選擇3任務一學習基于蟻群算法的最優路徑選擇一、蟻群算法理論在自然界中，螞蟻外出尋找食物的過程中，總是能夠找到一條從洞穴到食物之間的最短路徑。螞蟻沒有視覺，依靠的是體內分泌的一種化學物質——人類命名為信息素來相互通信。分泌信息素的量與路徑長短有關，路徑越長，信息素的濃度越低。信息素可以吸引螞蟻沿濃度高的路徑前進，吸引的螞蟻越多，留下的信息素就越多，螞蟻就越容易選擇這條路徑。這樣，大量螞蟻的集體行為如同信息的正反饋一般，整個蟻群最終會按照最短的路徑前進。4任務一學習基于蟻群算法的最優路徑選擇二、基于蟻群算法最優路徑模型蟻群算法的本質在于其選擇機制、更新機制、協調機制。作為一種應用于組合優化問題的算法，蟻群算法的基本的邏輯結構如下圖所示。三、模型建立用數學方法建立模型，給出一個n個節點組成的集合。尋找最優路徑的問題可以視為訪問每個節點一次找到最短路徑的問題。bi(t)，（i=1，…，n）表示t時刻在節點i中的螞蟻數量。螞蟻的總數可表示為

τij為t時刻從節點i到節點j路徑上的信息量，tij(0)可以設置為任意數值。節點i和節點j之間的距離dij可定義為為了不重復訪問，為每個螞蟻定義一個數據結構用于記錄螞蟻k訪問過的節點，稱為禁忌表tabuk。在螞蟻行動過程中tabuk動態調整，一次循環結束后禁忌表歸零。在行進過程中，螞蟻根據每條路徑上的信息素量及路徑的啟發信息來計算轉移概率Pij。啟發函數hij等于1/dij，表示螞蟻從節點i轉移到節點j的期望程度。節點i到節點j的轉移概率定義為

式中，allowedk={C-tabuk}表示螞蟻k下一步允許選擇的節點。α反映了螞蟻在運動過程中所積累的信息在運動時所起的作用，β反映了螞蟻在運動過程中啟發信息在選擇路徑時的受重視程度。5任務一學習基于蟻群算法的最優路徑選擇

6任務一學習基于蟻群算法的最優路徑選擇五、參數設置采用ANT-cycle模型需要設置以下參數：信息啟發式因子α：α<1時收斂速度較慢；α≥2時收斂速度較快，最佳取值范圍為1≤α≤1.5。期望啟發式因子β：β>5時收斂過快，系統迅速在次優循環處卡住；β≤1時收斂緩慢；1<β≤5時收斂速度加快。信息素揮發系數r：值低于0.2或大于0.5時收斂速度較慢，約0.3時最佳。信息素強度Q對算法的影響：表示螞蟻在循環一周時釋放在所經路徑上的信息總量，其作用是為了算法在正反饋的作用下，以合理的速度找到問題的全局最優解。Q值越大，則在螞蟻已走過的路徑上的信息素的積累越快。可以加強算法的正反饋性能，有利于算法的快速收斂。默認Q=100。六、基于蟻群算法的最優路徑選擇算法實現應用蟻群算法求解智能鼠路徑優化問題的主要步驟如下：第一步：輸入由0和1組成的矩陣代表地圖。其中0表示無障礙，1表示有障礙。7任務一學習基于蟻群算法的最優路徑選擇

8任務一學習基于蟻群算法的最優路徑選擇使用蟻群算法經過計算機計算最終得到的結果圖收斂曲線中迭代次數和路徑長度的關系圖9思考與總結（1）