PMACO: A pheromone-mutation based ant colony optimization for traveling salesman problem

Traveling salesman problem (TSP) is a popular routing problem, which is a sub-problem of many application domains such as transportation, network communication, vehicle routing and integrated circuits designs. Among many approaches which have been proposed for TSP so far, evolutionary algorithms effectively applied to solve it, and attempt to avoid trapping in local minima. In this paper, a hybrid approach (named PMACO) is proposed for TSP, which is based on ant colony optimization (ACO) and the mutation operators in genetic algorithm (GA). In this manner, in the each iteration a hybrid mutation scheme is applied to search the neighborhood area of the solution corresponding with the two best ants (the best current ant, and the total best ant found so far). The population is divided to two parts: the first is regenerated according to the pheromone rule in ACO, and the last is generated by applying the proposed hybrid mutation scheme. Also in this paper, the initial population was not considered randomly; it was generated according to nearest neighborhood rule, which force the ants toward better solutions, and leads to reduce the running time. Finally, we compared the performance of PMACO, with ACO and GA separately. For each algorithm, the various parameters and operators were tested, and the bests were chosen to tune that. Experimental results were carried out on benchmarks from the TSPLIB for validation.

I. Introduction

Traveling salesman problem (TSP) is a most popular routing problem, which is a sub-problem issue of many application domains such as transportation [1], network communication [2], vehicle routing [3], integrated circuits designs [4], and semiconductor industries [5]. TSP denotes a salesman who wants to visit a number of cities exactly once and finally returns to the starting city; the objective is to determine a tour with the minimum distance.