Modifications and Additions to Ant Colony Optimisation to Solve the Set Partitioning Problem

File Size Format
66834_1.pdf 227Kb Adobe PDF View
Title Modifications and Additions to Ant Colony Optimisation to Solve the Set Partitioning Problem
Author Randall, Marcus; Lewis, Andrew
Publication Title Proceedings 2010 Sixth IEEE International Conference on e-Science Workshops
Editor B. Werner
Year Published 2010
Publisher IEEE Computer Society
Abstract Ant colony optimisation has traditionally been used to solve problems that have few/light constraints or no constraints at all. Algorithms to maintain and restore feasibility have been successfully applied to such problems. Set partitioning is a very constrained combinatorial optimisation problem, for which even feasible solutions are difficult to construct. In this paper a binary ant colony optimisation framework is applied to this problem. To increase its effectiveness, feasibility restoration, solution improvement algorithms and candidate set strategies are added. These algorithms can be applied to complete solution vectors and as such can be used by any solver. Moreover, the principles of the support algorithms may be applied to other constrained problems. The overall results indicate that the ant colony optimisation algorithm can efficiently solve small to medium sized problems. It is envisaged that in future research parallel computation could be used to simultaneously reduce solver time while increasing solution quality.
Peer Reviewed Yes
Published Yes
Alternative URI http://dx.doi.org/10.1109/eScienceW.2010.27
Copyright Statement Copyright 2010 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
ISBN 978-0-7695-4295-9
Conference name 2010 Sixth IEEE International Conference on e-Science
Location Brisbane, Australia
Date From 2010-12-07
Date To 2010-12-10
URI http://hdl.handle.net/10072/37331
Date Accessioned 2011-02-02
Date Available 2011-03-16T07:58:27Z
Language en_AU
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Computer Software; Optimisation
Publication Type Conference Publications (Full Written Paper - Refereed)
Publication Type Code e1

Show simple item record

Griffith University copyright notice