新建 文本文档 (3).txt

这个是C语言版本的蚂蚁算法源程序,大家感兴趣的话,可以和我多多联系,可以共同商讨商讨

源代码：

// lastant.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "stdafx.h"
#include 
#include 
#include "math.h"
#include 
#include 
using namespace std;


const int MAXANT=10;//ant numbers
const int MAXCITY=100;
const int MAXIT=5000;
const double QVALUE=100;
const double ALPHA=1.0;
const double BETA=2;
const double RHO=0.9;
double rain=0.0;
const double Q0=0.3;
int besttour[MAXCITY+1];
 int maxss=0;
double  rnd(int low,int uper)
{

 //if (p==1)p=0.9999;
 //else if (p==0)p=0.0001;
 return ((rand()/(double)(RAND_MAX+1.0))*((uper)-(low))+(low));
};
int rnd(int uper)
{
 return (rand()%uper);
};

struct GInfo
{
 double deltatrail[MAXCITY][MAXCITY];
 double pheromone[MAXCITY][MAXCITY];
 double distance[MAXCITY][MAXCITY];
}WORLD;
class CAnt{
private:

 int allowed[MAXCITY];
 int topcity;


 double AntProduct( int from, int to )
 {
  double p;
  //if ( WORLD.distance[from][to]==0)
  //{ printf("WORLD.distance[from][to]==0\n");return 0;}
  //else//{char c;printf("error! form = %d to = %d\n",from,to);scanf("%c",&c);}
  //{
   p=( pow( WORLD.pheromone[from][to], ALPHA ) *pow( (1.0 / WORLD.distance[from][to]), BETA ) );
   if( p==0)p=rnd(0,1)*pow( (1.0 / WORLD.distance[from][to]), BETA );
  //{ char c;printf("p==00 WORLD.distance[from][to])=%f WORLD.pheromone[from][to]=%f from=%d to=%d topcity=%d\n", WORLD.distance[from][to],WORLD.pheromone[from][to],from ,to,topcity);scanf("%c",&c);}
  return (p);/*}*/
 }
 int ChooseNextCity();

public:

 double length;
 int visited[MAXCITY+1];

 void AddCity(int city);
 void UpdateLength();
 void Move();
 void Reset();
 CAnt()
 {
  int city;
  for(city=0;city<MAXCITY;CITY++)
   allowed[city]=1;
  topcity=0;
  length=0;
 }
};
void CAnt::Reset()
{
 int city;
 int i=visited[0];
 for(city=0;city<MAXCITY;CITY++)
 {allowed[city]=1;visited[city]=-1;}
 topcity=0;
 AddCity(i);
 length=0;
}

void CAnt::AddCity (int city)
{
 visited[topcity]=city;
 topcity++;
 allowed[city]=0;
}
void CAnt::Move()
{//the ant move to next town and add town ID to tabu.
 AddCity(ChooseNextCity());

}
int CAnt::ChooseNextCity()
{
 int from, to;
 double denom=0.0;

 // Choose the next city to visit 
 from = visited[topcity-1];

 //Work out denominator of formula
 for (to = 0 ; to < MAXCITY ; to++) {
  if (allowed[to] == 1) {
   denom += AntProduct( from, to );
  }
 } 
   srand( (unsigned)time( NULL )*MAXCITY*to);

 if (denom==0) {/*printf("denom==0");*/to=rnd(MAXCITY);}
 else
 do {

  double p;

  to++;
  if (to >= MAXCITY) to = 0;
  if ( allowed[to] == 1 ) 
  {
   p = AntProduct(from, to)/denom;

   if (rnd(0,1) < p ) 
    break;
  }

 } while (1);
 return to;
}
void CAnt::UpdateLength()
{// Update the length of tour
 int city;
 length=0;
 for(city=0;city<MAXCITY;CITY++)
  length+=WORLD.distance[visited[city]][visited[city+1]];
}
class CProject{

public:

 double shortest;
 CAnt ants[MAXANT];

