【路径规划】改进的蚁群算法避障路径规划【含Matlab源码 335期】 |
您所在的位置:网站首页 › 蚁群觅食视频播放 › 【路径规划】改进的蚁群算法避障路径规划【含Matlab源码 335期】 |
✅博主简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,Matlab项目合作可私信。 🍎个人主页:海神之光 🏆代码获取方式: 海神之光Matlab王者学习之路—代码获取方式 ⛳️座右铭:行百里者,半于九十。 更多Matlab仿真内容点击👇 Matlab图像处理(进阶版) 路径规划(Matlab) 神经网络预测与分类(Matlab) 优化求解(Matlab) 语音处理(Matlab) 信号处理(Matlab) 车间调度(Matlab) ⛄一、蚁群算法简介1 引言 在自然界中各种生物群体显现出来的智能近几十年来得到了学者们的广泛关注,学者们通过对简单生物体的群体行为进行模拟,进而提出了群智能算法。其中, 模拟蚁群觅食过程的蚁群优化算法(Ant Colony Optimization, A CO) 和模拟鸟群运动方式的粒子群算法(ParticleS warm Optimization,PSO) 是两种最主要的群智能算法。 蚁群算法是一种源于大自然生物世界的新的仿生进化算法,由意大利学者M.Dorigo, V.Mani ezzo和A.Color ni等人于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径行为而提出的一种基于种群的启发式随机搜索算法[1].蚂蚁有能力在没有任何提示的情形下找到从巢穴到食物源的最短路径,并且能随环境的变化,适应性地搜索新的路径,产生新的选择。其根本原因是蚂蚁在寻找食物时,能在其走过的路径上释放一种特殊的分泌物――信息素2,随着时间的推移该物质会逐渐挥发,后来的蚂蚁选择该路径的概率与当时这条路径上信息素的强度成正比。当一条路径上通过的蚂蚁越来越时,其留下的信息素也越来越多,后来蚂蚁选择该路径的概率也就越高,从而更增加了该路径上的信息素强度。而强度大的信息素会吸引更多的蚂蚁,从而形成一种正反馈机制。通过这种正反馈机制,蚂蚁最终可以发现最短路径。 最早的蚁群算法是蚂蚁系统(Ant System, AS) , 研究者们根据不同的改进策略对蚂蚁系统进行改进并开发了不同版本的蚁群算法,并成功地应用于优化领域。用该方法求解旅行商(TSP) 问题、分配问 题、车间作业调度(job-shop) 问题, 取得了较好的试验结果[3-6] 。蚁群算法具有分布式计算、无中心控制和分布式个体之间间接通信等特征,易于与其他优化算法相结合,它通过简单个体之间的协作表现出了求解复杂问题的能力,已被广泛应用于求解优化问题。蚁群算法相对而言易于实现,且算法中并不涉及复杂的数学操作,其处理过程对计算机的软硬件要求也不高,因此对它的研究在理论和实践中都具有重要的意义。 目前,国内外的许多研究者和研究机构都开展了对蚁群算法理论和应用的研究,蚁群算法已成为国际计算智能领域关注的热点课题。虽然目前蚁群算法没有形成严格的理论基础,但其作为一种新兴的进 化算法已在智能优化等领域表现出了强大的生命力。 2 蚁群算法理论 蚁群算法是对自然界蚂蚁的寻径方式进行模拟而得出的一种仿生算法。蚂蚁在运动过程中,能够在它所经过的路径上留下信息素进行信息传递,而且蚂蚁在运动过程中能够感知这种物质,并以此来指导 自己的运动方向。因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大[7]。 2.1真实蚁群的觅食过程 为了说明蚁群算法的原理,先简要介绍一下蚂蚁搜寻食物的具体过程。在自然界中,蚁群在寻找食物时,它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出 一种特殊的信息素。蚁群算法的信息交互主要是通过信息素来完成的。蚂蚁在运动过程中,能够感知这种物质的存在和强度。初始阶段,环境中没有信息素的遗留,蚂蚁寻找事物完全是随机选择路径, 随后寻找该事物源的过程中就会受到先前蚂蚁所残留的信息素的影响,其表现为蚂蚁在选择路径时趋向于选择信息素浓度高的路径。同时,信息素是一种挥发性化学物,会随着时间的推移而慢慢地消逝。如果每只蚂蚁在单位距离留下的信息素相同,那对于较短路径上残留的信息素浓度就相对较高,这被后来的蚂蚁选择的概率就大,从而导致这条短路径上走的蚂蚁就越多。而经过的蚂蚁越多,该路径上残留的信息素就将更多,这样使得整个蚂蚁的集体行为构成了信息素的正反馈过程,最终整个蚁群会找出最优路径。 若蚂蚁从A点出发,速度相同,食物在D点,则它可能随机选择路线ABD或A CD。假设初始时每条路线分配一只蚂蚁, 每个时间单位行走一步。图5.1所示为经过8个时间单位时的情形:走路线ABD的蚂蚁到达终点:而走路线A CD的蚂蚁刚好走到C点, 为一半路程。 2.2人工蚁群的优化过程 基于以上真实蚁群寻找食物时的最优路径选择问题,可以构造人工蚁群, 来解决最优化问题, 如TSP问题。人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高,所以能够最终被所有蚂蚁选择,也就是最终的优化结果。两者的区别在于人工蚁群有一定的记忆能力,能够记忆已经访问过的节点。同时,人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径,而不是盲目的。例如在TSP问题中, 可以预先知道当前城市到下一个目的地的距离。在TSP问题的人工蚁群算法中, 假设m只蚂蚁在图的相邻节点间移动,从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定:一是信息素值,也称信息素痕迹:二是可见度,即先验值。 信息素的更新方式有两种:一是挥发,也就是所有路径上的信息素以一定的比率减少,模拟自然蚁群的信息素随时间挥发的过程;二是增强,给评价值“好”(有蚂蚁走过)的边增加信息素。蚂蚁向下一个目标的运动是通过一个随机原则来实现的,也就是运用当前所在节点存储的信息,计算出下一步可达节点的概率,并按此概率实现一步移动,如此往复,越来越接近最优解。蚂蚁在寻找过程中,或在找到一个解后,会评估该解或解的一部分的优化程度,并把评价信息保存在相关连接的信息素中。 2.3真实蚂蚁与人工蚂蚁的异同 蚁群算法是一种基于群体的、用于求解复杂优化问题的通用搜索技术。与真实蚂蚁通过外信息的留存、跟随行为进行间接通信相似,蚁群算法中一群简单的人工蚂蚁通过信息素进行间接通信,并利用该信息和与问题相关的启发式信息逐步构造问题的解。 人工蚂蚁具有双重特性:一方面,它们是真实蚂蚁的抽象,具有真实蚂蚁的特性:另一方面,它们还有一些真实蚂蚁没有的特性,这些新的特性使人工蚂蚁在解决实际优化问题时,具有更好地搜索较优解的能力。 人工蚂蚁与真实蚂蚁的相同点为: (1)都是一群相互协作的个体。与真实蚁群一样,蚁群算法由一群人工蚂蚁组成,人工蚂蚁之间通过同步/异步协作来寻找问题的最优解。虽然单只人工蚂蚁可以构造出问题的解,但只有当多只人工蚂蚁 通过相互协作,才能发现问题的最优(次优)解。人工蚂蚁个体间通过写/读问题的状态变量来进行协作。 (2)都使用信息素的迹和蒸发机制。如真实蚂蚁一样,人工蚂蚁通过改变所访问过的问题的数字状态信息来进行间接的协作。在蚁群算法中,信息素是人工蚂蚁之间进行交流的唯一途径。这种通信方式在群体知识的利用上起到了至关重要的作用。另外,蚁群算法还用到了蒸发机制,这一点对应于真实蚂蚁中信息素的蒸发现象。蒸发机制使蚁群逐渐忘记过去的历史,使后来的蚂蚁在搜索中较少受到过去较差解的影响,从而更好地指导蚂蚁的搜索方向。 (3)搜索最短路径与局部移动。人工蚂蚁和真实蚂蚁具有相同的任务,即以局部移动的方式构造出从原点(蚁巢)到目的点(食物源)之间的最短路径。 (4)随机状态转移策略。人工蚂蚁和真实蚂蚁都按照概率决策规则从一种状态转移到另一种相邻状态。其中的概率决策规则是与问题相关的信息和局部环境信息的函数。在状态转移过程中,人工蚂蚁和 真实蚂蚁都只用到了局部信息,没有使用前瞻策略来预见将来的状态。 人工蚂蚁和真实蚂蚁的不同点为: (1)人工蚂蚁生活在离散的时间,从一种离散状态到另一种离散状态。 (2)人工蚂蚁具有内部状态,即人工蚂蚁具有一定的记忆能力,能记住自己走过的地方。 (3)人工蚂蚁释放信息素的数量是其生成解的质量的函数。 (4)人工蚂蚁更新信息素的时机依赖于特定的问题。例如,大多数人工蚂蚁仅仅在蚂蚁找到一个解之后才更新路径上的信息素。 2.4蚁群算法的特点 蚁群算法是通过对生物特征的模拟得到的一种优化算法,它本身具有很多优点: (1)蚁群算法是一种本质上的并行算法。每只蚂蚁搜索的过程彼此独立,仅通过信息激素进行通信。所以蚁群算法可以看作一个分布式的多智能体系统,它在问题空间的多点同时开始独立的解搜索,不仅增加了算法的可靠性,也使得算法具有较强的全局搜索能力。 (2)蚁群算法是一种自组织的算法。所谓自组织,就是组织力或组织指令来自于系统的内部,以区别于其他组织。如果系统在获得空间、时间或者功能结构的过程中,没有外界的特定干预,就可以说系统是自组织的。简单地说,自组织就是系统从无序到有序的变化过程。 (3)蚁群算法具有较强的鲁棒性。相对于其他算法,蚁群算法对初始路线的要求不高,即蚁群算法的求解结果不依赖于初始路线的选择,而且在搜索过程中不需要进行人工的调整。此外,蚁群算法的参 数较少,设置简单,因而该算法易于应用到组合优化问题的求解。 (4)蚁群算法是一种正反馈算法。从真实蚂蚁的觅食过程中不难看出,蚂蚁能够最终找到最优路径,直接依赖于其在路径上信息素的堆积,而信息素的堆积是一个正反馈的过程。正反馈是蚁群算法的重 要特征,它使得算法进化过程得以进行。 3 基本蚁群算法及其流程 4.3基于排序的蚁群算法 基于排序的蚁群算法(Rank-BasedAntSystem)是Bull n heimer、Hartl和Strauss等人提出的[11] 。在该算法中, 每个蚂蚁释放的信息素按照它们不同的等级进行挥发,另外类似于精英蚁群算法,精英蚂蚁在每次循环中释放更多的信息素。在修改信息素路径前,蚂蚁按照它们的旅行长度进行排名(短的靠前),蚂蚁释放信息素的量要和蚂蚁的排名相乘。在每次循环中,只有排名前w-1位的蚂蚁和精英蚂蚁才允许在路径上释放信息素。己知的最优路径给以最强的反馈,和系数w相乘;而排名第r位的蚂蚁则乘以系数“w-(≥0)。信息素如下式所示: %% 清空环境 clc;clear %% 障碍物数据 position = load(‘barrier.txt’); plot([0,200],[0,200],‘.’); hold on B = load(‘barrier.txt’); xlabel(‘km’,‘fontsize’,12) ylabel(‘km’,‘fontsize’,12) title(‘二维规划空间’,‘fontsize’,12) %% 描述起点和终点 S = [20,180]; T = [160,90]; plot([S(1),T(1)],[S(2),T(2)],‘.’); % 图形标注 text(S(1)+2,S(2),‘S’); text(T(1)+2,T(2),‘T’); %% 描绘障碍物图形 fill(position(1:4,1),position(1:4,2),[0,0,0]); fill(position(5:8,1),position(5:8,2),[0,0,0]); fill(position(9:12,1),position(9:12,2),[0,0,0]); fill(position(13:15,1),position(13:15,2),[0,0,0]); % 下载链路端点数据 L = load(‘lines.txt’); %% 描绘线及中点 v = zeros(size(L)); for i=1:20 plot([position(L(i,1),1),position(L(i,2),1)],[position(L(i,1),2)… ,position(L(i,2),2)],‘color’,‘black’,‘LineStyle’,‘–’); v(i,:) = (position(L(i,1),:)+position(L(i,2)😅)/2; plot(v(i,1),v(i,2),‘*’); text(v(i,1)+2,v(i,2),strcat(‘v’,num2str(i))); end %% 描绘可行路径 sign = load(‘matrix.txt’); [n,m]=size(sign); for i=1:n if i == 1 for k=1:m-1 if sign(i,k) == 1 plot([S(1),v(k-1,1)],[S(2),v(k-1,2)],'color',... 'black','Linewidth',2,'LineStyle','-'); end end continue; end for j=2:i if i == m if sign(i,j) == 1 plot([T(1),v(j-1,1)],[T(2),v(j-1,2)],'color',... 'black','Linewidth',2,'LineStyle','-'); end else if sign(i,j) == 1 plot([v(i-1,1),v(j-1,1)],[v(i-1,2),v(j-1,2)],... 'color','black','Linewidth',2,'LineStyle','-'); end end endend path = DijkstraPlan(position,sign); j = path(22); plot([T(1),v(j-1,1)],[T(2),v(j-1,2)],‘color’,‘yellow’,‘LineWidth’,3,‘LineStyle’,‘-.’); i = path(22); j = path(i); count = 0; while true plot([v(i-1,1),v(j-1,1)],[v(i-1,2),v(j-1,2)],‘color’,‘yellow’,‘LineWidth’,3,‘LineStyle’,‘-.’); count = count + 1; i = j; j = path(i); if i == 1 || j==1 break; end end plot([S(1),v(i-1,1)],[S(2),v(i-1,2)],‘color’,‘yellow’,‘LineWidth’,3,‘LineStyle’,‘-.’); count = count+3; pathtemp(count) = 22; j = 22; for i=2:count pathtemp(count-i+1) = path(j); j = path(j); end path = pathtemp; path = [1 9 8 7 13 14 12 22]; %% 蚁群算法参数初始化 pathCount = length(path)-2; %经过线段数量 pheCacuPara=2; %信息素计算参数 pheThres = 0.8; %信息素选择阈值 pheUpPara=[0.1 0.0003]; %信息素更新参数 qfz= zeros(pathCount,10); %启发值 phePara = ones(pathCount,10)*pheUpPara(2); %信息素 qfzPara1 = ones(10,1)*0.5; %启发信息参数 qfzPara2 = 1.1; %启发信息参数 m=10; %种群数量 NC=500; %循环次数 pathk = zeros(pathCount,m); %搜索结果记录 shortestpath = zeros(1,NC); %进化过程记录 %% 初始最短路径 dijpathlen = 0; vv = zeros(22,2); vv(1,:) = S; vv(22,:) = T; vv(2:21,:) = v; for i=1:pathCount-1 dijpathlen = dijpathlen + sqrt((vv(path(i),1)-vv(path(i+1),1))2+(vv(path(i),2)-vv(path(i+1),2))2); end LL = dijpathlen; %% 经过的链接线 lines = zeros(pathCount,4); for i = 1:pathCount lines(i,1:2) = B(L(path(i+1)-1,1)😅; lines(i,3:4) = B(L(path(i+1)-1,2)😅; end ⛄三、运行结果
1 matlab版本 2014a 2 参考文献 [1]王言军.改进蚁群算法的输电线巡检机器人避障路径规划[J].自动化与仪表. 2022,37(11) 3 备注 简介此部分摘自互联网,仅供参考,若侵权,联系删除 🍅 仿真咨询 1 各类智能优化算法改进及应用 生产调度、经济调度、装配线调度、充电优化、车间调度、发车优化、水库调度、三维装箱、物流选址、货位优化、公交排班优化、充电桩布局优化、车间布局优化、集装箱船配载优化、水泵组合优化、解医疗资源分配优化、设施布局优化、可视域基站和无人机选址优化 2 机器学习和深度学习方面 卷积神经网络(CNN)、LSTM、支持向量机(SVM)、最小二乘支持向量机(LSSVM)、极限学习机(ELM)、核极限学习机(KELM)、BP、RBF、宽度学习、DBN、RF、RBF、DELM、XGBOOST、TCN实现风电预测、光伏预测、电池寿命预测、辐射源识别、交通流预测、负荷预测、股价预测、PM2.5浓度预测、电池健康状态预测、水体光学参数反演、NLOS信号识别、地铁停车精准预测、变压器故障诊断 3 图像处理方面 图像识别、图像分割、图像检测、图像隐藏、图像配准、图像拼接、图像融合、图像增强、图像压缩感知 4 路径规划方面 旅行商问题(TSP)、车辆路径问题(VRP、MVRP、CVRP、VRPTW等)、无人机三维路径规划、无人机协同、无人机编队、机器人路径规划、栅格地图路径规划、多式联运运输问题、车辆协同无人机路径规划、天线线性阵列分布优化、车间布局优化 5 无人机应用方面 无人机路径规划、无人机控制、无人机编队、无人机协同、无人机任务分配 6 无线传感器定位及布局方面 传感器部署优化、通信协议优化、路由优化、目标定位优化、Dv-Hop定位优化、Leach协议优化、WSN覆盖优化、组播优化、RSSI定位优化 7 信号处理方面 信号识别、信号加密、信号去噪、信号增强、雷达信号处理、信号水印嵌入提取、肌电信号、脑电信号、信号配时优化 8 电力系统方面 微电网优化、无功优化、配电网重构、储能配置 9 元胞自动机方面 交通流 人群疏散 病毒扩散 晶体生长 10 雷达方面 卡尔曼滤波跟踪、航迹关联、航迹融合 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |