Adding Negative Learning to Ant Colony Optimization: A Comprehensive Study

Teddy Nurcahyadi and Christian Blum
Additional contact information
Teddy Nurcahyadi: Artificial Intelligence Research Institute (IIIA-CSIC), 08193 Bellaterra, Spain
Christian Blum: Artificial Intelligence Research Institute (IIIA-CSIC), 08193 Bellaterra, Spain

Mathematics, 2021, vol. 9, issue 4, 1-23

Abstract: Ant colony optimization is a metaheuristic that is mainly used for solving hard combinatorial optimization problems. The distinctive feature of ant colony optimization is a learning mechanism that is based on learning from positive examples. This is also the case in other learning-based metaheuristics such as evolutionary algorithms and particle swarm optimization. Examples from nature, however, indicate that negative learning—in addition to positive learning—can beneficially be used for certain purposes. Several research papers have explored this topic over the last decades in the context of ant colony optimization, mostly with limited success. In this work we present and study an alternative mechanism making use of mathematical programming for the incorporation of negative learning in ant colony optimization. Moreover, we compare our proposal to some well-known existing negative learning approaches from the related literature. Our study considers two classical combinatorial optimization problems: the minimum dominating set problem and the multi dimensional knapsack problem. In both cases we are able to show that our approach significantly improves over standard ant colony optimization and over the competing negative learning mechanisms from the literature.

Keywords: ant colony optimization; mathematical programming; negative learning; minimum dominating set; multi-dimensional knapsack problem (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/4/361/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/4/361/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:4:p:361-:d:497512

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().