Click here to Skip to main content
15,867,453 members
Articles / General Programming / Performance
Tip/Trick

TSP using ACO

Rate me:
Please Sign up or sign in to vote.
1.19/5 (4 votes)
24 May 2023CPOL2 min read 6K   4   11
Traveling Salesman Problem using Ant Colony Optimization
We present the novel algorithm realization on object-oriented basis with optimal performance for solving TSP using ACO.

Introduction

Usually, the NP-complete problems are solved using neural networks or other artificial algorithms. In this tip, we present ACO modeling software to solve NP-complete problems like TSP. As they're of polynomial nature, the parameters can be adjusted for swarm optimization for each ant defined in a separate class.

Background

The background behind this solution is the list of original scientific articles by Marco Dorigo who proposed the Swarm Algorithm (or ACO, for short). We present the realization on object-oriented basis.

Using the Code

The global variables are defined as follows including the matrixes or 2-dimensional arrays for statistical computations:

C++
#include <cstdio>

#include <vector>

#include <cstdlib>

#include <set>

#include <ctime>

using namespace std;

const int max_n = 4000;
const int max_ant = 2000;

double tau[max_n][max_n];
double eta[max_n][max_n];
double len[max_n][max_n];

double rho = 0.5;
double Q = 100;

int n, m, nc;

Here, the matrixes define the behavior of the artificial ants with parameters like rho and Q which are variable. Where n is the number of cities in TSP problem, m is number of ants and nc is the number of iterations of algorithm after finding first successful solution for the ant starting from the random city and visiting the nearest city at each iteration of algorithm.

We define object-oriented model as follows for artificial ant class as follows, there the path is the current path, along which the ant moves, and b_can is the matrix of unvisited cities, t_len variable stands for the length of the current path and start is a starting town:

C++
class Ant {
public:
  int start;
  vector < int > path;
  bool b_can[max_n];
  double t_len = 0;
  
  Ant() {
  	for (int i = 0; i < max_n; ++i) b_can[i] = true;
  }
  Ant(int _start) {
    start = _start;
    path.push_back(start);
	for (int i = 0; i < max_n; ++i) b_can[i] = true;
  }
  bool can(int t) {
  	return b_can[t];
  }
  int next() {
    int s = path[path.size() - 1];
    int ci = -1;
    double vmax = 0, vall = 0;
    for (int i = 0; i < n; ++i)
      if (can(i)) {
        vall += tau[s][i] * eta[s][i];
        if ((tau[s][i] * eta[s][i]) > vmax || ci < 0) {
          ci = i;
          vmax = tau[s][i] * eta[s][i];
        }
      }
    return ci;
  }
  void reuse() {
  	for (int i = 0; i < path.size(); ++i) {
  		b_can[path[i]] = true;
	}
  	
    while (path.size() > 0) {
    	path.pop_back();
	}
	
    path.push_back(start);
    
    b_can[start] = false;
    
    t_len = 0;
  }
  double getlen() {
    return t_len;
  }
  void step() {
    double tlen = getlen();
    for (int i = 1; i < path.size(); ++i) {
      int src = path[i - 1];
      int dst = path[i];
      tau[src][dst] = tau[src][dst] * rho + Q / tlen;
    }
  }
  void step(int t) {
    path.push_back(t);
    
    b_can[t] = false;
    
    t_len += len[path[path.size() - 2]][path[path.size() - 1]];
  }
};

The step() is a common procedure for each ant to make step to next city which is not in the list according to the best solution in the next() function.

The can() function shows if the candidate city can be visited at the current step of algorithm for the given ant. The reuse() function resets the internal variables of the entity in Ant class. As it can be seen from the above, the algorithm for each ant works as follows: each ant selects the candidate city according to the best value in next() function and if it's possible, this city is added to the list and the current path (defined by STL vector<int> path variable). If no path was found, the algorithm resets all variables for the ant, otherwise this can be done by implementing the new ant instantiation. The length of the tour is defined by the getlen() function.

The initialization is as follows for length between each towns defined by len array, and tau and eta as the parameters for artifical ants to make right decisions on each step of iteration of algorithm.

C++
scanf("%d", &n);
for (i = 0; i < n; ++i)
  for (j = 0; j < n; ++j) {
    scanf("%lf", len[i] + j);
    eta[i][j] = 1.0 / len[i][j];
    tau[i][j] = 1.0;
  }

srand(time(NULL));

Ant * ants = new Ant[m];
for (i = 0; i < m; ++i)
  ants[i].start = random(n);
double sol = 1e+100;
int NC = 0;
vector < int > best_tour;
for (NC = 0; NC < nc; NC += best_tour.size() == n ? 1 : 0) {
  for (i = 0; i < m; ++i) ants[i].reuse();
  for (;;) {
    bool b_ok = false;
    int dec[max_ant];
    for (i = 0; i < m; ++i) {
      dec[i] = ants[i].next();
      if (dec[i] >= 0) {
        b_ok = true;
        ants[i].step(dec[i]);
      }
    }
    if (!b_ok) break;
  }
  for (i = 0; i < m; ++i) {
    ants[i].step();
    if (ants[i].path.size() == n) {
      double tlen = ants[i].getlen();
      if (tlen < sol) {
        sol = tlen;
        best_tour = ants[i].path;
      }
    }
  }
}

Here, vector best_tour is the solution to the problem which is further to be output or applied to other refinement.

Points of Interest

Thus, we have learned the swarm algorithm for solving NP-complete problem like TSP, which could be generalized for common cases also.

History

  • 26th October, 2022 - Initial release
  • 2nd November, 2022 - Removed links
  • 3rd November, 2022 - Links deleted
  • 4th November, 2022 - License changed

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



Comments and Discussions

 
SuggestionClass Implementation Pin
Rick York26-May-23 8:24
mveRick York26-May-23 8:24 
SuggestionVectors Pin
Rick York21-May-23 9:55
mveRick York21-May-23 9:55 
GeneralRe: Vectors Pin
Mirzakhmet Syzdykov24-May-23 13:48
professionalMirzakhmet Syzdykov24-May-23 13:48 
QuestionWhat happen to the MIT free of charge ? Pin
Jan Pedersen2-Nov-22 6:49
Jan Pedersen2-Nov-22 6:49 
AnswerRe: What happen to the MIT free of charge ? Pin
Mirzakhmet Syzdykov7-Nov-22 22:52
professionalMirzakhmet Syzdykov7-Nov-22 22:52 
Generalcomment Pin
Maniezzo26-Oct-22 23:26
professionalManiezzo26-Oct-22 23:26 
GeneralRe: comment Pin
Mirzakhmet Syzdykov2-Nov-22 1:21
professionalMirzakhmet Syzdykov2-Nov-22 1:21 
GeneralMy vote of 1 Pin
Maniezzo26-Oct-22 23:24
professionalManiezzo26-Oct-22 23:24 
GeneralRe: My vote of 1 Pin
Mirzakhmet Syzdykov2-Nov-22 1:22
professionalMirzakhmet Syzdykov2-Nov-22 1:22 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.