日本汽车后视镜项目欲寻找合作伙伴落户中国

​蚁群算法基本步骤、原理、应用(附​蚁群算法流程图)

2018-07-12 16:41:54     来源: 贤集网

蚁群算法最早是由Marco Dorigo等人在1991年提出,他们在研究新型算法的过程中,发现蚁群在寻找食物时,通过分泌一种称为信息素的生物激素交流觅食信息从而能快速的找到目标,据此提出了基于信息正反馈原理的蚁群算法。下面随贤集网小编一起来了解下蚁群算法基本步骤、原理、应用(附蚁群算法流程图)。


蚁群算法的原理


蚁群算法的基本思想来源于自然界蚂蚁觅食的最短路径原理,根据昆虫科学家的观察,发现自然界的蚂蚁虽然视觉不发达,但它们可以在没有任何提示的情况下找到从食物源到巢穴的最短路径,并在周围环境发生变化后,自适应地搜索新的最佳路径。


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


蚁群算法


τij(t)表示在t时刻(i,j)边上的信息素浓度;ρ是在变化范围在[0,1]之间的常数系数,表示信息的持久度;


Q为预先设定的常量,该常量表示信息素的浓度,其取值会影响算法收敛的速度和正反馈的能力。Lk表示第k只蚂蚁在本次迭代中所走过各路径的总花费。


蚂蚁选择路径(i,j)的概率。


蚁群算法基本步骤


这里以TSP问题为例,算法设计的流程如下:


步骤1:对相关参数进行初始化,包括蚁群规模、信息素因子、启发函数因子、信息素挥发因子、信息素常数、最大迭代次数等,以及将数据读入程序,并进行预处理:比如将城市的坐标信息转换为城市间的距离矩阵。


步骤2:随机将蚂蚁放于不同出发点,对每个蚂蚁计算其下个访问城市,直到有蚂蚁访问完所有城市。


步骤3:计算各蚂蚁经过的路径长度Lk,记录当前迭代次数最优解,同时对路径上的信息素浓度进行更新。


步骤4:判断是否达到最大迭代次数,若否,返回步骤2;是,结束程序。


步骤5:输出结果,并根据需要输出寻优过程中的相关指标,如运行时间、收敛迭代次数等。


蚁群算法的关键参数


由于蚁群算法涉及到的参数蛮多的,且这些参数的选择对程序又都有一定的影响,所以选择合适的参数组合很重要。蚁群算法有个特点就是在寻优的过程中,带有一定的随机性,这种随机性主要体现在出发点的选择上。蚁群算法正是通过这个初始点的选择将全局寻优慢慢转化为局部寻优的。参数设定的关键就在于在“全局”和“局部”之间建立一个平衡点。


参数设定


在蚁群算法的发展中,关键参数的设定有一定的准则,一般来讲遵循以下几条:


1.尽可能在全局上搜索最优解,保证解的最优性;


2.算法尽快收敛,以节省寻优时间;


3.尽量反应客观存在的规律,以保证这类仿生算法的真实性。


关键参数


蚁群算法中主要有下面几个参数需要设定:


蚂蚁数量:


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


信息素因子:


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


启发函数因子:


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


信息素挥发因子:


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


信息素常数:


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


最大迭代次数:


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


蚁群算法的实际应用(案例)


蚁群算法解答旅行商问题


商旅问题(Traveling Salesman Problem,TSP),即一个商人要经过n个城市,形成一个闭环,怎么走路程最少?这就是商旅问题。

​蚁群算法基本步骤、原理、应用(附​蚁群算法流程图)

​蚁群算法基本步骤、原理、应用(附​蚁群算法流程图)

​蚁群算法基本步骤、原理、应用(附​蚁群算法流程图)

如图,我放置了10只蚂蚁,迭代次数为500次。而对于很复杂的、计算量很大的问题,各种系数的设定尤为重要。这里问题较为简单,不做讨论。


蚁群算法在水资源最优分配上的应用



在蚁群算法中,决策空间是以包含节点(决策变量)和边(变量的取值)的图的形式呈现。水资源的一种分配方案即为图中一系列边组成的路径。全局更优的分配路径上会留存更多的信息素,从而在之后的迭代中更易被选中。随着迭代次数的增加,算法可以逐渐收敛于更好的分配方案。本文以水资源在作物灌溉上的分配进一步说明了模型的运用方法,问题的决策树如下图所示(Nic为季节i时的作物数,Wk为给某种作物的供水量,Nw为供水方案总数):

