基于蚁群算法解决旅行商问题

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 <iostream>#include <math.h> #include <time.h> using namespace

10、std; const int N_ANT_COUNT = 34; /蚂蚁数量，一般取值原则为：城市数量 / 蚂蚁数量 = 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 bestto

11、urN_CITY_COUNT;/最佳路径列表 /获得指定范围内的一个随机数 double rnd(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; /临时保存信息

12、素，更新环境信息素的时候使用，每只蚂蚁周游完各个城市后开始计算 double m_dTrialN_CITY_COUNTN_CITY_COUNT; /城市间的信息素，就是环境信息素 double distanceN_CITY_COUNTN_CITY_COUNT; /城市间距离 ; GInfo Map; /定义蚂蚁类 class ant private: int ChooseNextCity(); /选择下一个城市 double probN_CITY_COUNT; /临时变量数组，选择下一个城市的时候，保存各个城市被选中的概率值 int m_nCityCount; /记录蚂蚁已经走过的城市数目 i

13、nt AllowedCityN_CITY_COUNT;/没有走过的城市，数组索引对应城市编号 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

14、 ant:move2last() for(int i=0;i<N_CITY_COUNT;i+) if (AllowedCityi=1) addcity(i); break; /清空数据，蚂蚁周游完各个城市后，要重新开始周游各个城市时调用 void ant:Clear() m_dLength=0; for(int i=0; i<N_CITY_COUNT;i+) probi=0; AllowedCityi=1; i=tabuN_CITY_COUNT-1; /用最后一个城市作为出发城市 m_nCityCount=0; addcity(i); /初始化 ant:ant() m_dLengt

15、h=m_dShortest=0; m_nCityCount=0; for(int i=0;i<N_CITY_COUNT;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

16、 j=10000; double temp=0.0; int curCity=tabum_nCityCount-1; /当前走到那个城市了 /先计算当前城市和没有走过的城市，两两之间的信息素的总和 for (int i=0;i<N_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;i<N_CITY_COUNT;

17、i+) if (AllowedCityi = 1) probi=pow(1.0/Map.distancecurCityi),DB_BETA)*pow(Map.m_dTrialcurCityi),DB_ALPHA)/temp; sel+=probi; else probi=0; /下面的操作实际上就是遗传算法中的轮盘选择 double mRate=rnd(0,sel); double mSelect=0; for ( i=0;i<N_CITY_COUNT;i+) if (AllowedCityi = 1) mSelect+=probi ; if (mSelect>=mRate) j=

18、i; break; /这种情况只有在temp=0.0的时候才会出现 if (j = 10000) for (i=0;i<N_CITY_COUNT;i+) if (AllowedCityi = 1) j=i; break; return j; /计算周游完城市后，走过的路径长度 void ant:UpdateResult() / 修正旅行距离for(int i=0;i<N_CITY_COUNT-1;i+) m_dLength+=Map.distancetabuitabui+1; m_dLength+=Map.distancetabuN_CITY_COUNT-1tabu0; /最后城市

19、和开始城市间的距离 /移动到下一个城市 void ant:move() /the ant move to next town and add town ID to tabu. int n=ChooseNextCity(); addcity(n); class project public: double m_dLength; ant antsN_ANT_COUNT; public: project(); void UpdateTrial(); void initmap(); void GetAnt(); void StartSearch(); ;/更新环境信息素 /这里采用的是 ANT-CYC

20、LE 模式，即每只蚂蚁周游完城市后才更新 void project:UpdateTrial() /calculate the changes of trial information int m=0; int n=0; for(int i=0;i<N_ANT_COUNT;i+) /计算每只蚂蚁在两两城市间留下的信息素，蚂蚁走过的路径越短，留下的信息素数值越大 for (int j=0;j<N_CITY_COUNT-1;j+) /计算两两城市间的信息素 m=antsi.tabuj; n =antsi.tabuj+1; Map.m_dDeltTrialmn+=DB_Q/antsi.m_

21、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.m_dDeltTrialnm+=DB_Q/antsi.m_dLength; /最新的环境信息素 = 消失掉的信息素 + 新留下的信息素 for (int a=0;a<N_CITY_COUNT;a+) for (int j=0;j<N_CITY_COUNT;j+) Map.m

22、_dTrialaj=(DB_ROU*Map.m_dTrialaj+Map.m_dDeltTrialaj ); Map.m_dDeltTrialaj=0; /初始化 void project:initmap() for(int i=0;i<N_CITY_COUNT;i+) for (int j=0;j<N_CITY_COUNT;j+) Map.m_dTrialij=1; Map.m_dDeltTrialij=0; project:project() /initial map initmap(); m_dLength=10e9; struct city int num; int x;

23、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,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,5

24、7,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;i<N_CITY_COUNT;i+) cci.x=x_Aryi; cci.y=y_Aryi; cci.num=i; /计算两两城市间距离，需要进行四舍五入取整 /eil51.tsp的最短路径426，是按四舍五入取整后的距离算出来的。 for(int b=0;b<N_CITY_COUNT;b+) for (int j=0;j<N_CITY_COUNT;j+) Map.dist

25、ancebj=(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;i<N_ANT_COUNT;i+) city=rnd(N_CITY_COUNT); antsi.addcity(city); void project:StartSearch() /begin to find best solution int max=0;/eve

26、ry 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;j<N_ANT_COUNT;j+) for (int i=0;i<N_CITY_COUNT-1;i+) antsj.move(); for(int c=0;c<N_ANT_COUNT;c+) antsc.move2last(); antsc.UpdateResult(); /计算路径

27、总长度 /find out the best solution of the step and put it into temp temp=ants0.m_dLength; for (int t=0;t<N_CITY_COUNT;t+) temptourt=ants0.tabut; for(int d=0;d<N_ANT_COUNT;d+) if (temp>antsd.m_dLength) temp=antsd.m_dLength; for (int t=0;t<N_CITY_COUNT;t+) temptourt=antsd.tabut; if (dbMin>

28、antsj.m_dLength) dbMin=antsj.m_dLength; if (temp<m_dLength) m_dLength=temp; for (int t=0;t<N_CITY_COUNT;t+) besttourt=temptourt; printf("%d : %.0fn",max,m_dLength); UpdateTrial(); /全部蚂蚁遍历各个城市后，更新环境信息素 for(int e=0;e<N_ANT_COUNT;e+) /再搜索一次 antse.Clear(); max+; printf("The short

29、est toure is : %fn",m_dLength); for (int t=0;t<N_CITY_COUNT;t+) printf(" %d ",besttourt); void shucout()cout<<"*本程序是利用蚁群算法求解TSP问题，即最旅游城市中的最段距离和行走路线*"<<endl<<endl<<endl<<endl<<endl<<endl<<endl;cout<<"51个城市X轴坐标为：&qu

30、ot;<<endl;cout<<"37,49,52,20,40,21,17,31,52,51, "<<endl;cout<<"42,31,5,12,36,52,27,17,13,57, "<<endl;cout<<"62,42,16,8,7,27,30,43,58,58, "<<endl;cout<<"37,38,46,61,62,63,32,45,59,5,"<<endl;cout<<"10,21,5,30,39,32,25,25,48,56, "<<endl;cout<<"30 "<<endl;cout<<"城市Y轴坐标为："<<endl;cout<<"52,49,64,26,30,47,63,62,33,21"<<endl;cout<<"41,32,