using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
public class AntColonyProgram
private static Random random = new Random(0);
private static int alpha = 3;
private static int beta = 2;
private static double rho = 0.03;
private static double Q = 2.0;
public static void Main(string[] args)
Console.WriteLine("\nBegin Ant Colony Optimization demo\n");
Console.WriteLine("Number cities in problem = " + numCities);
Console.WriteLine("\nNumber ants = " + numAnts);
Console.WriteLine("Maximum time = " + maxTime);
Console.WriteLine("\nAlpha (pheromone influence) = " + alpha);
Console.WriteLine("Beta (local node influence) = " + beta);
Console.WriteLine("Rho (pheromone evaporation coefficient) = " + rho.ToString("F2"));
Console.WriteLine("Q (pheromone deposit factor) = " + Q.ToString("F2"));
Console.WriteLine("\nInitialing dummy graph distances");
int[][] dists = MakeGraphDistances(numCities);
Console.WriteLine("\nInitialing ants to random trails\n");
int[][] ants = InitAnts(numAnts, numCities);
int[] bestTrail = AntColonyProgram.BestTrail(ants, dists);
double bestLength = Length(bestTrail, dists);
Console.Write("\nBest initial trail length: " + bestLength.ToString("F1") + "\n");
Console.WriteLine("\nInitializing pheromones on trails");
double[][] pheromones = InitPheromones(numCities);
Console.WriteLine("\nEntering UpdateAnts - UpdatePheromones loop\n");
UpdateAnts(ants, pheromones, dists);
UpdatePheromones(pheromones, ants, dists);
int[] currBestTrail = AntColonyProgram.BestTrail(ants, dists);
double currBestLength = Length(currBestTrail, dists);
if (currBestLength < bestLength)
bestLength = currBestLength;
bestTrail = currBestTrail;
Console.WriteLine("New best length of " + bestLength.ToString("F1") + " found at time " + time);
Console.WriteLine("\nTime complete");
Console.WriteLine("\nBest trail found:");
Console.WriteLine("\nLength of best trail found: " + bestLength.ToString("F1"));
Console.WriteLine("\nEnd Ant Colony Optimization demo\n");
Console.WriteLine(ex.Message);
private static int[][] InitAnts(int numAnts, int numCities)
int[][] ants = new int[numAnts][];
for (int k = 0; k <= numAnts - 1; k++)
int start = random.Next(0, numCities);
ants[k] = RandomTrail(start, numCities);
private static int[] RandomTrail(int start, int numCities)
int[] trail = new int[numCities];
for (int i = 0; i <= numCities - 1; i++)
for (int i = 0; i <= numCities - 1; i++)
int r = random.Next(i, numCities);
int idx = IndexOfTarget(trail, start);
private static int IndexOfTarget(int[] trail, int target)
for (int i = 0; i <= trail.Length - 1; i++)
throw new Exception("Target not found in IndexOfTarget");
private static double Length(int[] trail, int[][] dists)
for (int i = 0; i <= trail.Length - 2; i++)
result += Distance(trail[i], trail[i + 1], dists);
private static int[] BestTrail(int[][] ants, int[][] dists)
double bestLength = Length(ants[0], dists);
for (int k = 1; k <= ants.Length - 1; k++)
double len = Length(ants[k], dists);
int numCities = ants[0].Length;
int[] bestTrail_Renamed = new int[numCities];
ants[idxBestLength].CopyTo(bestTrail_Renamed, 0);
return bestTrail_Renamed;
private static double[][] InitPheromones(int numCities)
double[][] pheromones = new double[numCities][];
for (int i = 0; i <= numCities - 1; i++)
pheromones[i] = new double[numCities];
for (int i = 0; i <= pheromones.Length - 1; i++)
for (int j = 0; j <= pheromones[i].Length - 1; j++)
private static void UpdateAnts(int[][] ants, double[][] pheromones, int[][] dists)
int numCities = pheromones.Length;
for (int k = 0; k <= ants.Length - 1; k++)
int start = random.Next(0, numCities);
int[] newTrail = BuildTrail(k, start, pheromones, dists);
private static int[] BuildTrail(int k, int start, double[][] pheromones, int[][] dists)
int numCities = pheromones.Length;
int[] trail = new int[numCities];
bool[] visited = new bool[numCities];
for (int i = 0; i <= numCities - 2; i++)
int next = NextCity(k, cityX, visited, pheromones, dists);
private static int NextCity(int k, int cityX, bool[] visited, double[][] pheromones, int[][] dists)
double[] probs = MoveProbs(k, cityX, visited, pheromones, dists);
double[] cumul = new double[probs.Length + 1];
for (int i = 0; i <= probs.Length - 1; i++)
cumul[i + 1] = cumul[i] + probs[i];
double p = random.NextDouble();
for (int i = 0; i <= cumul.Length - 2; i++)
if (p >= cumul[i] && p < cumul[i + 1])
throw new Exception("Failure to return valid city in NextCity");
private static double[] MoveProbs(int k, int cityX, bool[] visited, double[][] pheromones, int[][] dists)
int numCities = pheromones.Length;
double[] taueta = new double[numCities];
for (int i = 0; i <= taueta.Length - 1; i++)
else if (visited[i] == true)
taueta[i] = Math.Pow(pheromones[cityX][i], alpha) * Math.Pow((1.0 / Distance(cityX, i, dists)), beta);
else if (taueta[i] > (double.MaxValue / (numCities * 100)))
taueta[i] = double.MaxValue / (numCities * 100);
double[] probs = new double[numCities];
for (int i = 0; i <= probs.Length - 1; i++)
probs[i] = taueta[i] / sum;
private static void UpdatePheromones(double[][] pheromones, int[][] ants, int[][] dists)
for (int i = 0; i <= pheromones.Length - 1; i++)
for (int j = i + 1; j <= pheromones[i].Length - 1; j++)
for (int k = 0; k <= ants.Length - 1; k++)
double length = AntColonyProgram.Length(ants[k], dists);
double decrease = (1.0 - rho) * pheromones[i][j];
if (EdgeInTrail(i, j, ants[k]) == true)
pheromones[i][j] = decrease + increase;
if (pheromones[i][j] < 0.0001)
pheromones[i][j] = 0.0001;
else if (pheromones[i][j] > 100000.0)
pheromones[i][j] = 100000.0;
pheromones[j][i] = pheromones[i][j];
private static bool EdgeInTrail(int cityX, int cityY, int[] trail)
int lastIndex = trail.Length - 1;
int idx = IndexOfTarget(trail, cityX);
if (idx == 0 && trail[1] == cityY)
else if (idx == 0 && trail[lastIndex] == cityY)
else if (idx == lastIndex && trail[lastIndex - 1] == cityY)
else if (idx == lastIndex && trail[0] == cityY)
else if (idx == lastIndex)
else if (trail[idx - 1] == cityY)
else if (trail[idx + 1] == cityY)
private static int[][] MakeGraphDistances(int numCities)
int[][] dists = new int[numCities][];
for (int i = 0; i <= dists.Length - 1; i++)
dists[i] = new int[numCities];
for (int i = 0; i <= numCities - 1; i++)
for (int j = i + 1; j <= numCities - 1; j++)
int d = random.Next(1, 9);
private static double Distance(int cityX, int cityY, int[][] dists)
return dists[cityX][cityY];
private static void Display(int[] trail)
for (int i = 0; i <= trail.Length - 1; i++)
Console.Write(trail[i] + " ");
if (i > 0 && i % 20 == 0)
private static void ShowAnts(int[][] ants, int[][] dists)
for (int i = 0; i <= ants.Length - 1; i++)
Console.Write(i + ": [ ");
for (int j = 0; j <= 3; j++)
Console.Write(ants[i][j] + " ");
for (int j = ants[i].Length - 4; j <= ants[i].Length - 1; j++)
Console.Write(ants[i][j] + " ");
Console.Write("] len = ");
double len = Length(ants[i], dists);
Console.Write(len.ToString("F1"));
private static void Display(double[][] pheromones)
for (int i = 0; i <= pheromones.Length - 1; i++)
for (int j = 0; j <= pheromones[i].Length - 1; j++)
Console.Write(pheromones[i][j].ToString("F4").PadLeft(8) + " ");