Optimization of Adaptive Genetic Algorithm Parameters in Traveling Salesman Problem

I Kayan Herdiana; I Made Candiasa; Gede Indrawan

doi:10.47709/cnahpc.v4i2.1581

Authors

I Kayan Herdiana Universitas Pendidikan Ganesha, Indonesia
I Made Candiasa Universitas Pendidikan Ganesha, Indonesia
Gede Indrawan Universitas Pendidikan Ganesha, Indonesia

DOI:

10.47709/cnahpc.v4i2.1581

Keywords:

Fitness, Genetic Algorithm, Optimization, Performance, TSP

Dimension Badge Record

Abstract

The TSP problem is one where a seller visits multiple destinations at the same time and they are only allowed to visit once. The purpose of this TSP is to shorten the shortest distance, thereby minimizing time and cost. There are various methods to solve the TSP problem, including greedy algorithm, brute force algorithm, hill climbing method, ant algorithm, and genetic algorithm. Each process in a genetic algorithm is affected by several parameters, including population size, maximum generation, crossover rate, and mutation rate. The purpose of this study is to apply genetic algorithms to the traveling salesman problem optimization, calculate the maximum influence of generation, chromosome number, crossover rate and mutation rate on the optimal genetic algorithm, calculate the range of chromosome number, population size, crossover rate and mutation rate for genetic algorithm in the traveling salesman problem and calculate the effect of adaptive genetic algorithm parameters on genetic algorithm results. Based on the results obtained from research and testing, the four parameters of the genetic algorithm are positively correlated with fitness results while negatively correlated with execution time performance where each adaptive parameter applied provides more optimal fitness results than static parameters. The four adaptive parameters that are applied together give optimal results, both fitness which reaches 1.0% and time reaches 38.7%.

Downloads

Download data is not yet available.

Google Scholar Cite Analysis
Abstract viewed = 311 times

References

Amine, K. (2019). Multiobjective Simulated Annealing: Principles and Algorithm Variants. Advances in Operations Research, 2019, 1–13. https://doi.org/10.1155/2019/8134674

Cao, Z., Chen, H., & Wang, X. (2022). Spectral clustering based on the local similarity measure of shared neighbors. ETRI Journal, etrij.2021-0230. https://doi.org/10.4218/etrij.2021-0230

Chen, H., Tan, G., Qian, G., & Chen, R. (2018). Ant Colony Optimization With Tabu Table to Solve TSP Problem. 2018 37th Chinese Control Conference (CCC), 2523–2527. https://doi.org/10.23919/ChiCC.2018.8483278

Fronita, M., Gernowo, R., & Gunawan, V. (2018). Comparison of Genetic Algorithm and Hill Climbing for Shortest Path Optimization Mapping. E3S Web of Conferences, 31, 11017. https://doi.org/10.1051/e3sconf/20183111017

Gamrath, G., Berthold, T., Heinz, S., & Winkler, M. (2019). Structure-driven fix-and-propagate heuristics for mixed integer programming. Mathematical Programming Computation, 11(4), 675–702. https://doi.org/10.1007/s12532-019-00159-1

Ginantra, N. L. W. S. R., & Anandita, I. B. G. (2019). Implementasi Algoritma Genetika Berbasis Web pada Sistem Penjadwalan Mengajar di SMK Dwijendra Denpasar. Jurnal Teknologi Informasi Dan Komputer, 5(1), 130–138.

Hardi, S., Zarlis, M., Effendi, S., & Lydia, M. S. (2020). Taxonomy Genetic Algorithm For Implementation Partially Mapped Crossover In Travelling Salesman Problem. Journal of Physics: Conference Series, 1641(1), 012104. https://doi.org/10.1088/1742-6596/1641/1/012104

Huang, X., Xu, C., & Zhang, L. (2020). An Efficient Algorithm for Optimizing the Test Path of Digital Microfluidic Biochips. Journal of Electronic Testing, 36(2), 205–218. https://doi.org/10.1007/s10836-020-05865-6

Mursalim, Purwanto, & Soeleman, M. A. (2021). Penentuan Centroid Awal Pada Algoritma K-Means Dengan Dynamic Artificial Chromosomes Genetic Algorithm Untuk Tuberculosis Dataset. Techno.Com, 20(1), 97–108. https://doi.org/10.33633/tc.v20i1.4230

Nam, Y., & Maslov, D. (2019). Low-cost quantum circuits for classically intractable instances of the Hamiltonian dynamics simulation problem. Npj Quantum Information, 5(1), 44. https://doi.org/10.1038/s41534-019-0152-0

Slowik, A., & Kwasnicka, H. (2020). Evolutionary Algorithms and Their Applications to Engineering Problems. Neural Computing and Applications, 32(16), 12363–12379. https://doi.org/10.1007/s00521-020-04832-8

Srinivasan, K., Satyajit, S., Behera, B. K., & Panigrahi, P. K. (2018, May 28). Efficient quantum algorithm for solving travelling salesman problem: An IBM quantum experience. arXiv. Retrieved from http://arxiv.org/abs/1805.10928

Utomo, R. B. (2017). Sirkuit Hamilton dalam Permainan Congklak. AdMathEdu?: Jurnal Ilmiah Pendidikan Matematika, Ilmu Matematika dan Matematika Terapan, 7(1), 39. https://doi.org/10.12928/admathedu.v7i1.7400

Villalba Matamoros, M. E., & Kumral, M. (2019). Calibration of Genetic Algorithm Parameters for Mining-Related Optimization Problems. Natural Resources Research, 28(2), 443–456. https://doi.org/10.1007/s11053-018-9395-2

Violina, S. (2021). Analysis of Brute Force and Branch & Bound Algorithms to solve the Traveling Salesperson Problem (TSP). Turkish Journal of Computer and Mathematics Education, 12(8), 1226–1229. https://doi.org/10.17762/turcomat.v12i8.3031

Wang, H., Lang, X., & Mao, W. (2021). Voyage optimization combining genetic algorithm and dynamic programming for fuel/emissions reduction. Transportation Research Part D: Transport and Environment, 90, 102670. https://doi.org/10.1016/j.trd.2020.102670

Wu, C., & Fu, X. (2020). An Agglomerative Greedy Brain Storm Optimization Algorithm for Solving the TSP. IEEE Access, 8, 201606–201621. https://doi.org/10.1109/ACCESS.2020.3035899

Zhang, H., Tong, W., Xu, Y., & Lin, G. (2016). The Steiner Traveling Salesman Problem with Online Advanced Edge Blockages. Computers & Operations Research, 70, 26–38. https://doi.org/10.1016/j.cor.2015.12.013