Genetic Algorithm Incorporating Group Theory for Solving the Euclidean 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. By ensuring that each individual/ tour shares an identical node order but begins from a distinct starting node, the initial population enhances diversity. This distinctiveness in starting nodes facilitates thorough exploration of the entire search space. The Partially Matched Crossover operator, grounded in principles of order, is a crucial mechanism for transferring sequence and value characteristics from parental to offspring tours. 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.