How Genetic Algorithms and Evolutionary Computing Can Be Used to Find Near-Optimal Solutions for the Travelling Salesman Problem

Metaheuristics can find near-optimal solutions for NP-complete problems

Last year, I took the ‘Genetic Algorithms and Evolutionary Computing’ course at KU Leuven. The evaluation of the course is based entirely on a programming project in Python, where the task is to find near-optimal solutions for the travelling salesman problem. Conceptually, several matrices are given that represent the distances between certain cities, after which the algorithm should find the shortest solution. The designed algorithm had to be submitted, after which they will run for 5 minutes on the departmental computers.

Photo by DeepMind on Unsplash

1) Design of the evolutionary algorithm

1.1) The three main features:

1. Fitness sharing has been used in the elimination step of the algorithm. This diversity promotion scheme is of crucial importance to avoid premature convergence, and hence makes sure that far better solutions can be found, instead of letting all individuals converge to one local minima.
2. By introducing the 2-opt local search operator, far better solutions were found more quickly…