Investigation of a Genetic Algorithm for Solving the Travelling Salesman Problem

The paper describes in detail the stages of the genetic algorithm (GA), including population initialisation, assessment of the fitness of the resulting solution, selection, crossover and mutation. The features of using the most common selection, crossover and mutation operators are analysed. The mathematical apparatus of the procedure for calculating the geographical distance between cities based on the Gaversus formula for the traveling salesman problem is presented. It is proposed to use a combined selection operator: tournament and elite, to improve the efficiency of the genetic algorithm in solving the traveling salesman problem (TSP). The proposed selection operator allows for a variety of solutions (tournament selection) and the preservation of the best individuals in the population from generation to generation (elite selection). This facilitates the search for new and unpredictable solutions that can be competitive and allows not to lose the best solutions during evolution. To evaluate the proposed solution, we investigated its use in a genetic algorithm designed to build the shortest route for 29 cities in Bavaria, in accordance with the TSP. The obtained simulation results demonstrate the effectiveness of using the combined selection operator to find the shortest route in comparison with the tournament and elite operator. Thus, the paper demonstrates the solution of TSP by applying a GA, the main components of which are the proposed combined selection operator, the operator of ordered crossing and the inversion mutation operator.