fork(3) download 
  1. #include<iostream>
  2. #include<stdlib.h>
  3. #include<math.h>
  4. #include<assert.h>
  5. #include<time.h>
  6. #include<fstream>
  7.  
  8. #define NUMBER_OF_INTERSECTIONS 8
  9. #define MAX_DISTANCE 100
  10. #define MIN_LOAD 0
  11. #define SIGNAL_TIME 2
  12. #define MAX_TOUR (NUMBER_OF_INTERSECTIONS * MAX_DISTANCE)
  13. #define MAX_ANTS 8
  14. using namespace std;
  15.  
  16. //Initial Definiton of the problem
  17. struct antType{
  18.  
  19. int curNode, nextNode, pathIndex;
  20. int tabu[NUMBER_OF_INTERSECTIONS];
  21. int path[NUMBER_OF_INTERSECTIONS];
  22. double tourLength;
  23. };
  24. struct antTime{
  25.  
  26. int curNode2,nextNode2,pathIndex2;
  27. int tabu2[NUMBER_OF_INTERSECTIONS];
  28. int path2[NUMBER_OF_INTERSECTIONS];
  29. double tourTime;
  30. };
  31. #define ALPHA 1.0
  32. #define BETA 5.0 //This parameter raises the weight of distance over pheromone
  33. #define RHO 0.5 //Evapouration rate
  34. #define QVAL 100
  35. #define MAX_TOURS 20
  36. #define MAX_TIME (MAX_TOURS * NUMBER_OF_INTERSECTIONS)
  37. #define INIT_PHER (1.0/NUMBER_OF_INTERSECTIONS)
  38.  
  39.  
  40. //cityType cities[NUMBER_OF_INTERSECTIONS];
  41. antType ants[MAX_ANTS];
  42. antTime ants2[MAX_ANTS];
  43.  antType antBest;
  44.  antTime antTBest;
  45.  
  46. double dist[NUMBER_OF_INTERSECTIONS][NUMBER_OF_INTERSECTIONS];
  47. double load[NUMBER_OF_INTERSECTIONS][NUMBER_OF_INTERSECTIONS];
  48.  
  49. double phero[NUMBER_OF_INTERSECTIONS][NUMBER_OF_INTERSECTIONS];
  50. double phero2[NUMBER_OF_INTERSECTIONS];
  51.  
  52. double best=(double)MAX_TOUR;
  53. double bestTime=(double)(NUMBER_OF_INTERSECTIONS*SIGNAL_TIME);
  54. int bestIndex;
  55. int bestTIndex;
  56.  
  57. void init()
  58. {
  59.     int from,to,ant;
  60.  
  61.     //creating cities
  62.  
  63.     for(from = 0; from < NUMBER_OF_INTERSECTIONS; from++)
  64.     {
  65.         //randomly place cities
  66.  
  67.        // cities[from].x = (1 + (rand() % (int)(50 - 1+ 1)));
  68.  
  69.        // cities[from].y = (1 + (rand() % (int)(50 - 1 + 1)));
  70.         //printf("\n %d %d",cities[from].x, cities[from].y);
  71.         for(to=0;to<NUMBER_OF_INTERSECTIONS;to++)
  72.         {
  73.             dist[from][to] = 0.0;
  74.             phero[from][to] = INIT_PHER;
  75.  
  76.         }
  77.     }
  78.  
  79.     //computing distance
  80.  
  81.     for(from = 0; from < NUMBER_OF_INTERSECTIONS; from++)
  82.     {
  83.         for( to =0; to < NUMBER_OF_INTERSECTIONS; to++)
  84.         {
  85.             if(to!=from && dist[from][to]==0.0)
  86.             {
  87.                // int xd = pow( abs(cities[from].x - cities[to].x), 2);
  88.                // int yd = pow( abs(cities[from].y - cities[to].y), 2);
  89.  
  90.                 dist[from][to] = (1 + (rand() % (int)(100 - 1+ 1)));
  91.                 dist[to][from] = dist[from][to];
  92.  
  93.             }
  94.         }
  95.     }
  96.  
  97.     //initializing the ANTs
  98.  
  99.     to = 0;
  100.     for( ant = 0; ant < MAX_ANTS; ant++)
  101.     {
  102.         if(to == NUMBER_OF_INTERSECTIONS)
  103.             to=0;
  104.  
  105.         ants[ant].curNode = to++;
  106.  
  107.         for(from = 0; from < NUMBER_OF_INTERSECTIONS; from++)
  108.         {
  109.             ants[ant].tabu[from] = 0;
  110.             ants[ant].path[from] = -1;
  111.         }
  112.  
  113.         ants[ant].pathIndex = 1;
  114.         ants[ant].path[0] = ants[ant].curNode;
  115.         ants[ant].nextNode = -1;
  116.         ants[ant].tourLength = 0;
  117.  
  118.         //loading first city into tabu list
  119.  
  120.         ants[ant].tabu[ants[ant].curNode] =1;
  121.  
  122.     }
  123. }
  124. void init_Ants()
  125. {
  126.     int from,to,ant;
  127.  
  128.     //creating cities
  129.  
  130.     for(from = 0; from < NUMBER_OF_INTERSECTIONS; from++)
  131.     {
  132.         phero2[from]= INIT_PHER;
  133.  
  134.     }
  135.     cout<<"\nENTER THE LOAD MATRIX\n";
  136.     //computing distance
  137.  
  138.     for(from = 0; from < NUMBER_OF_INTERSECTIONS; from++)
  139.     {
  140.         for( to =0; to < NUMBER_OF_INTERSECTIONS; to++)
  141.         {
  142.           cin>>load[from][to];
  143.         }
  144.     }
  145.  
  146.     //initializing the ANTs
  147.  
  148.     to = 0;
  149.     for( ant = 0; ant < MAX_ANTS; ant++)
  150.     {
  151.         if(to == NUMBER_OF_INTERSECTIONS)
  152.             to=0;
  153.  
  154.         ants2[ant].curNode2 =antBest.path[ant] ;
  155.  
  156.         for(from = 0; from < NUMBER_OF_INTERSECTIONS; from++)
  157.         {
  158.             ants2[ant].tabu2[from] = 0;
  159.             ants2[ant].path2[from] = -1;
  160.         }
  161.  
  162.         ants2[ant].pathIndex2 = 1;
  163.         ants2[ant].path2[0] = ants2[ant].curNode2;
  164.         ants2[ant].nextNode2 = -1;
  165.         ants2[ant].tourTime = 0;
  166.  
  167.         //loading first city into tabu list
  168.  
  169.         ants2[ant].tabu2[ants2[ant].curNode2] =1;
  170.  
  171.     }
  172. }
  173. void restartTime_Ants()
  174. {
  175.    int ant,i,to=0;
  176.  
  177.     for(ant = 0; ant<MAX_ANTS; ant++)
  178.     {
  179.         if(ants2[ant].tourTime < bestTime)
  180.         {
  181.             bestTime = ants[ant].tourLength;
  182.             bestIndex = ant;
  183.         }
  184.  
  185.         ants2[ant].nextNode2 = -1;
  186.         ants2[ant].tourTime = 0.0;
  187.  
  188.         for(i=0;i<NUMBER_OF_INTERSECTIONS;i++)
  189.         {
  190.             ants2[ant].tabu2[i] = 0;
  191.             ants2[ant].path2[i] = -1;
  192.         }
  193.  
  194.         if(to == NUMBER_OF_INTERSECTIONS)
  195.             to=0;
  196.  
  197.         ants2[ant].curNode2 = antBest.path[to++];
  198.  
  199.         ants2[ant].pathIndex2 = 1;
  200.         ants2[ant].path2[0] = ants2[ant].curNode2;
  201.  
  202.         ants2[ant].tabu2[ants2[ant].curNode2] = 1;
  203.     }
  204. }
  205. //reinitialize all ants and redistribute them
  206. void restartAnts()
  207. {
  208.     int ant,i,to=0;
  209.  
  210.     for(ant = 0; ant<MAX_ANTS; ant++)
  211.     {
  212.         if(ants[ant].tourLength < best)
  213.         {
  214.             best = ants[ant].tourLength;
  215.             bestIndex = ant;
  216.         }
  217.  
  218.         ants[ant].nextNode = -1;
  219.         ants[ant].tourLength = 0.0;
  220.  
  221.         for(i=0;i<NUMBER_OF_INTERSECTIONS;i++)
  222.         {
  223.             ants[ant].tabu[i] = 0;
  224.             ants[ant].path[i] = -1;
  225.         }
  226.  
  227.         if(to == NUMBER_OF_INTERSECTIONS)
  228.             to=0;
  229.  
  230.         ants[ant].curNode = to++;
  231.  
  232.         ants[ant].pathIndex = 1;
  233.         ants[ant].path[0] = ants[ant].curNode;
  234.  
  235.         ants[ant].tabu[ants[ant].curNode] = 1;
  236.     }
  237. }
  238. double antProduct(int from, int to)
  239. {
  240.     return(( pow( phero[from][to], ALPHA) * pow( (1.0/ dist[from][to]), BETA)));
  241. }
  242. int selectnextTimeNode(int ant)
  243. {
  244.    int from, to;
  245.     double denom = 0.0;
  246.  
  247.     from=ants2[ant].curNode2;
  248.  
  249.     for(to=0;to<NUMBER_OF_INTERSECTIONS;to++)
  250.             {
  251.                        if(ants2[ant].tabu2[to] == 0)
  252.                                {
  253.                                             denom += antProduct( from, to );
  254.     }
  255.       }
  256.             assert(denom != 0.0);
  257.                   do
  258.                     {
  259.                               double p;
  260.                   to++;
  261.                               if(to >= NUMBER_OF_INTERSECTIONS)
  262.             to=0;
  263.         if(ants2[ant].tabu2[to] == 0)
  264.         {
  265.             p = antProduct(from,to)/denom;
  266.  
  267.             //printf("\n%lf %lf", (double)rand()/RAND_MAX,p);
  268.             double x = ((double)rand()/RAND_MAX);
  269.             if(x < p)
  270.             {
  271.                 //printf("%lf %lf Yo!",p,x);
  272.  
  273.                 break;
  274.             }
  275.         }
  276.     }while(1);
  277.  
  278.     return to;
  279. }
  280. int selectnextNode( int ant )
  281. {
  282.     int from, to;
  283.     double denom = 0.0;
  284.  
  285.     from=ants[ant].curNode;
  286.  
  287.     for(to=0;to<NUMBER_OF_INTERSECTIONS;to++)
  288.             {
  289.                        if(ants[ant].tabu[to] == 0)
  290.                                {
  291.                                             denom += antProduct( from, to );
  292.     }
  293.       }
  294.             assert(denom != 0.0);
  295.                   do
  296.                     {
  297.                               double p;
  298.                   to++;
  299.                               if(to >= NUMBER_OF_INTERSECTIONS)
  300.             to=0;
  301.         if(ants[ant].tabu[to] == 0)
  302.         {
  303.             p = antProduct(from,to)/denom;
  304.  
  305.             //printf("\n%lf %lf", (double)rand()/RAND_MAX,p);
  306.             double x = ((double)rand()/RAND_MAX);
  307.             if(x < p)
  308.             {
  309.                 //printf("%lf %lf Yo!",p,x);
  310.  
  311.                 break;
  312.             }
  313.         }
  314.     }while(1);
  315.  
  316.     return to;
  317. }
  318. int simulateTime()
  319. {
  320.    int k;
  321.     int moving = 0;
  322.  
  323.     for(k=0; k<MAX_ANTS; k++)
  324.     {
  325.         //checking if there are any more cities to visit
  326.  
  327.         if( ants2[k].pathIndex2 < NUMBER_OF_INTERSECTIONS )
  328.                     {
  329.                                   ants2[k].nextNode2 = selectnextTimeNode(k);
  330.         ants2[k].tabu2[ants2[k].nextNode2] = 1;
  331.                     ants2[k].path2[ants2[k].pathIndex2++] = ants2[k].nextNode2;
  332.                                           ants2[k].tourTime += ((load[ants2[k].curNode2][ants2[k].nextNode2])/(dist[ants[k].curNode][ants[k].nextNode])*2);                      //handle last case->last city to first
  333.  
  334.             if(ants2[k].pathIndex2 == NUMBER_OF_INTERSECTIONS)
  335.             {
  336.                 ants2[k].tourTime += ((load[ants2[k].path2[NUMBER_OF_INTERSECTIONS -1]][ants2[k].path2[0]])/(dist[ants2[k].path2[NUMBER_OF_INTERSECTIONS -1]][ants2[k].path2[0]])*2);
  337.             }
  338.  
  339.             ants2[k].curNode2 = ants2[k].nextNode2;
  340.             moving++;
  341.  
  342.         }
  343.     }
  344.  
  345.     return moving;
  346. }
  347. int simulateAnts()
  348. {
  349.     int k;
  350.     int moving = 0;
  351.  
  352.     for(k=0; k<MAX_ANTS; k++)
  353.     {
  354.         //checking if there are any more cities to visit
  355.  
  356.         if( ants[k].pathIndex < NUMBER_OF_INTERSECTIONS )
  357.                     {
  358.                                   ants[k].nextNode = selectnextNode(k);
  359.         ants[k].tabu[ants[k].nextNode] = 1;
  360.                     ants[k].path[ants[k].pathIndex++] = ants[k].nextNode;
  361.                                           ants[k].tourLength += dist[ants[k].curNode][ants[k].nextNode];                      //handle last case->last city to first
  362.  
  363.             if(ants[k].pathIndex == NUMBER_OF_INTERSECTIONS)
  364.             {
  365.                 ants[k].tourLength += dist[ants[k].path[NUMBER_OF_INTERSECTIONS -1]][ants[k].path[0]];
  366.             }
  367.  
  368.             ants[k].curNode = ants[k].nextNode;
  369.             moving++;
  370.  
  371.         }
  372.     }
  373.  
  374.     return moving;
  375. }
  376.  
  377. //Updating trails
  378. void updateTime()
  379. {
  380.  int from,to,i,ant;
  381.  
  382.     //Pheromone Evaporation
  383.  
  384.     for(from=0; from<NUMBER_OF_INTERSECTIONS;from++)
  385.     {
  386.  
  387.                 phero2[from] *=( 1.0 - RHO);
  388.  
  389.                 if(phero2[from]<0.0)
  390.                 {
  391.                     phero2[from] = INIT_PHER;
  392.                 }
  393.             }
  394.  
  395.  
  396.  
  397.     //Add new pheromone to the trails
  398.  
  399.     for(ant=0;ant<MAX_ANTS;ant++)
  400.     {
  401.         for(i=0;i<NUMBER_OF_INTERSECTIONS;i++)
  402.         {
  403.  
  404.  
  405.                 from = ants2[ant].path2[i];
  406.  
  407.  
  408.  
  409.  
  410.             phero2[from] += (QVAL/ ants2[ant].tourTime);
  411.  
  412.  
  413.         }
  414.     }
  415.  
  416.     for (from=0; from < NUMBER_OF_INTERSECTIONS;from++)
  417.     {
  418.  
  419.  
  420.             phero2[from] *= RHO;
  421.  
  422.     }
  423. }
  424. void updateTrails()
  425. {
  426.     int from,to,i,ant;
  427.  
  428.     //Pheromone Evaporation
  429.  
  430.     for(from=0; from<NUMBER_OF_INTERSECTIONS;from++)
  431.     {
  432.         for(to=0;to<NUMBER_OF_INTERSECTIONS;to++)
  433.         {
  434.             if(from!=to)
  435.             {
  436.                 phero[from][to] *=( 1.0 - RHO);
  437.  
  438.                 if(phero[from][to]<0.0)
  439.                 {
  440.                     phero[from][to] = INIT_PHER;
  441.                 }
  442.             }
  443.         }
  444.     }
  445.  
  446.     //Add new pheromone to the trails
  447.  
  448.     for(ant=0;ant<MAX_ANTS;ant++)
  449.     {
  450.         for(i=0;i<NUMBER_OF_INTERSECTIONS;i++)
  451.         {
  452.             if( i < NUMBER_OF_INTERSECTIONS-1 )
  453.             {
  454.                 from = ants[ant].path[i];
  455.                 to = ants[ant].path[i+1];
  456.             }
  457.             else
  458.             {
  459.                 from = ants[ant].path[i];
  460.                 to = ants[ant].path[0];
  461.             }
  462.  
  463.             phero[from][to] += (QVAL/ ants[ant].tourLength);
  464.             phero[to][from] = phero[from][to];
  465.  
  466.         }
  467.     }
  468.  
  469.     for (from=0; from < NUMBER_OF_INTERSECTIONS;from++)
  470.     {
  471.         for( to=0; to<NUMBER_OF_INTERSECTIONS; to++)
  472.         {
  473.             phero[from][to] *= RHO;
  474.         }
  475.     }
  476.  
  477. }
  478. void emitDataTime(int bestTIndex)
  479. {
  480.   std::ofstream f1;
  481.     f1.open("DataTime.txt");
  482.  
  483.     antTBest = ants2[bestTIndex];
  484.     f1<<antTBest.curNode2<<" "<<antTBest.tourTime<<"\n";
  485.     int i;
  486.     for(i=0;i<NUMBER_OF_INTERSECTIONS;i++)
  487.     {
  488.         f1<<antTBest.path2[i]<<" ";
  489.     }
  490.  
  491.     f1.close();
  492.  
  493.  
  494. }
  495. void emitDataFile(int bestIndex)
  496. {
  497.   std::ofstream f1;
  498.     f1.open("Data.txt");
  499.  
  500.     antBest = ants[bestIndex];
  501.     f1<<antBest.curNode<<" "<<antBest.tourLength<<"\n";
  502.     int i;
  503.     for(i=0;i<NUMBER_OF_INTERSECTIONS;i++)
  504.     {
  505.         f1<<antBest.path[i]<<" ";
  506.     }
  507.  
  508.     f1.close();
  509.  
  510.     f1.open("city_data.txt");
  511.      for(int from = 0; from < NUMBER_OF_INTERSECTIONS; from++)
  512.     {
  513.         for( int to =0; to < NUMBER_OF_INTERSECTIONS; to++)
  514.         {
  515.  
  516.  
  517.                 f1<<dist[from][to]<<" ";
  518.             //dist[to][from] = dist[from][to];
  519.  
  520.             //}
  521.         }f1<<"\n";
  522.     }
  523.    // for(i=0;i<NUMBER_OF_INTERSECTIONS;i++)
  524.    // {
  525.    //     f1<<cities[i].x<<" "<<cities[i].y<<"\n";
  526.   //  }
  527.     f1.close();
  528.  
  529. }
  530. int main()
  531. {
  532.     int curTime = 0;
  533.     cout<<"MaxTime="<<MAX_TIME;
  534.  
  535.    srand(time(NULL));
  536.  
  537.     init();
  538.  
  539.  
  540.     while( curTime++ < MAX_TIME)
  541.     {
  542.         if( simulateAnts() == 0)
  543.         {
  544.             updateTrails();
  545.  
  546.             if(curTime != MAX_TIME)
  547.                 restartAnts();
  548.  
  549.             cout<<"\nTime is "<<curTime<<"("<<best<<")";
  550.  
  551.         }
  552.     }
  553.  
  554.     cout<<"\nBest tour = "<<best<<endl;
  555.  
  556.     emitDataFile(bestIndex);
  557.     init_Ants();
  558.     while(curTime++ < MAX_TIME)
  559.     {
  560.         if(simulateTime()==0)
  561.         {
  562.             updateTime();
  563.             if(curTime!=MAX_TIME)
  564.                 restartTime_Ants();
  565.             cout<<"\nFINAL WAITING MINIMUM TIME "<<curTime<<"("<<bestTime<<")";
  566.         }
  567. }
  568.  cout<<"\nBEST TIME="<<bestTime<<endl;
  569.  emitDataTime(bestTIndex);
  570.     return 0;
  571. }
  572.  
Success #stdin #stdout 0s 3244KB
comments (?)
stdin 
Standard input is empty
stdout 
MaxTime=160
Time is 8(246)
Time is 16(246)
Time is 24(246)
Time is 32(246)
Time is 40(246)
Time is 48(246)
Time is 56(246)
Time is 64(246)
Time is 72(246)
Time is 80(246)
Time is 88(246)
Time is 96(246)
Time is 104(246)
Time is 112(246)
Time is 120(246)
Time is 128(246)
Time is 136(246)
Time is 144(246)
Time is 152(246)
Time is 160(246)
Best tour = 246

ENTER THE LOAD MATRIX

BEST TIME=16
https://ideone.com/3JWv7E
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!