New Little-Window-Based Self-adaptive Ant Colony-Genetic Hybrid Algorithm

To improve the convergence time of basic ant colony optimization algorithm and avoid falling in local best, a novel ant colony-genetic hybrid algorithm is proposed. Firstly, the self-adaptive strategy of evaporation coefficient is adopted to enhance global search ability. Secondly, the global pheromone update rule is introduced to restrict ants release pheromone only in the best route and the worst route. And the local pheromone update rule is used to decrease pheromone on the traversed edges to avoid ants produce identical solutions and falling in local best. Thirdly, with the greedy inversion operator, genetic algorithm mutation mechanism deals with falling in local best and degeneration. Finally, variable width little-window limits the mobile range of ants so that inferior solutions could be eliminated in terms of fact. Comparing with traditional methods, the simulation result on TSP shows that new algorithm has higher convergence speed and better escape capability from local best.

1. Introduction

Ant Colony Optimization Algorithm (ACO) is a novel bionic algorithm that was presented by Italy scholar M. Dorigo et al. in the 1990s [1], [2], [3], [4]. It has proved to bring many advantages, such as distributed calculation, information positive feedback, and easy combining with other algorithms and so on. Nowadays, it has been applied to classic combinatorial optimization problems extensively, for example, TSP [5], QAP [6] and so on. But the basic ACO has some disadvantages such as longer convergent time and easy falling in local best.