using System; using System.Collections; using System.Linq; namespace SolverSpace { public class Solver { //Instance Variables private double xcoord, ycoord; private bool visited; private double number; //Properties public double Xcoord { get { return xcoord; } set { xcoord = value; } } //End Xcoord property public double Ycoord { get { return ycoord; } set { ycoord = value; } } //End Ycoord property public bool Visited { get { return visited; } set { visited = value; } } //End Visited property public double Number { get { return number; } set { number = value; } } //End Number property //City Constructor public Solver (int number, double xassign, double yassign) { Number = number; Xcoord = xassign; Ycoord = yassign; }//End City constructor //Methods public static double[,] CalculateDistance(object[] data) { int i = 0, j= 0; double xi = 0, xj = 0; double yi = 0, yj= 0; double[,] distances = new double[data.GetLength(0),data.GetLength(0)]; foreach (Solver C in data) { i++; //Increment row counter foreach (Solver C2 in data) { xi = C.Xcoord; yi = C.Ycoord; xj = C2.Xcoord; yj = C2.Ycoord; distances[i-1,j] = Math.Sqrt(Math.Pow((yj-yi),2)+Math.Pow((xj-xi),2)); //Calculate distance between cities if (j < data.GetLength(0) -1) //increment and reset column counter j++; else j = 0; } } return distances; //Returns a double[,] array with the distances between each of the cities with respect to others }//End CalculateDistance method public static object[] RetrieveData(double[,] table) { object[] cities = new object[table.GetLength(0)]; //create array to store the cities //City coordinates arranger for (int i = 0; i <= table.GetLength(0)-1; i++) { for(int j = 0; j<= table.GetLength(1)-3; j++) { Solver c = new Solver(Convert.ToInt32(table[i,j]),table[i, j + 1], table[i, j + 2 ]); //assign each city a number and X and Y coordinates cities[i] = c; } } return cities; //Returns an object[] array with cities. Each object represents a city. } //End method RetrieveData public static int[] GSolver(object[] cities, double[,] distances) { //Greedy Variables int beta = 7; double[] pij = new double[cities.GetLength(0)]; double[] decision = new double[cities.GetLength(0)]; double[] Tij = new double[cities.GetLength(0)]; double nij = 0, highestProb = 0; double localdecisionsum = 0; //Logic control variables int i = 0, h = 0, initCity = 0; int acum = 0, d = 1, l = 0 , t = 0; bool visit = false; //Tour variables Solver[] gCities = new Solver[cities.GetLength(0)]; int currentcity = 0, nextCity = 0; double current_tour_length = 0; int[] tour = new int[cities.GetLength(0) + 1]; int[] result = new int[cities.GetLength(0) + 2]; double shortest_tour = 0; //Instance the objects inside the method for further handling foreach (Solver C in cities) { gCities[t] = new Solver(Convert.ToInt32(C.Number), C.Xcoord, C.Ycoord); t++; } // End foreach C //Initialise Tij array values to a small constant for (i = 0; i < Tij.GetLength(0); i++) { Tij[i] = 1; } // End for i //This for represents each swarm whre number of ants = number of cities //Since this is the greedy, It will only make one swarm and select the shortest tour amongst all the tours //Therefore iterations =1 for (int num = 0; num < gCities.GetLength(0); num++) { //Restart condition variables acum = 0; d = 1; current_tour_length = 0; localdecisionsum = 0; highestProb = 0; visit = false; foreach (Solver R in gCities) { R.Visited = false; } // End foreach R //Define ant K starting city initCity = Convert.ToInt32(gCities[num].Number - 1); nextCity = initCity; tour[0] = initCity + 1; gCities[initCity].Visited = true; //Loop starts here for ant k while (acum < gCities.GetLength(0) - 1) { currentcity = nextCity; visit = false; //Calculate the numerator factor for each arc, using Tij and Nij (both pheromone and distance information) for (int j = 0; j < gCities.GetLength(0); j++) { //Avoid division by zero if (distances[currentcity, j] != 0) nij = Math.Pow(1 / distances[currentcity, j], beta); else nij = 0.000001; if (gCities[j].Visited == false) decision[j] = Tij[j] * nij; else decision[j] = 0; //Assign zero to a visited city //Calculate local probability sum, which is the denominator of the pij (sum of Tij * Nij) localdecisionsum += decision[j]; } //End for j //Calculate the real probability to go to each city //The highest number of this array will be the next visited city for (int k = 0; k < gCities.GetLength(0); k++) { if (gCities[k].Number == gCities[currentcity].Number || gCities[k].Visited == true) pij[k] = 0; if (gCities[k].Visited == false) pij[k] = decision[k] / localdecisionsum; } //End for k //Store the highest probability to obtain index of the nextCity to visit highestProb = pij.Max(); //Identify the index of the highes probability while (visit == false) { if (highestProb == pij[l] && gCities[l].visited == false) { nextCity = l; //Store the next visited city gCities[l].Visited = true; //Indicate that nextCity has now been visited current_tour_length += distances[currentcity, nextCity]; tour[d] = l + 1; d++; //Increment tour control counter acum++; // Increment loop control counter visit = true; l = 0; break; //Break for after finding the correct one } else { pij[l] = 0; highestProb = pij.Max(); l++; //Inrcement loop counter } } // end while visit l = 0;//Restart while visit counter } //End while acum //Store the tour path //Close the path by returning to the initial city current_tour_length += distances[nextCity, initCity]; tour[tour.GetLength(0) - 1] = Convert.ToInt32(gCities[initCity].Number); if (h == 0) { shortest_tour = Convert.ToInt32(current_tour_length); for (int r = 0; r < tour.GetLength(0); r++) { result[r] = tour[r]; } h++; } if (current_tour_length < shortest_tour) { shortest_tour = current_tour_length; for (int c = 0; c < tour.GetLength(0); c++) { result[c] = tour[c]; } } // end If to find shortest tour } // End for num result[cities.GetLength(0) + 1] = Convert.ToInt32(shortest_tour); return result; //Return an int array with the data of the shortest tour. Its length and the trajectory } //End GSolver Method public static int[] ACOSolver(object[] cities, double[,] distances, int runs) { //ACO Variables int beta = 7, iterations = runs ; double evaporationrate = 0.5; double[] pij = new double[cities.GetLength(0)]; double[] acumpij = new double[cities.GetLength(0) + 1]; double[] decision = new double[cities.GetLength(0)]; double[,] Tij = new double[cities.GetLength(0), cities.GetLength(0)]; double[,] deltaTij = new double[cities.GetLength(0), cities.GetLength(0)]; double nij = 0, highestProb = 0; double localdecisionsum = 0; double[] shortestPaths = new double[iterations]; int[,] swarmShortestTours = new int[iterations, cities.GetLength(0) + 1]; int Q = 3; Random randomNum = new Random(); // Random number generator int[,] antMemory = new int[cities.GetLength(0), cities.GetLength(0) + 1]; //Logic control variables int i = 0, h = 0, t = 0, initCity = 0, ant = 0, bestTourIndex = 0 ; int acum = 0 , d = 1 , x = 0 , l = 0, city = 0 , q = 0, s = 0; int betweenLeft = 0, betweenRight = 0; bool visit = false; //Tour variables Solver[] gCities = new Solver[cities.GetLength(0)]; int currentcity = 0, nextCity = 0; double current_tour_length = 0; int[] currenttour = new int[cities.GetLength(0) + 1]; int[] shortestCurrentTour = new int[cities.GetLength(0) + 1]; int[] result = new int[cities.GetLength(0) + 2]; double[] paths = new double[cities.GetLength(0)]; double shortest_tour = 0; //Instance the objects inside the method for further handling foreach (Solver C in cities) { gCities[t] = new Solver(Convert.ToInt32(C.Number), C.Xcoord, C.Ycoord); t++; } // End foreach C //Initialise Tij to a small value for (i = 0; i < Tij.GetLength(0); i++) { for (int j = 0; j < Tij.GetLength(1); j++) { Tij[i,j] = 1; } } // End for i //Initialise cumulative probability value acumpij[0] = 0; for (t = 0; t <=iterations; t++) { //Restart ant number counter ant = 0; x = 0; //Restart path storing variable //Restart Ant memory and paths for new tours for (int clear = 0; clear < antMemory.GetLength(0); clear++) { for (int memory = 0; memory < antMemory.GetLength(1); memory++) { antMemory[clear, memory] = 0; } } //This for each represents each swarm whre number of ants = number of cities for (int K = 0; K < gCities.GetLength(0); K++) { //Restart condition variables acum = 0; d = 1; current_tour_length = 0; localdecisionsum = 0; highestProb = 0; visit = false; city = 0; // Restart ant memory index trail counter //Initialise cumulative probability for (int cumulative = 1; cumulative < acumpij.GetLength(0); cumulative++) { acumpij[cumulative] = 0; } foreach (Solver R in gCities) { R.Visited = false; } // End foreach R //Define ant K starting city initCity = randomNum.Next((int)gCities[0].Number - 1, (int)gCities[gCities.GetLength(0)-1].Number); nextCity = initCity; currenttour[0] = initCity + 1; antMemory[ant, city] = initCity + 1; gCities[initCity].Visited = true; //Loop starts here for ant k while (acum < gCities.GetLength(0) - 1) { currentcity = nextCity; visit = false; //Restart cumulative probability for (int cumulative = 1; cumulative < acumpij.GetLength(0); cumulative++) { acumpij[cumulative] = 0; } //Calculate the numerator factor for each arc, using Tij and Nij (both pheromone and distance information) for (int j = 0; j < gCities.GetLength(0); j++) { //Avoid division by zero if (distances[currentcity, j] != 0) nij = Math.Pow(1 / distances[currentcity, j], beta); else nij = 0.000001; if (gCities[j].Visited == false) decision[j] = Tij[currentcity, j] * nij; else decision[j] = 0; //Assign zero to a visited city //Calculate local probability sum, which is the denominator of the pij (sum of Tij * Nij) localdecisionsum += decision[j]; } //End for j //Calculate the real probability to go to each city for (int k = 0; k < gCities.GetLength(0); k++) { if (gCities[k].Number == gCities[currentcity].Number || gCities[k].Visited == true) pij[k] = 0; if (gCities[k].Visited == false) pij[k] = decision[k] / localdecisionsum; } //End for k //Generate cumulative probability for (int cumulative = 1; cumulative < acumpij.GetLength(0); cumulative++) { acumpij[cumulative] += acumpij[cumulative - 1] + pij[cumulative - 1]; } //Generate random P number highestProb = randomNum.NextDouble(); //Determine between which cities the probability is while (highestProb > acumpij[s]) { betweenLeft = s; s++; //Increment cumulative probability array counter if (s > pij.GetLength(0)) { betweenLeft = pij.GetLength(0) - 2; betweenRight = pij.GetLength(0) - 1; break; } } if (s < pij.GetLength(0)) betweenRight = s; s = 0; //Decide which nearest city to visit if (betweenLeft == 0) highestProb = pij[betweenRight - 1]; else { if(betweenRight == 0) { highestProb = pij[betweenLeft - 1]; } else { if (pij[betweenLeft - 1] > pij[betweenRight - 1]) highestProb = pij[betweenLeft - 1]; else if (pij[betweenLeft - 1] < pij[betweenRight - 1]) highestProb = pij[betweenRight - 1]; } } //Store the highest probability to obtain index of the nextCity to visit //Identify the index of the highest probability while (visit == false) { //restart to prevent out of range index problem if (l > gCities.GetLength(0) - 1) l = 0; if (highestProb == pij[l] && gCities[l].visited == false) { nextCity = l; //Store the next visited city gCities[l].Visited = true; //Indicate that nextCity has now been visited current_tour_length += distances[currentcity, nextCity]; currenttour[d] = l + 1; city++; antMemory[ant, city] = l + 1; d++; //Increment tour control counter acum++; // Increment loop control counter visit = true; l = 0; break; //Break for after finding the correct one } else { pij[l] = 0; highestProb = pij.Max(); l++; //Inrcement loop counter } } // end while visit l = 0;//Restart while visit counter } //End while acum //Store the tour path //Close the path by returning to the initial city current_tour_length += distances[nextCity, initCity]; currenttour[currenttour.GetLength(0) - 1] = Convert.ToInt32(gCities[initCity].Number); //Store ant memory counter antMemory[ant, city + 1] = Convert.ToInt32(gCities[initCity].Number); //Store the paths of each ant paths[x] = current_tour_length; x++; // Increment counter //Initialize shortest tour value for further comparison if (h == 0) { shortest_tour = current_tour_length; for (int r = 0; r < currenttour.GetLength(0); r++) { shortestCurrentTour[r] = currenttour[r]; } h++; } //Compare each new tour to the shortest swarm tour and assign it if (current_tour_length < shortest_tour) { shortest_tour = current_tour_length; for (int c = 0; c < currenttour.GetLength(0); c++) { shortestCurrentTour[c] = currenttour[c]; } } // end If to find shortest tour //Next ant ant++; } // End for K //Store the shortest path of each iteration if (q < shortestPaths.GetLength(0)) { shortestPaths[q] = shortest_tour; for (int w = 0; w < shortestCurrentTour.GetLength(0); w++ ) swarmShortestTours[q, w] = shortestCurrentTour[w]; q++;// Increment shortesPaths tour counter } //Update pheromone values //Update Tij values //Part 1 sums all of the pheromone trails where each ant has been for (i = 0; i < antMemory.GetLength(0); i++) { for (int j = 0; j < antMemory.GetLength(1) - 1; j++) { int index1 = antMemory[i, j] - 1; int index2 = antMemory[i, j + 1] - 1; deltaTij[index1, index2] += Q / paths[x - 1]; } } // End for Tij Part 1 //Part 2 triggers evaporation rate for (i = 0; i < antMemory.GetLength(0); i++) { for (int j = 0; j < antMemory.GetLength(1) - 1; j++) { int index1 = antMemory[i, j] - 1; int index2 = antMemory[i, j + 1] - 1; Tij[index1, index2] = ((1 - evaporationrate) * Tij[index1, index2]) + deltaTij[index1,index2]; } } // End for Tij Part 2 } // End for t //Determine the best tour and its length shortest_tour = shortestPaths.Min(); for (int sweep = 0; sweep < shortestPaths.GetLength(0); sweep++) { if (shortest_tour == shortestPaths[sweep]) { bestTourIndex = sweep; } } for (int sweep = 0; sweep < swarmShortestTours.GetLength(1); sweep++) { result[sweep] = swarmShortestTours[bestTourIndex, sweep]; } //Store the tour length result[result.GetLength(0) - 1] = Convert.ToInt32(shortest_tour); return result; } //End ACOSolver Method }//End class City } //End namespace