Optimasi Travelling Salesman Problem Berbasis Algoritma Genetika dengan Probabilitas Crossover dan Mutasi Adaptif
DOI:
https://doi.org/10.70340/jirsi.v3i3.166Keywords:
crossover, mutation, optimization, NP-Hard , fitnessAbstract
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.
Downloads
References
G. E. Yuliastuti, W. F. Mahmudy, and A. M. Rizki, “Implementation of Genetic Algorithm to Solve Travelling Salesman Problem with Time Window (TSP-TW) for Scheduling Tourist Destinations in Malang City,” J. Inf. Technol. Comput. Sci., vol. 2, no. 1, pp. 1–10, 2017, doi: 10.25126/jitecs.20172122.
M. Boulif and A. Gharbi, “A new node-shift encoding representation for the travelling salesman problem,” 2023, [Online]. Available: http://arxiv.org/abs/2305.09257
J. Juwairiah, D. Pratama, H. C. Rustamaji, H. Sofyan, and D. B. Prasetyo, “Genetic Algorithm for Optimizing Traveling Salesman Problems with Time Windows (TSP-TW),” Int. J. Artif. Intell. Robot., vol. 1, no. 1, pp. 1–8, 2019, doi: 10.25139/ijair.v1i1.2024.
J. Zheng, J. Zhong, M. Chen, and K. He, “A reinforced hybrid genetic algorithm for the traveling salesman problem,” Comput. Oper. Res., vol. 157, pp. 1–17, 2023, doi: 10.1016/j.cor.2023.106249.
D. Fadhillah A, N. Ega, D. Sofisyah A, A. Riski, and E. Sakti, “Genetic Algorithm Design on Traveling Salesman Problem,” Informatics Softw. Eng., vol. 1, no. 1, pp. 24–29, 2023, doi: 10.58777/ise.v1i1.60.
S. Lukas, T. Anwar, and W. Yuliani, “Penerapan Algoritma Genetika Untuk Traveling Salesman Problem Dengan Menggunakan Metode Order Crossover Dan Insertion Mutation,” Semin. Nas. Apl. dan Teknol. Inf. (SNATI 2005), vol. 2005, no. Snati, pp. 1–5, 2005.
A. V. Eremeev and Y. V. Kovalenko, “Genetic Algorithm with Optimal Recombination for the Asymmetric Travelling Salesman Problem,” pp. 1–8, 2017, doi: 10.1007/978-3-319-73441-5_36.
S. Mahmoudinazlou and C. Kwon, “A hybrid genetic algorithm with type-aware chromosomes for Traveling Salesman Problems with Drone,” Eur. J. Oper. Res., vol. 318, no. 3, pp. 719–739, 2024, doi: 10.1016/j.ejor.2024.05.009.
A. Yusron Mubarok and U. Chotijah, “Penerapan Algoritma Genetika Untuk Mencari Optimasi Kombinasi Jalur Terpendek Dalam Kasus Travelling Salesman Problem,” J. Teknol. Terpadu, vol. 7, no. 2, pp. 77–82, 2021, doi: 10.54914/jtt.v7i2.424.
S. Rohman, L. Zakaria, A. Asmiati, and A. Nuryaman, “Optimisasi Travelling Salesman Problem dengan Algoritma Genetika pada Kasus Pendistribusian Barang PT. Pos Indonesia di Kota Bandar Lampung,” J. Mat. Integr., vol. 16, no. 1, p. 61, 2020, doi: 10.24198/jmi.v16.n1.27804.61-73.
Downloads
Published
Issue
Section
License
Copyright (c) 2024 Chichi Rizka Gunawan

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.