A Greedy Approach to Ant Colony Optimisation Inspired Mutation for Permutation Type Problems

Meta-heuristics have demonstrated relative success when applied to permutation problems such as the Traveling Salesman Problem (TSP). Two successful meta-heuristics are Genetic Algorithms (GAs) and Ant Colony Optimisation (ACO) but have widely differing methodologies, combining both could be beneficial. This paper achieves this using a mutation operator based on the novel ACO variant Partial-ACO. Applied to a range of TSP instances significant gains are achieved over standard mutation operators. Furthermore, to increase performance consideration is given to operating mutation in a greedy manner enabling constant use, a fully combined GA and ACO meta-heuristic solution. Experiments demonstrate that a greedy approach to ACO mutation improves results enabling solutions to TSP instances of several thousand cities within a few percent of optimal to be achieved without any local search methods.