Optimization of the Travelling Salesman Problem Based on Genetic Algorithm with Adaptive Crossover and Mutation Probabilitie

Gunawan, Chichi Rizka

Jurnal Ilmu Komputer dan Sistem Informasi
Vol. 3 No. 3 (2024): September 2024

The Travelling Salesman Problem (TSP) is a combinatorial optimization problem that aims to find the shortest route to visit each city exactly once and return to the starting city. As an NP-hard problem, solving TSP requires heuristic approaches. This study employs the Genetic Algorithm to solve TSP by integrating adaptive crossover and mutation probabilities. The adaptive approach allows the crossover and mutation parameters to be dynamically adjusted based on the population conditions at each generation, thereby improving the efficiency of the optimal solution search. The research begins with chromosome representation as a sequence of cities, followed by the initialization of the initial population randomly. Fitness evaluation is conducted based on the total travel distance to determine the solution’s quality. Selection of the best individuals, adaptive crossover, and adaptive mutation are applied to generate a better new population. Elitism is used to ensure that the best solutions are preserved. The algorithm iterates until it reaches the maximum number of generations or a specific fitness threshold. The results show that the adaptive approach produces an optimal travel route with the minimum total distance. The optimal route is visualized by connecting city points, and the fitness progression demonstrates significant improvement in the early generations and stabilization in the later generations. With a crossover probability of 0.8 and mutation probability of 0.005, the algorithm effectively maintains a balance between exploration and exploitation of the solution space, preventing premature convergence, and producing efficient solutions. This study demonstrates that the Genetic Algorithm with an adaptive approach if effective in solving TSP with a moderate number of cities. Additionally, this approach can be adapted for larger datasets or compared with other optimization methods, such as Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO), to further evaluate its performance.