Optimizing Genetic Algorithms for TSP: Evaluating Greedy Permuting Method with Diverse Selection and Crossover Techniques

Abstract

The Greedy Permuting Method (GPM) is a method introduced for initial population generation in the Genetic Algorithm (GA). For a test problem with 280 cities, the generated initial population can reach the best solution 12 times faster compared to the randomly generated population. However, GPM was tested with only one crossover operator and did not consider the initial population generation time, which might be longer to produce the ‘best’ initial population. This study aims to further dig into the potential of GPM in solving the Travelling Salesman Problem (TSP), by combining it with several selection techniques and well-performed crossover operators. We evaluate the GPM for its execution time to generate the initial population. Our experiments using 5 well-known TSP dataset problems show that GPM needs more time than the random method for initial population generation, and needs two-fold longer execution time in finding the best solution. However, after running 9 different algorithm configurations, the results obtained show GPM gives a closer result to the best-known result in pr76 (excess is 7.5%), compared to the random initial method (excess is 208.43%). When using GPM as the initial population method, the combination of Tournament Selection (TS) as the selection method, and Ordered Crossover (OX) as the crossover method gives the best result. We also compare the results of the best algorithm configuration with Spider Monkey Optimization (SMO), Ant System (AS), and Simulated Annealing (SA) algorithms.

Access to Document

Other files and links

• Link to publication in Scopus

Fingerprint