#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

　　{

　　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;

　　}[NextPage]

　　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;

　　} [NextPage]

　　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; [NextPage]

　　}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];

　　}

　　}[NextPage]

　　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