蚁群算法(实例帮助理解) |
您所在的位置:网站首页 › 欧盟为什么衰退 › 蚁群算法(实例帮助理解) |
1. 算法简介1.1 算法起源1.2 算法应用
2. 基本原理3. 算法设计3.1 算法步骤3.2 参数意义及设置3.3 构建路径3.4 更新信息素浓度3.5 判断是否中止
4. 实例演示(TSP问题)
1. 算法简介
1.1 算法起源
蚁群算法(ant colony optimization, ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法。其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。它能够求出从原点出发,经过若干个给定的需求点,最终返回原点的最短路径。这也就是著名的旅行商问题(Traveling Saleman Problem,TSP)。蚁群算法是一种模拟进化算法
1.2 算法应用
应用进展以蚁群算法为代表的蚁群智能已成为当今分布式人工智能研究的一个热点,许多源于蜂群和蚁群模型设计的算法己越来越多地被应用于企业的运转模式的研究。多年来世界各地研究工作者对蚁群算法进行了精心研究和应用开发,该算法现已被大量应用于数据分析、机器人协作问题求解、电力、通信、水利、采矿、化工、建筑、交通等领域。蚁群优化算法最初用于解决TSP问题,经过多年的发展,已经陆续渗透到其他领域中,比如图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。蚁群算法在若干领域己获得成功的应用,其中最成功的是在组合优化问题中的应用
2. 基本原理
蚂蚁在行走过程中会释放一种称为“信息素”的物质,用来标识自己的行走路径。 在寻找食物的过程中,根据信息素的浓度选择行走的方向,并最终到达食物所在的地方。 信息素会随着时间的推移而逐渐挥发。 例:下图为蚂蚁觅食过程图,现有两只蚂蚁均在A点,食物在B点。途中从A到B有两条路径(即A->B和A->C->B),假设两只蚂蚁速度相同,两只蚂蚁释放的信息素浓度相同,且图中三角形为等边三角形。那么在t0时刻,蚂蚁1沿ACB出发,蚂蚁2沿AB出发。当到t1时刻后,蚂蚁1到达C点,蚂蚁2到达B点(食物)。此时AC路径和AB路径的信息素浓度相同,且蚂蚁1将继续从C到B爬行,蚂蚁2则从B到A返回。当到t2时刻后,蚂蚁1到达B点(食物),蚂蚁2到达A点。此时发现AB路径的信息素浓度是BC路段的2倍,因此当蚂蚁1想要返回A点后,它不会再选择沿BCA原路返回,而是选择信息素浓度高的BA路径返回。这样持续下去,AB路径上的信息素浓度会越来越高,后面的蚂蚁都会选择AB路径来获取食物,从而找到了获取食物的最短路径。 初始化(各个参数): 在计算之初需要对相关的参数进行初始化,如蚂蚁数量m、信息素因子α、启发函数因子β、信息素挥发因子ρ、信息素常数Q、最大迭代次数t等等。 构建解空间: 将各个蚂蚁随机地放置于不同的出发点,对每个蚂蚁k(k=1,2,……,m),计算其下一个待访问的城市,直到所有蚂蚁访问完所有的城市。 更新信息素: 计算各个蚂蚁经过的路径长度L,记录当前迭代次数中的最优解(最短路径)。同时,对各个城市连接路径上的信息素浓度进行更新。 判断是否终止: 若迭代次数小于最大迭代次数则迭代次数加一,清空蚂蚁经过路径的记录表,并返回步骤二;否则终止计算,输出最优解。 下图是蚁群算法的整体流程图: 我们知道蚂蚁是根据信息素的浓度来判断所走的路线的,但是事实上,不是说哪条路的信息素浓度高蚂蚁就一定走哪条路,而是走信息素浓度高的路线的概率比较高。那么首先我们就需要知道蚂蚁选择走每个城市的概率,然后通过轮盘赌法(相当于转盘)确定蚂蚁所选择的城市。 蚂蚁选择城市的概率公式如下: 例:下图为计算蚂蚁从起点城市2到可达城市的概率(套公式,很好理解) 更新信息素的公式如下: 根据不同的规则我们可以将蚁群算法分为三种模型——蚁周模型(Ant-Cycle)、蚁量模型(Ant-Quantity)和蚁密模型(Ant-Density)。蚁周模型是完成一次路径循环后,蚂蚁才释放信息素,其利用的是全局信息。蚁量模型和蚁密模型蚂蚁完成一步后就更新路径上的信息素,其利用的是局部信息。本文章使用的是最常见的蚁周模型。 蚁周模型公式如下: 例:下图为信息素的更新过程,假设初始时各路径信息素浓度为10。 蚁群算法中的终止条件:是否达到迭代次数。 一次迭代就是指m只蚂蚁都走完所有的城市,即存在m个搜索路径。 将所有路径进行比较,选择长度最短的路径,做出这一次迭代的可视化结果,更新信息素。并将当前的最短路径与过往的最短路径长度进行对比,同时迭代次数加1。 然后判断当前迭代次数是否等于设置的迭代次数。如果等于则停止迭代,否则进行下一次迭代。 4. 实例演示(TSP问题)实例题目: 实例代码: matlab蚁群算法代码 matlab运行结果展示: |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |