蚁群算法解决TSP问题.doc

蚁群算法解决TSP问题 一、论述 1、算法来源 蚁群算法的基本原理来源于自然界蚂蚁觅食的最短路径原理，根据昆虫学家的观察，发现自然界的蚂蚁虽然视觉不发达，但它可以在没有任何提示的情况下找到从食物源到巢穴的最短路径，并且能在环境发生变化（如原有路径上有了障碍物）后，自适应地有哪些信誉好的足球投注网站新的最佳路径。 2、单个蚂蚁寻找路径 正反馈： 单个的蚂蚁为了避免自己迷路，它在爬行时，同时也会释放一种特殊的分泌物——信息素（Pheromone），而且它也能觉察到一定范围内的其它蚂蚁所分泌的信息素，并由此影响它自己的行为。当一条路上的信息素越来越多（当然，随着时间的推移会逐渐减弱），后来的蚂蚁选择这条路径的概率也就越来越大，从而进一步增加了该路径的信息素浓度，这种选择过程称为蚂蚁的自催化过程。 多样性： 同时为了保证蚂蚁在觅食的时候不至走进死胡同而无限循环，蚂蚁在寻找路径的过程中，需要有一定的随机性，虽然在觅食的过程中会根据信息素的浓度去觅食，但是有时候也有判断不准，环境影响等其他很多种情况，还有最终要的一点就是当前信息素浓度大的路径并不一定是最短的路径，需要不断的去修正，多样性保证了系统的创新能力。 正是这两点小心翼翼的巧妙结合才使得蚁群的智能行为涌现出来。 3、具体实现需要解决的两个首要问题 （1）如何实现单个蚂蚁寻路的过程 （2）如何实现信息素浓度的更新 二、具体实现 代码如下所示： [cpp] view plain copy 在CODE上查看代码片派生到我的代码片 #include iostream #include algorithm #include cstring #include windows.h #include stdio.h #include stdlib.h #include math.h #include time.h using namespace std; /* int CityPos[10][2]= {{87,7},{91,38},{83,46},{71,44},{64,60},{68,58},{83,69}, {87,76},{74,78},{71,71} }; //10个城市的坐标*/ unsigned seed=(unsigned)time(0);//原型：void srand(unsigned seed); //30个城市的坐标 int CityPos[30][2]={{87,7},{91,38},{83,46},{71,44},{64,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}}; #define CITY_NUM 30 //城市数量 #define ANT_NUM 30 //蚁群数量 #define TMAC 1000 //迭代最大次数 #define ROU 0.5 //误差大小 #define ALPHA 1 // 信息素重要程度的参数 #define BETA 4 // 启发式因子重要程度的参数 #define Q 100 //信息素残留参数 const int maxn = 100; double dis[maxn][maxn]; //距离 double info[maxn][maxn]; //信息素矩阵 double E[CITY_NUM][CITY_NUM]; //启发因子矩阵 int vis[CITY_NUM][CITY_NUM]; double Bestlength; double ans[CITY_NUM]; const double mmax = 10e9; //返回指定范围内的随机整数 int rnd(int nLow,int nUpper) { return nLow+(nUpper-nLow)*rand()/(RAND_MAX+1); } //返回指定范围内的随机浮点数 double rnd(double dbLow,double dbUpper) { double dbTemp=rand()/((double)RAND_MAX+1.0); return dbL