资源描述：
《用改进的人工鱼群算法求解tsp问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、用改进的人工鱼群算法求解TSP问题第24卷第2期石家庄铁道大学(自然科学版)v.i.24N..22011年06月JOURNALOFSHIJIAZHUANGTIEDAOUNIVERSITY(NATURALSCIENCE)Jn.2011用改进的人工鱼群算法求解TSP问题李跃松,樊金生,张巧迪(石家庄铁道大学信息科学与技术学院,河北石家庄050043)摘要:针对人工鱼群算法在寻优过程中存在的不足,结合嗅觉在自然界鱼类捕食过程中的重要作用,在基本人工鱼群算法的基础上,提出了具有嗅觉特征的人工鱼群算法.最后,利用改进的人工鱼群
2、算法成功解决了旅行商问题,并且通过比较基本人工鱼群算法与改进人工鱼群算法的实验结果,得出结论,改进后的人L鱼群算法在算法搜索时间,全局最优值精确度方面都有了显着的提高.关键词:组合优化问题;人工鱼群算法;嗅觉;旅行商问题中图分类号:FP393文献标识码:A文章编号:2095—0373(2011)02—0103—08组合优化问题…涉及经济管理,交通运输,通信网络等领域,主要是寻找离散事件的最优编排,分组,次序或者筛选等,是运筹学中的一个经典而重要的分支.典型的组合优化问题有旅行商问题(TravelingSalesman
3、Problem,TSP),加工调度问题(schedulingproblem),0-1背包问题(knapsackproblem),装箱问题(binpackingproblem),图着色问题(graphcoloringproblem),聚类问题(clusteringproblem)等.1旅行商问题在组合优化问题中,最具代表性的是旅行商问题(TravelingSalesmanProblem,TSP).TSP是运筹学中一个非常着名的命题,其命题描述为:城市个数/'t个,每两个城市之间的距离d已知.某旅行商从某个城市出发,经过
4、若干个城市有且仅有一次,最后返回起始城市.试图寻找一条闭合路径,要求该路径长度最短.2人工鱼群算法着名学者李晓磊在2003年提出了一种新型的智能优化算法——人工鱼群算法(ArtificialFishSwarmAlgorithm,AFSA)].人工鱼群算法的提出为组合优化问题的解决提供了一条全新的解决思路.2.1人工鱼群算法描述AFSA是一种基于模拟自然界中鱼群行为的并行搜索算法.AFSA的基本思想是模拟自然界鱼群的觅食行为,聚群行为和追尾行为,从构造单条人工鱼的底层行为做起,通过鱼群中各个人工鱼个体的局部寻优,达到全
5、局最优值在群体中突现出来的目的.'2.2一些定义人工鱼个体的状态可表示为向量X=(.,:,…,),其中,(i=1,…,/7,)为欲寻优的变量,人工鱼当前所在位置的食物浓度表示为Y=X),其中,l,为目标函数值;人工鱼个体之间的距离表示为d=『lX—;Visual表示人工鱼视野的感知距离;Step表示人工鱼移动的最大步长;为拥挤度因子.2.3行为描述2.3.1觅食行为设人工鱼的当前状态为,在其感知范围内随机选择一个状态x,,在求极大值问题中,当<(因收稿日期:2010—12—25作者简介:李跃松男1983年出生硕
6、士研究生104石家庄铁道大学(自然科学版)第24卷为极大值和极小值问题可以相互转换,因此,以下均为求极大问题讨论)时,则向该方向前进一步;反之,再重新随机选择状态,判断是否满足前进条件;这样反复尝试try—llllIllber次后,如果仍不满足前进条件,则随机移动一步.2.3.2聚群行为设人工鱼的当前状态为x,探索当前邻域内(即d<Visua1)的伙伴数目及中心位置,如果L/n,>6,表明伙伴中心有较多的食物并且不太拥挤,则朝伙伴的中心位置方向前进一步;否则,执行觅食行为.2.3.3追尾行为设人工鱼的当前
7、状态为置,探索当前邻域内(dtf<Visua1)的伙伴,如果/>6,表明伙伴的状态具有较高的食物浓度并且其周围不太拥挤,则朝伙伴的方向前进一步;否则,执行觅食行为.2.3.4随机行为随机行为即在人工鱼视野中随机选择一个状态,然后向该方向移动.随机行为是觅食行为的一个缺省行为.2.3.5公告板公告板主要用于记录寻优过程中最优人工鱼个体的状态.2.3.6人工鱼群算法的特点人工鱼群算法采用了自下而上的设计思路,从人工鱼(ArtificialFish,AF)的个体行为出发,达到了全局最优值的突现,为组合优化问题提
8、供了一条新的解决思路.由此,可以得出人工鱼群算法的特点:(1)并行性:多条人工鱼(ArtificialFish,AF)个体并行进行搜索;(2)简单性:算法只使用目标函数值;(3)全局性:算法具有良好的跳出局部极值的能力;(4)快速性:算法中虽然有一定的随机因素,但总体是在步步向最优化搜索;(5)跟踪性:能够快速跟踪变化的极值点.但是,人工鱼群算
