资源描述:
《蚁群算法解决TSP问题.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、蚁群算法解决TSP问题一、论述1、算法来源蚁群算法的基本原理来源于自然界蚂蚁觅食的最短路径原理,根据昆虫学家的观察,发现自然界的蚂蚁虽然视觉不发达,但它可以在没有任何提示的情况下找到从食物源到巢穴的最短路径,并且能在环境发生变化(如原有路径上有了障碍物)后,自适应地搜索新的最佳路径。2、单个蚂蚁寻找路径正反馈:单个的蚂蚁为了避免自己迷路,它在爬行时,同时也会释放一种特殊的分泌物——信息素(Pheromone),而且它也能觉察到一定范围内的其它蚂蚁所分泌的信息素,并由此影响它自己的行为。当一条路上的信
2、息素越来越多(当然,随着时间的推移会逐渐减弱),后来的蚂蚁选择这条路径的概率也就越来越大,从而进一步增加了该路径的信息素浓度,这种选择过程称为蚂蚁的自催化过程。多样性:同时为了保证蚂蚁在觅食的时候不至走进死胡同而无限循环,蚂蚁在寻找路径的过程中,需要有一定的随机性,虽然在觅食的过程中会根据信息素的浓度去觅食,但是有时候也有判断不准,环境影响等其他很多种情况,还有最终要的一点就是当前信息素浓度大的路径并不一定是最短的路径,需要不断的去修正,多样性保证了系统的创新能力。正是这两点小心翼翼的巧妙结合才使得
3、蚁群的智能行为涌现出来。3、具体实现需要解决的两个首要问题(1)如何实现单个蚂蚁寻路的过程(2)如何实现信息素浓度的更新二、具体实现代码如下所示:[cpp]viewplaincopy在CODE上查看代码片派生到我的代码片#include#include#include#include#include#include#include#includeus
4、ingnamespacestd;/*intCityPos[10][2]={{87,7},{91,38},{83,46},{71,44},{64,60},{68,58},{83,69},{87,76},{74,78},{71,71}};//10个城市的坐标*/unsignedseed=(unsigned)time(0);//原型:voidsrand(unsignedseed);//30个城市的坐标intCityPos[30][2]={{87,7},{91,38},{83,46},{71,44},{64
5、,60},{68,58},{83,69},{87,76},{74,78},{71,71},{58,69},{54,62},{51,67},{37,84},{41,94},{2,99},{7,64},{22,60},{25,62},{18,54},{4,50},{13,40},{18,40},{24,42},{25,38},{41,26},{45,21},{44,35},{58,35},{62,32}};#defineCITY_NUM30//城市数量#defineANT_NUM30//蚁群数量#def
6、ineTMAC1000//迭代最大次数#defineROU0.5//误差大小#defineALPHA1//信息素重要程度的参数#defineBETA4//启发式因子重要程度的参数#defineQ100//信息素残留参数constintmaxn=100;doubledis[maxn][maxn];//距离doubleinfo[maxn][maxn];//信息素矩阵doubleE[CITY_NUM][CITY_NUM];//启发因子矩阵intvis[CITY_NUM][CITY_NUM];doubleB
7、estlength;doubleans[CITY_NUM];constdoublemmax=10e9;//返回指定范围内的随机整数intrnd(intnLow,intnUpper){returnnLow+(nUpper-nLow)*rand()/(RAND_MAX+1);}//返回指定范围内的随机浮点数doublernd(doubledbLow,doubledbUpper){doubledbTemp=rand()/((double)RAND_MAX+1.0);returndbLow+dbTemp*(
8、dbUpper-dbLow);}//返回浮点数四舍五入取整后的浮点数doubleROUND(doubledbA){return(double)((int)(dbA+0.5));}structAnt{intPath[CITY_NUM];//蚂蚁走的路径doublelength;//路径总长度intvis[CITY_NUM];//走过城市标记intcur_cityno;//当前城市intmoved_cnt;//已走的数量//初始化voidInit(){memset(vis