fork(2) download
copy 
  1. using System;
  2.  
  3. // Demo of Ant Colony Optimization (ACO) solving a Traveling Salesman Problem (TSP).
  4. // There are many variations of ACO; this is just one approach.
  5. // The problem to solve has a program defined number of cities. We assume that every
  6. // city is connected to every other city. The distance between cities is artificially
  7. // set so that the distance between any two cities is a random value between 1 and 8
  8. // Cities wrap, so if there are 20 cities then D(0,19) = D(19,0).
  9. // Free parameters are alpha, beta, rho, and Q. Hard-coded constants limit min and max
  10. // values of pheromones.
  11.  
  12. namespace AntColony
  13. {
  14.   class AntColonyProgram
  15.   {
  16.     static Random random = new Random(0);
  17.  
  18.     static int alpha = 3; // influence of pheromone on direction
  19.     static int beta = 2;  // influence of adjacent node distance
  20.  
  21.     static double rho = 0.01; // pheromone decrease factor
  22.     static double Q = 2.0;   // pheromone increase factor
  23.  
  24.     static void Main(string[] args)
  25.     {
  26.       try
  27.       {
  28.         Console.WriteLine("\nBegin Ant Colony Optimization demo\n");
  29.  
  30.         int numCities = 60;
  31.         int numAnts = 4;
  32.         int maxTime = 1000;
  33.  
  34.         Console.WriteLine("Number cities in problem = " + numCities);
  35.  
  36.         Console.WriteLine("\nNumber ants = " + numAnts);
  37.         Console.WriteLine("Maximum time = " + maxTime);
  38.  
  39.         Console.WriteLine("\nAlpha (pheromone influence) = " + alpha);
  40.         Console.WriteLine("Beta (local node influence) = " + beta);
  41.         Console.WriteLine("Rho (pheromone evaporation coefficient) = " + rho.ToString("F2"));
  42.         Console.WriteLine("Q (pheromone deposit factor) = " + Q.ToString("F2"));
  43.  
  44.         Console.WriteLine("\nInitialing dummy graph distances");
  45.         int[][] dists = MakeGraphDistances(numCities);
  46.  
  47.         Console.WriteLine("\nInitialing ants to random trails\n");
  48.         int[][] ants = InitAnts(numAnts, numCities); // initialize ants to random trails
  49.         ShowAnts(ants, dists);
  50.  
  51.         int[] bestTrail = BestTrail(ants, dists); // determine the best initial trail
  52.         double bestLength = Length(bestTrail, dists); // the length of the best trail
  53.  
  54.         Console.Write("\nBest initial trail length: " + bestLength.ToString("F1") + "\n");
  55.         //Display(bestTrail);
  56.  
  57.         Console.WriteLine("\nInitializing pheromones on trails");
  58.         double[][] pheromones = InitPheromones(numCities);
  59.  
  60.         int time = 0;
  61.         Console.WriteLine("\nEntering UpdateAnts - UpdatePheromones loop\n");
  62.         while (time < maxTime)
  63.         {
  64.           UpdateAnts(ants, pheromones, dists);
  65.           UpdatePheromones(pheromones, ants, dists);
  66.  
  67.           int[] currBestTrail = BestTrail(ants, dists);
  68.           double currBestLength = Length(currBestTrail, dists);
  69.           if (currBestLength < bestLength)
  70.           {
  71.             bestLength = currBestLength;
  72.             bestTrail = currBestTrail;
  73.             Console.WriteLine("New best length of " + bestLength.ToString("F1") + " found at time " + time);
  74.           }
  75.           ++time;
  76.         }
  77.  
  78.         Console.WriteLine("\nTime complete");
  79.  
  80.         Console.WriteLine("\nBest trail found:");
  81.         Display(bestTrail);
  82.         Console.WriteLine("\nLength of best trail found: " + bestLength.ToString("F1"));
  83.  
  84.         Console.WriteLine("\nEnd Ant Colony Optimization demo\n");
  85.         Console.ReadLine();
  86.       }
  87.       catch (Exception ex)
  88.       {
  89.         Console.WriteLine(ex.Message);
  90.         Console.ReadLine();
  91.       }
  92.  
  93.     } // Main
  94.  
  95.     // --------------------------------------------------------------------------------------------
  96.  
  97.     static int[][] InitAnts(int numAnts, int numCities)
  98.     {
  99.       int[][] ants = new int[numAnts][];
  100.       for (int k = 0; k < numAnts; ++k)
  101.       {
  102.         int start = random.Next(0, numCities);
  103.         ants[k] = RandomTrail(start, numCities);
  104.       }
  105.       return ants;
  106.     }
  107.  
  108.     static int[] RandomTrail(int start, int numCities) // helper for InitAnts
  109.     {
  110.       int[] trail = new int[numCities];
  111.  
  112.       for (int i = 0; i < numCities; ++i) { trail[i] = i; } // sequential
  113.  
  114.       for (int i = 0; i < numCities; ++i) // Fisher-Yates shuffle
  115.       {
  116.         int r = random.Next(i, numCities);
  117.         int tmp = trail[r]; trail[r] = trail[i]; trail[i] = tmp;
  118.       }
  119.  
  120.       int idx = IndexOfTarget(trail, start); // put start at [0]
  121.       int temp = trail[0];
  122.       trail[0] = trail[idx];
  123.       trail[idx] = temp;
  124.  
  125.       return trail;
  126.     }
  127.  
  128.     static int IndexOfTarget(int[] trail, int target) // helper for RandomTrail
  129.     {
  130.       for (int i = 0; i < trail.Length; ++i)
  131.       {
  132.         if (trail[i] == target)
  133.           return i;
  134.       }
  135.       throw new Exception("Target not found in IndexOfTarget");
  136.     }
  137.  
  138.     static double Length(int[] trail, int[][] dists) // total length of a trail
  139.     {
  140.       double result = 0.0;
  141.       for (int i = 0; i < trail.Length - 1; ++i)
  142.         result += Distance(trail[i], trail[i + 1], dists);
  143.       return result;
  144.     }
  145.  
  146.     // -------------------------------------------------------------------------------------------- 
  147.  
  148.     static int[] BestTrail(int[][] ants, int[][] dists) // best trail has shortest total length
  149.     {
  150.       double bestLength = Length(ants[0], dists);
  151.       int idxBestLength = 0;
  152.       for (int k = 1; k < ants.Length; ++k)
  153.       {
  154.         double len = Length(ants[k], dists);
  155.         if (len < bestLength)
  156.         {
  157.           bestLength = len;
  158.           idxBestLength = k;
  159.         }
  160.       }
  161.       int numCities = ants[0].Length;
  162.       int[] bestTrail = new int[numCities];
  163.       ants[idxBestLength].CopyTo(bestTrail, 0);
  164.       return bestTrail;
  165.     }
  166.  
  167.     // --------------------------------------------------------------------------------------------
  168.  
  169.     static double[][] InitPheromones(int numCities)
  170.     {
  171.       double[][] pheromones = new double[numCities][];
  172.       for (int i = 0; i < numCities; ++i)
  173.         pheromones[i] = new double[numCities];
  174.       for (int i = 0; i < pheromones.Length; ++i)
  175.         for (int j = 0; j < pheromones[i].Length; ++j)
  176.           pheromones[i][j] = 0.01; // otherwise first call to UpdateAnts -> BuiuldTrail -> NextNode -> MoveProbs => all 0.0 => throws
  177.       return pheromones;
  178.     }
  179.  
  180.     // --------------------------------------------------------------------------------------------
  181.  
  182.     static void UpdateAnts(int[][] ants, double[][] pheromones, int[][] dists)
  183.     {
  184.       int numCities = pheromones.Length;
  185.       for (int k = 0; k < ants.Length; ++k)
  186.       {
  187.         int start = random.Next(0, numCities);
  188.         int[] newTrail = BuildTrail(k, start, pheromones, dists);
  189.         ants[k] = newTrail;
  190.       }
  191.     }
  192.  
  193.     static int[] BuildTrail(int k, int start, double[][] pheromones, int[][] dists)
  194.     {
  195.       int numCities = pheromones.Length;
  196.       int[] trail = new int[numCities];
  197.       bool[] visited = new bool[numCities];
  198.       trail[0] = start;
  199.       visited[start] = true;
  200.       for (int i = 0; i < numCities - 1; ++i)
  201.       {
  202.         int cityX = trail[i];
  203.         int next = NextCity(k, cityX, visited, pheromones, dists);
  204.         trail[i + 1] = next;
  205.         visited[next] = true;
  206.       }
  207.       return trail;
  208.     }
  209.  
  210.     static int NextCity(int k, int cityX, bool[] visited, double[][] pheromones, int[][] dists)
  211.     {
  212.       // for ant k (with visited[]), at nodeX, what is next node in trail?
  213.       double[] probs = MoveProbs(k, cityX, visited, pheromones, dists);
  214.  
  215.       double[] cumul = new double[probs.Length + 1];
  216.       for (int i = 0; i < probs.Length; ++i)
  217.         cumul[i + 1] = cumul[i] + probs[i]; // consider setting cumul[cuml.Length-1] to 1.00
  218.  
  219.       double p = random.NextDouble();
  220.  
  221.       for (int i = 0; i < cumul.Length - 1; ++i)
  222.         if (p >= cumul[i] && p < cumul[i + 1])
  223.           return i;
  224.       throw new Exception("Failure to return valid city in NextCity");
  225.     }
  226.  
  227.     static double[] MoveProbs(int k, int cityX, bool[] visited, double[][] pheromones, int[][] dists)
  228.     {
  229.       // for ant k, located at nodeX, with visited[], return the prob of moving to each city
  230.       int numCities = pheromones.Length;
  231.       double[] taueta = new double[numCities]; // inclues cityX and visited cities
  232.       double sum = 0.0; // sum of all tauetas
  233.       for (int i = 0; i < taueta.Length; ++i) // i is the adjacent city
  234.       {
  235.         if (i == cityX)
  236.           taueta[i] = 0.0; // prob of moving to self is 0
  237.         else if (visited[i] == true)
  238.           taueta[i] = 0.0; // prob of moving to a visited city is 0
  239.         else
  240.         {
  241.           taueta[i] = Math.Pow(pheromones[cityX][i], alpha) * Math.Pow((1.0 / Distance(cityX, i, dists)), beta); // could be huge when pheromone[][] is big
  242.           if (taueta[i] < 0.0001)
  243.             taueta[i] = 0.0001;
  244.           else if (taueta[i] > (double.MaxValue / (numCities * 100)))
  245.             taueta[i] = double.MaxValue / (numCities * 100);
  246.         }
  247.         sum += taueta[i];
  248.       }
  249.  
  250.       double[] probs = new double[numCities];
  251.       for (int i = 0; i < probs.Length; ++i)
  252.         probs[i] = taueta[i] / sum; // big trouble if sum = 0.0
  253.       return probs;
  254.     }
  255.  
  256.     // --------------------------------------------------------------------------------------------
  257.  
  258.     static void UpdatePheromones(double[][] pheromones, int[][] ants, int[][] dists)
  259.     {
  260.       for (int i = 0; i < pheromones.Length; ++i)
  261.       {
  262.         for (int j = i + 1; j < pheromones[i].Length; ++j)
  263.         {
  264.           for (int k = 0; k < ants.Length; ++k)
  265.           {
  266.             double length = Length(ants[k], dists); // length of ant k trail
  267.             double decrease = (1.0 - rho) * pheromones[i][j];
  268.             double increase = 0.0;
  269.             if (EdgeInTrail(i, j, ants[k]) == true) increase = (Q / length);
  270.  
  271.             pheromones[i][j] = decrease + increase;
  272.  
  273.             if (pheromones[i][j] < 0.0001)
  274.               pheromones[i][j] = 0.0001;
  275.             else if (pheromones[i][j] > 100000.0)
  276.               pheromones[i][j] = 100000.0;
  277.  
  278.             pheromones[j][i] = pheromones[i][j];
  279.           }
  280.         }
  281.       }
  282.     }
  283.  
  284.     static bool EdgeInTrail(int cityX, int cityY, int[] trail)
  285.     {
  286.       // are cityX and cityY adjacent to each other in trail[]?
  287.       int lastIndex = trail.Length - 1;
  288.       int idx = IndexOfTarget(trail, cityX);
  289.  
  290.       if (idx == 0 && trail[1] == cityY) return true;
  291.       else if (idx == 0 && trail[lastIndex] == cityY) return true;
  292.       else if (idx == 0) return false;
  293.       else if (idx == lastIndex && trail[lastIndex - 1] == cityY) return true;
  294.       else if (idx == lastIndex && trail[0] == cityY) return true;
  295.       else if (idx == lastIndex) return false;
  296.       else if (trail[idx - 1] == cityY) return true;
  297.       else if (trail[idx + 1] == cityY) return true;
  298.       else return false;
  299.     }
  300.  
  301.  
  302.     // --------------------------------------------------------------------------------------------
  303.  
  304.     static int[][] MakeGraphDistances(int numCities)
  305.     {
  306.       int[][] dists = new int[numCities][];
  307.       for (int i = 0; i < dists.Length; ++i)
  308.         dists[i] = new int[numCities];
  309.       for (int i = 0; i < numCities; ++i)
  310.         for (int j = i + 1; j < numCities; ++j)
  311.         {
  312.           int d = random.Next(1, 9); // [1,8]
  313.           dists[i][j] = d;
  314.           dists[j][i] = d;
  315.         }
  316.       return dists;
  317.     }
  318.  
  319.     static double Distance(int cityX, int cityY, int[][] dists)
  320.     {
  321.       return dists[cityX][cityY];
  322.     }
  323.  
  324.     // --------------------------------------------------------------------------------------------
  325.  
  326.     static void Display(int[] trail)
  327.     {
  328.       for (int i = 0; i < trail.Length; ++i)
  329.       {
  330.         Console.Write(trail[i] + " ");
  331.         if (i > 0 && i % 20 == 0) Console.WriteLine("");
  332.       }
  333.       Console.WriteLine("");
  334.     }
  335.  
  336.  
  337.     static void ShowAnts(int[][] ants, int[][] dists)
  338.     {
  339.       for (int i = 0; i < ants.Length; ++i)
  340.       {
  341.         Console.Write(i + ": [ ");
  342.  
  343.         for (int j = 0; j < 4; ++j)
  344.           Console.Write(ants[i][j] + " ");
  345.  
  346.         Console.Write(". . . ");
  347.  
  348.         for (int j = ants[i].Length - 4; j < ants[i].Length; ++j)
  349.           Console.Write(ants[i][j] + " ");
  350.  
  351.         Console.Write("] len = ");
  352.         double len = Length(ants[i], dists);
  353.         Console.Write(len.ToString("F1"));
  354.         Console.WriteLine("");
  355.       }
  356.     }
  357.  
  358.     static void Display(double[][] pheromones)
  359.     {
  360.       for (int i = 0; i < pheromones.Length; ++i)
  361.       {
  362.         Console.Write(i + ": ");
  363.         for (int j = 0; j < pheromones[i].Length; ++j)
  364.         {
  365.           Console.Write(pheromones[i][j].ToString("F4").PadLeft(8) + " ");
  366.         }
  367.         Console.WriteLine("");
  368.       }
  369.  
  370.     }
  371.  
  372.   } // class AntColonyProgram
  373.  
  374. } // ns
  375.  
