TSP using ACO

• Download source code - 444 KB
• Download demo - 1.4 MB

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:

#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:

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.

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

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