Machine Learning - Ant Colony Optimization for the Travelling Salesman Problem

The traveling salesman problem (TSP) is a deceptively simple combinatorial problem. It can be said very simply: a salesman spends his time visiting n cities cyclically. In one tour each city should only be visited once and the last city is the one the salesman started.
The question is: in what order should he visit the cities to minimize the distance traveled? TSP became a benchmark for many new approaches in combinatorial optimization.

This approach of solving the TSP is simulating the behavior of an ant colony. Even though ants have very limited skills their social behaviour in their colony can enable them to solve complex problems as through group behaviour. The intelligence of the global society arises from self organization mechanisms, based on the indirect communication between individuals through pheromones. The TSP routing problem can be seen as a case that requires a self organization type of algorithm, in order to handle the problem dynamics. The simulation show how the ant colony optimization is able to solve the different possible routing cases. This version is based on Ameya Joshi's's and Jared Giles's solutions.

Calculate and return best tour of given cities.


this.getTour = function( cities, numAnts, numTours, alpha, beta, rho, pro )
{
	var numCities = cities.length;

	if( numCities < 2 )
	{
		throw new Error( 'number of cities must be > 1.' )
	}

	numAnts = numAnts || 20;
	numTours = numTours || 500;

	_alpha = alpha || 1.0;
	_beta = beta || 5.0;
	_rho = rho || 0.5;
	_phe = 1.0 / numCities;
	_pro = pro || 100;

	_bestTourLength = Number.MAX_VALUE; // init with longest possible tour

	_cities = cities;
	_ants = [];
	_distances = newArray2D( numCities, numCities, 0.0 ); // (from, to)
	_pheromones = newArray2D( numCities, numCities, _phe ); // (from, to)

	var from, to, i;

	// Compute the distances for each of the cities on the map
	for( from = 0; from < numCities; ++from )
	{
		for( to = 0; to < numCities; to++ )
		{
			if( to != from && _distances[ from ][ to ] == 0.0 )
			{
				var xd = Math.abs( _cities[ from ].x - _cities[ to ].x );
				var yd = Math.abs( _cities[ from ].y - _cities[ to ].y );

				_distances[ from ][ to ] = Math.sqrt( (xd * xd) + (yd * yd) );
				_distances[ to ][ from ] = _distances[ from ][ to ];
			}
		}
	}

	// initialize the ants
	to = 0;

	for( i = 0; i < numAnts; ++i )
	{
		// distribute the ants to each of the cities uniformly
		if( to == numCities )
		{
			to = 0;
		}

		var ant = {
			curCity: to++,
			nextCity: -1,
			avoid: new Array( numCities ),
			pathIndex: 1,
			path: new Array( numCities ),
			tourLength: 0.0
		};

		for( from = 0; from < numCities; ++from )
		{
			ant.avoid[ from ] = 0;
			ant.path[ from ] = -1;
		}

		ant.path[ 0 ] = ant.curCity;

		// Mark ant's current city to be avoided
		ant.avoid[ ant.curCity ] = 1;

		_ants.push( ant );
	}

	var maxTime = numTours * numCities;
	var time = 0;
	var log = [];

	while( time++ < maxTime )
	{
		if( simulateAnts() == 0 )
		{
			updateTrails();

			if( time != maxTime )
			{
				restartAnts();
			}

			log.push( { time: time, best: _bestTourLength } );
		}
	}

	var tour = [];

	// tour through cities
	for( var j = 0; j < numCities; ++j )
	{
		tour.push( _cities[ _ants[ _bestIndex ].path[ j ] ] );
	}

	// back to tour origin
	tour.push( _cities[ _ants[ _bestIndex ].path[ 0 ] ] );

	return { cities: _cities, tour: tour, bestTour: _bestTourLength, pheromone: _pheromones, log: log };
};
					

Reinitialize the ant population to start another tour around the graph.


