基于蚁群算法的TSP问题求解
来源:用户上传
作者: 曹桂文
摘要:群集智能是现今人工智能领域研究的一个新的热点课题,本文介绍了蚁群算法的原理及求解TSP问题的具体实现步骤。
Abstract: Cluster intelligence is now artificial intelligence field of study a hot topic. this article describes the fundamental principles of the tsp problem and solution of the realization of steps.
关键词:群集智能 蚁群算法 TSP问题
Key words: swarm intelligence ant colony optimization aco Tsp problem
作者简介:1:曹桂文,女(1967-1)商丘市人,本科,商丘职业技术学院讲师,研究方向:主要从事基础数学教学研究。
2:张英,女(1968-12)商丘市人,本科,商丘职业技术学院讲师,研究方向:主要从事基础数学教学研究。
一、蚁群算法原量
经过研究发现,蚂蚁在觅食的过程中通过一种称之为信息素(pheromone)的物质相互传递信息。更具体一点就是:蚂蚁在运动过程中能够在其所经过的路径上留下信息素,而且在运动过程中能够感受到这种信息素的存在及其强度,并以此指导自己的运动方向。蚂蚁顷向于朝着信息素浓度高的方向前进,因此,由大量蚂蚁组成的蚁群的行为便表现出一种信息的正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。蚁群就是通过个体之间这种信息交换机来彼此协作达到搜索食物的目的。
设有甲、乙两只蚂蚁从蚁穴A出发,分别沿AC和ABC路径同时在C处发现食物,又同时沿原路返回(假设二者的速度一样),同时在路上留下信息素,信息素随着向四周散发其浓度会不断下降。因AC路径较短,故当蚂蚁甲返回蚁穴A时,AC上留下两次信息素,而乙蚂蚁则因为ABC路径较长,此时才到达D点,则AD路径上只留下一次信息素。故该段上信息素的浓度比AC路径上的低。而蚂蚁总是顷向于信息素浓度比较高的路径(AC),这条路径就是蚁穴A与食物C之间的最短路径。
蚁群通过信息交换与互相协作找到从蚁穴到食物源的最短路径的机制显然可以被借鉴来求解各种与最优路径机关的组合优化问题,Colorni和Dorigo等人在研究该问题的基础之上提出了一类模拟自然界蚁群觅食行为的模拟进化算法――蚁群算法(ant colony algorithm)。
而蚁群算法优化过程的本质在于:(1)选择机制。信息量越大的路径,被选择的概率越大;(2)更新机制。路径上面的信息量会随蚂蚁的经过而增长,同时也随着时间的推移逐渐减小;(3)协调机制。蚂蚁之间实际上是通过信息量来互相通信、协同工作的。这样的机制使得蚁群算法具有很强的发现较好解的能力。
二、蚁群算法实现步骤
TSP问题是指:给定n个城市和两两城市之间的距离,要求确定一条长度最短的Hanilton回路,即遍历所有城市当且仅当一次的最短回路。
2.1符号说明
为讨论问题的方便,作如下说明:
1,2,……,n分别表示城市编号;m是蚁群中蚂蚁的数量;dij(i,j=1,2, ……,n)表示城市i和j之间的距离;bi(t)表示在t时刻位于城市的蚂蚁数量(ηij(t)表示在t时刻所能提供的某种启发式信息,表示由城市i转移到城市j的期望程度。例如,可以取表示在t时刻蚁群在城市i和j连线上放置的信息素含量,以此来模拟实际蚂蚁分泌的信息素。初始时假设各种路径上的信息素恒等(为一预设常数);表示在t时刻蚂蚁k由城市i转移到城市j的概率。
2.1.1转移概率
蚁群中的第K只蚂蚁由城市i转移到城市j的概率为:
其中,allowedk=(1,2…,n)\tabuk表示蚂蚁k下一步允许走过的城市的集合,而tabuk是蚂蚁k到目前为止已走过的城市;α,β为参数,α表示路径上的信息量对蚂蚁选择路径所起的作用大小,当α=0时,算法就是传统的贪心算法;β表示ηij(t)的作用,而当β=0时,就成了纯粹的正反馈的启发式算法。
2.1.2信息素的调整
每一只蚂蚁都按照概率(1)来决定它的位置转移,当蚂蚁完成一次循环(即产生一个闭合路径),各路径上的信息素含量将依据一定的规则调整,随着时间的推移,以前留下的信息会逐渐消失,整个蚁群完成一组循环后,各路径上的信息素依下式调整;
其中,Q为常数,Lk为蚂蚁k在本次循环中所走路径的总长。
2.2蚁群算法步骤
2.2.1初始化
指定蚁群规模m,父代种群规模n;输入初始信息素及启发式信息ηij(0);随机生成初始蚁群A(0)=(A1(0),A2(0),……,Am(0));置t=0;
2.2.2选择操作
从A(t)中按照目标函数值选择出n只蚂蚁组成第t代蚁群B(t)=(Ai1(t),Ai2(t), ……,Ain(t))
2.2.3重组
(1)按公式③、④设置信息素增量。
(2)按公式②调整信息素含量。
(3)依适当方式获得启发式信息ηij(t+1)。
(4)独立、重复地以概率①随机产生蚂蚁Ak(t+1)(k=1,2,……,m),由此组成第t+1代蚁群,A(t+1)=(A1(t+1),A2(t+1), ……, Am(t+1)
2.2.4终止检验
如解已达到精度要求,或已达到预设进化时限,则停止,输出A(t+1)中最好的个体为所求问题的近似解;否则,令t=t+1转步骤2.2.3。
三、总结
以上讨论了基于蚁群算法的TSP问题的求解,实际上该算法能够很容易地修改以用于求解任意新发展组合优化问题,同时也可求解一般的函数优化问题。
当然,蚁群算法也有一些缺陷。例如,由于蚁群中多个个体的运动是随机的,当群体规模较大时,要找出一条较好的路径需要较长的搜索时间。另外,蚁群算法当进化到一定代数后就容易因为较优解的信息素含量不断强化使得蚂蚁大量聚集于较少的几条路径上,从而出现早熟、停滞现象,使得到的最优解只是局部最优的。这些还需进行更深入的研究。
参考文献:
[1]徐宗本.计算智能(第一册)模拟进化计算[M].高等教育出版社.2004.02
[2]李志伟.基于群集智能的蚁群优化算法研究[J].计算机工程与设计.2003.8
[3]孙新宇等.基于蚂蚁算法的工作排序优化[J].系统工程理论与实践.2003.11
[4]汪镭等.蚁群算法在连续空间寻优问题求解中的应用[J].控制与决策.2003.
转载注明来源:https://www.xzbu.com/1/view-290638.htm
