Search bias in constructive metaheuristics and implications for ant colony optimisation

James Montgomery*, Marcus Randall, Tim Hendtlass

*Corresponding author for this work

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

7 Citations (Scopus)
138 Downloads (Pure)

Abstract

Constructive metaheuristics explore a tree of constructive decisions, the topology of which is determined by the way solutions are represented and constructed. Some solution representations allow particular solutions to be reached on a greater number of paths in this construction tree than other solutions, which can introduce a bias to the search. A bias can also be introduced by the topology of the construction tree. This is particularly the case in problems where certain solution representations are infeasible. This paper presents an examination of the mechanisms that determine the topologies of construction trees and the implications for ant colony optimisation. The results provide insights into why certain assignment orders perform better in problems such as the quadratic and generalised assignment problems, in terms of both solution quality and avoiding infeasible solutions.

Original languageEnglish
Title of host publicationAnt Colony Optimization and Swarm Intelligence
Subtitle of host publicationANTS 2004
EditorsM Dorigo, M Birattari, C Blum, L M Gambardella, F Mondada, T Stutzle
Place of PublicationHeidelberg
PublisherSpringer
Pages390-397
Number of pages8
Volume3172 LNCS
ISBN (Print)3540226729, 9783540226727
DOIs
Publication statusPublished - 2004
EventInternational Workshop on Ant Colony Optimization and Swarm Intelligence - Brussels, Belgium
Duration: 5 Sep 20048 Sep 2004
Conference number: 4th
http://iridia.ulb.ac.be/ants/ants2004/
http://iridia.ulb.ac.be/ants/ants2004/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3172 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

ConferenceInternational Workshop on Ant Colony Optimization and Swarm Intelligence
Abbreviated title ANTS 2004
CountryBelgium
CityBrussels
Period5/09/048/09/04
Internet address

Fingerprint Dive into the research topics of 'Search bias in constructive metaheuristics and implications for ant colony optimisation'. Together they form a unique fingerprint.

  • Cite this

    Montgomery, J., Randall, M., & Hendtlass, T. (2004). Search bias in constructive metaheuristics and implications for ant colony optimisation. In M. Dorigo, M. Birattari, C. Blum, L. M. Gambardella, F. Mondada, & T. Stutzle (Eds.), Ant Colony Optimization and Swarm Intelligence : ANTS 2004 (Vol. 3172 LNCS, pp. 390-397). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3172 LNCS). Springer. https://doi.org/10.1007/978-3-540-28646-2_39