Improvement of the Genetic Algorithm Through Fuzzy C-Means Clustering with Local Search for Traveling Salesman Problem

The Traveling Salesperson Problem (TSP) is a well-known combinational optimization problem in computer science and operations research. To solve this, many approaches have been introduced and developed. One of the most effective and widely used algorithms is the genetic algorithm. However, its solution quality suffers due to swing randomness in the process. In this project, we propose an improved genetic algorithm where a clustering algorithm and local search mechanism are adopted. Actually, it is a "Two-Stage" method in which a fuzzy C-means (FCM) clustering algorithm is used in the first stage for the creation of initial populations, and in the second stage, an enhanced genetic algorithm is applied. The classical genetic algorithm is enhanced with an advanced selection strategy and first-improvement-based local searching in the mutation and it is named FCGAFIB. Also, a modified heuristic crossover is introduced here. 52 well-known TSP datasets are considered to test this algorithm. The proposed improvement of the genetic algorithm gives an acceptable solution within a reasonable time. The results of this proposed method are compared to five other state-of-the-art algorithms, of which two are cluster-based algorithms. The statistical analysis, convergency graphs, and visualization of the effect of fuzzy C-means on the initial population, as well as the visual solutions to those datasets, are presented. The experimental results and statistical analysis revealed that the proposed algorithm performs better than the compared algorithms in many datasets.

• Supervision