Opposition-Based Ant Colony Optimization Algorithm for the Traveling Salesman Problem
Open Access
- 24 September 2020
- journal article
- research article
- Published by MDPI AG in Mathematics
- Vol. 8 (10) , 1650
Abstract
Opposition-based learning (OBL) has been widely used to improve many swarm intelligent optimization (SI) algorithms for continuous problems during the past few decades. When the SI optimization algorithms apply OBL to solve discrete problems, the construction and utilization of the opposite solution is the key issue. Ant colony optimization (ACO) generally used to solve combinatorial optimization problems is a kind of classical SI optimization algorithm. Opposition-based ACO which is combined in OBL is proposed to solve the symmetric traveling salesman problem (TSP) in this paper. Two strategies for constructing opposite path by OBL based on solution characteristics of TSP are also proposed. Then, in order to use information of opposite path to improve the performance of ACO, three different strategies, direction, indirection, and random methods, mentioned for pheromone update rules are discussed individually. According to the construction of the inverse solution and the way of using it in pheromone updating, three kinds of improved ant colony algorithms are proposed. To verify the feasibility and effectiveness of strategies, two kinds of ACO algorithms are employed to solve TSP instances. The results demonstrate that the performance of opposition-based ACO is better than that of ACO without OBL.Keywords
This publication has 46 references indexed in Scilit:
- Enhanced opposition-based differential evolution for solving high-dimensional continuous optimization problemsSoft Computing, 2010
- Firefly algorithm, stochastic test functions and design optimisationInternational Journal of Bio-Inspired Computation, 2010
- A comparative study of Artificial Bee Colony algorithmApplied Mathematics and Computation, 2009
- A survey: algorithms simulating bee swarm intelligenceArtificial Intelligence Review, 2009
- Study on hybrid PS-ACO algorithmApplied Intelligence, 2009
- An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problemApplied Intelligence, 2008
- Ant colony optimization theory: A surveyTheoretical Computer Science, 2005
- – Ant SystemFuture Generation Computer Systems, 2000
- Ant colony system: a cooperative learning approach to the traveling salesman problemIEEE Transactions on Evolutionary Computation, 1997
- Ant system: optimization by a colony of cooperating agentsIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1996