精华内容
下载资源
问答
  • 蚁群算法的生物学原理
    2022-03-06 19:28:14

            蚁群算法(ACO)是属于元启发式算法的一种。是一种群体的智能方法。

    算法原理:

            蚂蚁在寻找食物源时,会在其经过的路径上释放一种信息素,并能够感知其它蚂蚁释放的信息素。信息素浓度的大小表征到食物源路径的远近信息素浓度越高,表示对应的路径距离越短。通常,蚂蚁会以较大的概率优先选择信息素浓度较高的路径,并释放一定量的信息素,以增强该条路径上的信息素浓度,但也有一定的概率随机选择其他路径,这样会形成一个正反馈。最终,蚂蚁能够找到一条从巢穴到食物源的最佳路径,即最短距离。值得一提的是,生物学家同时发现,路径上的信息素浓度会随着时间的推进而逐渐衰减。

    待续。。。。

    10分钟搞懂蚁群算法 - 云+社区 - 腾讯云 (tencent.com)

    更多相关内容
  • 1. 什么是蚁群算法蚁群算法的本身来源于一种生物的自然现象,即蚂蚁在寻找食物过程中发现路径的行为,是...2.蚁群算法的基本原理 蚂蚁在觅食过程中能够在其经过的路上留下一种称之为信息素的物质,并在觅食过程中

    1. 什么是蚁群算法?

    蚁群算法的本身来源于一种生物的自然现象,即蚂蚁在寻找食物过程中发现路径的行为,是一种模拟进化的算法。蚁群算法的寻优快速性是由通过正反馈式的信息传递和积累来实现的,分布式计算特征可以避免算法的早熟收敛,与此同时,具有贪婪式启发搜索特征的蚁群系统还可以在搜索过程的初期阶段寻找到可以接受的问题解答。生物学家的长时间观察发现,蚂蚁是通过分泌空间中的信息素来实现信息的交流从而实现群体行为

    2.蚁群算法的基本原理

    蚂蚁在觅食过程中能够在其经过的路上留下一种称之为信息素的物质,并在觅食过程中能够感知这些物质的强度,作为指导自己行为的方向,他们一定是朝着该物质强度高的方向移动,因此大量蚂蚁组成的集体觅食就表现为一种对信息素正反馈的现象。

    某一条路径越短,路径上经过的蚂蚁越多,其信息素遗留的也就越多,信息素的浓度也就越高,蚂蚁选择这条路径的概率也就越大,由此构成了正反馈过程,从而逼近了最优路径,找到最优路径。当蚂蚁从食物源走到蚁穴,或者从蚁穴走到食物的地方,都会在经过的路上释放信息素,蚂蚁可以感觉出路径上信息素浓度的大小,并且以较高的概率选择信息素浓度较高的路径。

    人工蚂蚁搜索包含了3种智能行为:

    1. 蚂蚁利用信息素进行相互通信。蚂蚁在所选择的路径上会释放一种信息素的物质,当其他蚂蚁进行路径选择时,会根据路径上的信息素浓度进行选择,这样信息素就会作为蚂蚁之间通信的媒介

    2.蚂蚁的记忆行为。一只蚂蚁搜索过的路径在下次搜索时就不再被该蚂蚁选择,因此在蚁群算法种建立禁忌表进行模拟。

    3. 蚂蚁的集群活动。通过一只蚂蚁的运动很难达到食物源,但整个蚁群进行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时,路径上留下的信息素数量也就越多,导致信息素强度增大,蚂蚁选择该路径的概率随之增大,从而进一步增加该路径的信息素强度,而通过的蚂蚁较少的路径上的信息素会随着时间的推移而挥发,从而变得越来越少。

    3. 蚁群算法实现的重要规则

    3.1 避障规则

    蚂蚁如果在移动的方向上有障碍物挡住,它会随机选择另一个方向,并且有信息素指引的话,它会按照觅食的规则行为

    3.2 播撒信息素规则

    每只蚂蚁在刚找到食物或者窝的时候散发的信息素最多,并随着它走远的距离播撒的信息素也越来越少。

    3.3 范围

    蚂蚁观察到的范围是一个方格世界,蚂蚁有一个参数为速度半径(一般为3),那么他能观察到的范围就是一个3X3个方格世界,并且能移动的距离也在这个范围以内

    3.4 移动规则

    每只蚂蚁都朝向信息素最多的方向移动,并且当周围没有信息素引导的时候,蚂蚁就会按照自己原来运动的方向惯性移动下去,并且在运动方向有一个随机的小扰动。为了防止蚂蚁原地转圈,它会记住最近刚走过哪些点,如果发现要走的下一个点已经最近走过了,它会刻意去避开。

    3.5 觅食规则

    在每只蚂蚁能感知的范围内寻找是否有食物,如果有就直接走过去,否则看是否有信息素,并且比较在能感知的范围内哪一点的信息素最多,这样,它就朝信息素多的地方走,并且每只蚂蚁都会以小概率犯错误,从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样,只不过它对窝的信息素做出反应,而对食物信息素没反应。

    3.6 环境

    蚂蚁所在的环境是一个虚拟的世界,其中有障碍物,有别的蚂蚁,还有信息素,信息素有两种,一种是找到食物的蚂蚁洒下的食物信息素,一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。

    根据这几条规则,蚂蚁之间并没有直接的关系,但是每只蚂蚁都和环境发生交互,而通过信息素这个纽带,实际上把各个蚂蚁之间关联起来了。比如,当一只蚂蚁找到了食物,它并没有直接告诉其它蚂蚁这儿有食物,而是向环境播撒信息素,当其他的蚂蚁经过它附近的时候,就会感觉到信息素的存在,进而根据信息素的指引找到了食物。                      

    4 蚁群算法的特点

    蚁群算法是通过对生物特征的模拟得到的一种计算算法,其本身具有很多特点。

    4.1 蚁群算法是一种本质上并行的算法

    每只蚂蚁搜素过程彼此独立,仅通过信息激素进行通信。所以蚁群算法则可以看作是一个分布式的多智能体系统,它在问题空间的多点同时开始进行独立的解搜索,不仅增加了算法的可靠性,也使得算法具有较强的全局搜索能力。

    4.2 蚁群算法是一种自组织的算法

    所谓自组织,就是组织力或组织指令是来自于系统的内部,区别于它组织。如果系统在获得空间的、时间的或者功能结果的过程中,没有外界的特定干预,便说系统是自组织的。简单地说,就是即是系统从无序到有序的变化过程。

    以蚂蚁群体优化为例子说明。当算法开始的初期,单个的人工蚂蚁无序的寻找解,算法经过一段时间的演化,人工蚂蚁间通过信息激素的作用,自发地越来越趋向于寻找到接近最优解的一些解,这就是一个无序到有序的过程。

    4.3 蚁群算法具有较强的鲁棒性

    相对于其他算法,蚁群算法对初始路线要求不高,即蚁群算法的求解结果不依赖于初始线路的选择,而在搜素过程中不需要进行人工的调整。其次,蚁群算法的参数数目少,设置简单,易于蚁群算法应用到其他组合优化问题的求解。

    4.4 蚁群算法是一种正反馈的算法

    从真实蚂蚁的觅食过程中不难看出,蚂蚁能够最终找到最短路径,直接依赖于最短路径上信息激素的堆积,而信息激素的堆积却是一个正反馈的过程。正反馈是蚂蚁算法的重要特征,它使得算法演化过程得以进行。

    5 经典蚁群算法

    5.1 蚂蚁系统

    蚂蚁系统是最早的蚁群算法,其搜索过程大概如下:在初始时刻,m只蚂蚁随机放置于城市中,各条路径上的信息素初始值相等,设\tau _{ij}(0)=\tau _{0}为信息素初始值,可设\tau _{0}=m/L_{m},L_{m}是由最近邻启发式方法构造的路径长度。其次,蚂蚁k(k=1,2,...,m),按照随机比例规则选择下一步要转移的城市,其选择概率为

     其中,\tau _{0}为边(i,j)上的信息素;\eta _{ij}=1/d_{ij}为从城市i到城市j的启发式因子;a_{k}为蚂蚁k下一步被允许访问的城市集合。

    为了不让蚂蚁选择已经访问过的城市,采用禁忌表ta_{k}来记录蚂蚁k当前所走过的城市。经过t时刻,所有蚂蚁都完成一次周游,计算每只蚂蚁所走过的路径长度,并保存最短的路径长度,同时,更新各边上的信息素。首先是信息素挥发,其次是蚂蚁在它们所经过的边上释放信息素,其公式为

    \tau _{ij}=(1-\rho )\tau _{ij}

    其中,\Delta \tau _{ij}^{k}是第k只蚂蚁向它经过的边释放的信息素,定义为

     根据上式可知,蚂蚁构建的路径长度d_{ij}越小,则路径上各条边就会获得更多的信息素,则在以后的迭代中就更有可能被其他的蚂蚁选择。

    蚂蚁完成一次循环后,清空禁忌表,重新回到初始城市,准备下一次周游。

    大量的仿真实验发现,蚂蚁系统在解决小桂妈TSP问题时性能尚可,能较快的发现最优解,但随着测试问题规模的扩大,蚁群系统算法的性能下降的比较严重,容易出现停滞现象。因此,出现了大量的针对其缺点的改进算法。

    5.2 精英蚂蚁系统

    精英蚂蚁系统是对基本蚁群系统算法的第一次改进,它首先由Dorigo等人中提出,它的设计思想是对算法每次循环之后给予最优路径额外的信息素量,找出这个解的蚂蚁成为精英蚂蚁。

    将这条最有路径记为T^{bs}, 针对路径T^{bs}的额外强化是通过向T^{bs}中的每一条边增加e/L^{bs}大小的信息素得到的,其中e是一个参数,它定义了给予路径T^{bs}的权值大小, L^{bs}代表了T^{bs}的长度。这样相应的信息素的更新公式为

     其中, \Delta \tau _{ij}^{k}(t)的定义方法跟以前的相同;\Delta \tau _{ij}^{bs}(t)的定义为

     Dorigo等人的文章列举的计算结果表明,使用经营策略并选取一个适当的e值将使得蚂蚁系统算法不但可以得到更好的解,而且能够在更少的迭代次数下得到一些更好的解。

    5.3 最大-最小蚂蚁系统

    最大-最小蚂蚁系统是到目前为止解决TSP问题最好的ACA算法方案之一。最大-最小蚂蚁系统算法是在蚂蚁系统算法的基础之上,主要作了如下的改进。

    (1)将各条路径可能的外激素浓度限制于[\tau _{min},\tau _{max}],超出这个范围的值被强制设为\tau _{min}或者是\tau _{max},可以避免算法过早收敛于局部最优解,有效地避免某条路径上的信息量远大于其余路径,避免所有蚂蚁都集中到同一条路径上。

    (2)信息素的初始值被设定为其取值范围的上界。在算法的初始时刻,\rho取较小的值时,算法有更好的发现较好解的能力。

    (3)强调对最优解的利用。每次迭代结束后,只有最优解所属路径上的信息被更新,从而更好地利用了历史信息。

    所有蚂蚁完成一次迭代后,对路径上的信息做全局更新,即

     允许更新的路径可以时全局最优解,或本次迭代的最优解。实践证明逐渐增加全局最优解的使用频率,会使该算法获得较好的性能。

    5.4 基于排序的蚁群算法

    基于排序的蚂蚁系统是对蚂蚁系统算法的一种改进。其改进思想是:在每次迭代完成后,蚂蚁所经路径将按从小到大的顺序排列,即L^{1}(t)\leqslant L^{2}(t)\leq ... L^{m}(t), 算法根据路径长度赋予不同的权重,路径长度越短,权重越大。全局最优解的权重为w,第r个最优解的权重为,则ASrank的信息素更新规则为

     其中

    5.5 蚁群系统

    蚁群系统是由Dorigo等人提出来的改进的蚁群算法,它与蚂蚁系统的不同之处主要体现在以下3个方面。

    (1)除了全局信息素更新规则外,还采用了局部信息素更新规则。

    (2)信息素挥发和信息素释放动作只在至今最优路径的边上执行,即每次迭代之后只有至今最优蚂蚁被允许释放信息素。

    (3)采用不同的路径选择规则,能更好地利用蚂蚁所积累的搜索经验。

    在蚁群系统中,位于城市i的蚂蚁k,根据伪随机比例规则选择城市j作为下一个访问的城市。路径选择规则的公式为

     其中,q是均匀分布在区间[0,1]中的一个随机变量;q_{0}(0\leq q_{0}\leq 1)是一个参数;J是根据以上公式给出的概率分布产生出来的一个随机变量(其中\alpha =1)。

    蚁群系统的全局信息素更新规则为

    蚁群系统的局部信息素更新规则定义如下:

    在路径构建过程中,蚂蚁每经过一条边(i,j),都将立刻调用这条规则更新该边上的信息素,即

    \tau _{ij}=(1-\rho )\tau _{ij}+\xi \tau_{0}

    其中,\xi\tau _{0}是两个参数,\xi满足0< \xi < 1\tau _{0}是信息素量的初始值。局部更新的作用在于,蚂蚁每一次经过边(i,j),该边的信息素\tau _{ij}将会减少,从而使得其他蚂蚁选中该边的概率相对减少。

    6 自适应蚁群算法

    蚁群算法在构造解的过程中,利用随机选择策略,这种选择策略使得进化速度较慢,正反馈原理旨在强化性能较好的解,却容易出现停滞现象。

    在选择策略方面采用确定性选择和随机选择相结合的选择策略,并且在搜索过程中动态的调整确定性选择的概率。当进化到一定代数后,进化方向已经基本确定,这时对路径上信息量做动态调整。

    缩小最好和最差路径上的信息量的差距,并且适当放大随机选择的概率,以小于1对解空间的更完全搜索,可以有效地克服基本蚁群算法的不足,此算法属于自适应算法。

    蚂蚁在行进过程中常常选择信息量较大的路径,但当许多蚂蚁选中同一条路径是,该路径中的信息量就会陡然增大,从而使得多只蚂蚁集中到某一条路径上,造成一种堵塞和停滞现象,表现在使用蚁群算法解决问题时就容易导致早熟和局部收敛。

    自适应蚁群算法建立了一种新的自适应的信息量更新策略。

    当问题规模较大时,由于信息量挥发系数的存在,使那些从未被搜索过的路径上的信息量减少到接近于0,从而降低了算法在这些路径上的搜索能力;反之,当某条路径中信息量较大时,这些路径中的信息量增大,搜索过的路径再次被选择的机会就会变得较大。

    搜素过的路径被再次选择的机会变大,会影响算法的全局搜索能力,此时通过固定地变化挥发系数虽然可以提高全局搜索能力,但却使得算法的收敛速度降低。

    自适应蚁群算法提出一种自适应的变化\tau值的方法,将信息素更新的公式为

     其中,\varphi _{m}为连续收敛次数m/c,是一个于收敛次数m成正比的函数,收敛次数m越多,\varphi _{m}的取值越大(c为常数)。

    根据解的分布情况自适应地进行信息量的更新,从而动态地调整各路径上的信息量强度,使蚂蚁既不过分集中也不过分分散,从而避免了早熟和局部收敛,提高全局搜索能力。

     改进的蚁群算法的代码框架描述如下:

     上述算法程序根据解的分布情况自适应地进行信息量的更新,从而动态地调整了路径上的信息量强度,增加了解空间的多样性,提高了全局搜索能力,避免了局部收敛和早熟现象。

    改进后的蚁群算法具有比传统蚁群算法和MMAS蚁群算法更强的搜索全局最优解的能力,并具有更好的稳定性和收敛性。

    注明:本博客内容取自某些书籍或者网络其他来源,如有侵权请联系博主进行删除,谢谢

    展开全文
  • 蚁群算法的基本原理;蚁群算法的基本原理;简化蚂蚁的寻食过程;简化蚂蚁的寻食过程;简化蚂蚁的寻食过程;蚁群算法模型的建立;蚁群算法模型的建立;蚁群算法模型的建立;蚁群算法模型的建立; 蚁群算法的基本步骤 ;基本蚁群...
  • 顾名思义,蚁群算法借鉴了蚂蚁在寻找食物路径上的独到智慧——蚂蚁群体在复杂环境下能够依赖其生物本能找到到达食物来源的最短路径,而这项神奇本领来自于一种名为“信息素”的化学物质。蚂蚁会在其经过的路径上留下...

    大家好,今天笔者与诸位分享的是智能优化算法中蚁群算法的相关知识。蚁群算法源于Marco Dorigo教授在攻读电子工程博士期间对于群体智能领域孜孜不倦的探索。顾名思义,蚁群算法借鉴了蚂蚁在寻找食物路径上的独到智慧——蚂蚁群体在复杂环境下能够依赖其生物本能找到到达食物来源的最短路径,而这项神奇本领来自于一种名为“信息素”的化学物质。蚂蚁会在其经过的路径上留下可被同类识别的信息素,当蚁群内的其他蚂蚁感知到同伴分泌的信息素后,便会沿着信息素标识的路径爬行,并分泌出更多的信息素,而越短的路径在单位时间内就会有越多的蚂蚁爬过,留下较高浓度的信息素,形成了一种正反馈调节,经过一段时间后,整个蚁群便都会沿着最短路径找到食物了。

    在蚂蚁的启发下,教授开辟了解决优化问题(1)的新思路:用蚂蚁的行走路径表示待优化问题的可行解,整个蚂蚁群体(2)的所有路径构成待优化问题的解空间,通过设置环境和信息素(为了最大限度地消除非最优解的影响,信息素在这里被设置为随时间演化而逐渐消散),将“蚂蚁路径”在正反馈的作用下集中到最优解上,从而完成优化。

    介绍完蚁群算法的背景和相关原理后,我们再来看一下蚁群算法的几个步骤:

    一、初始化参数

    1. 蚂蚁数量m
    2. 信息素常量Q
    3. 最大迭代次数t
    4. 信息素因子α(反映了蚂蚁运动路径中路径上积累的信息素的量在指导蚁群搜索中的相对重要程度)
    5. 启发函数因子β(反映了启发式信息(3)在指导蚁群搜索中的相对重要程度,蚁群寻优过程中先验性、确定性因素作用的强度)
    6. 信息素挥发因子ρ(反映了信息素的消失水平,1-ρ则反应了保持水平)

    二、构建解空间

    1.每只蚂蚁随机选择出发点,之后维护一个路径记忆向量来存放经过点

    2.通过轮盘赌算法(4)选择下一个到达的地点

     这里做几点简要说明

    i,j为起点和终点;η表示i,j两点路径距离的倒数;τ表示经过指定时间后的信息素浓度;allowed表示尚未到达过的地点总和。下面通过一张图片来为大家进行说明。

     假设初始时所有路径上的信息素浓度均为1,信息素因子为2,启发因子为3,那么蚂蚁从4点开始,到其他地点的概率为 ps:鉴于某公式编辑器的无理取闹,这里不得已采用手写方式

     产生一个0到1之间的随机数,如果该数小于等于0.11则选择点1,大于则选择点2

    三、更新信息素

    相关公式(5)如下:

     这里的Lk为总路径长度

    四、判断是否终止 

    将从数据初始化到所有蚂蚁走完全部地点这一过程称为一次迭代,获取这次迭代中所有的路径信息并加以比较,得出最短路径,再与之前的迭代结果相比较选取更短路径,之后更新信息素,还原数据,进行下一次迭代,直至达到最大迭代次数,这时的总最短路径即为最优解。

    介绍完蚁群算法的大致思路后,下面会为大家展示相应的代码。

    鉴于笔者还是初学阶段(手动doge),选取的数据量比较少,并且编写的代码还是会有不少纰漏之处,还望大家海涵。

    import os
    os.getcwd()
    import numpy as np
    import matplotlib.pyplot as plt
    #导入所需的库和模块
    
    spots=np.array([[18.47,95.10],[16.47,94.64],[20.09,94.54],[14.39,93.37],[25.23,97.24],[22.00,93.05]])
    #输入6个地点坐标
    
    def getdist1(spots):
        num=spots.shape[0]
        dist1=np.zeros((6,6))
    #生成一个六阶方阵
        for i in range(num):
            for j in range(i,num):
                dist1[i][j] = dist1[j][i] = np.linalg.norm(spots[i] - spots[j])
        return dist1
    #计算出六个点之间的欧几里得度量
    
    #初始化数据,字母含义详见步骤一
    m=8
    Q=1
    numspot=spots.shape[0]
    t=150
    α=1
    β=3
    ρ=0.2
    iter=0 #迭代初始
    dist1=getdist1(spots)
    
    etatable=1.0 / (dist1 + np.diag([1e10] * numspot))
    # diag(),将一维数组转化为方阵 启发函数矩阵,表示蚂蚁从城市i转移到城市j的期望程度
    pheromonetable=np.ones((numspot, numspot)) # 信息素矩阵
    pathtable=np.zeros((m, numspot)).astype(int) # 路径记录表
    distmat=getdist1(spots) # 城市的距离矩阵
    lengthaver=np.zeros(t)  # 迭代50次,存放每次迭代后,路径的平均长度
    lengthbest = np.zeros(t)  # 迭代50次,存放每次迭代后,最佳路径长度
    pathbest=np.zeros((t, numspot))  # 迭代50次,存放每次迭代后,最佳路径城市的坐标,一共为300
    
    while iter<t:
        if m<=numspot:
            pathtable[:,0] = np.random.permutation(range(numspot))[:m]
            #情况一 蚂蚁数量小于等于地点数
        else:
            pathtable[:numspot,0]=np.random.permutation(range(numspot))[:]
            pathtable[numspot:,0]=np.random.permutation(range(numspot))[:m - numspot]
            #情况二 蚂蚁数量大于地点数,出现一个地点存在多只蚂蚁的情况
        length=np.zeros(m)
    
        for i in range(m):
            i=0
            visiting = pathtable[i,0]  # 当前所在的城市
            set()
            visited=set()
            visited.add(visiting)
            unvisited=set(range(numspot))
            unvisited.remove(visiting)
            #编纂未到达的地点,将已到达的地点删除
    
            for j in range(1,numspot):
                listunvisited = list(unvisited)
                probtrans = np.zeros(len(listunvisited))
                for k in range(len(listunvisited)):
                    probtrans[k]=np.power(pheromonetable[visiting][listunvisited[k]],α) \
                                   * np.power(etatable[visiting][listunvisited[k]],β)
                cumsumprobtrans=(probtrans / sum(probtrans)).cumsum()
                cumsumprobtrans-=np.random.rand()
                k=listunvisited[list(cumsumprobtrans > 0).index(True)]
                #通过轮盘赌法选出下一个要经过的地点并求出其概率,再根据随机数所在的区间确定到达的下一个点
    
                pathtable[i,j]=k
                unvisited.remove(k)
                visited.add(k)
                length[i]+=dist1[visiting][k]
                visiting=k
            length[i]+=dist1[visiting][pathtable[i,0]]
        lengthaver[iter]=length.mean()
        #进行了一次完整的迭代并求出最佳路径
    
        if iter==0:
            lengthbest[iter]=length.min()
            pathbest[iter]=pathtable[length.argmin()].copy()
        #进行第一次迭代,选择本次最短的路径,返回索引值下标并将其记录
        else:
            if length.min()>lengthbest[iter - 1]:
                lengthbest[iter]=lengthbest[iter - 1]
                pathbest[iter]=pathbest[iter - 1].copy()
            else:
                lengthbest[iter]=length.min()
                pathbest[iter]=pathtable[length.argmin()].copy()
    
        # 此部分是为了更新信息素
        changepheromonetable=np.zeros((numspot,numspot))
        for i in range(m):  # 更新所有的蚂蚁
            for j in range(numspot - 1):
                changepheromonetable[pathtable[i, j]][pathtable[i, j + 1]] += Q / dist1[pathtable[i, j]][
                    pathtable[i, j + 1]]
            changepheromonetable[pathtable[i, j + 1]][pathtable[i, 0]] += Q / dist1[pathtable[i, j + 1]][pathtable[i, 0]]
        pheromonetable=(1-ρ) * pheromonetable + changepheromonetable
       #不断更新信息素并进行计算
    
        iter+=1  # 迭代次数加1
        print("this iteration end:", iter)
        if (iter - 1) % 20 == 0:
            print("schedule:", iter - 1)
        #达到最大迭代次数,迭代完成

     这里会出现一个小问题,change~开头的语句会警告说遇到被零除的情况,不过不妨碍最终的结果。下面是笔者在编写时拓展的一些知识,为了不影响整体观感放到了最后。

    1. 蚁群算法在后来的应用中主要用于处理TSP问题(即旅行商问题),是指一名推销员要拜访多个地点时,如何找到在拜访每个地点一次后再回到起点的最短路径听起来规则虽然简单,但在地点数目增多后求解却极为复杂是作为千禧年七大难题之一的NP完全问题的典型例题,由此可见蚁群算法的出现确实具有划时代的意义。不仅于此,蚁群算法还在通讯工程,交通运输等诸多领域取得了非凡的成就,其创始者教授本人也因此在业界名声大噪。
    2. 在整个蚂蚁群体中,每一只“蚂蚁”都是平权的,这样可以在问题空间的多点同时开展独立的解搜索,不仅增强了算法的可靠性,也使得算法具备了较强的全局搜索能力。
    3. 笔者发现大部分关于蚁群算法的文章都没能够详尽地解释启发式信息的具体作用,主要是一个特定名词“先验性”没有介绍清楚。为此,笔者咨询了一下心理学相关的朋友——先验性最早是由康德提出的,认为某些具有“先验”特性的东西在人的经验之前,比如一个婴幼儿要认识某种事物,会去看,去摸,得到经验后才能去判断,但是他饿了渴了会直接哇哇大哭,这是先天的能力,不需要经验。同理,如果启发式信息的重要程度过大,先验性过强,那么无论是蚂蚁还是旅行商都会表现出过分的“主观臆断”来,缺乏合理性,而过小又会无视信息素,近乎完全随机。
    4. 轮盘赌选择法(roulette wheel selection)是最简单也是最常用的选择方法,在该方法中,各个个体的选择概率和其适应度值成比例,适应度越大,选中概率也越大。但实际在进行轮盘赌选择时个体的选择往往不是依据个体的选择概率,而是根据“累积概率”来进行选择。设某一部分x(i)的适应度值表示为f(xi),该部分被选中的概率为p(xi),累积概率为q(xi),对应的计算公式如下:

    在计算完p(xi)和q(xi)之后随机生成一个取值范围在0到1之间的数组m,并从小到大排列,若q(xi)大于数组m中的元素,则xi被选中,反之则比较下一个直至选出一个个体为止。

    5.蚁群算法共分为三种模型,分别为蚁周模型、蚁量模型和蚁密模型,笔者采用的是蚁周模型,在完成一次完整的路径之后,蚂蚁才会释放信息素。

    在文章的最后。我要感谢csdn和b站上介绍蚁群算法等相关知识的前辈,在我编撰这篇博客时提供了很大的帮助,也欢迎看到这篇文章的每一位朋友提出自己的意见和建议,我们可以共同努力,共同进步。虽然可能有些晚了,不过还是祝大家1024程序员节快乐。

    展开全文
  • 蚁群算法原理及matlab代码实现

    万次阅读 多人点赞 2019-04-27 15:13:30
    蚁群算法基本原理: 背景: 在自然界中,生物群体所表现出的智能得到越来越多的关注,许多的群智能优化算法都是通过对群体智能的模拟而实现的。其中模拟蚂蚁群体觅食的蚁群算法成为一种主要的群智能算法。 算法...

    蚁群算法基本原理:

    背景: 在自然界中,生物群体所表现出的智能得到越来越多的关注,许多的群智能优化算法都是通过对群体智能的模拟而实现的。其中模拟蚂蚁群体觅食的蚁群算法成为一种主要的群智能算法。

    算法原理:

    在自然界中,对于觅食的蚂蚁群体,其可以在任何和没有提示的情况下找到食物和巢穴之间的最短路径。并且能够根据和环境的变迁,自适应地找到新的最优路径。根据生物学家研究,蚂蚁群体这一行为的根本原因是:蚂蚁在寻找食物的过程中,能在其走过的路径上释放一种特殊的物质----信息素,随着时间的推移,这种信息素会逐渐地挥发,而对于后来的蚂蚁,选择某条路径的概率与该路径上信息素的浓度成正比。当某一条路径上通过的蚂蚁越多的时候,这条路径上的信息素的浓度就会累积越大,后来的蚂蚁选择此路径的概率也就越大。路径上蚂蚁越多,导致信息素浓度越高,从而会吸引更多的蚂蚁,从而形成一种正反馈机制,通过这种机制,最终蚁群可以发现最短路径。

    真实蚁群觅食过程:

            在觅食的初始阶段,环境中没有信息素,所以蚂蚁选择哪条路径完全是随机的。之后选择路径就会受到信息素的影响。这里需要说明的时是,信息素是一种生物体内分泌的化学物质,会随着时间的推移而挥发,如果每只蚂蚁在单位距离上留下的信息素浓度相同,则对于越短的路径,信息素的残留浓度就会越高,这被后来的蚂蚁选择的概率也就越大。而经过的蚂蚁越多,由于群体中的正反馈机制,路径上信息素的浓度也就越大,最终会导致整个蚁群寻找到最短路径。

    举个栗子:

    如下图所示:

     

    假设从A点到B点,A,B之间的距离一定,有三条路径可选。

    初始时每条路径分配一只蚂蚁,记为1,2,3,假设L(ACB)=2*L(ADB), L(AEB)=3*L(ADB),所有蚂蚁的行走速度相同。假设蚂蚁沿着ADB从A到B,需要4个单位时间;所以在t取不同值的时候:

    t=4:

    蚂蚁1到达D, 蚂蚁2走到一半路程,蚂蚁3走了三分之一的路程

    t=8:

    蚂蚁1返回A, 蚂蚁2到达B,蚂蚁3走了三分之二的路程

    .....

    t=48:

    蚂蚁1往返于AB之间6次, 蚂蚁2往返于AB间3次,蚂蚁3往返于AB间2次

    在不考虑信息素挥发的条件下:

    三条路径上信息素浓度之比:D(ADB):D(ACB):D(AEB)=6:3:2

    按照蚁群寻找路径的正反馈机制:按照信息素的指导,蚁群在路径ADB上指派6只蚂蚁,在路径ACB上指派3只蚂蚁,在路径AEB上指派2只蚂蚁.

    若继续寻找,则按照正反馈机制,最终所有蚂蚁都会选择最短的路径ABD,而放弃其他两条路径。

    蚁群算法数学模型的建立:

    1.在对实际的蚁群进行建模的过程中,需要解决,蚁群中蚂蚁个体的建模问题,信息素的更新机制,以及整个蚁群的内部机制

    a. 信息素的更新机制:

           信息素的更新方式有两种,一种是挥发,也就是所有路径上的信息素以一定的比率减少。另一种是信息素的增强,给有蚂蚁走过的路径增加信息素。

    b. 蚂蚁个体的建模问题:

           虽然单个蚂蚁可以构造出问题的可行解,但是蚂蚁个体之间需要通过协作才能找出待优化问题的最优解或者次优解,而信息素就是蚂蚁之间进行互相协作的媒介。信息素的蒸发机制使得对过去的寻优历史有一定的遗忘度,避免使后来的蚂蚁在搜索中受到较差解的影响。

    下面以TSP问题为例,给出蚁群算法的模型:
    参考文献:【1】M. Dorigo, V. Maniezzo and A. Colorni, "Ant system: optimization by a colony of cooperating agents," in IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 26, no. 1, pp. 29-41, Feb. 1996.

    TSP问题: 

    在一张地图上有n个城市,一名推销员需要不重复的一次走过n个城市进行推销,求解他按照怎样的路径,从才能使走过的距离最短。

    这个问题的解法可以描述如下:

    假设城市 i 的坐标坐标为

    城市i,j之间的距离可以表示为:

    为每只蚂蚁设置一个禁忌表,记录其走过的城市(防止重复走过城市),禁忌表中第一个位置是蚂蚁是初始时刻蚂蚁所在的城市,当所有城市都加入禁忌表的时候,表示蚂蚁走完了所有的城市,完成一次周游。令 为城市i, j之间的信息素的量,初始时刻其取值为:

    假设在(t, t+n)时刻所有蚂蚁完成一次周游,则在t+n时刻城市i, j 之间的信息素含量可以表示为:

    其中:表示时间段 (t, t+n) 之间信息素的挥发系数。则表示信息素的剩余量。挥发系数取值范围(0, 1)

              表示在时间段 (t, t+n) 之间信息素的增加量,其计算方式如下所示:

    表示第k只蚂蚁在本次迭代中留在路径i, j之间的信息素的量, 计算方式如下所示(ant-cycle模型):

    其中:是正常数, 表示蚂蚁k在周游中经过的路径。

    原文中对参数的解释如下:

    同时论文中还提到两种的计算方式:

    (1)ant-density模型

    (2)ant-quantity模型:

      ant-cycle模型的实际效果更好,因为他应用了全局信息更新路径上的信息素,而其他两种模型只是用了局部信息。

    在t时刻, 蚂蚁k从城市i转移到城市可的概率可以由以下方式计算得到:

    其中:是一个启发式因子,计算方式为:

    表示蚂蚁从城市i转移到城市j的期望程度。

    表示在城市i处蚂蚁k可以选择走的城市的集合。表示信息素和期望启发式因子的相对重要程度。

    分析上面的公式可知:

     路径i,j信息素含量越高,蚂蚁选择该路径的概率越大,而路径i.j之间的距离越大吗,启发式因子就越小,则蚂蚁选择该路径的概率就越小,蚂蚁选择路径i,j的概率与上述两个因素都有关系。

    matlab代码实现:

    clear all;
    close all;
    clc;
    C = [1304 2312;         % 城市坐标
        3639 1315;
        4177 2244;
        3712 1399;
        3488 1535;
        3326 1556;
        3238 1229;
        4196 1044;
        4312 790;
        4386 570;
        3007 1970;
        2562 1756;
        2788 1491;
        2381 1676;
        1332 695;
        3715 1678;
        3918 2179;
        4061 2370;
        3780 2212;
        3676 2578;
        4029 2838;
        4263 2931;
        3429 1980;
        3507 2376;
        3394 2643;
        3439 3201;
        2935 3240;
        3140 3550;
        2545 2357;
        2778 2826;
        2370 2975];
    % figure(1);
    % scatter(C(:,1),C(:,2),'k','d');
    % title('城市分布图');
    
    [M,N] = size(C);
    % M为问题的规模  M个城市
    distance = zeros(M,M);     % 用来记录任意两个城市之间的距离
    % 求任意两个城市之间的距离
    for m=1:M
        for n=1:M
            distance(m,n) = sqrt(sum((C(m,:)-C(n,:)).^2));
        end
    end
    m = 50;   % 蚂蚁的个数   一般取10-50    
    alpha = 1;   %  信息素的重要程度    一般取【1,4】
    beta = 5;    %  启发式英子的重要程度   一般取【3,5】
    rho = 0.25;    % 信息素蒸发系数
    G = 150;
    Q = 100; % 信息素增加系数
    Eta = 1./distance;  % 启发式因子
    Tau = ones(M,M);  % 信息素矩阵  存储着每两个城市之间的信息素的数值
    Tabu = zeros(m,M);  % 禁忌表,记录每只蚂蚁走过的路程
    gen = 1;  
    R_best = zeros(G,M);  % 各代的最佳路线
    L_best = inf.*ones(G,1);   % 每一代的最佳路径的长度     初始假设为无穷大
    %   开始迭代计算
    while gen<G
        %  将m只蚂蚁放到n个城市上
        random_pos = [];
        for i=1:(ceil(m/M))  % m只蚂蚁随即放到M座城市 
            random_pos = [random_pos,randperm(M)];   %  random_pos=[1~31 + 1~31]   将每只蚂蚁放到随机的城市  在random_pos 中随机选择m个数,代表蚂蚁的初始城市
        end
        Tabu(:,1) = (random_pos(1,1:m))';   % 第一次迭代每只蚂蚁的禁忌表
        
        for i=2:M      %  从第二个城市开始
            for j=1:m   %  每只蚂蚁
                visited = Tabu(j,1:(i-1));   %  在访问第i个城市的时候,第j个蚂蚁访问过的城市
                % visited=visited(1,:);
                unvisited = zeros(1,(M+1-i));  %  待访问的城市
                visit_P = unvisited;   %  蚂蚁j访问剩下的城市的概率
                count = 1;
                for k=1:M   % 这个循环是找出未访问的城市  
                    if isempty(find(visited==k))   %还没有访问过的城市  如果成立。则证明第k个城市没有访问过
                        unvisited(count) = k;
                        count = count+1;
                    end
                end
                %  计算待选择城市的概率
                for k=1:length(unvisited)    % Tau(visited(end),unvisited(k))访问过的城市的最后一个与所有未访问的城市之间的信息素
                    visit_P(k) = ((Tau(visited(end),unvisited(k)))^alpha)*(Eta(visited(end),unvisited(k))^beta);
                end
                visit_P = visit_P/sum(visit_P);   %  访问每条路径的概率的大小
                %   按照概率选择下一个要访问的城市
                %   这里运用轮盘赌选择方法      这里也可以选择选择概率最大的路径去走, 这里采用轮盘赌选择法。
                Pcum = cumsum(visit_P);
                selected = find(Pcum>=rand);
                to_visited = unvisited(selected(1));
                Tabu(j,i) = to_visited;  % 添加到禁忌表
            end
        end
        if gen>=2
            Tabu(1,:) = R_best(gen-1,:);
        end
        %  记录m只蚂蚁迭代的最佳路线
        L = zeros(1,m);
        for i=1:m
            R = Tabu(i,:);
            L(i) = distance(R(M),R(1));   % 因为要走一周回到原来的地点    
            for j=1:(M-1)
                L(i) = L(i)+distance(R(j),R(j+1));
            end
        end
        L_best(gen) = min(L);    %  记录每一代中路径的最短值
        pos = find(L==L_best(gen));
        R_best(gen,:) = Tabu(pos(1),:);   % 最优的路径
        
        %  更新信息素的值
        Delta_Tau = zeros(M,M);
        for i=1:m   %  m只蚂蚁
            for j=1:(M-1)   %  M座城市
                Delta_Tau(Tabu(i,j),Tabu(i,j+1)) = Delta_Tau(Tabu(i,j),Tabu(i,j+1)) + Q/L(i);    %  m只蚂蚁的信息素累加 这里采用的是论文中ant-cycle模型
            end
            Delta_Tau(Tabu(i,M),Tabu(i,1)) = Delta_Tau(Tabu(i,M),Tabu(i,1)) + Q/L(i);
        end
        Tau = (1-rho).*Tau+Delta_Tau;   % 更新路径上的信息素含量
        %  禁忌表清零
        Tabu = zeros(m,M);
        
        for i=1:(M-1)
            plot([C(R_best(gen,i),1),C(R_best(gen,i+1),1)],[C(R_best(gen,i),2),C(R_best(gen,i+1),2)],'bo-');
            hold on;
        end
        plot([C(R_best(gen,n),1),C(R_best(gen,1),1)],[C(R_best(gen,n),2),C(R_best(gen,1),2)],'ro-');
        title(['最短路径:',num2str(L_best(gen))]);
        hold off;
        pause(0.05);
        gen = gen+1;
    end
    
    figure(2);
    plot(L_best);
    title('路径长度变化曲线');
    xlabel('迭代次数');
    ylabel('路径长度数值');

    运行结果:

     

    最优路径相同,只是起点不一样。

     

    展开全文
  • 蚁群算法是受自然界中蚁群搜索食物行为启发而提出的一种智能优化算法,通过介绍蚁群觅食过程中基于信息素的最短路径的搜索策略,给出基于MATLAB的蚁群算法在旅行商问题中的应用,对问题求解进行局部优化。...
  • 智能算法——蚁群算法

    千次阅读 2022-03-14 08:23:06
    蚁群算法是受到对真实蚂蚁群觅食行为研究的启发而提出。生物学研究表明:一群相互协作的蚂蚁能够找到食物和巢穴之间的最短路径,而单只蚂蚁则不能。生物学家经过大量细致观察研究发现,蚂蚁个体之间的行为是相互作用...
  • 蚁群算法发展.pptx

    2020-06-20 07:58:01
    蚁群算法的基本原理;蚁群算法的基本原理;简化蚂蚁的寻食过程;简化蚂蚁的寻食过程;简化蚂蚁的寻食过程;蚁群算法模型的建立;蚁群算法模型的建立;蚁群算法模型的建立;蚁群算法模型的建立; 蚁群算法的基本步骤 ;基本蚁群...
  • 蚁群算法详解

    2022-02-28 15:09:00
    蚁群算法是为经典优化问题,旅行商问题,量身打造的一个解决方案。从生物学的角度说,那可真是生动形象。 一个商品推销员要去若干个城市推销商品,该推销员从一个城市出发,需要经过所有城市后,回到出发地。应如何...
  • 第1章 &nbsp &nbsp绪论&nbsp &nbsp &nbsp &nbsp1.1 &nbsp &nbsp引言&nbsp &nbsp &...nbsp蚂蚁的生物学特征&nbsp &nbsp &nbsp &nbsp1....
  • 蚁群算法(ACO)

    千次阅读 2022-06-11 22:11:22
    蚁群算法(python实现)
  • 蚁群算法是一种源于大自然生物世界的新的仿生进化算法,由意大利学者M. Dorigo, V. Maniezzo和A. Colorni等人于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径行为而提出的一种基于种群的启发式随机搜索算法"。蚂蚁...
  • 完整代码已上传我的资源:[【边缘检测】基于matlab蚁群算法图像边缘检测【含Matlab源码 1189期】](https://download.csdn.net/download/TIQCmatlab/34447635) **获取代码方式2:** 通过订阅紫极神光博客**付费专栏*...
  • 简单易懂,蚁群算法解决旅行商问题

    万次阅读 多人点赞 2018-10-29 21:06:40
    原文把蚁群解决旅行商问题写的很清楚,只不过本人认为原文中有一些小错误,特此更改(文中红色加粗字体为改正处),代码中出现的一些算法的小问题也进行了更正(比如代码中的贪心算法),代码也附在下面,谢谢博主的...
  • 蚁群算法

    万次阅读 多人点赞 2018-08-27 06:35:38
    群蚁算法基本原理 3.群蚁算法的基本流程 4.群蚁算法计算实例 5.TSP问题的群蚁算法C#代码实现 6.资源与参考文献  若干年前读研的时候,学院有一个教授,专门做群蚁算法的,很厉害,偶尔了解了一点点。感觉也是...
  • 1.1 算法概述生物现象由来行为特征蚁群算法的应用算法特点ACA算法特点补充:启发式算法初始化参数构建模型判断算法是否达到迭代次数 1.什么是蚁群算法? 1.1 算法概述 蚁群算法(Ant Colony Algorithm, ACA)由Marco ...
  • 基于蚁群算法图像边缘检测的认识

    千次阅读 2021-10-24 13:29:57
    以小波变换、数学形态、模糊数学,分形理论等以高新技术为基础的图像边缘提取方法。 其他的边缘检测方法不做叙述 1.21 一阶微分边缘算子 一阶微分边缘算子也称为梯度边缘算子,它是利用图像在边缘处的阶跃性,即
  • 深度学习经典算法 | 蚁群算法解析

    千次阅读 2020-06-28 23:48:44
    蚁群算法的基本原理来源于自然界中蚂蚁觅食的最短路径问题。根据昆虫家的观察,发现自然界的蚂蚁虽然视觉不发达,但它可以在没有任何提示的情况下找到从食物源到巢穴的最短路径,并且能在环境发生变化(如原有路径...
  • 蚁群算法用于航路规划的matlab简单实现
  • 1.1 蚁群算法原理  蚁群算法是受到对真实蚂蚁群觅食行为研究的启发而提出。生物学研究表明:一群相互协作的蚂蚁能够找到食物和巢穴之间的最短路径,而单只蚂蚁则不能。生物学家经过大量细致观察研究发现,蚂蚁个体...
  • 来喽!一、群体智能1.1 群体 群体智能这个概念来自对自然界中一些昆虫,如蚂蚁、蜜蜂等。...这种群居性生物表现出来的智能行为被称为群体智能。群体智能是在集体层面表现出来的分布式、无中心、自组织系统。 ...
  • 3.2 蚁群算法说明 在说明群蚁算法流程之前,我们对算法原理和几个注意点进行描述: 1.TSP问题的人工蚁群算法中,假设m只蚂蚁在图的相邻节点间移动,从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每...
  • 尽管建立这种模式的初衷是为了帮助人们去理解这类昆虫的复杂行为,蚂蚁也不可能从这些解释中获益,但是数学及汁算机方面的专家和工程师却把这种超越生物本身的模型转化成了一项有用的优化和控制算法一蚁群算法,也称...
  • 蚁群算法原理与实现(python)

    千次阅读 多人点赞 2019-12-25 19:45:29
    文章目录蚁群算法的背景蚁群算法的思想蚁群算法的python实现实例总结 蚁群算法的背景 古有牛顿在苹果树下被苹果砸中发现万有引力,三十年前有人观察蚂蚁觅食发明蚁群算法蚁群算法是意大利学者Dorigo、Maniezzo等人...
  • 2.蚁群算法基本原理 2.1 算法综述  对于VRP问题,求解算法大致可分为精确算法和人工智能算法两大类。精确性算法基于严格的数学手段,在可以求解的情况下,解的质量较好。但是由于算法严格,运算量大,特别是大规模的...
  • 1 VRP基本原理 车辆路径规划问题(Vehicle Routing Problem,VRP)是运筹里重要的研究问题之一。VRP关注有一个供货商与K个销售点的路径规划的情况,可以简述为:对一系列发货点和收货点,组织调用一定的车辆,安排...
  • ​问题定义:巡回旅行商问题 给定一组n个城市和俩俩之间的直达距离,...近年来,有很多解决该问题的较为有效的算法不断被推出,例如Hopfield神经网络方法,模拟退火方法以及遗传算法方法等。TSP搜索空间随着城市数n的.
  • 3.2 蚁群算法说明 在说明群蚁算法流程之前,我们对算法原理和几个注意点进行描述: 1.TSP问题的人工蚁群算法中,假设m只蚂蚁在图的相邻节点间移动,从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每...
  • 模拟退火与遗传与蚁群算法

    千次阅读 2019-08-12 15:13:11
     根据热力原理,在温度为T时,出现能量差为dE的降温的概率为p(dE),表示为:     其中k是波尔兹曼常数,值为 ,exp表示自然指数,且dE。因此dE/kT,所以p(dE)函数的取值范围是(0,1)。满足概率密度函数...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 733
精华内容 293
热门标签
关键字:

蚁群算法的生物学原理