Optimal Parameter Value of Genetic Algorithms for Different Size Instances in Solving Traveling Salesman Problem

Abstract

This study focuses on optimizing the parameters of the Genetic Algorithm (GA) to solve the Traveling Salesman Problem (TSP). TSP instances were selected based on the differences in dataset sizes and their uniqueness, which had not been used in previous research. Additionally, genetic operators such as Elitism, order crossover (OX), and swap mutation were employed in the GA. The objective of this study is to analyze the impact of parameter tuning on the performance of the GA by varying the values of population size, number of generations, crossover rate, and mutation rate. Several experiments were conducted, and the optimal parameter values such as population size of 100, 750 generations, and crossover and mutation rates (CMR 2 = [0.9, 0.01] and [0.7, 0.01]), were determined in this study. Subsequently, these values were compared with the values of the common approach used in previous research, which is CMR 1 = [0.9, 0.03]. The study results indicate that the best combination is CMR 2 which outperforms CMR 1 in finding the minimum travel distance and achieving a shorter computation time. Across datasets with varying characteristics for each instance, it was found that a high crossover rate (0.9) contributes to better algorithm accuracy compared to a low crossover rate (0.7). However, TSP instances with larger sizes demonstrated the ability to identify optimum travel distances using a lower crossover rate (0.7). Furthermore, an increase in mutation rate does not necessarily contribute to find the best solution. Nevertheless, the CMR 2 combination, with a lower mutation (0.01) rate compared to CMR 1 (0.03), has contributed to better solutions, especially in the TSP instances examined in this research.