《基于蚁群算法解决旅行商问题.doc》由会员分享，可在线阅读，更多相关《基于蚁群算法解决旅行商问题.doc（29页珍藏版）》请在三一办公上搜索。
1、学 号： 能力拓展训练题 目基于蚁群算法解决tsp问题学 院计算机科学与技术学院专 业班 级姓 名指导教师20112012学年 第2学期目录一.介绍- 2 -二 详细设计说明- 3 -2.1模块描述- 3 -2.2性能- 3 -2.3算法- 3 -2.4流程逻辑-7-2.5接口- 8 -三 程序- 9 -四.结果- 20 -五.程序设计心得与体会- 21 -六.参考文献- 22 -基于蚁群算法解决tsp问题摘 要：TSP问题是典型的NP - hard组合优化问题,蚁群算法是一种求解此类问题的优化算法,通过模拟蚂蚁觅食行为来解决NP问题。文章使用蚁群算法求解TSP问题,并结合TSP问题的特点选择
2、了一种合适的蚁群更新策略。关键词：TSP问题,蚁群算法,群集智能,信息素一、介绍 旅行商问题( Traveling Salesman Problem, 简称TSP)是一个经典的NP难题,也是组合优化中研究最多的问题之一,它解决如何找到一条从一个城市出发经过若干个城市后又返回原城市的最短路径。城市管道铺设优化、物流业的车辆调度、制造业中的切割路径优化等,现实生活中的优化问题都可以归结为TSP问题进行求解。寻找一种有效的解决该问题的算法,具有重要的现实意义。蚁群算法是DorigoM等提出的,该算法采用了分布式并行计算机制,易于与其他方法结合,而且具有强的鲁棒性,是求解TSP问题的一种理想方法。算法
3、的主要思想为:模拟蚂蚁觅食行为。蚂蚁在运行过程中会释放一种特殊的分泌物- 信息素来寻找路径。信息素会随着时间消减,后面的蚂蚁选择信息素多的路径,这样便形成了一个正反馈机制。在整个寻径过程中,虽然单只蚂蚁的选择能力有限,但它们的行为具有非常高的自组织性,相互之间交换路径,最终寻找到最优路径。二、详细设计说明2.1模块描述本程序共有void addcity(); void Clear(); void UpdateResult(); void move(); void move2last(); void shucout()；void project:initmap()；void project:Ge
4、tAnt()；void project:StartSearch() ；void project:UpdateTrial() 。子程序模块和int main()一个主程序。void shucout()显示欢迎信息模块 void ant:move2last() 只剩下一个城市没走过时才调用，直接移动到最后一个城市void ant:Clear() 清空数据，蚂蚁周游完各个城市后，要重新开始周游各个城市时调用 void ant:addcity(int city) 增加一个城市到走过的城市数组中，并改变没走过的城市数组中的标志 void ant:UpdateResult() 计算周游完城市后，走过的路径
5、长度 void ant:move() 移动到下一个城市 void project:initmap() 初始化 void project:GetAnt() 初始化随机种子 void project:StartSearch() 开始寻找最好的解决方法void project:UpdateTrial() 更新环境信息素 ，每只蚂蚁周游完城市后才更新 2.2性能本程序按原理来说迭代次数越大，程序得出的结果越精确，但当数值超过1000以后，结果基本不变。要求城市数量 / 蚂蚁数量 = 1.5左右 dbMin=100000000.0; 叠迭中的最小路径长度。2.3算法本程序是基于蚁群算法求解问题，设为城市
6、，之间的几何距离，。设 表示时刻位于城市的蚂蚁的个数，蚂蚁总数，表示时刻在 连线上残留的信息量，初始时刻各条路径上的信息量为（为常数）。用参数表示信息量的保留度，则经过个时刻后，路径 上的信息量根据下式作调整： 表示第只蚂蚁在本次循环中留在路径 上的信息量，表示本次循环所有经过的蚂蚁留在 上的信息量。 定义。蚂蚁（，）在运动过程中，表示在时刻蚂蚁由位置转移到位置的概率： 我们用tabuN_CITY_COUNT记录蚂蚁目前已经走过的城市集合，AllowedCityN_CITY_COUNT表示蚂蚁下一步允许选择的城市集合，它等于全部的城市集合除去第只蚂蚁已走过的集合tabuN_CITY_COUNT
7、。 定义为第只蚂蚁在本次循环中走过的路径和。 用蚁群算法解决问题是一个递推过程 ，当时，将蚂蚁放在各城市，设定每条路径上的信息量初值，每只蚂蚁根据公式决定的概率从城市到城市。表示曾经有多少蚂蚁经过路径；说明较近的城市有更大的可能性被选中。用来控制两者对蚂蚁选择的影响力程度。经过一个循环后，根据公式；计算更新每条路径的信息量。将所有的复原，最后求出本次循环的最短路径。这个过程不断重复，直到所有的蚂蚁都选择同样的路径，或者循环次数达到预先设定的最高次数。解决个城市的问题算法设计如下：初始化：设定，循环计数器，对每条路径设定初始信息量,将只蚂蚁放在个城市上（为了使问题简化，设定。设定集合的索引，对从
8、到，把第只蚂蚁放在起始位置，对应的设定集合重复下面的步骤，直到集合满为止（这一步将重复次）：设定；对从到，根据公式确定的概率，选择下一步移动的目标城市在时间时，第只蚂蚁所在的城市是;将第只蚂蚁移到城市；把加入到集合中。对从到：将第只蚂蚁从移动到；计算第只蚂蚁所走过的路程和，并更新最小路径；对每条路径：； 对每条路径根据计算；设定；设定；对每条路径，设定。如果，则清空所有的集合转到第二步；否则，得出最短的路径。在这儿我们用的是算法，这种算法，每当结束一个循环后，根据公式 计算。2.4流程逻辑开始初始化设定集合,对每只蚂蚁=计算蚂蚁所走过的路程和更新最小路径对每条路径计算设定acbacbNY清空所
9、有的集合得出最短路径N集合满Y结束图12.5接口程序中的子函数：void addcity(int city); void Clear(); void UpdateResult(); void move(); void move2last(); void shucout();void UpdateTrial(); void initmap(); void GetAnt(); void StartSearch(); 三程序#include #include #include using namespace std; const int N_ANT_COUNT = 34; /蚂蚁数量，一般取值原则为
10、：城市数量 / 蚂蚁数量 = 1.5左右 const int N_CITY_COUNT = 51; /城市数量 int N_IT_COUNT; /= 5000; /迭代次数，就是搜索次数 const double DB_Q=100; /总的信息素 const double DB_ALPHA=1; /信息素重要程度 const double DB_BETA=3; /这个数越大，则蚂蚁往信息素大的地方走的概率就越大 const double DB_ROU=0.5; /环境信息素挥发速度 int besttourN_CITY_COUNT;/最佳路径列表 /获得指定范围内的一个随机数 double r
11、nd(int low,double uper) double p=(rand()/(double)RAND_MAX)*(uper)-(low)+(low); return (p); ; /获得指定上限范围内的一个随机数 int rnd(int uper) return (rand()%uper); ; /tsp地图信息，包含了信息素，城市距离，和信息素变化矩阵 class GInfo public: double m_dDeltTrialN_CITY_COUNTN_CITY_COUNT; /临时保存信息素，更新环境信息素的时候使用，每只蚂蚁周游完各个城市后开始计算 double m_dTria
12、lN_CITY_COUNTN_CITY_COUNT; /城市间的信息素，就是环境信息素 double distanceN_CITY_COUNTN_CITY_COUNT; /城市间距离 ; GInfo Map; /定义蚂蚁类 class ant private: int ChooseNextCity(); /选择下一个城市 double probN_CITY_COUNT; /临时变量数组，选择下一个城市的时候，保存各个城市被选中的概率值 int m_nCityCount; /记录蚂蚁已经走过的城市数目 int AllowedCityN_CITY_COUNT;/没有走过的城市，数组索引对应城市编号
13、 public: double m_dLength; double m_dShortest; int tabuN_CITY_COUNT; /记录走过的城市，里面存的是城市的编号，数组索引表示走的顺序。 public: ant(); void addcity(int city); void Clear(); void UpdateResult(); void move(); void move2last(); void shucout(); /只剩下一个城市没走过时才调用，直接移动到最后一个城市 void ant:move2last() for(int i=0;iN_CITY_COUNT;i+)
14、 if (AllowedCityi=1) addcity(i); break; /清空数据，蚂蚁周游完各个城市后，要重新开始周游各个城市时调用 void ant:Clear() m_dLength=0; for(int i=0; iN_CITY_COUNT;i+) probi=0; AllowedCityi=1; i=tabuN_CITY_COUNT-1; /用最后一个城市作为出发城市 m_nCityCount=0; addcity(i); /初始化 ant:ant() m_dLength=m_dShortest=0; m_nCityCount=0; for(int i=0;iN_CITY_C
15、OUNT;i+) AllowedCityi=1; probi=0; /增加一个城市到走过的城市数组中，并改变没走过的城市数组中的标志 void ant:addcity(int city) /add city to tabu; tabum_nCityCount=city; m_nCityCount+; AllowedCitycity=0; int ant:ChooseNextCity() /更新概率的路径选择 /选择一条路径,从 tabum_nCityCount-1到下一个 int j=10000; double temp=0.0; int curCity=tabum_nCityCount-1;
16、 /当前走到那个城市了 /先计算当前城市和没有走过的城市，两两之间的信息素的总和 for (int i=0;iN_CITY_COUNT;i+) if (AllowedCityi = 1) temp=temp+pow(1.0/Map.distancecurCityi),DB_BETA)*pow(Map.m_dTrialcurCityi),DB_ALPHA); /计算没有走过的城市被选中的概率 double sel=0; for (i=0;iN_CITY_COUNT;i+) if (AllowedCityi = 1) probi=pow(1.0/Map.distancecurCityi),DB_B
17、ETA)*pow(Map.m_dTrialcurCityi),DB_ALPHA)/temp; sel+=probi; else probi=0; /下面的操作实际上就是遗传算法中的轮盘选择 double mRate=rnd(0,sel); double mSelect=0; for ( i=0;i=mRate) j=i; break; /这种情况只有在temp=0.0的时候才会出现 if (j = 10000) for (i=0;iN_CITY_COUNT;i+) if (AllowedCityi = 1) j=i; break; return j; /计算周游完城市后，走过的路径长度 voi
18、d ant:UpdateResult() / 修正旅行距离for(int i=0;iN_CITY_COUNT-1;i+) m_dLength+=Map.distancetabuitabui+1; m_dLength+=Map.distancetabuN_CITY_COUNT-1tabu0; /最后城市和开始城市间的距离 /移动到下一个城市 void ant:move() /the ant move to next town and add town ID to tabu. int n=ChooseNextCity(); addcity(n); class project public: dou
19、ble m_dLength; ant antsN_ANT_COUNT; public: project(); void UpdateTrial(); void initmap(); void GetAnt(); void StartSearch(); ;/更新环境信息素 /这里采用的是 ANT-CYCLE 模式，即每只蚂蚁周游完城市后才更新 void project:UpdateTrial() /calculate the changes of trial information int m=0; int n=0; for(int i=0;iN_ANT_COUNT;i+) /计算每只蚂蚁在两两
20、城市间留下的信息素，蚂蚁走过的路径越短，留下的信息素数值越大 for (int j=0;jN_CITY_COUNT-1;j+) /计算两两城市间的信息素 m=antsi.tabuj; n =antsi.tabuj+1; Map.m_dDeltTrialmn+=DB_Q/antsi.m_dLength; Map.m_dDeltTrialnm+=DB_Q/antsi.m_dLength; /最后城市到开始城市间的信息素 m=antsi.tabuN_CITY_COUNT-1; n =antsi.tabu0; Map.m_dDeltTrialmn+=DB_Q/antsi.m_dLength; Map.
21、m_dDeltTrialnm+=DB_Q/antsi.m_dLength; /最新的环境信息素 = 消失掉的信息素 + 新留下的信息素 for (int a=0;aN_CITY_COUNT;a+) for (int j=0;jN_CITY_COUNT;j+) Map.m_dTrialaj=(DB_ROU*Map.m_dTrialaj+Map.m_dDeltTrialaj ); Map.m_dDeltTrialaj=0; /初始化 void project:initmap() for(int i=0;iN_CITY_COUNT;i+) for (int j=0;jN_CITY_COUNT;j+)
22、 Map.m_dTrialij=1; Map.m_dDeltTrialij=0; project:project() /initial map initmap(); m_dLength=10e9; struct city int num; int x; int y; ccN_CITY_COUNT; /城市坐标数据来自国际通用的数据 eil51.tsp int x_Ary51= 37,49,52,20,40,21,17,31,52,51, 42,31,5,12,36,52,27,17,13,57, 62,42,16,8,7,27,30,43,58,58, 37,38,46,61,62,63,32
23、,45,59,5, 10,21,5,30,39,32,25,25,48,56, 30 ; int y_Ary51= 52,49,64,26,30,47,63,62,33,21, 41,32,25,42,16,41,23,33,13,58, 42,57,57,52,38,68,48,67,48,27, 69,46,10,33,63,69,22,35,15,6, 17,10,64,15,10,39,32,55,28,37, 40 ; for (int i=0;iN_CITY_COUNT;i+) cci.x=x_Aryi; cci.y=y_Aryi; cci.num=i; /计算两两城市间距离，需要
24、进行四舍五入取整 /eil51.tsp的最短路径426，是按四舍五入取整后的距离算出来的。 for(int b=0;bN_CITY_COUNT;b+) for (int j=0;jN_CITY_COUNT;j+) Map.distancebj=(int)(sqrt(pow(ccb.x-ccj.x),2)+pow(ccb.y-ccj.y),2)+0.5); void project:GetAnt() /初始化随机种子 srand(unsigned)time(NULL); /为每只蚂蚁随机分配一个出发城市 int city=0; for (int i=0;iN_ANT_COUNT;i+) city
25、=rnd(N_CITY_COUNT); antsi.addcity(city); void project:StartSearch() /begin to find best solution int max=0;/every ant tours times double temp; int temptourN_CITY_COUNT; double dbMin=0.0; while (max N_IT_COUNT) dbMin=100000000.0; /本次叠迭中的最小路径长度 for(int j=0;jN_ANT_COUNT;j+) for (int i=0;iN_CITY_COUNT-1
26、;i+) antsj.move(); for(int c=0;cN_ANT_COUNT;c+) antsc.move2last(); antsc.UpdateResult(); /计算路径总长度 /find out the best solution of the step and put it into temp temp=ants0.m_dLength; for (int t=0;tN_CITY_COUNT;t+) temptourt=ants0.tabut; for(int d=0;dantsd.m_dLength) temp=antsd.m_dLength; for (int t=0;
27、tantsj.m_dLength) dbMin=antsj.m_dLength; if (tempm_dLength) m_dLength=temp; for (int t=0;tN_CITY_COUNT;t+) besttourt=temptourt; printf(%d : %.0fn,max,m_dLength); UpdateTrial(); /全部蚂蚁遍历各个城市后，更新环境信息素 for(int e=0;eN_ANT_COUNT;e+) /再搜索一次 antse.Clear(); max+; printf(The shortest toure is : %fn,m_dLength)
28、; for (int t=0;tN_CITY_COUNT;t+) printf( %d ,besttourt); void shucout()cout*本程序是利用蚁群算法求解TSP问题，即最旅游城市中的最段距离和行走路线*endlendlendlendlendlendlendl;cout51个城市X轴坐标为：endl;cout37,49,52,20,40,21,17,31,52,51, endl;cout42,31,5,12,36,52,27,17,13,57, endl;cout62,42,16,8,7,27,30,43,58,58, endl;cout37,38,46,61,62,63,
29、32,45,59,5,endl;cout10,21,5,30,39,32,25,25,48,56, endl;cout30 endl;cout城市Y轴坐标为：endl;cout52,49,64,26,30,47,63,62,33,21endl;cout41,32,25,42,16,41,23,33,13,58endl;cout42,57,57,52,38,68,48,67,48,27endl;cout69,46,10,33,63,69,22,35,15,6endl;cout17,10,64,15,10,39,32,55,28,37endl;cout40endl;cout请输入迭代次数，就是搜索
30、次数(次数越大越准确最好在20006000）N_IT_COUNT;/主程序入口 int main() shucout();project TSP; TSP.GetAnt(); TSP.StartSearch(); getchar(); return 0; 四结果五心得体会通过对蚁群算法程序设计，不仅让我巩固了知识而且还让我了解了关于蚁群算法的很多知识，着对于我来说，是不小的收获，以前根本就不知道蚁群算法，现在有了基本的了解，感觉自己收获不少。经过这次设计我体会颇多，我加强了对程序设计这门课程的认识，并且复习了自己以前学习到的知识，自己的逻辑思考能力也提高不少。这些都使得我对计算机语言的学习有了
31、更深入的认识！总之，通过这次课程设计，我收获颇丰，相信会为自己以后的学习和工作带来很大的好处。最重要的还是激发了我编程和对算法的兴趣和热情，让我从一个只懂理论变成了能做一些小型程序。整体地评价这次课程设计，我认为收获很大，正如上面所说的那样，通过课程设计，既复习了以前的旧知识，又学到了一些新的知识。像应用程序的设计和创建，经历了平时在课堂和考试中不会出现的难题和考验。而这些问题，又都是课本上很少提到的、更深一层的实践与知识相结合的问题，这并不是我们平时只靠课本，就可以轻易解决的。所以，锻炼了我们面对难题，学会用已掌握的知识去解决具体问题的能力，进一步培养了独立思考问题和解决问题的能力。六参考文献 谭浩强著 程序设计.北京：清华大学出版社；1999谭浩强著 程序设计题解与上机指导.北京：清华大学出版社；1999 马良朱刚宁爱兵著蚁群优化算法；2008蚁群算法贴吧。
