Genetic Algorithm Incorporating Group Theory for Solving the General Travelling Salesman Problem

Abstract

This paper presents a novel Genetic Algorithm (GA) designed to tackle the Travelling Salesman Problem (TSP) with remarkable efficacy. It integrates group theory into population initialization, employs Partially Matched Crossover (PMX), and adopts a 2-optimal mutation strategy. The pioneering approach harnesses algebraic structures in constructing group tours, utilizing integer addition modulo n within Zn to generate varied initial solutions. The initial population enhances diversity by ensuring that each individual/tour shares an identical node order but begins from a distinct starting node. This distinctiveness in starting nodes facilitates thorough exploration of the entire search space. The Partially mapped Crossover operator, grounded in order principles, is a crucial mechanism for transferring sequence and value characteristics from parental to offspring tour. This operation effectively guides a strong local search. Subsequently, applying a 2-opt optimal mutation seeks to refine the solution further, targeting a more globally optimal outcome. The effectiveness of this methodology is evaluated through experiments with TSP instances sourced from the widely recognized TSPLIB. Furthermore, the superiority of our proposed approach is demonstrated through comparisons with state-of-the-art methods developed within hybrid frameworks. Statistical analyses underscore the significance and effectiveness of the proposed methodology. © The Author(s), under exclusive licence to Springer Nature Singapore Pte Ltd. 2024.