Introduction
Following on from a previous posting on Simulated Annealing applied to travelling salesman problems, here is a posting that carries on in a similar vein, this time focusing on genetic algorithms as our optimization technique of choice.
There is a wealth of information on genetic algorithms available online. For this reason I will keep the explanations to a minimum, since there is already plenty of information already out there explaining these concepts succinctly. A resource I found useful can be found at this links:
Genetic Alorithms for the Travelling Salesman Problem: A Review of Representations and Operators
Click the following video link to see the GA at work on the ‘Att48.tsp’ test problem:
Algorithm Overview
Unlike the simulated annealing / hill climbing methods that operate on a single tour, the genetic algorithm operates on a population of individual tours. For this implementation I start with a population of randomly generated tours, which have standard genetic operators crossover, mutation and selection applied to then over a set number of iterations in an attempt to improve the goodness of the population of tours over time.
Without going into the C++ implementation details, an explanation of how the algorithm works is as follows. Each successive population is evaluated in terms of its fitness. The shorter the overall tour distance, the higher its fitness. The program identifies the best solution in the population at each generation, logging its distance to a text file. Then a selection mechanism is used to obtain the better solutions, in this case a tournament selection mechanism is employed. After selection, pairs of tours are chosen arbitrarily and portions of their tour cities are exchanged in order to produce a new offspring. Also some mutation operators are employed to disrupt randomly selected tours so as to more effectively explore the solution space.
// Run the genetic algorithm
Tour* GeneticAlgorithm::Run( const int& iter )
{
bestIndex = Evaluate();
Tour* tour = pop.GetTour( bestIndex );
LogResult( tour->GetFitness(), iter, 10 );
Select();
Crossover();
Mutate();
return tour;
}
The PMX Crossover Operator
For this type of problem that consists of ordered lists of cities, the use of a direct exchange between tours to produce new offspring is not feasible without losing the given ordering. A number of techniques are available, the one chosen here is the partially matched crossover, or PMX for short.
In this method, two crossover points are arbitrarily selected and the PMX proceeds by position wise exchanges. The two crossover points give matching selection. It affects crossover by using position-by-position exchange operations. Here is the C++ implementation:
// Apply two-point crossover to selected Tour pair
void Population::Crossover( const int& index1,
const int& index2,
const int& point1,
const int& point2,
const int& bestIndex )
{
std::vector<int> offspr;
if ( point1 < 0 || point1 >= chrSize ) return;
if ( point2 < 0 || point2 >= chrSize ) return;
int p1 = point1;
int p2 = point2;
if ( p1 > p2 )
{
int tmp = p1;
p1 = p2;
p2 = tmp;
}
// Create new offspring to replace parent
Tour* tour1 = GetTour( index1 );
Tour* tour2 = GetTour( index2 );
std::vector<int> s1;
std::vector<int> s2;
for ( int i = p1; i < p2; i++ ) { int city1 = tour1->GetCity( i );
int city2 = tour2->GetCity( i );
s1.push_back( city1 );
s2.push_back( city2 );
}
std::sort( s1.begin(), s1.end() );
std::sort( s2.begin(), s2.end() );
// Find all numbers unique to both s1 and s2
std::set<int> intersection;
std::set_intersection( s1.begin(),
s1.end(),
s2.begin(),
s2.end(),
std::inserter( intersection, intersection.end() ) );
std::vector<int> s1_new;
std::vector<int> s2_new;
int size = p2 - p1;
for ( int i = 0; i < size; i++ )
{
int val1 = s1[ i ];
int val2 = s2[ i ];
bool is_in1 = intersection.find(val1) != intersection.end();
bool is_in2 = intersection.find(val2) != intersection.end();
if ( !is_in1 )
{
s1_new.push_back( val1 );
}
if ( !is_in2 )
{
s2_new.push_back( val2 );
}
}
int index = 0;
for ( int i = 0; i < chrSize; i++ ) { if ( i >= p1 && i < p2 ) { int val = tour2->GetCity( i );
offspr.push_back( val );
}
else
{
int val = tour1->GetCity( i );
// Is val in s2_new set?
std::vector<int>::iterator it;
it = find( s2_new.begin(), s2_new.end(), val );
bool is_in = it != s2_new.end();
if ( is_in )
{
int val_new = s1_new[ index++ ];
offspr.push_back( val_new );
}
else
{
offspr.push_back( val );
}
}
}
// Copy the values to create one new offspring
int member = rand() % pop.size();
while ( member == bestIndex )
{
member = rand() % pop.size();
}
Tour* tour = pop.at( member );
tour->SetCities( offspr );
}
Mutation Operators
At a given probability of mutation, three different mutation heuristics are used at approximately equal probabilities. The first heuristic swaps randomly chosen city pairs a randomly small (1 – 4) number of times. The second heuristic rotates randomly selected portions of cities a random number of times. The third heuristic reverses cities between two ranomly selected points in the tour. C++ implementation below:
// Apply mutation to selected Tour
void Population::Mutation( const int& index )
{
Tour* tour = pop.at( index );
int tsize = tour->TourSize();
int p1 = 1 + rand() % ( tsize - 1 );
int p2 = 1 + rand() % ( tsize - 1 );
while ( p1 == p2 )
{
p2 = 1 + rand() % ( tsize - 1 );
}
int r = rand() % 100;
if ( r < 33 )
{
int n = 1 + rand() % 3;
for ( int i = 0; i < n; i++ ) { p1 = 1 + rand() % ( tsize - 1 ); p2 = 1 + rand() % ( tsize - 1 ); while ( p1 == p2 ) { p2 = 1 + rand() % ( tsize - 1 ); } tour->Swap( p1, p1 );
}
}
else if ( r < 67 ) { int c[ 3 ]; c[ 0 ] = 1 + rand() % ( tsize - 1 ); c[ 1 ] = 1 + rand() % ( tsize - 1 ); c[ 2 ] = 1 + rand() % ( tsize - 1 ); while ( c[ 0 ] == c[ 1 ] || c[ 1 ] == c[ 2 ] || c[ 1 ] == c[ 2 ] ) { c[ 0 ] = 1 + rand() % ( tsize - 1 ); c[ 1 ] = 1 + rand() % ( tsize - 1 ); c[ 2 ] = 1 + rand() % ( tsize - 1 ); } std::sort( c, c + 3 ); tour->Rotate( c[ 0 ], c[ 1 ], c[ 2 ] );
}
else
{
tour->ReverseCities( p1, p2 );
}
}
The Tour data structure:
The “Tour” class is used to house the ordering of cities for a tour, and perform other utilities such as calculate the distance between individual cities and tours, store the best tour found, create a random tour etc. It essentially stores the tours as a standard C++ vector array of integers, along the fitness value of the tour and is the same structure as that used in a previous posting that describes the application of simulated annealing to the same travelling salesperson problem:
class Tour
{
public:
Tour(void);
Tour( CoordMatrix* mat );
Tour( CoordMatrix* mat, std::vector< int > tour );
~Tour(void);
void Swap( const int& c1,const int& c2 );
void TwoOpt( const int& c1,
const int& c2,
const int& c3,
const int& c4 );
void Scramble( const int& p1, const int &p2 );
void Rotate( const int& p1, const int& p2, const int& p3 );
void ReverseCities( const int& c1, const int& c2 );
double CalcTourFitness( CoordMatrix* mat ) const;
int TourSize() const;
int GetCity( const int& index );
void StoreTour( std::vector<int>& v );
void SetMatrix( CoordMatrix* mat );
void CreateRandomTour( const int& size );
void CreateNearestNeighbourTour( const int& size, CoordMatrix* mat );
void SetCities( const std::vector<int>& v );
void SetCity( const int& index, const int& value );
void Reset();
void SetFitness( const double& value );
double GetFitness() const;
double TourDistance( CoordMatrix* mat ) const;
private:
double Distance( const int& c1,
const int& c2,
CoordMatrix* mat ) const;
int GetNearestNeighbour( const int& c,
std::set<int>& cset,
CoordMatrix* mat );
private:
std::vector< int > cities;
double fitness;
};
Some initial results
As with simulated annealing, genetic algorithms also have the problem of finding suitable combinations of tunable parameters, in this case mutation and crossover rates, so as to help the algorithm generate reasonable solutions within reasonable time scales. After quite a bit of fooling around, some parameters that were found to be useful were:
Crossover: 20%
Mutation: 5%
Population size: 100
Tournament size: Population / 4
(If you want to play around with some other values, just open the TSPalgorithm.cpp file and tweak the values given at the top of the page.) Applying the algorithm to the Att48.tsp problem, over 5000 iterations yielded the following solution:
While the next image shows the progress of the genetic algorithm over 5000 iterations. Simply by using the logging facility within the code, the best solution obtained at every 10th iteration was obtained, stored to a text file, and converted into a line graph using an Open Office spreadsheet:
Usage
Running the software is very simple. While running the Visual Studio project in Debug or Release mode, locate and open the saved TSP file, and then click Run. At each iteration, the best solution found by the genetic algorithm so far is retained and displayed in the user interface.
Example .tsp file “Att48.tsp” downloadable from here:
https://www.technical-recipes.com/Downloads/att48.tsp
Download the Visual Studio 2010 project and code:
