aco.rar_ACO_TSP ACO_c aco tsp_visual c

＃include <iostream> ＃include <fstream> ＃include <math.h> ＃include <time.h> using namespace std; const int iAntCount=34; //ant numbers const int iCityCount=51; const int iItCount=2000; //最大迭代次数 const double Q=100; const double alpha=1; const double beta=5; const double rou=0.5; int besttour[iCityCount]; //最优路径列表 double rnd(int low,double uper) //获得随机数 { double p=(rand()/(double)RAND_MAX)*((uper)-(low))+(low); return (p); }; int rnd(int uper) { return (rand()%uper); }; class GInfo //TSP地图信息，包含信息素，城市距离和信息素变化矩阵 { public: double m_dDeltTrial[iCityCount][iCityCount]; double m_dTrial[iCityCount][iCityCount]; double distance[iCityCount][iCityCount]; }; GInfo Map; class ant { private: int ChooseNextCity(); //选择城市 double prob[iCityCount]; int m_iCityCount; int AllowedCity[iCityCount]; //没有走过的城市 public: void addcity(int city); int tabu[iCityCount]; void Clear(); void UpdateResult(); double m_dLength; double m_dShortest; void move(); ant(); void move2last(); }; void ant::move2last() { int i; for(i=0;i<iCityCount;i++) if (AllowedCity[i]==1) { addcity(i); break; } } void ant::Clear() { m_dLength=0; int i; for(i=0;i<iCityCount;i++) { prob[i]=0; AllowedCity[i]=1; } i=tabu[iCityCount-1]; m_iCityCount=0; addcity(i); } ant::ant() { m_dLength=m_dShortest=0; m_iCityCount=0; int i; for(i=0;i<iCityCount;i++) { AllowedCity[i]=1; prob[i]=0; } } void ant::addcity(int city) //add city to tabu; { tabu[m_iCityCount]=city; m_iCityCount++; AllowedCity[city]=0; } int ant::ChooseNextCity() { //Update the probability of path selection //select a path from tabu[m_iCityCount-1] to next int i; int j=10000; double temp=0; int curCity=tabu[m_iCityCount-1]; for (i=0;i<iCityCount;i++) { if((AllowedCity[i]==1)) { temp+=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha); } } double sel=0; for (i=0;i<iCityCount;i++) { if((AllowedCity[i]==1)) { prob[i]=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha)/temp; sel+=prob[i]; } else prob[i]=0; } double mRate=rnd(0,sel); double mSelect=0; for ( i=0;i<iCityCount;i++) { if((AllowedCity[i]==1)) mSelect+=prob[i] ; if (mSelect>=mRate) {j=i;break;} } if (j==10000) { temp=-1; for (i=0;i<iCityCount;i++) { if((AllowedCity[i]==1)) if (temp<pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha)) { temp=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha); j=i; } } } return j; } void ant::UpdateResult() // Update the length of tour { int i; for(i=0;i<iCityCount-1;i++) m_dLength+=Map.distance[tabu[i]][tabu[i+1]]; m_dLength+=Map.distance[tabu[iCityCount-1]][tabu[0]]; } void ant::move() //the ant move to next town and add town ID to tabu { int j; j=ChooseNextCity(); addcity(j); } class project { public: void UpdateTrial(); double m_dLength; void initmap(); ant ants[iAntCount]; void GetAnt(); void StartSearch(); project(); }; void project::UpdateTrial() //calculate the changes of trial information { int i; int j; for(i=0;i<iAntCount;i++) { for (j=0;j<iCityCount-1;j++) { Map.m_dDeltTrial[ants[i].tabu[j]][ants[i].tabu[j+1]]+=Q/ants[i].m_dLength ; Map.m_dDeltTrial[ants[i].tabu[j+1]][ants[i].tabu[j]]+=Q/ants[i].m_dLength; } Map.m_dDeltTrial[ants[i].tabu[iCityCount-1]][ants[i].tabu[0]]+=Q/ants[i].m_dLength; Map.m_dDeltTrial[ants[i].tabu[0]][ants[i].tabu[iCityCount-1]]+=Q/ants[i].m_dLength; } for (i=0;i<iCityCount;i++) { for (j=0;j<iCityCount;j++) { Map.m_dTrial[i][j]=(rou*Map.m_dTrial[i][j]+Map.m_dDeltTrial[i][j] ); Map.m_dDeltTrial[i][j]=0; } } } void project::initmap() { int i; int j; for(i=0;i<iCityCount;i++) for (j=0;j<iCityCount;j++) { Map.m_dTrial[i][j]=1; Map.m_dDeltTrial[i][j]=0; } } project::project() { //initial map,read map infomation from file . et. initmap(); m_dLength=10e9; ifstream in("eil51.tsp"); struct city { int num; int x; int y; }cc[iCityCount]; for (int i=0;i<iCityCount;i++) { in>>cc[i].num>>cc[i].x>>cc[i].y; besttour[i]=0; } int j; for(i=0;i<iCityCount;i++) for (j=0;j<iCityCount;j++) { { Map.distance[i][j]=sqrt(pow((cc[i].x-cc[j].x),2)+pow((cc[i].y-cc[j].y),2)); } } } void project::GetAnt() //randomly put ant into map { int i=0; int city; srand( (unsigned)time( NULL ) +rand()); for (i=0;i<iAntCount;i++) { city=rnd(iCityCount); ants[i].addcity(city); } } void project::StartSearch() //begin to find best solution { int max=0;//every ant tours times int i; int j; double temp; int temptour[iCityCount]; while (max<iItCount) { for(j=0;j<iAntCount;j++) { for (i=0;i<iCityCount-1;i++) ants[j].move(); } for(j=0;j<iAntCount;j++) { ants[j].move2last(); ants[j].UpdateResult (); } //find out the best solution of the step and put it into temp int t; temp=ants[0].m_dLength; for (t=0;t<iCityCount;t++) temptour[t]=ants[0].tabu[t]; for(j=0;j<iAntCount;j++) { if (temp>ants[j].m_dLength) { temp=ants[j].m_dLength; for ( t=0;t<iCityCount;t++) temptour[t]=ants[j].tabu[t]; } } if(temp<m_dLength){ m_dLength=temp; for ( t=0;t<iCityCount;t++) besttour[t]=temptour[t]; } printf("%d : %f\n",max,m_dLength); UpdateTrial(); for(j=0;j<iAntCount;j++) ants[j].Clear(); max++; }//while printf("The shortest toure is : %f\n",m_dLength); for ( int t=0;t<iCityCount;t++) printf(" %d ",besttour[t]); } int main() { project TSP; TSP.GetAnt(); TSP.StartSearch(); return 0; } TSP文件内容如下： 1 37 52 2 49 49 3 52 64 4 20 26 5 40 30 6 21 47 7 17 63 8 31 62 9 52 33 10 51 21 11 42 41 12 31 32 13 5 25 14 12 42 15 36 16 16 52 41 17 27 23 18 17 33 19 13 13 20 57 58 21 62 42 22 42 57 23 16 57 24 8 52 25 7 38 26 27 68 27 30 48 28 43 67 29 58 48 30 58 27 31 37 69 32 38 46 33 46 10 34 61 33 35 62 63 36 63 69 37 32 22 38 45 35 39 59 15 40 5 6 41 10 17 42 21 10 43 5 64 44 30 15 45 39 10 46 32 39 47 25 32 48 25 55 49 48 28 50 56 37 51 30 40