Adding Negative Learning to Ant Colony Optimization: A Comprehensive Study
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 metaheuristi...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-02-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/9/4/361 |
| _version_ | 1797411461087100928 |
|---|---|
| author | Teddy Nurcahyadi Christian Blum |
| author_facet | Teddy Nurcahyadi Christian Blum |
| author_sort | Teddy Nurcahyadi |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-09T04:46:23Z |
| format | Article |
| id | doaj.art-e1f047458d344a53a68332ee19d5ef38 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-09T04:46:23Z |
| publishDate | 2021-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-e1f047458d344a53a68332ee19d5ef382023-12-03T13:16:06ZengMDPI AGMathematics2227-73902021-02-019436110.3390/math9040361Adding Negative Learning to Ant Colony Optimization: A Comprehensive StudyTeddy Nurcahyadi0Christian Blum1Artificial Intelligence Research Institute (IIIA-CSIC), 08193 Bellaterra, SpainArtificial Intelligence Research Institute (IIIA-CSIC), 08193 Bellaterra, SpainAnt 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.https://www.mdpi.com/2227-7390/9/4/361ant colony optimizationmathematical programmingnegative learningminimum dominating setmulti-dimensional knapsack problem |
| spellingShingle | Teddy Nurcahyadi Christian Blum Adding Negative Learning to Ant Colony Optimization: A Comprehensive Study Mathematics ant colony optimization mathematical programming negative learning minimum dominating set multi-dimensional knapsack problem |
| title | Adding Negative Learning to Ant Colony Optimization: A Comprehensive Study |
| title_full | Adding Negative Learning to Ant Colony Optimization: A Comprehensive Study |
| title_fullStr | Adding Negative Learning to Ant Colony Optimization: A Comprehensive Study |
| title_full_unstemmed | Adding Negative Learning to Ant Colony Optimization: A Comprehensive Study |
| title_short | Adding Negative Learning to Ant Colony Optimization: A Comprehensive Study |
| title_sort | adding negative learning to ant colony optimization a comprehensive study |
| topic | ant colony optimization mathematical programming negative learning minimum dominating set multi-dimensional knapsack problem |
| url | https://www.mdpi.com/2227-7390/9/4/361 |
| work_keys_str_mv | AT teddynurcahyadi addingnegativelearningtoantcolonyoptimizationacomprehensivestudy AT christianblum addingnegativelearningtoantcolonyoptimizationacomprehensivestudy |