 void UpdateTrial();
 void GetAnt();
 void StartSearch();
 CProject();
};
void CProject::StartSearch()
{
//every ant tours times
 int i;
 int j;
 double temp;
 int temptour[MAXCITY+1];
 while (maxss<MAXIT)
 {
  for (i=0;i<MAXCITY-1;I++)
   for(j=0;j
    ants[j].Move();

  for(j=0;j
  {
   ants[j].visited[MAXCITY]=ants[j].visited[0];
   ants[j].UpdateLength ();
  }

  //find out the best solution of the step and put it into temp
  int t;
  temp=ants[0].length ;
  for (t=0;t<MAXCITY+1;T++)
   temptour[t]=ants[0].visited[t];
  for(j=0;j
  {
   if (temp>ants[j].length) {
    temp=ants[j].length;
    for ( t=0;t<MAXCITY+1;T++)
     temptour[t]=ants[j].visited[t];
   }
  }

  if(temp<SHORTEST){
   shortest=temp;
   printf("%d : %f\n",maxss,shortest);
   for ( t=0;t<MAXCITY+1;T++)
    besttour[t]=temptour[t];
  }
  if (maxss %100==0)printf(" %d \n",maxss);
  UpdateTrial(); 

  for(j=0;j
   ants[j].Reset();

  maxss++;
 }
 printf("The shortest toure is : %f\n",shortest);
    //temp=0;
 for ( int t=0;t<=MAXCITY;t++)
 { 
  printf(" %d ",besttour[t]);
 }

}
void CProject::UpdateTrial()
{
 int from, to, i, ant;

 /* WORLD.pheromone Evaporation */
 //for (from = 0 ; from < MAXCITY ; from++) {

 // for (to = 0 ; to < MAXCITY ; to++) {

 //  if (from != to) {

 //   WORLD.pheromone[from][to] *= (1.0 - RHO);

 //   if (WORLD.pheromone[from][to] < 0.0) WORLD.pheromone[from][to] = 0;

 //  }

 // }

 //}

 // Add new WORLD.pheromone to the trails

 // Look at the tours of each ant
 for (from = 0 ; from < MAXCITY ; from++)
 {
  for (to = 0 ; to < MAXCITY ; to++) 
  {
   WORLD.pheromone[from][to] *= RHO;
  }
 } 
 for (ant = 0 ; ant < MAXANT ; ant++) {

  // Update each leg of the tour given the tour length
  for (i = 0 ; i < MAXCITY ; i++) {

   from = ants[ant].visited[i];
   to = ants[ant].visited[i+1];
   WORLD.pheromone[from][to] += (QVALUE / ants[ant].length);
   WORLD.pheromone[to][from] = WORLD.pheromone[from][to];

   //printf("%f\n",WORLD.pheromone[from][to]);
  }

 }
//if (maxss%500==0)
// rain*=0.1;
 double mayrain=rnd(0,1);
 if (mayrain<RAIN)
 {
  printf("raining!\n");
  int citynum=(MAXCITY);
  int j;
  for (i=0;i<CITYNUM;I++)
  {
   for (j=0;j<CITYNUM;J++)
   {
    WORLD.pheromone [rnd(MAXCITY)][rnd(MAXCITY)]=0.5;
   }
  }
 }

}

void CProject::GetAnt()
{
 int i=0;
 int city;
 srand( (unsigned)time( NULL ));
 for (i=0;i<MAXANT;I++)
 {
  city=rnd(MAXCITY);
  ants[i].AddCity(city);
 }
}
CProject::CProject()
{

 struct city
 {

  int x;
  int  y;
 }cc[MAXCITY];

 int num;
 int i;
 int j;

 for(i=0;i<MAXCITY;I++)
  for (j=0;j<MAXCITY;J++)
  {
   WORLD.pheromone [i][j]=0.5;
  }

  shortest=10e9;


  ifstream in("kroa100.tsp");

  for (i=0;i<MAXCITY;I++)
  {
   in>>num>>cc[i].x>>cc[i].y;
  }

  for(i=0;i<MAXCITY;I++)
   for (j=0;j<MAXCITY;J++)
    WORLD.distance[i][j]=sqrt(pow((cc[i].x-cc[j].x),2)+pow((cc[i].y-cc[j].y),2));
}
int _tmain(int argc, _TCHAR* argv[])
{
 CProject TSP;
 TSP.GetAnt();
 TSP.StartSearch();
 char c;
 scanf("%c",&c);
 return 0;
}


另外，TSP文件的处理方式：

原来的格式是这样的（eil51.tsp）：

NAME : eil51
COMMENT : 51-city problem (Christofides/Eilon)
TYPE : TSP
DIMENSION : 51
EDGE_WEIGHT_TYPE : EUC_2D
NODE_COORD_SECTION
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
EOF


把它变化成：

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


程序就可以处理了。也可以改代码。