Anti-pheromone as a tool for better exploration of search space

James Montgomery, Marcus Randall

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

40 Citations (Scopus)
16 Downloads (Pure)

Abstract

Many animals use chemical substances known as pheromones to induce behavioural changes in other members of the same species. The use of pheromones by ants in particular has lead to the development of a number of computational analogues of ant colony behaviour including Ant Colony Optimisation. Although many animals use a range of pheromones in their communication, ant algorithms have typically focused on the use of just one, a substance that encourages succeeding generations of (artificial) ants to follow the same path as previous generations. Ant algorithms for multi-objective optimisation and those employing multiple colonies have made use of more than one pheromone, but the interactions between these different pheromones are largely simple extensions of single criterion, single colony ant algorithms. This paper investigates an alternative form of interaction between normal pheromone and anti-pheromone. Three variations of Ant Colony System that apply the anti-pheromone concept in different ways are described and tested against benchmark travelling salesman problems. The results indicate that the use of anti-pheromone can lead to improved performance. However, if anti-pheromone is allowed too great an influence on ants’ decisions, poorer performance may result.

Original languageEnglish
Title of host publicationAnt Algorithms - 3rd International Workshop, ANTS 2002, Proceedings
EditorsMarco Dorigo , Gianni di Caro, Michael Sampels
PublisherSpringer-Verlag London Ltd.
Pages100-110
Number of pages11
ISBN (Print)9783540457244
DOIs
Publication statusPublished - 1 Jan 2002
Event3rd International Workshop on Ant Algorithms, ANTS 2002 - Brussels, Belgium
Duration: 12 Sep 200214 Sep 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2463
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd International Workshop on Ant Algorithms, ANTS 2002
CountryBelgium
CityBrussels
Period12/09/0214/09/02

Fingerprint

Pheromone
Search Space
Animals
Traveling salesman problem
Ant colony optimization
Multiobjective optimization
Ant Algorithm
Communication
Ant Colony System
Ant Colony Algorithm
Travelling salesman problems
Ant Colony
Interaction
Multi-objective Optimization
Benchmark
Analogue
Path

Cite this

Montgomery, J., & Randall, M. (2002). Anti-pheromone as a tool for better exploration of search space. In M. Dorigo , G. di Caro, & M. Sampels (Eds.), Ant Algorithms - 3rd International Workshop, ANTS 2002, Proceedings (pp. 100-110). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2463). Springer-Verlag London Ltd.. https://doi.org/10.1007/3-540-45724-0_9
Montgomery, James ; Randall, Marcus. / Anti-pheromone as a tool for better exploration of search space. Ant Algorithms - 3rd International Workshop, ANTS 2002, Proceedings. editor / Marco Dorigo ; Gianni di Caro ; Michael Sampels. Springer-Verlag London Ltd., 2002. pp. 100-110 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{cfab690ef9cc44f2963be15dcea24dec,
title = "Anti-pheromone as a tool for better exploration of search space",
abstract = "Many animals use chemical substances known as pheromones to induce behavioural changes in other members of the same species. The use of pheromones by ants in particular has lead to the development of a number of computational analogues of ant colony behaviour including Ant Colony Optimisation. Although many animals use a range of pheromones in their communication, ant algorithms have typically focused on the use of just one, a substance that encourages succeeding generations of (artificial) ants to follow the same path as previous generations. Ant algorithms for multi-objective optimisation and those employing multiple colonies have made use of more than one pheromone, but the interactions between these different pheromones are largely simple extensions of single criterion, single colony ant algorithms. This paper investigates an alternative form of interaction between normal pheromone and anti-pheromone. Three variations of Ant Colony System that apply the anti-pheromone concept in different ways are described and tested against benchmark travelling salesman problems. The results indicate that the use of anti-pheromone can lead to improved performance. However, if anti-pheromone is allowed too great an influence on ants’ decisions, poorer performance may result.",
author = "James Montgomery and Marcus Randall",
year = "2002",
month = "1",
day = "1",
doi = "10.1007/3-540-45724-0_9",
language = "English",
isbn = "9783540457244",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag London Ltd.",
pages = "100--110",
editor = "{Dorigo }, Marco and {di Caro}, Gianni and Michael Sampels",
booktitle = "Ant Algorithms - 3rd International Workshop, ANTS 2002, Proceedings",
address = "Italy",

}

