08. April 2013 · Comments Off on Solving Traveling Salesperson Problem using Genetic Algorithm · Categories: Programming · Tags: , ,
ShareEmail this to someoneShare on RedditTweet about this on TwitterShare on FacebookShare on Google+Share on LinkedIn

We are going implement genetic algorithm that solves Traveling Salesperson Problem using Genetic Algorithm Library.

Traveling Salesperson Problem Application

Screenshot – TSP application

The chromosome is an array of cities [pointers to objects of the TspCity class] in the order in which they are visited. It is implemented by the TspChromosome class. The class inherits GaMultiValueChromosome to implement a custom initialization of the chromosome by overriding the MakeFromPrototype method. This method copies cities into the chromosomes’ code and then it shuffles their positions. This class also overrides the MakeCopy method and defines a copy constructor.

class TspChromosome : public GaMultiValueChromosome<const TspCity*>
{
public:
    TspChromosome(GaChromosomeDomainBlock<const TspCity*>* configBlock) :
        GaMultiValueChromosome(configBlock) { }

    TspChromosome(const TspChromosome& chromosome,
        bool setupOnly) :
        GaMultiValueChromosome<const TspCity*>(chromosome, setupOnly) { }

    virtual GaChromosomePtr GACALL MakeCopy(bool setupOnly) const
        { return new TspChromosome( *this, setupOnly ); }

    virtual GaChromosomePtr GACALL MakeNewFromPrototype() const;

    int GACALL GetCityPosition(const TspCity* city) const;
};

Using a simple single-point or multi-point crossover operation will generate a large amount of invalid solutions which degrades the algorithm’s performance and results. To prevent the generation of invalid solutions, the algorithm uses a custom crossover operation. The operation takes a random city from one parent and copies it to the child chromosome. Then, it searches for the cities which are connected to the chosen city [in both parents] and takes the nearest one [and copies it to the child chromosome] if it is not already taken. It is taken if the operation chooses another connected city. If all the connected cities are taken, the operation randomly chooses a city that has not been taken. Then, the crossover uses that city to extend the path in the same way. The process is repeated to select all the cities. The TspCrossover class implements this crossover operation:

class TspCrossover : public GaCrossoverOperation
{
public:
    virtual GaChromosomePtr GACALL operator ()(
        const GaChromosome* parent1,
        const GaChromosome* parent2) const;

    virtual GaParameters* GACALL MakeParameters() const { return NULL; }

    virtual bool GACALL CheckParameters(
        const GaParameters& parameters) const { return true; }

private:
    inline void SelectNextCity(const TspCity* previousCity,
        const TspCity** currentBestNextCity,
        const TspCity* nextCity) const;
};

The algorithm uses the built-in GaSwapMutation operation. The fitness value is equal to the length of the path. The TspFitnessOperation class implements the fitness operation:

class TspFitness : public GaFitnessOperation
{
public:
    virtual float GACALL operator ()(
        const GaChromosome* chromosome) const;

    virtual GaParameters* GACALL MakeParameters() const { return NULL; }

    virtual bool GACALL CheckParameters(
        const GaParameters& parameters) const { return true; }
};

Parameters of chromosomes:

  1. mutation probability: 3%
  2. mutation size: 2
  3. improving only mutations: no
  4. crossover probability: 80%
  5. number of crossover points: 1 [ignored]

CCB:

  1. TspCrossover
  2. TspSwapMutation
  3. TspFitnessOperation
  4. TspMinFitnessComparator
  5. Value set is not defined

Population parameters:

  1. population size: 100
  2. resizable population: no [an incremental algorithm is used which does not require a resizable population]
  3. population is sorted: yes
  4. scaled fitness is used for sorting: no
  5. tracking of the best chromosomes: 0 [population is already sorted]
  6. tracking of the worst chromosomes: 0 [population is already sorted]

Configuration of the population:

  1. GaSelectRandomBest selection which selects 8 chromosomes
  2. GaSimpleCoupling which produces 8 offspring chromosomes
  3. GaRandomReplaces which replaces 8 chromosomes in each generation, with an elitism size of 10 chromosomes
  4. No scaling operation

The algorithm uses GaFitnessProgressCriteria because the exact termination condition is not known. The criteria will stop the algorithm if it is unable to improve the fitness value for more than 1 in 50000 generations. The genetic algorithm is incremental.

The TSP class is the container for the object of the algorithm. The TspCity class represents and stores information about a city [such as its coordinates and name]. It has the GetDistance method which calculates the distances between the cities. TspCities manages the collection of cities entered by the user.

Downloads

Source code and Demo application

Comments closed