Time limit exceeded #stdin #stdout 5s 36744KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Begin Ant Colony Optimization demo

Number cities in problem = 60

Number ants = 4
Maximum time = 1000

Alpha (pheromone influence) = 3
Beta (local node influence) = 2
Rho (pheromone evaporation coefficient) = 0.01
Q (pheromone deposit factor) = 2.00

Initialing dummy graph distances

Initialing ants to random trails

0: [ 51 37 2 21 . . . 27 35 58 45 ] len = 289.0
1: [ 24 45 9 59 . . . 32 39 34 40 ] len = 259.0
2: [ 47 33 9 36 . . . 39 29 34 58 ] len = 275.0
3: [ 48 59 44 56 . . . 10 33 7 16 ] len = 271.0

Best initial trail length: 259.0

Initializing pheromones on trails

Entering UpdateAnts - UpdatePheromones loop

New best length of 251.0 found at time 0
New best length of 238.0 found at time 1
New best length of 235.0 found at time 38
New best length of 226.0 found at time 51
New best length of 225.0 found at time 101
New best length of 224.0 found at time 134
New best length of 206.0 found at time 140
New best length of 202.0 found at time 141
New best length of 199.0 found at time 184
New best length of 193.0 found at time 216
New best length of 186.0 found at time 228
New best length of 181.0 found at time 236
New best length of 167.0 found at time 240
New best length of 164.0 found at time 248
New best length of 151.0 found at time 258
New best length of 137.0 found at time 271
New best length of 132.0 found at time 301
New best length of 125.0 found at time 323
New best length of 121.0 found at time 354
New best length of 118.0 found at time 356
New best length of 116.0 found at time 358
New best length of 103.0 found at time 360
New best length of 98.0 found at time 399
New best length of 97.0 found at time 412
New best length of 88.0 found at time 419
New best length of 85.0 found at time 426
New best length of 84.0 found at time 429
New best length of 83.0 found at time 432
New best length of 75.0 found at time 434
New best length of 71.0 found at time 443
New best length of 70.0 found at time 467
New best length of 69.0 found at time 468
New best length of 68.0 found at time 471
New best length of 67.0 found at time 476
New best length of 65.0 found at time 478
New best length of 63.0 found at time 479
New best length of 62.0 found at time 496
https://ideone.com/NRx8er
language:
C# (gmcs 5.20.1)
created:
11 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!