一、概念
蚁群系统(Ant System(AS)或Ant Colony System(ACS))是由意大利学者Dorigo、Maniezzo等人于20世纪90年代首先提出来的。他们在研究蚂蚁觅食的过程中，发现蚁群整体会体现一些智能的行为，例如蚁群可以在不同的环境下，寻找最短到达食物源的路径。
后经进一步研究发现，这是因为蚂蚁会在其经过的路径上释放一种可以称之为“信息素(pheromone)”的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会沿着“信息素”浓度较高路径行走，而每只路过的蚂蚁都会在路上留下“信息素”，这就形成一种类似正反馈的机制，这样经过一段时间后，某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。整个蚁群就会沿着最短路径到达食物源了。
这种算法具有分布计算、信息正反馈和启发式搜索的特征，本质上是进化算法中的一种启发式全局优化算法。
蚁群算法是一种用来寻找优化路径的概率型算法。 讯享网
二、应用
求解TSP问题
TSP问题：已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路。
讯享网路径的选择目标是要求得的路径路程为所有路径之中的最小值。
蚁群算法原理
蚂蚁在路径上释放信息素,当蚂蚁碰到还没走过的路口，就随机挑选一条路走，同时，释放与路径长度有关的信息素，信息素的浓度与路径长度成反比。后来的蚂蚁再次碰到该路口时，蚂蚁在选择下一个要转移的城市时候是基于概率选择的，选择信息素浓度较高路径，最优路径上的信息素浓度越来越高，最终蚁群找到最优寻食路径。
蚁群算法与TSP问题
原理：
将m个蚂蚁随机地放在多个城市，让这些蚂蚁从所在的城市出发，n步（一个蚂蚁从一个城市到另外一个城市为1步）之后返回到出发的城市。如果m个蚂蚁所走出的m条路经对应的中最短者不是TSP问题的最短路程，则重复这一过程，直至寻找到满意的TSP问题的最短路径为止。
路径构建
m:蚂蚁总数，在TSP问题中，每次循环当中，每只蚂蚁所走出的每条路径为TSP问题的候选解，m只蚂蚁一次循环所走出来的m条路经为TSP问题的一个解子集，所以这个解子集越大则算法的全局搜索能力越强，但是过大会使算法的收敛速度降低。如果m太小的话，算法也很容易就陷入局部最优，过早的出现停滞现象。
alpha：信息素重要程度因子，反映了蚂蚁在从城市i向城市j移动时，这两个城市之间道路上所累积的信息素在指导蚂蚁选择城市j的程度，即蚁群在路径搜素中随即性因素作用的强度。alpha值越大，蚂蚁选择之前走过的路径的可能性越大，搜索路径的随机性减弱，alpha越小，蚁群搜索范围就会减小，容易陷入局解最优。
beta：启发函数重要程度因子，beta值越大，蚁群就越容易选择局部较短路径，这时算法的收敛速度是加快了，但是随机性却不高，容易得到局部的相对最优。
tabu：禁忌表，用于存放第k只蚂蚁已经走过的城市。
rho：是信息素挥发因子，规定0≤ rho≤1，1- rho为信息残留因子，rho过小时，在各路径上残留的信息素过多，导致无效的路径继续被搜索，影响到算法的收敛速率，rho过大，无效的路径虽然可以被排除搜索，但是不能保证有效的路径也会被放弃搜索，影响到最优值的搜索，在AS中通常设置为 rho =0.5。
三、实验过程
（1）随机产生50个的城市坐标信息
round(rand(50,2)*4000)+1000 产生的数据
讯享网 2204 2888 1708 2879 3366 2135 1245 1009 3163 1774 4837 3657 1179 2747 3539 1523 4774 2251 1037 3795 2045 3202 2440 4955 1256 2874 1733 4631 1425 4783 2315 2293 2763 4099 2028 3990 4507 4693 1493 4696 3813 4099 3445 2484 4609
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/16296.html