Optimizing Path of The Travelling Salesman Problem Through Modified Genetic Algorithms

Abstract

The Traveling Salesman Problem (TSP) stands as one of the earliest and most pervasive optimization challenges, aiming to streamline the salesman's travel route, ensuring efficiency and avoiding redundancy. With an extensive number of cities to visit and the requirement to find the shortest route, solving the TSP becomes computationally daunting. To tackle this, various approaches are explored, including the genetic algorithm. This study employs a modified genetic algorithm, inspired by biological processes such as population dynamics, crossover, mutation, and natural selection. Introducing a novel intersection approach amalgamating sliding flipping and swapping methods, the study investigates towns with populations ranging from (10,50) to (150,200) across two scenarios. In the first scenario, experiments were conducted with a fixed iterations (10000) and a population is (150), resulting in execution times of (20.00 s), (55.14) s, (37.11 s), and (120.14 s) when choose cities (100,200,10,20), respectively. The other scenario the population sizes of (50) or (100) and iteration numbers of (1000) or (500) were explored. The times needed for solution determination were (01.20 s),( 02.30 s), (02.74 s), and (17.15 s) for cities (10,20,100,200), in accordance. Notably, outcomes indicate a proportional relationship between iteration, population, and the number of cities. When integrating the three techniques, a shorter and faster path is achieved compared to the standard genetic algorithm outcomes