Montgomery, J & Randall, M 2002, Anti-pheromone as a tool for better exploration of search space. in M Dorigo , G di Caro & M Sampels (eds), Ant Algorithms - 3rd International Workshop, ANTS 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2463, Springer-Verlag London Ltd., pp. 100-110, 3rd International Workshop on Ant Algorithms, ANTS 2002, Brussels, Belgium, 12/09/02. https://doi.org/10.1007/3-540-45724-0_9

Anti-pheromone as a tool for better exploration of search space. / Montgomery, James; Randall, Marcus.

Ant Algorithms - 3rd International Workshop, ANTS 2002, Proceedings. ed. / Marco Dorigo ; Gianni di Caro; Michael Sampels. Springer-Verlag London Ltd., 2002. p. 100-110 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2463).

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

TY - GEN

T1 - Anti-pheromone as a tool for better exploration of search space

AU - Montgomery, James

AU - Randall, Marcus

PY - 2002/1/1

Y1 - 2002/1/1

N2 - Many animals use chemical substances known as pheromones to induce behavioural changes in other members of the same species. The use of pheromones by ants in particular has lead to the development of a number of computational analogues of ant colony behaviour including Ant Colony Optimisation. Although many animals use a range of pheromones in their communication, ant algorithms have typically focused on the use of just one, a substance that encourages succeeding generations of (artificial) ants to follow the same path as previous generations. Ant algorithms for multi-objective optimisation and those employing multiple colonies have made use of more than one pheromone, but the interactions between these different pheromones are largely simple extensions of single criterion, single colony ant algorithms. This paper investigates an alternative form of interaction between normal pheromone and anti-pheromone. Three variations of Ant Colony System that apply the anti-pheromone concept in different ways are described and tested against benchmark travelling salesman problems. The results indicate that the use of anti-pheromone can lead to improved performance. However, if anti-pheromone is allowed too great an influence on ants’ decisions, poorer performance may result.

AB - Many animals use chemical substances known as pheromones to induce behavioural changes in other members of the same species. The use of pheromones by ants in particular has lead to the development of a number of computational analogues of ant colony behaviour including Ant Colony Optimisation. Although many animals use a range of pheromones in their communication, ant algorithms have typically focused on the use of just one, a substance that encourages succeeding generations of (artificial) ants to follow the same path as previous generations. Ant algorithms for multi-objective optimisation and those employing multiple colonies have made use of more than one pheromone, but the interactions between these different pheromones are largely simple extensions of single criterion, single colony ant algorithms. This paper investigates an alternative form of interaction between normal pheromone and anti-pheromone. Three variations of Ant Colony System that apply the anti-pheromone concept in different ways are described and tested against benchmark travelling salesman problems. The results indicate that the use of anti-pheromone can lead to improved performance. However, if anti-pheromone is allowed too great an influence on ants’ decisions, poorer performance may result.

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

U2 - 10.1007/3-540-45724-0_9

DO - 10.1007/3-540-45724-0_9

M3 - Conference contribution

SN - 9783540457244

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

SP - 100

EP - 110

BT - Ant Algorithms - 3rd International Workshop, ANTS 2002, Proceedings

A2 - Dorigo , Marco

A2 - di Caro, Gianni

A2 - Sampels, Michael

PB - Springer-Verlag London Ltd.

ER -

Montgomery J, Randall M. Anti-pheromone as a tool for better exploration of search space. In Dorigo M, di Caro G, Sampels M, editors, Ant Algorithms - 3rd International Workshop, ANTS 2002, Proceedings. Springer-Verlag London Ltd. 2002. p. 100-110. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-45724-0_9