Open AccessPopulation Diversity in Ant-inspired Optimization Algorithms
Author(s) -
Aleksander Byrski,
Krzysztof Węgrzyński,
Wojciech Radwański,
Grażyna Starzec,
Mateusz Starzec,
Monika Bargieł,
Aleksandra Urbańczyk,
Marek Kisiel-Dorohinicki
Publication year - 2021
Publication title -
computer science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.145
H-Index - 5
eISSN - 2300-7036
pISSN - 1508-2806
DOI - 10.7494/csci.2021.22.3.4301
Subject(s) - computer science , ant colony optimization algorithms , metaheuristic , evolutionary algorithm , parallel metaheuristic , premature convergence , convergence (economics) , population , extremal optimization , ant colony , optimization problem , artificial intelligence , mathematical optimization , focus (optics) , machine learning , algorithm , genetic algorithm , meta optimization , mathematics , physics , demography , sociology , optics , economics , economic growth
Finding a balance between exploration and exploitation is very important in the case of metaheuristics optimization, especially in the systems leveraging population of individuals expressing (as in Evolutionary Algorithms, etc.) or constructing (as in Ant Colony Optimization) solutions. Premature convergence is a real problem and finding means of its automatic detection and counteracting are of great importance. Measuring diversity in Evolutionary Algorithms working in real-value search space is often computationally complex, but feasible while measuring diversity in combinatorial domain is practically impossible (cf. Closest String Problem). Nevertheless, we propose several practical and feasible diversity measurement techniques dedicated to Ant Colony Optimization algorithms, leveraging the fact that even though analysis of the search space is at least an NP problem, we can focus on the pheromone table, where the direct outcomes of the search are expressed and can be analyzed. Besides proposing the measurement techniques, we apply them to assess the diversity of several variants of ACO, and closely analyze their features for the classic ACO. The discussion of the results is the first step towards applying the proposed measurement techniques in auto-adaptation of the parameters affecting directly the exploitation and exploration features in ACO in the future.