精华内容
下载资源
问答
  • 2018-05-09 10:17:42
    转自百度百科和http://www.cnblogs.com/biaoyu/archive/2012/09/26/2704456.html
    蚁群算法(ant colony optimization, ACO),又称 蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟 进化算法,初步的研究表明该算法具有许多优良的性质。针对 PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。
    中文名
    蚁群算法
    外文名
    ant colony optimization
    简    称
    ACO
    别    称
    蚂蚁算法
    速度半径
    (一般是3)

    定义

    编辑
    各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后,它会向 环境释放一种挥发性分泌物pheromone (称为信息素,该物质随着时间的推移会逐渐挥发消失,信息素浓度的大小表征路径的远近)来实现的,吸引其他的蚂蚁过来,这样越来越多的蚂蚁会找到食物。有些蚂蚁并没有像其它蚂蚁一样总重复同样的路,他们会另辟蹊径,如果另开辟的道路比原来的其他道路更短,那么,渐渐地,更多的蚂蚁被吸引到这条较短的路上来。最后,经过一段时间运行,可能会出现一条最短的路径被大多数蚂蚁重复着。

    原理

    编辑
    设想,如果我们要为蚂蚁设计一个人工智能的程序,那么这个程序要多么复杂呢?首先,你要让蚂蚁能够避开障碍物,就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物,其次,要让蚂蚁找到食物,就需要让他们遍历空间上的所有点;再次,如果要让蚂蚁找到最短的路径,那么需要计算所有可能的路径并且比较它们的大小,而且更重要的是,你要小心翼翼地编程,因为程序的错误也许会让你前功尽弃。这是多么不可思议的程序!太复杂了,恐怕没人能够完成这样繁琐冗余的程序。
    然而,事实并没有你想得那么复杂,上面这个程序每个蚂蚁的核心程序编码不过100多行!为什么这么简单的程序会让蚂蚁干这样复杂的事情?答案是:简单规则的涌现。事实上,每只蚂蚁并不是像我们想象的需要知道整个世界的信息,他们其实只关心很小范围内的眼前信息,而且根据这些局部信息利用几条简单的规则进行决策,这样,在蚁群这个集体里,复杂性的行为就会凸现出来。这就是 人工生命、复杂性科学解释的规律!那么,这些简单规则是什么呢?

    问题

    编辑
    蚂蚁究竟是怎么找到食物的呢?在没有蚂蚁找到食物的时候,环境没有有用的信息素,那么蚂蚁为什么会相对有效的找到食物呢?这要归功于蚂蚁的移动规则,尤其是在没有信息素时候的移动规则。首先,它要能尽量保持某种惯性,这样使得蚂蚁尽量向前方移动(开始,这个前方是随机固定的一个方向),而不是原地无谓的打转或者震动;其次,蚂蚁要有一定的随机性,虽然有了固定的方向,但它也不能像粒子一样 直线运动下去,而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性,尽量保持原来的方向,但又有新的试探,尤其当碰到障碍物的时候它会立即改变方向,这可以看成一种选择的过程,也就是环境的障碍物让蚂蚁的某个方向正确,而其他方向则不对。这就解释了为什么单个蚂蚁在复杂的诸如 迷宫的地图中仍然能找到隐蔽得很好的食物。
    当然,在有一只蚂蚁找到了食物的时候,大部分蚂蚁会沿着信息素很快找到食物的。但不排除会出现这样的情况:在最初的时候,一部分蚂蚁通过随机选择了同一条路径,随着这条路径上蚂蚁释放的信息素越来越多,更多的蚂蚁也选择这条路径,但这条路径并不是最优(即最短)的,所以,导致了迭代次数完成后,蚂蚁找到的不是最优解,而是次优解,这种情况下的结果可能对实际应用的意义就不大了。
    蚂蚁如何找到最短路径的?这一是要归功于信息素,另外要归功于环境,具体说是计算机时钟。信息素多的地方显然经过这里的蚂蚁会多,因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物,开始的时候,走这两条路的蚂蚁数量同样多(或者较长的路上蚂蚁多,这也无关紧要)。当蚂蚁沿着一条路到达终点以后会马上返回来,这样,短的路蚂蚁来回一次的时间就短,这也意味着重复的频率就快,因而在单位时间里走过的蚂蚁数目就多,洒下的信息素自然也会多,自然会有更多的蚂蚁被吸引过来,从而洒下更多的信息素……;而长的路正相反,因此,越来越多地蚂蚁聚集到较短的路径上来,最短的路径就近似找到了。也许有人会问局部最短路径和全局最短路的问题,实际上蚂蚁逐渐接近全局最短路的,为什么呢?这源于蚂蚁会犯错误,也就是它会按照一定的概率不往信息素高的地方走而另辟蹊径,这可以理解为一种创新,这种创新如果能缩短路途,那么根据刚才叙述的原理,更多的蚂蚁会被吸引过来。

    详细说明

    编辑

    范围

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

    环境

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

    觅食规则

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

    移动规则

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

    避障规则

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

    信息素规则

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

    相关研究

    编辑

    引申

    跟着蚂蚁的踪迹,你找到了什么?通过上面的原理叙述和实际操作,我们不难发现蚂蚁之所以具有智能行为,完全归功于它的简单行为规则,而这些规则综合起来具有下面两个方面的特点:
    1、多样性
    2、 正反馈
    多样性保证了蚂蚁在觅食的时候不至走进死胡同而无限循环,正反馈机制则保证了相对优良的信息能够被保存下来。我们可以把多样性看成是一种创造能力,而正反馈是一种学习强化能力。正反馈的力量也可以比喻成权威的意见,而多样性是打破权威体现的创造性,正是这两点小心翼翼的巧妙结合才使得智能行为涌现出来了。
    引申来讲,大自然的进化,社会的进步、人类的创新实际上都离不开这两样东西,多样性保证了系统的创新能力,正反馈保证了优良特性能够得到强化,两者要恰到好处的结合。如果多样性过剩,也就是系统过于活跃,这相当于蚂蚁会过多的随机运动,它就会陷入混沌状态;而相反,多样性不够,正反馈机制过强,那么系统就好比一潭死水。这在蚁群中来讲就表现为,蚂蚁的行为过于僵硬,当环境变化了,蚂蚁群仍然不能适当的调整。
    既然复杂性、智能行为是根据底层规则涌现的,既然底层规则具有多样性和正反馈特点,那么也许你会问这些规则是哪里来的?多样性和正反馈又是哪里来的?我本人的意见:规则来源于大自然的进化。而大自然的进化根据刚才讲的也体现为多样性和正反馈的巧妙结合。而这样的巧妙结合又是为什么呢?为什么在你眼前呈现的世界是如此栩栩如生呢?答案在于环境造就了这一切,之所以你看到栩栩如生的世界,是因为那些不能够适应环境的多样性与正反馈的结合都已经死掉了,被环境淘汰了!

    搜索引擎算法

    蚁群算法的由来:蚂蚁是地球上最常见、数量最多的昆虫种类之一,常常成群结队地出现在人类的日常生活环境中。这些昆虫的群体生物智能特征,引起了一些学者的注意。意大利学者M.Dorigo,V.Maniezzo等人在观察蚂蚁的觅食习性时发现,蚂蚁总能找到巢穴与食物源之间的最短路径。经研究发现,蚂蚁的这种群体协作功能是通过一种遗留在其来往路径上的叫做信息素(Pheromone)的 挥发性化学物质来进行通信和协调的。 化学通信是蚂蚁采取的基本信息交流方式之一,在蚂蚁的生活习性中起着重要的作用。通过对蚂蚁 觅食行为的研究,他们发现,整个蚁群就是通过这种信息素进行相互协作,形成 正反馈,从而使多个路径上的蚂蚁都逐渐聚集到最短的那条路径上。
    这样,M.Dorigo等人于1991年首先提出了蚁群算法。其主要特点就是:通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法。它充分利用了生物蚁群能通过个体间简单的信息传递,搜索从蚁巢至食物间最短路径的集体寻优特征,以及该过程与 旅行商问题求解之间的相似性。得到了具有NP难度的旅行商问题的最优解答。同时,该算法还被用于求解Job-Shop调度问题、二次指派问题以及多维 背包问题等,显示了其适用于组合优化类 问题求解的优越特征。
    多年来世界各地研究工作者对蚁群算法进行了精心研究和应用开发,该算法现已被大量应用于数据分析、机器人协作问题求解、电力、通信、水利、采矿、化工、建筑、交通等领域。
    蚁群算法之所以能引起相关领域研究者的注意,是因为这种求解模式能将问题求解的快速性、全局优化特征以及有限时间内答案的合理性结合起来。其中,寻优的快速性是通过正反馈式的信息传递和积累来保证的。而算法的早熟性收敛又可以通过其分布式计算特征加以避免,同时,具有贪婪启发 
    图3蚁群在障碍物前经过一段时间后的情形
    式搜索特征的蚁群系统又能在搜索过程的早期找到可以接受的问题解答。这种优越的问题分布式求解模式经过相关领域研究者的关注和努力,已经在最初的算法模型基础上得到了很大的改进和拓展。
    经过一定时间,从食物源返回的蚂蚁到达D点同样也碰到障碍物,也需要进行选择。此时A, B两侧的信息素浓度相同,它们仍然一半向左,一半向右。但是当A侧的蚂蚁已经完全绕过障碍物到达C点时,B侧的蚂蚁由于需走的路径更长,还不能到达C点,图3表示蚁群在障碍物前经过一段时间后的情形。
    此时对于从蚁巢出发来到C点的蚂蚁来说,由于A侧的信息素浓度高,B侧的信息素较低,就倾向于选择A侧的路径。这样的结果是A侧的蚂蚁越来越多,最终所有蚂蚁都选择这条较短的路径,图4 表示蚁群最终选择的路径
    图4 蚁群最终选择的路径
    上述过程,很显然是由蚂蚁所留下的信息素的“正反馈”过程而导致的。蚂蚁个体就是通过这种信息的交流来达到搜索食物的目的。蚁群算法的基本思想也是从这个过程转化而来的。
    蚁群算法的特点:
    1)蚁群算法是一种自组织的算法。在系统论中,自组织和它组织是组织的两个基本分类,其区别在于组织力或组织指令是来自于系统的内部还是来自于系统的外部,来自于系统内部的是自组织,来自于系统外部的是他组织。如果系统在获得空间的、时间的或者功能结构的过程中,没有外界的特定干预,我们便说系统是自组织的。在抽象意义上讲,自组织就是在没有外界作用下使得系统熵减小的过程(即是系统从无序到有序的变化过程)。蚁群算法充分体现了这个过程,以蚂蚁群体优化为例子说明。当算法开始的初期,单个的人工蚂蚁无序的寻找解,算法经过一段时间的演化,人工蚂蚁间通过信息激素的作用,自发的越来越趋向于寻找到接近最优解的一些解,这就是一个无序到有序的过程。
    2)蚁群算法是一种本质上并行的算法。每只蚂蚁搜索的过程彼此独立,仅通过信息激素进行通信。所以蚁群算法则可以看作是一个分布式的多agent系统,它在问题空间的多点同时开始进行独立的解搜索,不仅增加了算法的可靠性,也使得算法具有较强的全局搜索能力。
    3)蚁群算法是一种正反馈的算法。从真实蚂蚁的觅食过程中我们不难看出,蚂蚁能够最终找到最短路径,直接依赖于最短路径上信息激素的堆积,而信息激素的堆积却是一个正反馈的过程。对蚁群算法来说,初始时刻在环境中存在完全相同的信息激素,给予系统一个微小扰动,使得各个边上的轨迹浓度不相同,蚂蚁构造的解就存在了优劣,算法采用的反馈方式是在较优的解经过的路径留下更多的信息激素,而更多的信息激素又吸引了更多的蚂蚁,这个正反馈的过程使得初始的不同得到不断的扩大,同时又引导整个系统向 最优解的方向进化。因此,正反馈是蚂蚁算法的重要特征,它使得算法演化过程得以进行。
    4)蚁群算法具有较强的鲁棒性。相对于其它算法,蚁群算法对初始路线要求不高,即蚁群算法的求解结果不依赖于初始路线的选择,而且在搜索过程中不需要进行人工的调整。其次,蚁群算法的参数数目少,设置简单,易于蚁群算法应用到其它组合优化问题的求解。
    蚁群算法的应用进展以蚁群算法为代表的蚁群智能已成为当今分布式人工智能研究的一个热点,许多源于蜂群和蚁群模型设计的算法己越来越多地被应用于企业的运转模式的研究。美国 五角大楼正在资助关于群智能系统的研究工作-群体战略(Swarm Strategy),它的一个实战用途是通过运用成群的空中 无人驾驶飞行器和地面车辆来转移敌人的注意力,让自己的军队在敌人后方不被察觉地安全进行。英国电信公司和美国世界通信公司以电子蚂蚁为基础,对新的电信网络管理方法进行了试验。群智能还被应用于工厂生产计划的制定和运输部门的后勤管理。美国太平洋西南航空公司采用了一种直接源于蚂蚁行为研究成果的运输管理软件,结果每年至少节约了1000万美元的费用开支。英国 联合利华公司己率先利用群智能技术改善其一家牙膏厂的运转情况。美国通用汽车公司、法国液气公司、荷兰公路交通部和美国一些移民事务机构也都采用这种技术来改善其运转的机能。鉴于群智能广阔的应用前景,美国和欧盟均于近几年开始出资资助基于群智能模拟的相关研究项目,并在一些院校开设群体智能的相关课程。国内,国家自然科学基金”十五”期间 学科交叉类优先资助领域中的认知科学及其信息处理的研究内容中也明确列出了群智能领域的进化、自适应与现场认知主题。
    蚁群优化算法最初用于解决TSP问题,经过多年的发展,已经陆续渗透到其他领域中,比如图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。蚁群算法在若干领域己获得成功的应用,其中最成功的是在组合优化问题中的应用。
    在网络路由处理中,网络的流量分布不断变化,网络链路或结点也会随机地失效或重新加入。蚁群的自身催化与正向 反馈机制正好符合了这类问题的求解特点,因而,蚁群算法在网络领域得到一定应用。蚁群 觅食行为所呈现出的并行与分布特性使得算法特别适合于并行化处理。因而,实现算法的并行化执行对于大量复杂的实际应用问题的求解来说是极具潜力的。
    在某群体中若存在众多无智能的个体,它们通过相互之间的简单合作所表现出来的智能行为即称为集群智能(Swarm Intelligence)。互联网上的交流,不过是更多的神经元连接(人脑)通过互联网相互作用的结果,光缆和路由器不过是轴突和突触的延伸。从 自组织现象的角度上看,人脑的智能和蚁群也没有本质上的区别,单个 神经元没有智能可言,单个蚂蚁也没有,但是通过连接形成的体系,是一个智能体。(作者: 李精灵 编选:中国电子商务研究中心)


    1. 蚁群算法简介

         蚁群算法(Ant Clony Optimization, ACO)是一种群智能算法,它是由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为,从而为求解复杂问题提供了一个新的可能性。蚁群算法最早是由意大利学者Colorni A., Dorigo M. 等于1991年提出。经过20多年的发展,蚁群算法在理论以及应用研究上已经得到巨大的进步。

          蚁群算法是一种仿生学算法,是由自然界中蚂蚁觅食的行为而启发的。在自然界中,蚂蚁觅食过程中,蚁群总能够按照寻找到一条从蚁巢和食物源的最优路径。图(1)显示了这样一个觅食的过程。

    image

    图(1)蚂蚁觅食

     

         在图1(a)中,有一群蚂蚁,假如A是蚁巢,E是食物源(反之亦然)。这群蚂蚁将沿着蚁巢和食物源之间的直线路径行驶。假如在A和E之间突然出现了一个障碍物(图1(b)),那么,在B点(或D点)的蚂蚁将要做出决策,到底是向左行驶还是向右行驶?由于一开始路上没有前面蚂蚁留下的信息素(pheromone),蚂蚁朝着两个方向行进的概率是相等的。但是当有蚂蚁走过时,它将会在它行进的路上释放出信息素,并且这种信息素会议一定的速率散发掉。信息素是蚂蚁之间交流的工具之一。它后面的蚂蚁通过路上信息素的浓度,做出决策,往左还是往右。很明显,沿着短边的的路径上信息素将会越来越浓(图1(c)),从而吸引了越来越多的蚂蚁沿着这条路径行驶。

    2. TSP问题描述

          蚁群算法最早用来求解TSP问题,并且表现出了很大的优越性,因为它分布式特性,鲁棒性强并且容易与其它算法结合,但是同时也存在这收敛速度慢,容易陷入局部最优(local optimal)等缺点。

          TSP问题(Travel Salesperson Problem,即旅行商问题或者称为中国邮递员问题),是一种,是一种NP-hard问题,此类问题用一般的算法是很大得到最优解的,所以一般需要借助一些启发式算法求解,例如遗传算法(GA),蚁群算法(ACO),微粒群算法(PSO)等等。

          TSP问题可以分为两类,一类是对称TSP问题(Symmetric TSP),另一类是非对称问题(Asymmetric TSP)。所有的TSP问题都可以用一个图(Graph)来描述:

    是所有城市的集合. 表示第i个城市, 为城市的数目;

    是所有城市之间连接的集合;

    是所有城市之间连接的成本度量(一般为城市之间的距离);

    如果, 那么该TSP问题为对称的,否则为非对称的。

    一个TSP问题可以表达为:

    求解遍历图,所有的节点一次并且回到起始节点,使得连接这些节点的路径成本最低。

    3. 蚁群算法原理

          假如蚁群中所有蚂蚁的数量为m,所有城市之间的信息素用矩阵pheromone表示,最短路径为bestLength,最佳路径为bestTour。每只蚂蚁都有自己的内存,内存中用一个禁忌表(Tabu)来存储该蚂蚁已经访问过的城市,表示其在以后的搜索中将不能访问这些城市;还有用另外一个允许访问的城市表(Allowed)来存储它还可以访问的城市;另外还用一个矩阵(Delta)来存储它在一个循环(或者迭代)中给所经过的路径释放的信息素;还有另外一些数据,例如一些控制参数,该蚂蚁行走玩全程的总成本或距离(tourLength),等等。假定算法总共运行MAX_GEN次,运行时间为t。

    蚁群算法计算过程如下:

    (1)初始化

    设t=0,初始化bestLength为一个非常大的数(正无穷),bestTour为空。初始化所有的蚂蚁的Delt矩阵所有元素初始化为0,Tabu表清空,Allowed表中加入所有的城市节点。随机选择它们的起始位置(也可以人工指定)。在Tabu中加入起始节点,Allowed中去掉该起始节点。

    (2)为每只蚂蚁选择下一个节点。

    为每只蚂蚁选择下一个节点,该节点只能从Allowed中以某种概率(公式1)搜索到,每搜到一个,就将该节点加入到Tabu中,并且从Allowed中删除该节点。该过程重复n-1次,直到所有的城市都遍历过一次。遍历完所有节点后,将起始节点加入到Tabu中。此时Tabu表元素数量为n+1(n为城市数量),Allowed元素数量为0。接下来按照(公式2)计算每个蚂蚁的Delta矩阵值。最后计算最佳路径,比较每个蚂蚁的路径成本,然后和bestLength比较,若它的路径成本比bestLength小,则将该值赋予bestLength,并且将其Tabu赋予BestTour。

    (公式1)

    (公式2)

    其中表示选择城市j的概率,表示第个蚂蚁,表示城市在第时刻的信息素浓度,表示从城市i到城市j的可见度,

    ,表示城市之间的成本(或距离)。由此可见越小,越大,也就是从城市到的可见性就越大。表示蚂蚁在城市与之间留下的信息素。

    表示蚂蚁经过一个循环(或迭代)锁经过路径的总成本(或距离),即tourLength. 均为控制参数。

    (3)更新信息素矩阵

    令t,按照(公式3)更新信息素矩阵phermone。

    (公式3)

    为时刻城市与之间的信息素浓度。为控制参数,为城市与之间信息素经过一个迭代后的增量。并且有

    (公式4)

    其中由公式计算得到。

    (4)检查终止条件

    如果达到最大代数MAX_GEN,算法终止,转到第(5)步;否则,重新初始化所有的蚂蚁的Delt矩阵所有元素初始化为0,Tabu表清空,Allowed表中加入所有的城市节点。随机选择它们的起始位置(也可以人工指定)。在Tabu中加入起始节点,Allowed中去掉该起始节点,重复执行(2),(3),(4)步。

    (5)输出最优值

    4. Java实现

          在该java实现中我们选择使用tsplib上的数据att48,这是一个对称tsp问题,城市规模为48,其最优值为10628.其距离计算方法如图(2)所示:

    image

    图(2)att48距离计算方法

          实现中,使用了两个java类,一个Ant类,一个ACO类。

    具体实现代码如下(此代码借鉴了蚁群优化算法的JAVA实现):

    Ant类:

      1: import java.util.Random;
    
      2: import java.util.Vector;
    
      3: 
    
      4: /**
    
      5:  * 
    
      6:  * @author BIAO YU
    
      7:  *
    
      8:  */
    
      9: public class Ant implements Cloneable {
    
     10: 
    
     11:   private Vector<Integer> tabu; //禁忌表
    
     12:   private Vector<Integer> allowedCities; //允许搜索的城市
    
     13:   private float[][] delta; //信息数变化矩阵
    
     14:   private int[][] distance; //距离矩阵
    
     15:   
    
     16:   private float alpha; 
    
     17:   private float beta;
    
     18:   
    
     19:   private int tourLength; //路径长度
    
     20:   private int cityNum; //城市数量
    
     21:   
    
     22:   private int firstCity; //起始城市
    
     23:   private int currentCity; //当前城市
    
     24:   
    
     25:   public Ant(){
    
     26:     cityNum = 30;
    
     27:     tourLength = 0;
    
     28:     
    
     29:   }
    
     30:   
    
     31:   /**
    
     32:    * Constructor of Ant
    
     33:    * @param num 蚂蚁数量
    
     34:    */
    
     35:   public Ant(int num){
    
     36:     cityNum = num;
    
     37:     tourLength = 0;
    
     38:     
    
     39:   }
    
     40:   
    
     41:   /**
    
     42:    * 初始化蚂蚁,随机选择起始位置
    
     43:    * @param distance 距离矩阵
    
     44:    * @param a alpha
    
     45:    * @param b beta
    
     46:    */
    
     47:   public void init(int[][] distance, float a, float b){
    
     48:     alpha = a;
    
     49:     beta = b;
    
     50:     allowedCities = new Vector<Integer>();
    
     51:     tabu = new Vector<Integer>();
    
     52:     this.distance = distance;
    
     53:     delta = new float[cityNum][cityNum];
    
     54:     for (int i = 0; i < cityNum; i++) {
    
     55:       Integer integer = new Integer(i);
    
     56:       allowedCities.add(integer);
    
     57:       for (int j = 0; j < cityNum; j++) {
    
     58:         delta[i][j] = 0.f;
    
     59:       }
    
     60:     }
    
     61:     
    
     62:     Random random = new Random(System.currentTimeMillis());
    
     63:     firstCity = random.nextInt(cityNum);
    
     64:     for (Integer i:allowedCities) {
    
     65:       if (i.intValue() == firstCity) {
    
     66:         allowedCities.remove(i);
    
     67:         break;
    
     68:       }
    
     69:     }
    
     70:     
    
     71:     tabu.add(Integer.valueOf(firstCity));
    
     72:     currentCity = firstCity;
    
     73:   }
    
     74:   
    
     75:   /**
    
     76:    * 选择下一个城市
    
     77:    * @param pheromone 信息素矩阵
    
     78:    */
    
     79:   public void selectNextCity(float[][] pheromone){
    
     80:     float[] p = new float[cityNum];
    
     81:     float sum = 0.0f;
    
     82:     //计算分母部分
    
     83:     for (Integer i:allowedCities) {
    
     84:       sum += Math.pow(pheromone[currentCity][i.intValue()], alpha)*Math.pow(1.0/distance[currentCity][i.intValue()], beta);
    
     85:     }
    
     86:     //计算概率矩阵
    
     87:     for (int i = 0; i < cityNum; i++) {
    
     88:       boolean flag = false;
    
     89:       for (Integer j:allowedCities) {
    
     90:         
    
     91:         if (i == j.intValue()) {
    
     92:           p[i] = (float) (Math.pow(pheromone[currentCity][i], alpha)*Math.pow(1.0/distance[currentCity][i], beta))/sum;
    
     93:           flag = true;
    
     94:           break;
    
     95:         }
    
     96:       }
    
     97:       
    
     98:       if (flag == false) {
    
     99:         p[i] = 0.f;
    
    100:       }
    
    101:     }
    
    102:     
    
    103:     //轮盘赌选择下一个城市
    
    104:     Random random = new Random(System.currentTimeMillis());
    
    105:     float sleectP = random.nextFloat();
    
    106:     int selectCity = 0;
    
    107:     float sum1 = 0.f;
    
    108:     for (int i = 0; i < cityNum; i++) {
    
    109:       sum1 += p[i];
    
    110:       if (sum1 >= sleectP) {
    
    111:         selectCity = i;
    
    112:         break;
    
    113:       }
    
    114:     }
    
    115:     
    
    116:     //从允许选择的城市中去除select city
    
    117:     for (Integer i:allowedCities) {
    
    118:       if (i.intValue() == selectCity) {
    
    119:         allowedCities.remove(i);
    
    120:         break;
    
    121:       }
    
    122:     }
    
    123:     //在禁忌表中添加select city
    
    124:     tabu.add(Integer.valueOf(selectCity));
    
    125:     //将当前城市改为选择的城市
    
    126:     currentCity = selectCity;
    
    127:     
    
    128:   }
    
    129:   
    
    130:   /**
    
    131:    * 计算路径长度
    
    132:    * @return 路径长度
    
    133:    */
    
    134:   private int calculateTourLength(){
    
    135:     int len = 0;
    
    136:     for (int i = 0; i < cityNum; i++) {
    
    137:       len += distance[this.tabu.get(i).intValue()][this.tabu.get(i+1).intValue()];
    
    138:     }
    
    139:     return len;
    
    140:   }
    
    141:   
    
    142:   
    
    143:   
    
    144:   public Vector<Integer> getAllowedCities() {
    
    145:     return allowedCities;
    
    146:   }
    
    147: 
    
    148:   public void setAllowedCities(Vector<Integer> allowedCities) {
    
    149:     this.allowedCities = allowedCities;
    
    150:   }
    
    151: 
    
    152:   public int getTourLength() {
    
    153:     tourLength = calculateTourLength();
    
    154:     return tourLength;
    
    155:   }
    
    156:   public void setTourLength(int tourLength) {
    
    157:     this.tourLength = tourLength;
    
    158:   }
    
    159:   public int getCityNum() {
    
    160:     return cityNum;
    
    161:   }
    
    162:   public void setCityNum(int cityNum) {
    
    163:     this.cityNum = cityNum;
    
    164:   }
    
    165: 
    
    166:   public Vector<Integer> getTabu() {
    
    167:     return tabu;
    
    168:   }
    
    169: 
    
    170:   public void setTabu(Vector<Integer> tabu) {
    
    171:     this.tabu = tabu;
    
    172:   }
    
    173: 
    
    174:   public float[][] getDelta() {
    
    175:     return delta;
    
    176:   }
    
    177: 
    
    178:   public void setDelta(float[][] delta) {
    
    179:     this.delta = delta;
    
    180:   }
    
    181: 
    
    182:   public int getFirstCity() {
    
    183:     return firstCity;
    
    184:   }
    
    185: 
    
    186:   public void setFirstCity(int firstCity) {
    
    187:     this.firstCity = firstCity;
    
    188:   }
    
    189:   
    
    190: }
    
    191: 

    ACO类:

      1: import java.io.BufferedReader;
    
      2: import java.io.FileInputStream;
    
      3: import java.io.IOException;
    
      4: import java.io.InputStreamReader;
    
      5: 
    
      6: /**
    
      7:  * 
    
      8:  * @author BIAO YU
    
      9:  * 
    
     10:  *
    
     11:  */
    
     12: public class ACO {
    
     13: 
    
     14:   private Ant[] ants; //蚂蚁
    
     15:   private int antNum; //蚂蚁数量
    
     16:   private int cityNum; //城市数量
    
     17:   private int MAX_GEN; //运行代数
    
     18:   private float[][] pheromone; //信息素矩阵
    
     19:   private int[][] distance; //距离矩阵
    
     20:   private int bestLength; //最佳长度
    
     21:   private int[] bestTour; //最佳路径
    
     22:   
    
     23:   //三个参数
    
     24:   private float alpha; 
    
     25:   private float beta;
    
     26:   private float rho;
    
     27:   
    
     28:   
    
     29:   public ACO(){
    
     30:     
    
     31:   }
    
     32:   /** constructor of ACO
    
     33:    * @param n 城市数量
    
     34:    * @param m 蚂蚁数量
    
     35:    * @param g 运行代数
    
     36:    * @param a alpha
    
     37:    * @param b beta
    
     38:    * @param r rho
    
     39:    * 
    
     40:   **/
    
     41:   public ACO(int n, int m, int g, float a, float b, float r) {
    
     42:     cityNum = n;
    
     43:     antNum = m;
    
     44:     ants = new Ant[antNum];
    
     45:     MAX_GEN = g;
    
     46:     alpha = a;
    
     47:     beta = b;
    
     48:     rho = r;
    
     49:     
    
     50:   }
    
     51:   
    
     52:   @SuppressWarnings("resource")
    
     53:   /**
    
     54:    * 初始化ACO算法类
    
     55:    * @param filename 数据文件名,该文件存储所有城市节点坐标数据
    
     56:    * @throws IOException
    
     57:    */
    
     58:   private void init(String filename) throws IOException{
    
     59:     //读取数据  
    
     60:         int[] x;  
    
     61:         int[] y;  
    
     62:         String strbuff;  
    
     63:         BufferedReader data = new BufferedReader(new InputStreamReader(new FileInputStream(filename)));  
    
     64:         
    
     65:         distance = new int[cityNum][cityNum];  
    
     66:         x = new int[cityNum];  
    
     67:         y = new int[cityNum];  
    
     68:         for (int i = 0; i < cityNum; i++) {  
    
     69:             strbuff = data.readLine(); 
    
     70:             String[] strcol = strbuff.split("");  
    
     71:             x[i] = Integer.valueOf(strcol[1]);  
    
     72:             y[i] = Integer.valueOf(strcol[2]);  
    
     73:         }  
    
     74:         //计算距离矩阵 ,针对具体问题,距离计算方法也不一样,此处用的是att48作为案例,它有48个城市,距离计算方法为伪欧氏距离,最优值为10628 
    
     75:         for (int i = 0; i < cityNum - 1; i++) {  
    
     76:             distance[i][i] = 0;  //对角线为0
    
     77:             for (int j = i + 1; j < cityNum; j++) {  
    
     78:               double rij = Math.sqrt(((x[i] - x[j]) * (x[i] - x[j])+ (y[i] - y[j]) * (y[i] - y[j]))/10.0);
    
     79:               int tij = (int) Math.round(rij);
    
     80:               if (tij < rij) {
    
     81:                 distance[i][j] = tij + 1;  
    
     82:                     distance[j][i] = distance[i][j];  
    
     83:         }else {
    
     84:           distance[i][j] = tij;  
    
     85:                     distance[j][i] = distance[i][j]; 
    
     86:         }
    
     87:             }  
    
     88:         }  
    
     89:         distance[cityNum - 1][cityNum - 1] = 0;  
    
     90:         
    
     91:         //初始化信息素矩阵  
    
     92:         pheromone=new float[cityNum][cityNum];  
    
     93:         for(int i=0;i<cityNum;i++)  
    
     94:         {  
    
     95:             for(int j=0;j<cityNum;j++){  
    
     96:                 pheromone[i][j]=0.1f;  //初始化为0.1
    
     97:             }  
    
     98:         }  
    
     99:         bestLength=Integer.MAX_VALUE;  
    
    100:         bestTour=new int[cityNum+1];  
    
    101:         //随机放置蚂蚁  
    
    102:         for(int i=0;i<antNum;i++){  
    
    103:             ants[i]=new Ant(cityNum);  
    
    104:             ants[i].init(distance, alpha, beta);  
    
    105:         }  
    
    106:   }
    
    107:   
    
    108:   public void solve(){
    
    109:     
    
    110:     for (int g = 0; g < MAX_GEN; g++) {
    
    111:       for (int i = 0; i < antNum; i++) {
    
    112:         for (int j = 1; j < cityNum; j++) {
    
    113:           ants[i].selectNextCity(pheromone);
    
    114:         }
    
    115:         ants[i].getTabu().add(ants[i].getFirstCity());
    
    116:         if (ants[i].getTourLength() < bestLength) {
    
    117:           bestLength = ants[i].getTourLength();
    
    118:           for (int k = 0; k < cityNum + 1; k++) {
    
    119:             bestTour[k] = ants[i].getTabu().get(k).intValue();
    
    120:           }
    
    121:         }
    
    122:         for (int j = 0; j < cityNum; j++) {
    
    123:           ants[i].getDelta()[ants[i].getTabu().get(j).intValue()][ants[i].getTabu().get(j+1).intValue()] = (float) (1./ants[i].getTourLength());
    
    124:           ants[i].getDelta()[ants[i].getTabu().get(j+1).intValue()][ants[i].getTabu().get(j).intValue()] = (float) (1./ants[i].getTourLength());
    
    125:         }
    
    126:       }
    
    127:       
    
    128:       //更新信息素
    
    129:       updatePheromone();
    
    130:       
    
    131:        //重新初始化蚂蚁
    
    132:           for(int i=0;i<antNum;i++){  
    
    133:              
    
    134:               ants[i].init(distance, alpha, beta);  
    
    135:           }  
    
    136:     }
    
    137:     
    
    138:     //打印最佳结果
    
    139:     printOptimal();
    
    140:   }
    
    141:   
    
    142:   //更新信息素
    
    143:   private void updatePheromone(){
    
    144:     //信息素挥发  
    
    145:         for(int i=0;i<cityNum;i++)  
    
    146:             for(int j=0;j<cityNum;j++)  
    
    147:                 pheromone[i][j]=pheromone[i][j]*(1-rho);  
    
    148:         //信息素更新  
    
    149:         for(int i=0;i<cityNum;i++){  
    
    150:             for(int j=0;j<cityNum;j++){  
    
    151:                 for (int k = 0; k < antNum; k++) {
    
    152:           pheromone[i][j] += ants[k].getDelta()[i][j];
    
    153:         } 
    
    154:             }  
    
    155:         }  
    
    156:   }
    
    157:   
    
    158:   private void printOptimal(){
    
    159:     System.out.println("The optimal length is: " + bestLength);
    
    160:     System.out.println("The optimal tour is: ");
    
    161:     for (int i = 0; i < cityNum + 1; i++) {
    
    162:       System.out.println(bestTour[i]);
    
    163:     }
    
    164:   }
    
    165:   
    
    166:   public Ant[] getAnts() {
    
    167:     return ants;
    
    168:   }
    
    169: 
    
    170:   public void setAnts(Ant[] ants) {
    
    171:     this.ants = ants;
    
    172:   }
    
    173: 
    
    174:   public int getAntNum() {
    
    175:     return antNum;
    
    176:   }
    
    177: 
    
    178:   public void setAntNum(int m) {
    
    179:     this.antNum = m;
    
    180:   }
    
    181: 
    
    182:   public int getCityNum() {
    
    183:     return cityNum;
    
    184:   }
    
    185: 
    
    186:   public void setCityNum(int cityNum) {
    
    187:     this.cityNum = cityNum;
    
    188:   }
    
    189: 
    
    190:   public int getMAX_GEN() {
    
    191:     return MAX_GEN;
    
    192:   }
    
    193: 
    
    194:   public void setMAX_GEN(int mAX_GEN) {
    
    195:     MAX_GEN = mAX_GEN;
    
    196:   }
    
    197: 
    
    198:   public float[][] getPheromone() {
    
    199:     return pheromone;
    
    200:   }
    
    201: 
    
    202:   public void setPheromone(float[][] pheromone) {
    
    203:     this.pheromone = pheromone;
    
    204:   }
    
    205: 
    
    206:   public int[][] getDistance() {
    
    207:     return distance;
    
    208:   }
    
    209: 
    
    210:   public void setDistance(int[][] distance) {
    
    211:     this.distance = distance;
    
    212:   }
    
    213: 
    
    214:   public int getBestLength() {
    
    215:     return bestLength;
    
    216:   }
    
    217: 
    
    218:   public void setBestLength(int bestLength) {
    
    219:     this.bestLength = bestLength;
    
    220:   }
    
    221: 
    
    222:   public int[] getBestTour() {
    
    223:     return bestTour;
    
    224:   }
    
    225: 
    
    226:   public void setBestTour(int[] bestTour) {
    
    227:     this.bestTour = bestTour;
    
    228:   }
    
    229: 
    
    230:   public float getAlpha() {
    
    231:     return alpha;
    
    232:   }
    
    233: 
    
    234:   public void setAlpha(float alpha) {
    
    235:     this.alpha = alpha;
    
    236:   }
    
    237: 
    
    238:   public float getBeta() {
    
    239:     return beta;
    
    240:   }
    
    241: 
    
    242:   public void setBeta(float beta) {
    
    243:     this.beta = beta;
    
    244:   }
    
    245: 
    
    246:   public float getRho() {
    
    247:     return rho;
    
    248:   }
    
    249: 
    
    250:   public void setRho(float rho) {
    
    251:     this.rho = rho;
    
    252:   }
    
    253: 
    
    254: 
    
    255:   /**
    
    256:    * @param args
    
    257:    * @throws IOException 
    
    258:    */
    
    259:   public static void main(String[] args) throws IOException {
    
    260:     ACO aco = new ACO(48, 100, 1000, 1.f, 5.f, 0.5f);
    
    261:     aco.init("c://data.txt");
    
    262:     aco.solve();
    
    263:   }
    
    264: 
    
    265: }
    
    266: 

    5. 总结

          蚁群算法和其它的启发式算法一样,在很多场合都得到了应用,并且取得了很好的结果。但是同样存在着很多的缺点,例如收敛速度慢,容易陷入局部最优,等等。对于这些问题,还需要进一步的研究和探索,另外蚁群算法的数学机理至今还没有得到科学的解释,这也是当前研究的热点和急需解决的问题之一。


    更多相关内容
  • 资源名:利用改进的蚂蚁算法_带精英策略的蚂蚁算法_求解TSP问题_深入理解蚂蚁算法的优化原理_matlab 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能...
  • 基于蚂蚁算法的动态分布式路由算法.rar
  • 针对中国邮路问题中先寻找奇数度结点,再进行奇数度结点之间路线添加的问题,引入了蚂蚁算法,通过其随机概率选择和最短路线激励策略,有效地解决了结点之间的最短路线的问题,避免了常规方法中必须先进行奇数度结点匹配...
  • 一个与人工智能相关的VB蚂蚁算法实例代码,寻找最短路径,蚂蚁会找到蚂蚁窝与食物之间最短的路径,找到这种智能路径的方法就是依靠于本算法,让蚂蚁变得非常聪明,可用于VB各种编程中,特别是游戏当中。
  • 蚂蚁算法是通过信息素的累积和更新收敛于最优路径上,具有分布式并行全 局搜索能力. 但初期信息素匮乏,求解速度慢. 算法是将遗传算法与蚂蚁算法融合,采用遗传算法生成信息素分布,利用 蚂蚁算法求精确解,优势...
  • 交互式蚂蚁算法

    2021-01-14 17:27:11
    为此, 提出一种将人对问题解的数量评价值作为目标函数值的交互式蚂蚁算法. 从人机交互的特点出发, 设计 了算法模型的结构、信息素的放置方式与更新策略和用户的评价方式. 最后利用模拟算法环境的函数优化实验和...
  • 蚂蚁算法

    千次阅读 2019-11-05 17:03:30
    蚁群算法1.概念及原理2....原理:蚁群算法的基本思想来源于自然界蚂蚁觅食的最短路径原理,根据昆虫科学家的观察,发现自然界的蚂蚁虽然视觉不发达,但它们可以在没有任何提示的情况下找到从食物源到巢穴的...

    1.概念及原理

    概念:蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。
    原理:蚁群算法的基本思想来源于自然界蚂蚁觅食的最短路径原理,根据昆虫科学家的观察,发现自然界的蚂蚁虽然视觉不发达,但它们可以在没有任何提示的情况下找到从食物源到巢穴的最短路径,并在周围环境发生变化后,自适应地搜索新的最佳路径。

    蚂蚁在寻找食物源的时候,能在其走过的路径上释放一种叫信息素的激素,使一定范围内的其他蚂蚁能够察觉到。当一些路径上通过的蚂蚁越来越多时,信息素也就越来越多,蚂蚁们选择这条路径的概率也就越高,结果导致这条路径上的信息素又增多,蚂蚁走这条路的概率又增加,生生不息。这种选择过程被称为蚂蚁的自催化行为。对于单个蚂蚁来说,它并没有要寻找最短路径,只是根据概率选择;对于整个蚁群系统来说,它们却达到了寻找到最优路径的客观上的效果,这就是群体智能。

    2.代码设计

    关键参数:
    蚂蚁数量:

    设M表示城市数量,m表示蚂蚁数量。m的数量很重要,因为m过大时,会导致搜索过的路径上信息素变化趋于平均,这样就不好找出好的路径了;m过小时,易使未被搜索到的路径信息素减小到0,这样可能会出现早熟,没找到全局最优解。一般上,在时间等资源条件紧迫的情况下,蚂蚁数设定为城市数的1.5倍较稳妥。

    信息素因子:

    信息素因子反映了蚂蚁在移动过程中所积累的信息量在指导蚁群搜索中的相对重要程度,其值过大,蚂蚁选择以前走过的路径概率大,搜索随机性减弱;值过小,等同于贪婪算法,使搜索过早陷入局部最优。实验发现,信息素因子选择[1,4]区间,性能较好。

    启发函数因子:

    启发函数因子反映了启发式信息在指导蚁群搜索过程中的相对重要程度,其大小反映的是蚁群寻优过程中先验性和确定性因素的作用强度。过大时,虽然收敛速度会加快,但容易陷入局部最优;过小时,容易陷入随机搜索,找不到最优解。实验研究发现,当启发函数因子为[3,4.5]时,综合求解性能较好。

    信息素挥发因子:

    信息素挥发因子表示信息素的消失水平,它的大小直接关系到蚁群算法的全局搜索能力和收敛速度。实验发现,当属于[0.2,0.5]时,综合性能较好。

    信息素常数:

    这个参数为信息素强度,表示蚂蚁循环一周时释放在路径上的信息素总量,其作用是为了充分利用有向图上的全局信息反馈量,使算法在正反馈机制作用下以合理的演化速度搜索到全局最优解。值越大,蚂蚁在已遍历路径上的信息素积累越快,有助于快速收敛。实验发现,当值属于[10,1000]时,综合性能较好。

    最大迭代次数:

    最大迭代次数值过小,可能导致算法还没收敛就已结束;过大则会导致资源浪费。一般最大迭代次数可以取100到500次。一般来讲,建议先取200,然后根据执行程序查看算法收敛的轨迹来修改取值。

    %% 旅行商问题(TSP)优化
    %% 清空环境变量
    clear all
    clc
    
    %% 导入数据
    load citys_data.mat
    
    %% 计算城市间相互距离
    fprintf('Computing Distance Matrix... \n');
    n = size(citys,1);
    D = zeros(n,n);
    for i = 1:n
        for j = 1:n
            if i ~= j
                D(i,j) = sqrt(sum((citys(i,:) - citys(j,:)).^2));
            else
                D(i,j) = 1e-4;      
            end
        end    
    end
    
    %% 初始化参数
    fprintf('Initializing Parameters... \n');
    m = 40;                              % 蚂蚁数量
    alpha = 2;                           % 信息素重要程度因子
    beta = 4;                            % 启发函数重要程度因子
    rho = 0.3;                           % 信息素挥发因子
    Q = 1;                               % 常系数
    Eta = 1./D;                          % 启发函数
    Tau = ones(n,n);                     % 信息素矩阵
    Table = zeros(m,n);                  % 路径记录表
    iter = 1;                            % 迭代次数初值
    iter_max = 150;                      % 最大迭代次数 
    Route_best = zeros(iter_max,n);      % 各代最佳路径       
    Length_best = zeros(iter_max,1);     % 各代最佳路径的长度  
    Length_ave = zeros(iter_max,1);      % 各代路径的平均长度  
    
    %% 迭代寻找最佳路径
    figure;
    while iter <= iter_max
        fprintf('迭代第%d次\n',iter);
        % 随机产生各个蚂蚁的起点城市
          start = zeros(m,1);
          for i = 1:m
              temp = randperm(n);
              start(i) = temp(1);
          end
          Table(:,1) = start; 
          % 构建解空间
          citys_index = 1:n;
          % 逐个蚂蚁路径选择
          for i = 1:m
              % 逐个城市路径选择
             for j = 2:n
                 tabu = Table(i,1:(j - 1));           % 已访问的城市集合(禁忌表)
                 allow_index = ~ismember(citys_index,tabu);
                 allow = citys_index(allow_index);  % 待访问的城市集合
                 P = allow;
                 % 计算城市间转移概率
                 for k = 1:length(allow)
                     P(k) = Tau(tabu(end),allow(k))^alpha * Eta(tabu(end),allow(k))^beta;
                 end
                 P = P/sum(P);
                 % 轮盘赌法选择下一个访问城市
                 Pc = cumsum(P);     
                target_index = find(Pc >= rand); 
                target = allow(target_index(1));
                Table(i,j) = target;
             end
          end
          % 计算各个蚂蚁的路径距离
          Length = zeros(m,1);
          for i = 1:m
              Route = Table(i,:);
              for j = 1:(n - 1)
                  Length(i) = Length(i) + D(Route(j),Route(j + 1));
              end
              Length(i) = Length(i) + D(Route(n),Route(1));
          end
          % 计算最短路径距离及平均距离
          if iter == 1
              [min_Length,min_index] = min(Length);
              Length_best(iter) = min_Length;  
              Length_ave(iter) = mean(Length);
              Route_best(iter,:) = Table(min_index,:);
          else
              [min_Length,min_index] = min(Length);
              Length_best(iter) = min(Length_best(iter - 1),min_Length);
              Length_ave(iter) = mean(Length);
              if Length_best(iter) == min_Length
                  Route_best(iter,:) = Table(min_index,:);
              else
                  Route_best(iter,:) = Route_best((iter-1),:);
              end
          end
          % 更新信息素
          Delta_Tau = zeros(n,n);
          % 逐个蚂蚁计算
          for i = 1:m
              % 逐个城市计算
              for j = 1:(n - 1)
                  Delta_Tau(Table(i,j),Table(i,j+1)) = Delta_Tau(Table(i,j),Table(i,j+1)) + Q/Length(i);
              end
              Delta_Tau(Table(i,n),Table(i,1)) = Delta_Tau(Table(i,n),Table(i,1)) + Q/Length(i);
          end
          Tau = (1-rho) * Tau + Delta_Tau;
        % 迭代次数加1,清空路径记录表
    
     %   figure;
     %最佳路径的迭代变化过程
        [Shortest_Length,index] = min(Length_best(1:iter));
        Shortest_Route = Route_best(index,:);
        plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...
        [citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-');
        pause(0.3);
     
        iter = iter + 1;
        Table = zeros(m,n);
    
     % end
    end
    
    %% 结果显示
    [Shortest_Length,index] = min(Length_best);
    Shortest_Route = Route_best(index,:);
    disp(['最短距离:' num2str(Shortest_Length)]);
    disp(['最短路径:' num2str([Shortest_Route Shortest_Route(1)])]);
    
    %% 绘图
    figure(1)
    plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...
         [citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-');
    grid on
    for i = 1:size(citys,1)
        text(citys(i,1),citys(i,2),['   ' num2str(i)]);
    end
    text(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),'       起点');
    text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),'       终点');
    xlabel('城市位置横坐标')
    ylabel('城市位置纵坐标')
    title(['蚁群算法优化路径(最短距离:' num2str(Shortest_Length) ')'])
    figure(2)
    plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:')
    legend('最短距离','平均距离')
    xlabel('迭代次数')
    ylabel('距离')
    title('各代最短距离与平均距离对比')
    
    

    3.结果显示

    1.alpha对运行结果的影响
    当alpha=1时
    m = 60; % 蚂蚁数量
    alpha = 1; % 信息素重要程度因子
    beta = 2; % 启发函数重要程度因子
    rho = 0.6; % 信息素挥发因子

    在这里插入图片描述
    当alpha=6时
    m = 60; % 蚂蚁数量
    alpha = 6; % 信息素重要程度因子
    beta = 2; % 启发函数重要程度因子
    rho = 0.6; % 信息素挥发因子
    在这里插入图片描述
    当alpha=8时
    m = 60; % 蚂蚁数量
    alpha = 8; % 信息素重要程度因子
    beta = 2; % 启发函数重要程度因子
    rho = 0.6; % 信息素挥发因子

    在这里插入图片描述
    信息素重要程度因子越大,蚂蚁选择之前走过的路径可能性就越大,搜索路径的随机性就减弱,信息素重要程度因子越小,蚁群搜索范围就会减少,容易陷入局部最优

    2.beta对运行结果的影响
    当bata=2时
    m = 60; % 蚂蚁数量
    alpha = 6; % 信息素重要程度因子
    beta = 2; % 启发函数重要程度因子
    rho = 0.6; % 信息素挥发因子
    在这里插入图片描述
    当bata=5时
    m = 60; % 蚂蚁数量
    alpha = 6; % 信息素重要程度因子
    beta = 5; % 启发函数重要程度因子
    rho = 0.6; % 信息素挥发因子
    在这里插入图片描述
    当bata=9时
    m = 60; % 蚂蚁数量
    alpha = 6; % 信息素重要程度因子
    beta = 9; % 启发函数重要程度因子
    rho = 0.6; % 信息素挥发因子
    在这里插入图片描述
    启发函数因子反映了启发式信息在指导蚁群搜索过程中的相对重要程度,其大小反映的是蚁群寻优过程中先验性和确定性因素的作用强度。过大时,虽然收敛速度会加快,但容易陷入局部最优;过小时,容易陷入随机搜索,找不到最优解。

    3.rho对运行结果的影响
    当rho=0.1时
    m = 60; % 蚂蚁数量
    alpha = 6; % 信息素重要程度因子
    beta = 2; % 启发函数重要程度因子
    rho = 0.1; % 信息素挥发因子
    在这里插入图片描述
    当rho=0.6时
    m = 60; % 蚂蚁数量
    alpha = 6; % 信息素重要程度因子
    beta = 2; % 启发函数重要程度因子
    rho = 0.6; % 信息素挥发因子
    在这里插入图片描述

    当rho=0.8时
    m = 60; % 蚂蚁数量
    alpha = 6; % 信息素重要程度因子
    beta = 2; % 启发函数重要程度因子
    rho = 0.8; % 信息素挥发因子
    在这里插入图片描述

    信息素挥发因子过小时,在各路径上的残留的信息素过多,导致无效的路径继续被搜索,影响到算法的收敛速率;信息素挥发因子过大时,无效的路径虽然可以被排除搜索,但是不能保证正确路径不会被放弃搜索,影响到最优值的搜索

    展开全文
  • 万方上被引用超过100次的论文,内容如题
  • 蚂蚁算法求解TSP旅行商问题,有详细的源代码及注释,采用面向对象设计思路
  • 提出一种求解多目标函数优化的元胞蚂蚁算法.该方法将元胞自动机演化规则引入蚂蚁算法,给出了在连续空间多目标函数优化的算法描述,定义了与蚂蚁信息素释放有关的元胞演化规则及蚂蚁邻域的转移概率,并实现了算法的具体...
  • 蚂蚁算法解决多目标TSP问题,对多目标进行深入探讨,
  • 计算机智能组卷的关键技术在于组卷算法,蚂蚁算法在初期信息素缺乏导致搜索时间较长;遗传算法需要在一组解中寻找最优解而产生大量的重复数据,导致算法效率较低。为了开发出一个具有高效性和鲁棒性的组卷算法,提出...
  • 蚂蚁算法的一个程序-AntSystem_7z.zip 蚂蚁算法的一个简单程序
  • 遗传算法和蚂蚁算法求解TSP(旅行商问题)实验报告(内含部分源代码)
  • 蚂蚁算法原理

    2015-09-15 16:29:40
    蚂蚁算法简介
  • 蚂蚁算法蚁群算法-原理-思路-步骤-程序实现

    千次阅读 多人点赞 2020-11-02 16:14:09
    蚂蚁算法蚁群算法-原理-思路-步骤-程序实现 ❀算法介绍 蚁群优化算法是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。...

    蚂蚁算法蚁群算法-原理-思路-步骤-程序实现

    ❀算法介绍

    历史

    蚁群优化算法是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。

    背景

    现实世界中,(初始状态)每个蚂蚁将在一定范围内随机游走,并通过在所经过路径上选留信息素的方式,不断把相关的食物信息反馈给蚁群。如果其他蚂蚁发现了那条路径,那么这些妈蚁很可能不再保持原来的随机游走,而跟随这条路径**(一条路径上的信息素越多,其他蚂蚁选择这条路径的可能性越大)**。如果由该路径他们最终发现了食物,那么他们将在这条路径上继续增加信息素。由于这条路径上信息素的不断增加,最终所有蚂蚁将找到食物。

    ❀算法原理

    • 蚁群算法试验中,在各个蚂蚁在没有事先告诉它们食物在什么地方的前提下开始寻找;
    • 其次,要让蚂蚁找到食物,就需要让它们遍历空间上的所有点
    • 再次,如果要让蚂蚁找到最短的路找食物。当一只找到食物以后,它会向环境释放一种信息素,吸引其他的蚂蚁过来,这样越来越多的蚂蚁会找到食物。
    • 但有些蚂蚁并没有像其它蚂蚁一样总重复同样的路,它们会另辟蹊径,**如果令开辟的道路比原来的其他道路更短,那么更多的蚂蚁被吸引到这条较短的路上来。**最后,经过一段时间运行,可能会出现一条最短的路径被大多数蚂蚁重复着。

    蚁群算法原理(该图来自Theresa Meggie et al.)

    1. 假设,dij为节点i到节点j距离,节点i、j上的信息素含量用τij(t)表示。先选定一个起始节点,将所有u个蚂蚁放在起点处,所有路径上信息素含量相同,蚂蚁k根据各条路径上信息素分布的大小选择下一个移动节点,加入禁忌表List来记录每一只蚂蚁经过节点的顺序,防止蚂蚁再次经过该节点,蚂蚁经过所有指定的节点即完成了一次算法的迭代。在蚂蚁搜索路径节点的过程中,t时刻下,蚂蚁k从节点i移动至节点j的移动概率p为:

    在这里插入图片描述

    1. 其中,allowedk表示蚂蚁k从当前节点移动到下一个所有可能经过节点的集合。依据上述内容α为信息素启发式因子,代表路径上信息素存在的多少,信息素多表示该路径通过的蚂蚁多,反之少量蚂蚁通过。β为期望启发因子,表示蚂蚁在选择该路径节点重要性的考虑,其值越大,说明移动到此点的几率越大,启发式函数ηij(t)计算方法为:

    在这里插入图片描述

    1. 由上式可以看出启发函数ηij(t)和dij对于每一只蚂蚁成反比关系,节点之间的距离越长,启发函数的值越小。当所有的蚂蚁完成一次循环后,各个城市间链接路径上的信息素浓度需进行更新。首先是信息素挥发,其次是蚂蚁在它们所经过的边上释放信息素,其中ρ为信息素挥发系数,且0<ρ≤1,计算公式为:

    在这里插入图片描述

    在这里插入图片描述

    当(i,j)在Lk上在这里插入图片描述
    =dij,当蚂蚁构建的路径长度dij越小,则路径上各条边就会获得更多的信息素,则在以后的迭代中就更有可能被其他的蚂蚁选择。每当蚂蚁完成一次循环后,便清空禁忌表,重新回到初始城市,准备下一次周游。
    除此之外还可以通过更新改进信息素规则和启发函数可以缩小全局路径和理论最优路径差值。

    ❀算法步骤

    • 1.对相关参数进行初始化,如蚁群规模(蚂蚁数量)u、信息素重要程度因子α、启发函数重要程度因子β、信息素挥发因子ρ、信息素释放总量Q、最大迭代次数itermax。

      2.构建解空间,将各个蚂蚁随机地置于不同的出发点,计算每个蚂蚁k(k=1,2,3…m)下一个待访问城市,直到所有蚂蚁访问完所有城市。

      3.更新信息苏计算每个蚂蚁经过路径长度Lk(k=1,2,…,m),记录当前迭代次数中的最优解(最短路径)。同时,对各个城市连接路径上信息素浓度进行更新。

      4.判断是否终止若iter<itermax,则令iter=iter+1,清空蚂蚁经过路径的记录表,并返回步骤2;否则,终止计算,输出最优解。

    流程图

    ❀程序实现

    def getdistmat(coordinates):
        num = coordinates.shape[0]
        distmat = np.zeros((52, 52))
        for i in range(num):
            for j in range(i, num):
                distmat[i][j] = distmat[j][i] = np.linalg.norm(coordinates[i] - coordinates[j])
        return distmat
    
    //初始化
    distmat = getdistmat(coordinates)
    numant = 45  // 蚂蚁个数
    numcity = coordinates.shape[0]  // 城市个数
    alpha = 1  // 信息素重要程度因子
    beta = 5  // 启发函数重要程度因子
    rho = 0.1  // 信息素的挥发速度
    Q = 1//信息素释放总量
    iter = 0//循环次数
    itermax = 275//循环最大值
    etatable = 1.0 / (distmat + np.diag([1e10] * numcity))  // 启发函数矩阵,表示蚂蚁从城市i转移到矩阵j的期望程度
    pheromonetable = np.ones((numcity, numcity))  // 信息素矩阵
    pathtable = np.zeros((numant, numcity)).astype(int)  // 路径记录表
    distmat = getdistmat(coordinates)  // 城市的距离矩阵
    lengthaver = np.zeros(itermax)  // 各代路径的平均长度
    lengthbest = np.zeros(itermax)  // 各代及其之前遇到的最佳路径长度
    pathbest = np.zeros((itermax, numcity))  // 各代及其之前遇到的最佳路径长度
    //核心点-循环迭代
    while iter < itermax:
        // 随机产生各个蚂蚁的起点城市
        if numant <= numcity:  // 城市数比蚂蚁数多
            pathtable[:, 0] = np.random.permutation(range(0, numcity))[:numant]
        else:  // 蚂蚁数比城市数多,需要补足
            pathtable[:numcity, 0] = np.random.permutation(range(0, numcity))[:]
            pathtable[numcity:, 0] = np.random.permutation(range(0, numcity))[:numant - numcity]
        length = np.zeros(numant)  # 计算各个蚂蚁的路径距离
        for i in range(numant):
            visiting = pathtable[i, 0]  # 当前所在的城市
            unvisited = set(range(numcity))  # 未访问的城市,以集合的形式存储{}
            unvisited.remove(visiting)  # 删除元素;利用集合的remove方法删除存储的数据内容
            for j in range(1, numcity):  # 循环numcity-1次,访问剩余的numcity-1个城市
                # 每次用轮盘法选择下一个要访问的城市
                listunvisited = list(unvisited)
                probtrans = np.zeros(len(listunvisited))
                for k in range(len(listunvisited)):
                    probtrans[k] = np.power(pheromonetable[visiting][listunvisited[k]], alpha) \
                                   * np.power(etatable[visiting][listunvisited[k]], alpha)
                cumsumprobtrans = (probtrans / sum(probtrans)).cumsum()
                cumsumprobtrans -= np.random.rand()
                k = listunvisited[(np.where(cumsumprobtrans > 0)[0])[0]]
                # 元素的提取(也就是下一轮选的城市)
                pathtable[i, j] = k  # 添加到路径表中(也就是蚂蚁走过的路径)
                unvisited.remove(k)  # 然后在为访问城市set中remove()删除掉该城市
                length[i] += distmat[visiting][k]
                visiting = k
            length[i] += distmat[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((numcity, numcity))
        for i in range(numant):
            for j in range(numcity - 1):
                changepheromonetable[pathtable[i, j]][pathtable[i, j + 1]] += Q / distmat[pathtable[i, j]][
                    pathtable[i, j + 1]]  # 计算信息素增量
            changepheromonetable[pathtable[i, j + 1]][pathtable[i, 0]] += Q / distmat[pathtable[i, j + 1]][pathtable[i, 0]]
        pheromonetable = (1 - rho) * pheromonetable + changepheromonetable  # 计算信息素公式
        iter += 1  # 迭代次数指示器+1
        print("iter(迭代次数):", iter)
    
    # 做出平均路径长度和最优路径长度
    fig, axes = plt.subplots(nrows=2, ncols=1, figsize=(12, 10))
    axes[0].plot(lengthaver, 'k', marker=u'')
    axes[0].set_title('Average Length')
    axes[0].set_xlabel(u'iteration')
    
    axes[1].plot(lengthbest, 'k', marker=u'')
    axes[1].set_title('Best Length')
    axes[1].set_xlabel(u'iteration')
    fig.savefig('average_best.png', dpi=500, bbox_inches='tight')
    plt.show()
    
    # 作出找到的最优路径图
    bestpath = pathbest[-1]
    plt.plot(coordinates[:, 0], coordinates[:, 1], 'r.', marker=u'$\cdot$')
    plt.xlim([-100, 2000])
    plt.ylim([-100, 1500])
    
    for i in range(numcity - 1):
        m = int(bestpath[i])
        n = int(bestpath[i + 1])
        plt.plot([coordinates[m][0], coordinates[n][0]], [coordinates[m][1], coordinates[n][1]], 'k')
    plt.plot([coordinates[int(bestpath[0])][0], coordinates[int(n)][0]],
             [coordinates[int(bestpath[0])][1], coordinates[int(n)][1]], 'b')
    ax = plt.gca()
    ax.set_title("Best Path")
    ax.set_xlabel('X axis')
    ax.set_ylabel('Y_axis')
    
    plt.savefig('best path.png', dpi=500, bbox_inches='tight')
    plt.show()
    
    

    在这里插入图片描述
    在这里插入图片描述

    ❀参考文献

    [1]张丽珍,何龙,吴迪,杜战其.改进型蚁群算法在路径规划中的研究[J].制造业自动化,2020,42(02):55-59.
    [2]肖艳秋,焦建强,乔东平,杜江恒,周坤.蚁群算法的基本原理及应用综述[J].轻工科技,2018,34(03):69-72.
    [3]程序算法https://blog.csdn.net/haoxun03/article/details/104209214haoxun03
    在已有程序上做了修改与补充。

    展开全文
  • 【老生谈算法】蚂蚁算法matlab代码及说明.docx
  • 蚂蚁算法解决TSP

    2015-08-04 13:05:59
    利用c语言编写的,蚂蚁算法解决TSP问题,下载后可直接运行。
  • 蚂蚁算法matlab

    千次阅读 2019-11-05 15:12:50
    蚂蚁算法解决旅行商问题 1.简介 蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 [1] 这种算法具有分布计算、信息...

    蚂蚁算法解决旅行商问题

    1.简介

    蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 [1]
    这种算法具有分布计算、信息正反馈和启发式搜索的特征,本质上是进化算法中的一种启发式全局优化算法。

    2.算法原理

    TSP求解中,假设蚁群算法中的每只蚂蚁是具有以下特征的简单智能体:每次周游,每只蚂蚁在其经过的支路(i.j)上都留下信息素。蚂蚁选择城市的概率与城市之间的距离和当前连接之路上所包含的信息素余量有关。禁忌表用来控制蚂蚁以走访过的城市。
    在这里插入图片描述

    2.1算法参数函数分析

    函数分析:

    路劲构建:作为蚂蚁访问下一个城市选择的依据
    在这里插入图片描述
    信息素更新:ρ是信息素的挥发率,Δτij是第k只蚂蚁在它经过的 边上释放的信息素量,它等于蚂蚁k本轮构建路径长度的 倒数。Ck表示路径长度,它是Rk中所有边的长度和。
    在这里插入图片描述

    参数分析:

    蚂蚁数量:蚂蚁的数量决定了信息素变化,同时数量的过多过少可能会导致找不到全局最优解。所以蚂蚁的数量一般设定为城市数量的1.5倍。
    信息素因子:信息素因子是蚂蚁在搜索中重要的向导,其值过大,蚂蚁选择以前走过的路劲概率会大大提高,搜索随机性会减少,其值过小则容易使陷入局部最优。
    启发函数因子:反映的是蚁群寻优过程中先验性和确定性因素的作用强度。过大时,虽然收敛速度会加快,但容易陷入局部最优,过小时容易陷入随机搜索,找不到最优解。
    信息挥发率:表示信息素的消失水平,它的大小直接关系刀蚁群算法的全局搜索能力和收敛速度。
    最大迭代次数:最大迭代次数过小,可能导致算法还没收敛就结束了,过大则会导致浪费资源,本文中实验次数取100次。

    3.matlab具体实现

    3.1代码截图

    %% 旅行商问题(TSP)优化
    %% 清空环境变量
    clear all
    clc
    
    %% 导入数据
    load citys_data.mat
    
    %% 计算城市间相互距离
    fprintf('Computing Distance Matrix... \n');
    n = size(citys,1);
    D = zeros(n,n);
    for i = 1:n
        for j = 1:n
            if i ~= j
                D(i,j) = sqrt(sum((citys(i,:) - citys(j,:)).^2));
            else
                D(i,j) = 1e-4;      
            end
        end    
    end
    
    %% 初始化参数
    fprintf('Initializing Parameters... \n');
    m = 50;                              % 蚂蚁数量
    alpha = 3;                           % 信息素重要程度因子
    beta = 3;                            % 启发函数重要程度因子
    rho = 0.3;                           % 信息素挥发因子
    Q = 1;                               % 常系数
    Eta = 1./D;                          % 启发函数
    Tau = ones(n,n);                     % 信息素矩阵
    Table = zeros(m,n);                  % 路径记录表
    iter = 1;                            % 迭代次数初值
    iter_max = 100;                      % 最大迭代次数 
    Route_best = zeros(iter_max,n);      % 各代最佳路径       
    Length_best = zeros(iter_max,1);     % 各代最佳路径的长度  
    Length_ave = zeros(iter_max,1);      % 各代路径的平均长度  
    
    %% 迭代寻找最佳路径
    figure;
    while iter <= iter_max
        fprintf('迭代第%d次\n',iter);
        % 随机产生各个蚂蚁的起点城市
          start = zeros(m,1);
          for i = 1:m
              temp = randperm(n);
              start(i) = temp(1);
          end
          Table(:,1) = start; 
          % 构建解空间
          citys_index = 1:n;
          % 逐个蚂蚁路径选择
          for i = 1:m
              % 逐个城市路径选择
             for j = 2:n
                 tabu = Table(i,1:(j - 1));           % 已访问的城市集合(禁忌表)
                 allow_index = ~ismember(citys_index,tabu);
                 allow = citys_index(allow_index);  % 待访问的城市集合
                 P = allow;
                 % 计算城市间转移概率
                 for k = 1:length(allow)
                     P(k) = Tau(tabu(end),allow(k))^alpha * Eta(tabu(end),allow(k))^beta;
                 end
                 P = P/sum(P);
                 % 轮盘赌法选择下一个访问城市
                 Pc = cumsum(P);     
                target_index = find(Pc >= rand); 
                target = allow(target_index(1));
                Table(i,j) = target;
             end
          end
          % 计算各个蚂蚁的路径距离
          Length = zeros(m,1);
          for i = 1:m
              Route = Table(i,:);
              for j = 1:(n - 1)
                  Length(i) = Length(i) + D(Route(j),Route(j + 1));
              end
              Length(i) = Length(i) + D(Route(n),Route(1));
          end
          % 计算最短路径距离及平均距离
          if iter == 1
              [min_Length,min_index] = min(Length);
              Length_best(iter) = min_Length;  
              Length_ave(iter) = mean(Length);
              Route_best(iter,:) = Table(min_index,:);
          else
              [min_Length,min_index] = min(Length);
              Length_best(iter) = min(Length_best(iter - 1),min_Length);
              Length_ave(iter) = mean(Length);
              if Length_best(iter) == min_Length
                  Route_best(iter,:) = Table(min_index,:);
              else
                  Route_best(iter,:) = Route_best((iter-1),:);
              end
          end
          % 更新信息素
          Delta_Tau = zeros(n,n);
          % 逐个蚂蚁计算
          for i = 1:m
              % 逐个城市计算
              for j = 1:(n - 1)
                  Delta_Tau(Table(i,j),Table(i,j+1)) = Delta_Tau(Table(i,j),Table(i,j+1)) + Q/Length(i);
              end
              Delta_Tau(Table(i,n),Table(i,1)) = Delta_Tau(Table(i,n),Table(i,1)) + Q/Length(i);
          end
          Tau = (1-rho) * Tau + Delta_Tau;
        % 迭代次数加1,清空路径记录表
    
     %   figure;
     %最佳路径的迭代变化过程
        [Shortest_Length,index] = min(Length_best(1:iter));
        Shortest_Route = Route_best(index,:);
        plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...
        [citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-');
        pause(0.3);
     
        iter = iter + 1;
        Table = zeros(m,n);
    
     % end
    end
    
    %% 结果显示
    [Shortest_Length,index] = min(Length_best);
    Shortest_Route = Route_best(index,:);
    disp(['最短距离:' num2str(Shortest_Length)]);
    disp(['最短路径:' num2str([Shortest_Route Shortest_Route(1)])]);
    
    %% 绘图
    figure(1)
    plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...
         [citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-');
    grid on
    for i = 1:size(citys,1)
        text(citys(i,1),citys(i,2),['   ' num2str(i)]);
    end
    text(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),'       起点');
    text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),'       终点');
    xlabel('城市位置横坐标')
    ylabel('城市位置纵坐标')
    title(['蚁群算法优化路径(最短距离:' num2str(Shortest_Length) ')'])
    figure(2)
    plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:')
    legend('最短距离','平均距离')
    xlabel('迭代次数')
    ylabel('距离')
    title('各代最短距离与平均距离对比')
    

    3.2结果截图及分析

    为了更好的确定信息素因子启发函数因子及挥发因子之间的关系,采取控制变量的方式得取实验结果进行一一比较,得出最优解数据确定三个因子的取值。

    确定不变的变量:

    蚂蚁数量=50,迭代次数=100次

    1 alpha=1,beta=3,rho=0.3

    在这里插入图片描述

    2 alpha=2,beta=3,rho=0.3

    在这里插入图片描述

    3 alpha=3,beta=3,rho=0.3

    在这里插入图片描述
    小结改变alpha(信息素重要程度),通过观察发现增高alpha值提高了函数的收敛速度,但陷入了局部最优不能找到函数的最优解,其原因是alpha增高了,降低了蚁群的随机搜索性,最后通过对比,发现当alpha=2使函数有了比较明显的优化,故将alpha改为2。

    4 alpha=2,beta=4,rho=0.3

    在这里插入图片描述
    小结本图修改了beta(函数启发因子)为4。所求得得最短路径随之变化,它表现的是启发式信息在指导蚁群搜索过程之中相对重要的程度,它的大小影响着蚁群在整个寻短过程中的先验性和确定性。将4图和图2进行比较,发现收敛速度无明显增加,且陷入了局部最优。故beta不修改。

    5 alpha=2,beta=3,rho=0.4

    在这里插入图片描述
    小结本阶段将修改rho(信息素挥发度)来找到最优rho,本图5与图2进行比较,收敛速度明显加快,但依旧陷入局部最优。故不做修改,继续修改rho值实验。

    6 alpha=2,beta=3,rho=0.5

    在这里插入图片描述
    小结本图6与图2相比依旧为局部最优故增加rho只能降低蚁群的搜索不确定性,故增大rho不做讨论。

    7 alpha=2,beta=3,rho=0.2

    在这里插入图片描述
    小结本图7与图2比较收敛速度明显下降,且任然为局部最优。故rho最优值确立为3。

    3.3总结:

    本实验通过比较得出alpha=2,beta=3,rho=3为最优,除此之外得出了rho的大小直接影响了蚁群算法的全局搜索能力和收敛速度。各个参数实际上都直接或间接得影响着蚁群的搜索能力及收敛速度。同时蚁群算法的优点也显而易见。在解决最短路径长度这一块,蚁群能很快得得出几十几百甚至成千上万个城市之间得旅行商问题。在实际生活中生产中,蚁群算法还可以解决其他一些问题,通过改良版的蚁群优化算法有更高效的执行效率,例如光网络的智能化管理,计算机网络路由,聚类问题等等。

    展开全文
  • 论文研究-基于双层蚂蚁算法的半导体炉管制程批调度研究.pdf,
  • 在将几何约束问题的约束方程组转化为优化模型的时候,引入一种利用元胞演化规律和蚂蚁寻优特点的离散元胞蚂蚁算法.离散元胞蚂蚁算法是一种新型的仿生算法,它利用元胞在离散元胞空间的演化规律和蚂蚁寻优的特点,为解决...
  • 针对煤炭监测数据的复杂多变性及Deep Web数据查询结果网页描述信息的特点,提出了一种基于蚂蚁算法和本体指导网页信息抽取的方法。首先构建基于简单本体的数据抽取系统,通过对结果页面中包含本体语义信息的数据的映像...
  • 改进的蚂蚁算法车辆运行调度算法研究.pdf
  • 资源名:车辆路径问题_矩阵蚂蚁算法_VRP_精确解_全局最优解_matlab源码 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者更换...
  • 人工智能的作业,简单的蚂蚁算法,大一作业,轻喷
  • 大数据-算法-改进蚂蚁算法在VRPDP问题的应用研究.pdf
  • 大数据-算法-基于新型蚂蚁算法的QoSR理论及技术研究.pdf
  • 蚂蚁算法用于求解任务分配...文中介绍了任务分配问题和蚂蚁算法,给出了求解任务分配问题的蚂蚁算法的数学描述及求解的算法步骤,在此基础上提出求解任务分配问题的改进蚂蚁算法。两个实例验证了改进蚂蚁算法的优越性。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 26,806
精华内容 10,722
关键字:

蚂蚁算法