function restartAnts()
{
	var numCities = _cities.length;
	var numAnts = _ants.length;
	var to = 0;

	for( var i = 0; i < numAnts; ++i )
	{
		var ant = _ants[ i ];

		if( ant.tourLength < _bestTourLength )
		{
			_bestTourLength = ant.tourLength;
			_bestIndex = i;
		}

		ant.nextCity = -1;
		ant.tourLength = 0.0;

		for( var j = 0; j < numCities; j++ )
		{
			ant.avoid[ j ] = 0;
			ant.path[ j ] = -1;
		}

		if( to == numCities )
		{
			to = 0;
		}

		ant.curCity = to++;
		ant.pathIndex = 1;
		ant.path[ 0 ] = ant.curCity;
		ant.avoid[ ant.curCity ] = 1;
	}
}
					

Compute the denominator for the path probability equation (concentration of pheromone of the current path over the sum of all concentrations of available paths).


function antProduct( from, to )
{
   var p = Math.pow( _pheromones[ from ][ to ], _alpha );
   var d = Math.pow( ( 1.0 / _distances[ from ][ to ] ), _beta );

   return p * d;
}
					

Using the path probability selection algorithm and the current pheromone levels of the graph, select the next city the ant will travel to.


function selectNextCity( ant )
{
  var from, to;
  var d = 0.0;
  var numCities = _cities.length;

  // Choose the next city to visit
  from = _ants[ ant ].curCity;

  // Compute denomination
  for( to = 0; to < numCities; ++to )
  {
	  if( _ants[ ant ].avoid[ to ] == 0 )
	  {
		  d += antProduct( from, to );
	  }
  }

  do {
	  to++;

	  if( to >= numCities )
	  {
		  to = 0;
	  }

	  if( _ants[ ant ].avoid[ to ] == 0 )
	  {
		  var p = antProduct( from, to ) / d;

		  if( random() < p )
		  {
			  break;
		  }
	  }

  } while( true );

  return to;
}
					

Simulate a single step for each ant in the population. This function will return zero once all ants have completed their tours.


function simulateAnts()
{
  var moving = 0;

  var numCities = _cities.length;
  var numAnts = _ants.length;

  for( var i = 0; i < numAnts; ++i )
  {
	  var ant = _ants[ i ];

	  // ensure this ant still has cities to visit
	  if( ant.pathIndex < numCities )
	  {
		  ant.nextCity = selectNextCity( i );
		  ant.avoid[ ant.nextCity ] = 1;
		  ant.path[ ant.pathIndex++ ] = ant.nextCity;
		  ant.tourLength += _distances[ ant.curCity ][ ant.nextCity ];

		  // handle the final case (last city to first)
		  if( ant.pathIndex == numCities )
		  {
			  ant.tourLength += _distances[ ant.path[ numCities - 1 ] ][ ant.path[ 0 ] ];
		  }

		  ant.curCity = ant.nextCity;

		  moving++;
	  }
  }

  return moving;
}
					

Update the pheromone levels on each arc based upon the number of ants that have travelled over it, including evaporation of existing pheromone.


function updateTrails()
{
  var from;
  var to;

  var numCities = _cities.length;
  var numAnts = _ants.length;

  // Pheromone Evaporation
  for( from = 0; from < numCities; ++from )
  {
	  for( to = 0; to < numCities; ++to )
	  {
		  if( from != to )
		  {
			  _pheromones[ from ][ to ] *= 1.0 - _rho;

			  if( _pheromones[ from ][ to ] < 0.0 )
			  {
				  _pheromones[ from ][ to ] = _phe;
			  }
		  }
	  }
  }

  // add new pheromone to the trails. look at the tours of each ant
  for( var i = 0; i < numAnts; ++i )
  {
	  var ant = _ants[ i ];

	  // update each leg of the tour
	  for( var j = 0; j < numCities; ++j )
	  {
		  if( j < numCities - 1 )
		  {
			  from = ant.path[ j ];
			  to = ant.path[ j + 1 ];
		  }
		  else
		  {
			  from = ant.path[ j ];
			  to = ant.path[ 0 ];
		  }

		  _pheromones[ from ][ to ] += _pro / ant.tourLength;
		  _pheromones[ to ][ from ] = _pheromones[ from ][ to ];
	  }
  }

  for( from = 0; from < numCities; ++from )
  {
	  for( to = 0; to < numCities; ++to )
	  {
		  _pheromones[ from ][ to ] *= _rho;
	  }
  }
}