Modifications and additions to ant colony optimisation to solve the set partitioning problem

Marcus Randall, Andrew Lewis

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

3 Citations (Scopus)

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 simultaneouly reduce solver time while increasing solution quality.

Original languageEnglish
Title of host publicationProceedings - 6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010
Pages110-116
Number of pages7
DOIs
Publication statusPublished - 2010
Event6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010 - Brisbane, QLD, Australia
Duration: 7 Dec 201010 Dec 2010

Conference

Conference6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010
CountryAustralia
CityBrisbane, QLD
Period7/12/1010/12/10

Fingerprint

Ant colony optimization
Combinatorial optimization
Constrained optimization
Restoration

Cite this

Randall, M., & Lewis, A. (2010). Modifications and additions to ant colony optimisation to solve the set partitioning problem. In Proceedings - 6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010 (pp. 110-116). [5693150] https://doi.org/10.1109/eScienceW.2010.27
Randall, Marcus ; Lewis, Andrew. / Modifications and additions to ant colony optimisation to solve the set partitioning problem. Proceedings - 6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010. 2010. pp. 110-116
@inproceedings{63c1b854699d4cf69adb81723028aff3,
title = "Modifications and additions to ant colony optimisation to solve the set partitioning problem",
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 simultaneouly reduce solver time while increasing solution quality.",
author = "Marcus Randall and Andrew Lewis",
year = "2010",
doi = "10.1109/eScienceW.2010.27",
language = "English",
isbn = "9780769542959",
pages = "110--116",
booktitle = "Proceedings - 6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010",

}

Randall, M & Lewis, A 2010, Modifications and additions to ant colony optimisation to solve the set partitioning problem. in Proceedings - 6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010., 5693150, pp. 110-116, 6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010, Brisbane, QLD, Australia, 7/12/10. https://doi.org/10.1109/eScienceW.2010.27

Modifications and additions to ant colony optimisation to solve the set partitioning problem. / Randall, Marcus; Lewis, Andrew.

Proceedings - 6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010. 2010. p. 110-116 5693150.

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

TY - GEN

T1 - Modifications and additions to ant colony optimisation to solve the set partitioning problem

AU - Randall, Marcus

AU - Lewis, Andrew

PY - 2010

Y1 - 2010

N2 - 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 simultaneouly reduce solver time while increasing solution quality.

AB - 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 simultaneouly reduce solver time while increasing solution quality.

UR - http://www.scopus.com/inward/record.url?scp=79951846204&partnerID=8YFLogxK

U2 - 10.1109/eScienceW.2010.27

DO - 10.1109/eScienceW.2010.27

M3 - Conference contribution

SN - 9780769542959

SP - 110

EP - 116

BT - Proceedings - 6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010

ER -

Randall M, Lewis A. Modifications and additions to ant colony optimisation to solve the set partitioning problem. In Proceedings - 6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010. 2010. p. 110-116. 5693150 https://doi.org/10.1109/eScienceW.2010.27