资源描述：
《一种改进的并行蚁群优化求解算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第23卷第1期甘肃联合大学学报(自然科学版)Vol.23No.12009年1月JournalofGansuLianheUniversity(NaturalSciences)Jan.2009文章编号:1672691X(2009)01006705一种改进的并行蚁群优化求解算法雷筱珍,赖万钦(福建交通职业技术学院,福建福州350007)摘要:为了提高并行蚁群优化算法的求解性能,对ACO算法进行了改进.针对有明显聚类特征的大规模TSP问题,充分利用问题本身所具有的特征,提出了一种带聚类处理的蚁群算法,该算法比较ACS算法可以
2、在更短的时间内找到相同质量的解,而且在相同的运行时间内,该改进算法总能找到最好的解.在VC++环境下进行仿真实验,求解了TSP库中的实例pr136、pr107,分别得到了其最短距离,结果表明了编程思路的正确性及高效性.关键词:蚁群算法;并行优化改进;TSP;VC++6.0实现中图分类号:TP39文献标识码:A0引言1基本蚁群算法的描述[1]20世纪90年代初,意大利学者DorigoM1.1蚁群算法的提出[8~9]等人提出了一种新型的模拟进化算法蚁群算蚁群算法是意大利学者DorigoM等于法(AntColonyAlg
3、orithm,ACA),并将该算法应20世纪90年代初受自然界中真实蚁群算法的集用于著名的旅行商问题(TravelingSalesman体有觅食行为的启发而首先提出的一种基于群体Problem,TSP),获得了较好的实验结果,但同时的新型的随机搜索模拟进化算法蚂蚁系统也发现该算法存在收敛速度慢、易出现停滞现象(AntSystem,间称AS).蚂蚁在外出觅食时,个[2]等缺陷.针对该算法的不足,许多学者提出了改体之间通过一种称为信息素(Pheromone)的物质[3~5]进的蚁群算法,从一定程度上提高了算法的进行信息传递,蚂蚁在
4、运动过程中,能够在经过的收敛速度,消除了算法中的停滞现象.但是由于该路径上留下这种物质,并能感知这种物质,并依此3算法的时间复杂度为O(Nn),n为问题规模,N来指导自己的运动方向.大量蚂蚁组成的蚁群的[2]为算法迭代次数)较高,很难用于求解大规模的集体行为便体现为一种信息的正反馈现象即:某TSP问题(包括其它组合优化问题).本文针对有一路径上走过的蚂蚁越多,留下的信息就越多,后明显聚类特征的大规模TSP问题,充分利用问题者选择该路径的可能性就越大.本身所具有的特征,提出了一种带聚类处理的蚁1.2基本蚁群算法在TSP问题中的应用群
5、算法,该算法首先根据TSP问题中城市的分布蚂蚁系统(AS)算法是第一个蚁群算法的模[6]特征用模糊c均值法进行聚类处理聚成c个型,被称为基本蚁群算法.类.如果将类i(i=1,2,,c)本身看成是一座超要说明基本蚂蚁系统的模型,首先引入TSP级城市i,则由这c个超级城市(类)构成的TSP问题.问题的解即为所有i个类的连接顺序,然后找出一般地来说,旅行商问题(TravelingSales各类的临界城市(指在类i有且仅有的两座分别manProblem,间称TSP问题)可以描述如下:与另外两个不同的类相连的城市),再对类i(i=设C={
6、c1,c2,,cn}为n个城市的集合,L=[7]1,2,,c)采用AS算法并行求解,获得每个类{lij
7、ci,cj!C}是C中元素两两连接的集合,G=中及从一类到另外两个类之间的最短路径,最后(C,L)是一个图,已知各城市之间的距离,TSP问将所有类的最短路径按顺序连接起来,则构成了题的求解目的是从G中找出长度最短的Hamil待求解问题的一个可行解.tonian圈,即找出对C={c1,c2,,cn}中n个城收稿日期:20081020.作者简介:雷筱珍(1970),女,甘肃天水人,福建交通职业技术学院讲师,主要从事数据库新技术
8、,数据挖掘研究.68甘肃联合大学学报(自然科学版)第23卷市访问且只访问一次的最短的一条封闭曲线.=C(C为常数),即各路径上的信息量相等,将信于是AS算法可以描述如:将m只人工蚂蚁息素增量置0,禁忌表初始为空,将各蚂蚁的初始k随机的放在n座城市,每只人工蚂蚁的行为符合城市置于当前禁忌表中.以概率Pij(t)选择城市下列规律:依据概率选择下一个将要访问的城市,j,将蚂蚁k移动到城市j,并将刚选择到的城市j这个概率是两城市间距离及连接两个城市的边上加入到禁忌表中,当禁忌表
9、满时(即走完了所有城的信息量的函数;在完成一次循环之前,不允许蚂市),更新刚走过的每条边的信息量值,然后开始蚁选择已经访问过的城市,该过程由一个数据结新一轮循环,记录到目前为止的最短路径,直到所构禁忌表来控制;完成一次循环后,蚂
