Introduction

The Travelling Salesman Problem (TSP) is an NP-hard problem in combinatorial optimizaiton.
It asks: ‘Given a set of N cities, find the shortest tour, such that the Travelling Salesman can visit all the cities without having to go to each city more than once.’

Determining an exact solution by Checking every possible tour for a TSP with a large number of nodes is difficult, as the worst-case runtime complexity is $O(n!)$. The fastest exact algorithms can solve the problem in time $O(n^2 2^n)$.

Heuristic and approximation algorithms trade-off accurate results for a faster execution time.

One metaheuristic algorithm to solve the TSP is the Genetic Algorithm.

The Genetic Algorithm emulates the process of biological evolution. The algorithm begins with by initializing a population. This can be random or use an educated guess / approximation of the ideal individual. The population is evaluated against a fitness function or objective function. The best indivviduals are then selected according to a selection ratio and a crossover operation is performed to generate a new population. This process is repeated until an exit condition is met.

The Pseudocode for the Genetic Algorithm is:

population = initialize_population()
while evolution:
    fitness = fitness_function(population)
    population = crossover(population, fitness, selection_ratio)

The Genetic Algorithm poses a few interesting choices for implementation to solve the TSP, which are discussed below.

Tour Representation

A flexible method of encoding a tour is by using a list of indices. The nodes are stored in an array, with each element in the tour referring to the index of the respective node.

Initial Population

The Initial Conditions to start the

The Initial population can be generated in two ways:

  1. Randomized Population
  2. An Educated Guess

Crossover

How are the Results Generated?

Resources Used (Change Later)

Travelling Salesman Problem using Genetic Algorithm

On Solving Travelling Salesman Problems by Genetic Algorithms

Crossover Operators in Genetic Algorithms: A Review

Implementation or TODO List

  • Compare Population Initialization Methods
    • Random (Currently Implemented)
    • Nearest Neighbor
    • Implement as many TSP approximation methods as possible
  • Crossover Methods
    • Ordered Crossover (OX)
    • Partially Mapped Crossover (PMX)
    • Cycle Crossover (CX)
    • Edge Recombination Crossover (ERX)
  • Library Parser
  • Testing
    • Initialization Methods: Random vs. Nearest Neighbor
    • Crossover Methods: OX vs. PMX vs. CX vs. ERX
    • OX better when randomized every time vs. once per generation?
  • Figures Needed to Create
    • Demonstration of each Crossover Method