Search bias in constructive metaheuristics and implications for ant colony optimisation

James Montgomery; Marcus Randall; Tim Hendtlass

doi:10.1007/978-3-540-28646-2_39

Search bias in constructive metaheuristics and implications for ant colony optimisation

James Montgomery^*, Marcus Randall, Tim Hendtlass

^*Corresponding author for this work

Bond Business School

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

11 Citations (Scopus)

210 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 language	English
Title of host publication	Ant Colony Optimization and Swarm Intelligence
Subtitle of host publication	ANTS 2004
Editors	M Dorigo, M Birattari, C Blum, L M Gambardella, F Mondada, T Stutzle
Place of Publication	Heidelberg
Publisher	Springer
Pages	390-397
Number of pages	8
Volume	3172 LNCS
ISBN (Print)	3540226729, 9783540226727
DOIs	https://doi.org/10.1007/978-3-540-28646-2_39
Publication status	Published - 2004
Event	International Workshop on Ant Colony Optimization and Swarm Intelligence - Brussels, Belgium Duration: 5 Sept 2004 → 8 Sept 2004 Conference number: 4th http://iridia.ulb.ac.be/ants/ants2004/ http://iridia.ulb.ac.be/ants/ants2004/

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3172 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	International Workshop on Ant Colony Optimization and Swarm Intelligence
Abbreviated title	ANTS 2004
Country/Territory	Belgium
City	Brussels
Period	5/09/04 → 8/09/04
Internet address	http://iridia.ulb.ac.be/ants/ants2004/ http://iridia.ulb.ac.be/ants/ants2004/

Access to Document

10.1007/978-3-540-28646-2_39

Search bias in constructive metaheuristics and implications for ant colony optimisationAccepted author manuscript, 159 KBLicence: Unspecified

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

Montgomery, James ; Randall, Marcus ; Hendtlass, Tim. / Search bias in constructive metaheuristics and implications for ant colony optimisation. Ant Colony Optimization and Swarm Intelligence : ANTS 2004. editor / M Dorigo ; M Birattari ; C Blum ; L M Gambardella ; F Mondada ; T Stutzle. Vol. 3172 LNCS Heidelberg : Springer, 2004. pp. 390-397 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2f8327e7701e4a748e9ec207aa1cd1f2,

title = "Search bias in constructive metaheuristics and implications for ant colony optimisation",

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.",

author = "James Montgomery and Marcus Randall and Tim Hendtlass",

year = "2004",

doi = "10.1007/978-3-540-28646-2_39",

language = "English",

isbn = "3540226729",

volume = "3172 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "390--397",

editor = "M Dorigo and M Birattari and C Blum and Gambardella, {L M} and F Mondada and T Stutzle",

booktitle = "Ant Colony Optimization and Swarm Intelligence",

address = "Germany",

note = "International Workshop on Ant Colony Optimization and Swarm Intelligence, ANTS 2004 ; Conference date: 05-09-2004 Through 08-09-2004",

url = "http://iridia.ulb.ac.be/ants/ants2004/, http://iridia.ulb.ac.be/ants/ants2004/",

}

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, LM Gambardella, F Mondada & T Stutzle (eds), Ant Colony Optimization and Swarm Intelligence : ANTS 2004. vol. 3172 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3172 LNCS, Springer, Heidelberg, pp. 390-397, International Workshop on Ant Colony Optimization and Swarm Intelligence, Brussels, Belgium, 5/09/04. https://doi.org/10.1007/978-3-540-28646-2_39

Search bias in constructive metaheuristics and implications for ant colony optimisation. / Montgomery, James; Randall, Marcus; Hendtlass, Tim.
Ant Colony Optimization and Swarm Intelligence : ANTS 2004. ed. / M Dorigo; M Birattari; C Blum; L M Gambardella; F Mondada; T Stutzle. Vol. 3172 LNCS Heidelberg: Springer, 2004. p. 390-397 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3172 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

TY - GEN

T1 - Search bias in constructive metaheuristics and implications for ant colony optimisation

AU - Montgomery, James

AU - Randall, Marcus

AU - Hendtlass, Tim

N1 - Conference code: 4th

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

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

U2 - 10.1007/978-3-540-28646-2_39

DO - 10.1007/978-3-540-28646-2_39

M3 - Conference contribution

AN - SCOPUS:26944450617

SN - 3540226729

SN - 9783540226727

VL - 3172 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 390

EP - 397

BT - Ant Colony Optimization and Swarm Intelligence

A2 - Dorigo, M

A2 - Birattari, M

A2 - Blum, C

A2 - Gambardella, L M

A2 - Mondada, F

A2 - Stutzle, T

PB - Springer

CY - Heidelberg

T2 - International Workshop on Ant Colony Optimization and Swarm Intelligence

Y2 - 5 September 2004 through 8 September 2004

ER -

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

Search bias in constructive metaheuristics and implications for ant colony optimisation

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this