Automated design of state transition rules in ant colony optimization by genetic programming: a comprehensive investigation
Open Access
- 28 January 2025
- journal article
- research article
- Published by Springer Nature in Memetic Computing
- Vol. 17 (1) , 1-22
Abstract
The automated design of Ant Colony Optimization (ACO) algorithms has become increasingly significant, particularly in addressing complex combinatorial optimization problems. Although existing methods have achieved some success, they still face limitations, particularly the high dependency on expert knowledge, pre-solved data, and challenges in interpretability. Genetic Programming (GP), as a proven technology, has shown potential in optimizing the automated design state transition rules of ACO. However, existing research on GP-ACO is insufficient, particularly in terms of experimental validation and systematic evaluation. To address these issues, this study conducts comprehensive experiments to explore several key questions: the generality of GP-ACO on homogeneously distributed maps, the impact of different ACO variants on the learning capabilities of GP-ACO, the effect of 2-opt local search on the learning capabilities of GP-ACO, the enhancement of learning capabilities through the addition of more global information, and the interpretability of GP-ACO. The findings indicate that GP-ACO exhibits robust generality; variations among ACO variants have minimal impact on learning performance; 2-opt local search can somewhat diminish the performance of GP-ACO in the Max–Min Ant System; additional global information can significantly enhance the learning capabilities of GP-ACO; and GP-ACO has good interpretability.Keywords
All Related Versions
Funding Information
- Victoria University of Wellington
This publication has 36 references indexed in Scilit:
- Boosting ant colony optimization via solution prediction and machine learningComputers & Operations Research, 2022
- Genetic programming-based hyper-heuristic approach for solving dynamic job shop scheduling problem with extended technical precedence constraintsComputers & Operations Research, 2021
- Ant Colony Optimization: Overview and Recent Advances2018
- Improved auto control ant colony optimization using lazy ant approach for grid scheduling problemFuture Generation Computer Systems, 2016
- Automatic Design of Ant Algorithms with Grammatical Evolution2012
- Designing Pheromone Update Strategies with Strongly Typed Genetic Programming2011
- Exploring Hyper-heuristic Methodologies with Genetic Programming2009
- A survey of search methodologies and automated system development for examination timetablingJournal of Scheduling, 2008
- The Generalized Traveling Salesman and Orienteering Problems2007
- Ant Colony System for a Dynamic Vehicle Routing ProblemJournal of Combinatorial Optimization, 2005