基于Matlab的Dijkstra算法与蚁群优化算法路径规划

3基于matlab的Dijkstra和蚁群优化算法路径规划 Dijkstra算法研究的是从初始点到其他每一结点的最短路径从而得到最短路径 蚂蚁会以较大的概率优先选择信息素浓度较高的路径 并释放一定量的信息素 以增强该条路径上的信息素浓度 形成一个正反馈 最终 蚂蚁能够找到一条从巢穴到食物源的最佳路径 程序已调通可直接运行今天咱们聊聊机器人路径规划里两个经典玩法学院派老大哥Dijkstra和生物仿生流派的蚁群算法。这两种算法在MATLAB里跑起来还挺有意思特别是看着蚂蚁们怎么从瞎晃悠到找到最优路线跟看动物世界似的。先看Dijkstra这老实人算法。核心思想就一句话——所有岔路都走一遍肯定能找到最短的。来看这段MATLAB实现function [path, dist] dijkstra(adjMatrix, startNode) numNodes size(adjMatrix,1); visited false(1,numNodes); distance inf(1,numNodes); distance(startNode) 0; for i 1:numNodes-1 [~, currentNode] min(distance .* ~visited); visited(currentNode) true; for neighbor find(adjMatrix(currentNode,:)) if ~visited(neighbor) (distance(currentNode) adjMatrix(currentNode,neighbor) distance(neighbor)) distance(neighbor) distance(currentNode) adjMatrix(currentNode,neighbor); end end end % 后边还有回溯路径的代码... end这代码最骚的是用邻接矩阵存图结构currentNode每次选未访问节点里最小的。注意那个.* ~visited操作既排除了已访问节点又保持矩阵维度这种向量化操作才是MATLAB的精髓。不过当节点数上去之后这种暴力搜索效率就捉急了。3基于matlab的Dijkstra和蚁群优化算法路径规划 Dijkstra算法研究的是从初始点到其他每一结点的最短路径从而得到最短路径 蚂蚁会以较大的概率优先选择信息素浓度较高的路径 并释放一定量的信息素 以增强该条路径上的信息素浓度 形成一个正反馈 最终 蚂蚁能够找到一条从巢穴到食物源的最佳路径 程序已调通可直接运行转头看看蚁群算法完全是另一番景象。百来只蚂蚁在地图上瞎逛愣是能走出最优路线。参数设置是门玄学咱们看核心迭代部分for iter 1:maxIter % 蚂蚁放出去溜达 for k 1:numAnts path startNode; while path(end) ~ endNode next selectNextNode(tau, eta, allowedNodes, alpha, beta); path [path, next]; end % 更新信息素... end % 信息素挥发 tau (1 - rho) * tau; % 精英蚂蚁加强 [bestDist, idx] min(allDistances); tau updateTau(tau, bestPath, bestDist); endselectNextNode函数里藏着蚂蚁选路的秘密——用轮盘赌选择概率prob (tau(current,allowed).^alpha) .* (eta(current,allowed).^beta); prob prob / sum(prob); nextIndex randsample(1:length(allowed), 1, true, prob);alpha控制信息素权重beta影响启发因子通常取距离倒数。参数调不好就容易陷入局部最优这时候加个精英保留策略让每次迭代的最优路径额外增加信息素相当于给算法加了个记忆功能。跑起来对比挺有意思Dijkstra在30x30的栅格地图上稳稳当当生成最短路径耗时0.8秒蚁群算法前20代还在抽风似的乱撞50代后突然开窍找到最优解耗时3.2秒但路径更丝滑。实际应用里前者适合静态环境导航后者在动态障碍物场景下更有优势——毕竟蚂蚁们随时能用信息素更新路线。最后说个坑信息素初始值别设太小否则前期收敛太慢。见过有人设成0.01结果迭代200次还没找到路活活把程序跑成屏保动画。建议用1/(平均节点数*平均距离)当初始值亲测好使。