​蚁群算法基本步骤、原理、应用(附​蚁群算法流程图)


在每个决策点需要确定的选择包括在某块土地上季节i种植何种作物(Ci,j)以及需要分配多少水量给该作物(Wk)。若某种作物种植时间为1年,则后续季节不再进行决策。问题的约束条件包括可用的土地面积以及可资利用的水资源量。在每一节点,蚂蚁选择某一条边(A点到B点)的概率由下式决定:

​蚁群算法基本步骤、原理、应用(附​蚁群算法流程图)

式中,t表示迭代的次数,τAB表示此时该路径上的信息素浓度,ηAB代表蚂蚁对该条路径的能见度,反映对决策空间的认识。NA为以A点为起点的边的数目,α和β分别表征信息素和能见度的重要程度。其中,信息素的计算公式如下:

​蚁群算法基本步骤、原理、应用(附​蚁群算法流程图)

可以看出,第t+1次搜索时,路径AB上信息素的浓度的一部分继承自上一次迭代(ρ为滞留系数),另一部分增量是用于鼓励每一次迭代的最优解和全局最优解,同时算法还规定了信息素浓度的上下限,以避免陷入搜索的停滞。而能见度概念的引入是为了保证选择经济效益最高的作物和最大的水资源分配方案。所以能见度实际上是决策点处对作物收益或者水资源分配方案最大预期的度量。蚁群在信息素和能见度的指导下,不断积累对搜索空间的知识,在满足迭代终止条件后(通常是达到一定的迭代次数),可认为获得近似全局最优解。


在案例研究中,作者关注了能见度概念对结果的影响。文章计算了有无能见度指导下,30次试验(每次搜索的起点都是随机的)的目标平均值(Objective Function OF)。结果如下表所示:

​蚁群算法基本步骤、原理、应用(附​蚁群算法流程图)


上表呈现了引入能见度(ACO-SDVO-VF)与否的结果,原假设是利用了能见度的算法其目标函数平均值不显著好于不利用能见度的算法。表中的数值代表在100%水资源供应量下,两种算法的目标(收益)平均值和相同最佳值的偏差。可以看出引入能见度可以明显提升解的质量和收敛速度。在不同水资源供应量下,仍有类似结论。




利用蚁群算法来解决水资源分配的优化问题,该方法也可以推广到给水管网和雨水管网的设计优化上。与常用的遗传算法相比,蚁群算法的优点在于它可以充分利用历次搜索积累的知识来逼近最优解,尤其是当搜索空间较大时,蚁群算法可以极大地提升计算效率,而这一点却是遗传算法很难实现的。此处还引入了能见度的概念,案例研究表明能见度可以提高算法的收敛速度和解的质量。针对的虽然是单目标优化问题,但是该算法经过适当改造后,可用于求解多目标优化问题。但是目前针对蚁群算法在复杂高维多目标优化问题上的研究仍不多,算法还有待进一步完善。


附蚁群算法流程图

​蚁群算法基本步骤、原理、应用(附​蚁群算法流程图)

以上就是关于蚁群算法基本步骤、原理、应用的知识介绍,蚁群算法根据模拟蚂蚁寻找食物的最短路径行为来设计的仿生算法,因此一般而言,蚁群算法用来解决最短路径问题,并真的在旅行商问题(TSP,一个寻找最短路径的问题)上取得了比较好的成效。目前,也已渐渐应用到其他领域中去,在图着色问题、车辆调度问题、集成电路设计、通讯网络、数据聚类分析等方面都有所应用。

我来说几句

* 获取验证码
最新评论

还没有人评论哦,抢沙发吧~

为您推荐

木林森将合并Forest Lighting和朗德万斯
木林森将合并Forest Lighting和朗德万斯
11月20日 16:56   木林森
中国电信在深圳已开通31个5G站点
中国电信在深圳已开通31个5G站点
11月20日 15:33   中国电信
传三星Galaxy Note 10将配备迄今最大屏幕6.66英寸
传三星Galaxy Note 10将配备迄今最大屏幕6.66英寸
11月20日 15:30   三星  Galaxy Note 10
全球首个铁路智能信号灯系统