¹School of Computer Science and Technology, Jiangsu University of Science and Technology, Zhenjiang 212003, China
²Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080, China

---

Abstract—By use of the properties of ant colony algorithm and genetic algorithm, a novel ant colony genetic hybrid algorithm, whose framework of hybrid algorithm is genetic algorithm, is proposed to solve the traveling salesman problems. The selection operator is an artificial version of natural selection, and chromosomes with better length of tour have higher probabilities of being selected in the next generation. Based on the properties of pheromone in ant colony algorithm the ant colony crossover operation is given. Four mutation strategies are put forward using the characteristic of traveling salesman problems. The hybrid algorithm with 2-opt local search can effectively find better minimum beyond premature convergence. Ants choose several tours based on trail, and these tours will replace the worse solution. Compare with the simulated annealing algorithm, the standard genetic algorithm and the standard ant colony algorithm, all the 4 hybrid algorithms are proved effective. Especially the hybrid algorithm with strategy D is a simple and effective better algorithm than others.

Index Terms—ant colony algorithm, genetic algorithm, traveling salesman problem.

[PDF]

Cite: Shang Gao, Zaiyue Zhang, Cungen Cao, "A Novel Ant Colony Genetic Hybrid Algorithm," Journal of Software vol. 5, no. 11, pp. 1179-1186, 2010.