Title: A genetic ant colony optimisation system (GenANT) for quadratic assignment problems

Authors: Kuan Yew Wong, Phen Chiak See

Addresses: Faculty of Mechanical Engineering, Department of Manufacturing and Industrial Engineering, Universiti Teknologi Malaysia, 81310 UTM Skudai, Malaysia. ' Faculty of Mechanical Engineering, Department of Manufacturing and Industrial Engineering, Universiti Teknologi Malaysia, 81310 UTM Skudai, Malaysia

Abstract: In recent years, various metaheuristic approaches have been created to solve quadratic assignment problems (QAPs). Among others is the ant colony optimisation (ACO) algorithm, which was inspired by the foraging behaviour of ants. Although it has solved some QAPs successfully, it still contains some weaknesses and is unable to solve large QAP instances effectively. Thereafter, various suggestions have been made to improve the performance of the ACO algorithm. One of them is to hybridise ACO with other metaheuristic algorithms. Particularly, there is an increasing interest to hybridise ACO with genetic algorithm (GA) to obtain better search performance. This article introduces a new hybrid ACO algorithm known as GenANT, which combines the max-min ant system (MMAS; i.e. a type of ACO algorithm) with GA to solve QAPs. A novel minimum pheromone threshold strategy is also introduced to enhance the collaboration between MMAS and GA. An experimental evaluation on the performance of GenANT is presented at the end of the article following by conclusions.

Keywords: ACO; ant colony optimisation; GAs; genetic algorithms; MMAS; max-min ant systems; QAPs; quadratic assignment problems; metaheuristics.

DOI: 10.1504/IJMOR.2009.026277

International Journal of Mathematics in Operational Research, 2009 Vol.1 No.4, pp.456 - 475

Published online: 05 Jun 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article