Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.3/81222

Title

Improving the performance of ant colony optimisation algorithms using biased optimisation visibility

Author(s)

Moser, Irene;  Hendtlass, Tim

Abstract

When used to solve traveling salesperson problems (TSP), Ant Colony Optimisation algorithms use the proximity of two nodes to determine the weight or cost of the edge connecting them. The weights counterpoint the pheromone in the state transition rule, used to determine the desirability of a certain next move. The proximity does not always reflect the desirability of the possible edge correctly, because some vertices are at a further distance from their nearest neighbours than others. In the Ant System and Ant Colony System algorithms nodes whose shortest connecting arcs are comparatively long tend to be chosen by the ants at a very late stage in the tour. Thus unfavourable tours are made, which do not contribute to finding a tour close to the optimum. We propose an improvement which introduces a node-specific bias to ACOs. The biased visibility improves the performance of the AS and ACS algorithms on TSP.

Publication type

Journal article

Research centre

Swinburne University of Technology. Faculty of Information and Communication Technologies. Centre for Intelligent Systems and Complex Processes

Source

Complexity International, Vol. 12 (Oct 2008), article no. msid18

Publication year

2008

FOR Code(s)

0103 Numerical and Computational Mathematics;  0801 Artificial Intelligence and Image Processing;  0802 Computation Theory and Mathematics

Keyword(s)

ACO;  Ant colony optimisation;  Optimisation;  Travelling salesperson problems;  TSP

Publisher

Faculty of Information Technology, Monash University

ISSN

1320-0682

Publisher URL

http://www.complexity.org.au/ci/vol12/msid18/

Copyright

Copyright © 2005.

Peer reviewed