Visibility Adaptation in Ant Colony Optimization for Solving Traveling Salesman Problem
Ant Colony Optimization (ACO) is a practical and well-studied bio-inspired algorithm to generate feasible solutions for combinatorial optimization problems such as the Traveling Salesman Problem (TSP). ACO is inspired by the foraging behavior of ants, where an ant selects the next city to visit acco...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-07-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/10/14/2448 |
| _version_ | 1797417204187136000 |
|---|---|
| author | Abu Saleh Bin Shahadat M. A. H. Akhand Md Abdus Samad Kamal |
| author_facet | Abu Saleh Bin Shahadat M. A. H. Akhand Md Abdus Samad Kamal |
| author_sort | Abu Saleh Bin Shahadat |
| collection | DOAJ |
| description | Ant Colony Optimization (ACO) is a practical and well-studied bio-inspired algorithm to generate feasible solutions for combinatorial optimization problems such as the Traveling Salesman Problem (TSP). ACO is inspired by the foraging behavior of ants, where an ant selects the next city to visit according to the pheromone on the trail and the visibility heuristic (inverse of distance). ACO assigns higher heuristic desirability to the nearest city without considering the issue of returning to the initial city or starting point once all the cities are visited. This study proposes an improved ACO-based method, called ACO with Adaptive Visibility (ACOAV), which intelligently adopts a generalized formula of the visibility heuristic associated with the final destination city. ACOAV uses a new distance metric that includes proximity and eventual destination to select the next city. Including the destination in the metric reduces the tour cost because such adaptation helps to avoid using longer links while returning to the starting city. In addition, partial updates of individual solutions and 3-Opt local search operations are incorporated in the proposed ACOAV. ACOAV is evaluated on a suite of 35 benchmark TSP instances and rigorously compared with ACO. ACOAV generates better solutions for TSPs than ACO, while taking less computational time; such twofold achievements indicate the proficiency of the individual adoption techniques in ACOAV, especially in AV and partial solution update. The performance of ACOAV is also compared with the other ten state-of-the-art bio-inspired methods, including several ACO-based methods. From these evaluations, ACOAV is found as the best one for 29 TSP instances out of 35 instances; among those, optimal solutions have been achieved in 22 instances. Moreover, statistical tests comparing the performance revealed the significance of the proposed ACOAV over the considered bio-inspired methods. |
| first_indexed | 2024-03-09T06:15:24Z |
| format | Article |
| id | doaj.art-2c61f46dab1949b594c230983f19dc78 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-09T06:15:24Z |
| publishDate | 2022-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-2c61f46dab1949b594c230983f19dc782023-12-03T11:53:42ZengMDPI AGMathematics2227-73902022-07-011014244810.3390/math10142448Visibility Adaptation in Ant Colony Optimization for Solving Traveling Salesman ProblemAbu Saleh Bin Shahadat0M. A. H. Akhand1Md Abdus Samad Kamal2Department of Computer Science and Engineering, Khulna University of Engineering & Technology, Khulna 9203, BangladeshDepartment of Computer Science and Engineering, Khulna University of Engineering & Technology, Khulna 9203, BangladeshGraduate School of Science and Technology, Gunma University, Kiryu 376-8515, JapanAnt Colony Optimization (ACO) is a practical and well-studied bio-inspired algorithm to generate feasible solutions for combinatorial optimization problems such as the Traveling Salesman Problem (TSP). ACO is inspired by the foraging behavior of ants, where an ant selects the next city to visit according to the pheromone on the trail and the visibility heuristic (inverse of distance). ACO assigns higher heuristic desirability to the nearest city without considering the issue of returning to the initial city or starting point once all the cities are visited. This study proposes an improved ACO-based method, called ACO with Adaptive Visibility (ACOAV), which intelligently adopts a generalized formula of the visibility heuristic associated with the final destination city. ACOAV uses a new distance metric that includes proximity and eventual destination to select the next city. Including the destination in the metric reduces the tour cost because such adaptation helps to avoid using longer links while returning to the starting city. In addition, partial updates of individual solutions and 3-Opt local search operations are incorporated in the proposed ACOAV. ACOAV is evaluated on a suite of 35 benchmark TSP instances and rigorously compared with ACO. ACOAV generates better solutions for TSPs than ACO, while taking less computational time; such twofold achievements indicate the proficiency of the individual adoption techniques in ACOAV, especially in AV and partial solution update. The performance of ACOAV is also compared with the other ten state-of-the-art bio-inspired methods, including several ACO-based methods. From these evaluations, ACOAV is found as the best one for 29 TSP instances out of 35 instances; among those, optimal solutions have been achieved in 22 instances. Moreover, statistical tests comparing the performance revealed the significance of the proposed ACOAV over the considered bio-inspired methods.https://www.mdpi.com/2227-7390/10/14/2448ant colony optimizationadaptive visibilitytraveling salesman problempartial solution update3-opt local search |
| spellingShingle | Abu Saleh Bin Shahadat M. A. H. Akhand Md Abdus Samad Kamal Visibility Adaptation in Ant Colony Optimization for Solving Traveling Salesman Problem Mathematics ant colony optimization adaptive visibility traveling salesman problem partial solution update 3-opt local search |
| title | Visibility Adaptation in Ant Colony Optimization for Solving Traveling Salesman Problem |
| title_full | Visibility Adaptation in Ant Colony Optimization for Solving Traveling Salesman Problem |
| title_fullStr | Visibility Adaptation in Ant Colony Optimization for Solving Traveling Salesman Problem |
| title_full_unstemmed | Visibility Adaptation in Ant Colony Optimization for Solving Traveling Salesman Problem |
| title_short | Visibility Adaptation in Ant Colony Optimization for Solving Traveling Salesman Problem |
| title_sort | visibility adaptation in ant colony optimization for solving traveling salesman problem |
| topic | ant colony optimization adaptive visibility traveling salesman problem partial solution update 3-opt local search |
| url | https://www.mdpi.com/2227-7390/10/14/2448 |
| work_keys_str_mv | AT abusalehbinshahadat visibilityadaptationinantcolonyoptimizationforsolvingtravelingsalesmanproblem AT mahakhand visibilityadaptationinantcolonyoptimizationforsolvingtravelingsalesmanproblem AT mdabdussamadkamal visibilityadaptationinantcolonyoptimizationforsolvingtravelingsalesmanproblem |