Modifications and additions to ant colony optimisation to solve the set partitioning probleme-Science 2010: Sixth IEEE international conference on e-Science workshops
Date of this Version12-7-2010
Document TypeConference Paper
AbstractAnt 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 simultaneouly reduce solver time while increasing solution quality.
Citation InformationMarcus Randall and Andrew Lewis. "Modifications and additions to ant colony optimisation to solve the set partitioning problem" e-Science 2010: Sixth IEEE international conference on e-Science workshops (2010) p. 110 - 116
Available at: http://works.bepress.com/marcus_randall/34/