2022年2022年基本蚁群算法代码C .pdf
基本蚁群算法代码C 版/Basic Ant Colony Algorithm for TSP#include#include#include#include#include#include#include#define N 31/city size#define M 31/ant number double inittao=1;/初始信息量的多少double taoNN;/每条路径上的信息量double detataoNN;/，代表相应路径上的信息素增量double distanceNN;/城市距离矩阵double yitaNN;/启发函数，其值yitaij=1/distanceij int tabuMN;/禁忌表，tabuij=1表示蚂蚁 i 已经走过了j 城市?int routeMN;/保存蚂蚁 k 的路径的数组为routekN double solutionM;int BestRouteN;double BestSolution=10000000000;double alfa,beta,rou,Q;/Pijk(t)表示 t 时刻蚂蚁k 由城市 i 转移到城市j 的状态转移概率，/alfa 是信息启发式因子，表示轨迹的相对重要性，反映蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间的协作性越强/beta 是期望启发式因子，表示能见度的相对重要性，反映在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越大，则该状态转移概率越接近于贪心规则/rou 是信息残留因子(与书上不同，书上用rou 表示信息挥发系数，而用1-rou 表示信息残留因子)/Q 为信息素强度，用于计算蚂蚁留在路径上的信息量int NcMax;/迭代次数void initparameter(void);/initialize the parameters of basic ACA double EvalueSolution(int*a);/evaluate the solution of TSP,and calculate the length of path void InCityXY(double x,double y,char*infile);/input the nodes coordinates of TSP void initparameter(void)alfa=1;beta=5;rou=0.9;Q=100;NcMax=200;/最大迭代次数 void main(void)名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 6 页 -int NC=0;initparameter();double xN;double yN;InCityXY(x,y,city31.tsp);/初始化距离矩阵for(int i=0;iN;i+)for(int j=i+1;jN;j+)distanceji=sqrt(xi-xj)*(xi-xj)+(yi-yj)*(yi-yj);distanceij=distanceji;/calculate the heuristic parameters:计算启发式因子for(i=0;iN;i+)for(int j=0;jN;j+)taoij=inittao;if(j!=i)/yitaij=100/distanceij;/the dividend should be 1 here yitaij=1/distanceij;for(int k=0;kM;k+)for(i=0;iN;i+)routeki=-1;srand(time(NULL);for(k=0;kM;k+)routek0=k%N;/设置初始城市tabukroutek0=1;/设置初始城市被访问标记/each ant try to find the optimal path do int s=1;double partsum;double pper;double drand;/ant choose one whole path while(sN)/开始计算第k 只蚂蚁的路径for(k=0;kM;k+)名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 6 页 -int jrand=rand()%3000;/生成一个 0 到 3000 之间的随机数.drand=jrand/3001.0;/哇这里可以加个.让 3000 变成 doube!partsum=0;pper=0;/转移概率/根据概率函数计算蚂蚁的转移概率for(int j=0;jN;j+)if(tabukj=0)partsum+=pow(taorouteks-1j,alfa)*pow(yitarouteks-1j,beta);/routeks-1 表示蚂蚁 k 第 s-1 步走到的城市，s=1 表示蚂蚁从初始城市出发/taorouteks-1j表示蚂蚁 k 经过的前一个城市到下一个没被访问的城市j 的信息量 for(j=0;jdrand)/当 drand 落在第 j 个城市上时，选择j 城市break;tabukj=1;/禁忌表置访问标志routeks=j;/保存蚂蚁 k 的第 s 步经过的城市 s+;/在 N 次循环后，所有蚂蚁的禁忌表都已填满/计算每个蚂蚁走过的路径的长度，并找到最短路径保存，记录此路径并更改信息素。/the pheromone is updated for(i=0;iN;i+)for(int j=0;jN;j+)detataoij=0;/计算每个蚂蚁经过路径的长度，保存到当前代为止最好的解路径及其长度for(k=0;kM;k+)solutionk=EvalueSolution(routek);/蚂蚁 k 经过的路线的总长度if(solutionkBestSolution)BestSolution=solutionk;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 6 页 -for(s=0;sN;s+)BestRoutes=routeks;/计算各个路径上的信息素增量for(k=0;kM;k+)for(s=0;sN-1;s+)detataorouteksrouteks+1+=Q/solutionk;detataoroutekN-1routek0+=Q/solutionk;/更新路径上的信息素for(i=0;iN;i+)for(int j=0;jN;j+)taoij=rou*taoij+detataoij;if(taoij20)/信息素上界，避免94 行和 101 行中，启发信息被路径信息淹没taoij=20;/将蚂蚁的路径再重新置空,为下一次循环做准备,要不然每个蚂蚁的路径都已经满了,则没有办法进行下一次迭代了.for(k=0;kM;k+)for(int j=1;jN;j+)/注意起始城市，即j=0 没有被清空 tabukroutekj=0;routekj=-1;NC+;while(NCNcMax);/output the calculating results fstream result;result.open(optimal_results.log,ios:app);if(!result)coutcant open the file!n;exit(0);result*-*endl;resultthe initialized parameters of ACA are as follows:endl;名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 6 页 -resultalfa=alfa,beta=beta,rou=rou,Q=Qendl;resultthe maximum iteration number of ACA is:NcMaxendl;resultthe shortest length of the path is:BestSolutionendl;resultthe best route is:endl;for(i=0;iN;i+)resultBestRoutei;resultendl;result*-*endlendl;result.close();coutthe shortest length of the path is:BestSolutionendl;double EvalueSolution(int*a)double dist=0;for(int i=0;iN-1;i+)dist+=distanceaiai+1;dist+=distanceaia0;return dist;void InCityXY(double x,double y,char*infile)fstream inxyfile(infile,ios:in|ios:nocreate);if(!inxyfile)coutcant open the infile file!n;exit(0);int i=0;while(!inxyfile.eof()inxyfilexiyi;if(+i=N)break;/*31 个城市坐标：1304 2312 3639 1315 4177 2244 3712 1399 名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 6 页 -3488 1535 3326 1556 3238 1229 4196 1004 4312 790 4386 570 3007 1970 2562 1756 2788 1491 2381 1676 1332 695 3715 1678 3918 2179 4061 2370 3780 2212 3676 2578 4029 2838 4263 2931 3429 1908 3507 2367 3394 2643 3439 3201 2935 3240 3140 3550 2545 2357 2778 2826 2370 2975 运行后可得到15602 的巡游路径*/名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 6 页 -
