An improved ant colony optimization algorithm with embedded genetic algorithm for the traveling salesman problem

In this paper we proposed an improved ant colony optimization algorithm with embedded genetic algorithm to solve the traveling salesman problem. The main idea is to let genetic algorithm simulate the consulting mechanism, which may have more chances to find a better solution, to optimize the solutions found by the ants. In the proposed algorithm, we employed a new greedy way of solution construction and designed an improved crossover operator for consultation in the embedded genetic algorithm. Experimental results showed that the proposed algorithm could find better solutions of benchmark instances within fewer iterations than existing ant colony algorithms.

I. Introduction

The ant colony optimization (ACO) algorithm is a multi agent system in which the behavior of each ant is inspired by the foraging behavior of real ants to solve optimization problem. The main idea of ACO is to use the equivalent of the pheromone trail used by real ants as a medium for cooperation and communication among a colony of artificial ants. ACO algorithm has been successfully applied to several NP-hard combinatorial optimization problems, such as the traveling salesman problem(TSP) [9], the quadratic assignment problem (QAP) [14], the vehicle routing problem (VRP) [13] and the job-shop scheduling problem (JSP) [3], since it was introduced by Dorigo [9]. Among these problems, TSP plays an important role in ACO algorithm because almost all researches on ACO have been tested on this problem. TSP was chosen mainly for three reasons [5]: (I) it is a problem to which the ACO is easily adapted, (II) it is one of the most studied NP-hard problems in combinatorial optimization, and (III) it is easier comprehend. Thus, we here focused on TSP as application domains for the proposed algorithm.