A Hybrid Approach of GA and ACO for TSP

摘要

This paper proposed a hybrid approach of Genetic Algorithm (GA) and Ant Colony Optimization (ACO) for the Traveling Salesman Problem. In this approach, every chromosome of GA is at the same time an ant of ACO. Whenever GA performs the operation of crossover and mutation, the approach firstly computes the linkage strength between gene codes of parental chromosome(s) according to the pheromone matrix of ACO, and it then selects the crossover or mutation point(s) according to the linkage strength. A threshold is generated to classify the gene linkage as strong or weak, the strong linkage segments of parents are retained to offspring as far as possible. By this way, GA can avoid its useful building blocks being frequently destroyed by genetic operations. Experiments on TSPLIB validated the building block learning capability of our approach.