Unsupervised Fuzzy Clustering-based Genetic Algorithms to Traveling Salesman Problem

In this paper a new genetic algorithm based on an unsupervised fuzzy clustering is proposed for Traveling Salesman Problem (TSP). The proposed algorithm involves on three phases. In the first phase, the cities are divided into several sub-tours by the clustering algorithm. In the second phase, each partition of cities is considered as a smaller scale TSP problem and this smaller size TSP problem is solved by a genetic algorithm which gets an optimal sub-tour of the cities of this partition. In the third phase, a new technique for connecting all these sub- tours into an appropriate tour of whole cities. As well as, this appropriate tour is improved by a genetic algorithm for cluster centers and a heuristic method. The computer simulations on some standard test problems show good performance for the proposed algorithm.