Source-linked AI summary
An Improved Discrete Bat Algorithm for Symmetric and Asymmetric Traveling Salesman Problems
Eneko Osaba, Xin-She Yang, Fernando Diaz, Pedro Lopez-Garcia, Roberto Carballedo
TL;DR
The paper asks whether Bat Algorithm can be adapted effectively to routing problems, specifically TSP and ATSP. It develops a discrete BA and an improved variant, then compares them across 37 instances with established metaheuristics. The improved BA outperforms the alternatives significantly in most cases.
Problem
Bat Algorithm had been rarely applied to routing problems, motivating evaluation on the symmetric and asymmetric Traveling Salesman Problems.
Method
The paper develops a discrete BA and an improved version that changes bat movement according to solution-space location, using Hamming distance between bats.
Results
Across 37 instances, the Improved Bat Algorithm outperformed the other alternatives, with improvements significant in most cases.
Takeaways & Limitations
The study supports the IBA as a promising approximation method for the TSP and ATSP within the tested benchmark scope.
Takeaways & Limitations
The conclusions cannot be generalized to other discrete problems, and the comparison used five selected techniques.
Abstract
from arXiv · showhide
Bat algorithm is a population metaheuristic proposed in 2010 which is based on the echolocation or bio-sonar characteristics of microbats. Since its first implementation, the bat algorithm has been used in a wide range of fields. In this paper, we present a discrete version of the bat algorithm to solve the well-known symmetric and asymmetric traveling salesman problems. In addition, we propose an improvement in the basic structure of the classic bat algorithm. To prove that our proposal is a promising approximation method, we have compared its performance in 37 instances with the results obtained by five different techniques: evolutionary simulated annealing, genetic algorithm, an island based distributed genetic algorithm, a discrete firefly algorithm and an imperialist competitive algorithm. In order to obtain fair and rigorous comparisons, we have conducted three different statistical tests along the paper: the Student's $t$-test, the Holm's test, and the Friedman test. We have also compared the convergence behaviour shown by our proposal with the ones shown by the evolutionary simulated annealing, and the discrete firefly algorithm. The experimentation carried out in this study has shown that the presented improved bat algorithm outperforms significantly all the other alternatives in most of the cases.
1 Introduction
Routing problems matter because they model socially and commercially relevant situations while posing major computational challenges. This paper develops and evaluates a discrete and improved Bat Algorithm for TSP and ATSP.
- Routing problems support transport and logistics applications, where efficient resolution can produce social or business benefits.
- Because routing problems are NP-Hard, solving them efficiently remains a major scientific challenge.
- The Bat Algorithm, proposed in 2010, is a microbat-echolocation metaheuristic applied across multiple optimization fields.
- The paper presents a discrete BA for TSP and ATSP and an improved version whose performance significantly exceeds the basic versions.
- The IBA is evaluated on 37 TSP-ATSP instances against two basic BAs and five established metaheuristics using rigorous statistical comparisons.
2 Related Work
Prior work has applied BA variants and hybrid methods to several optimization domains, but routing applications remain rare. The paper addresses this gap with a discrete IBA whose movement uses Hamming distance and location-dependent patterns.
- BA research includes fuzzy-logic, chaotic, binary, and hybrid variants for ergonomic screening, parameter adaptation, feature selection, and numerical optimization.
- Despite substantial BA research, the algorithm has rarely been applied to routing problems.
- The proposed IBA introduces Hamming distance to measure swarm-bat separation, an approach not previously used for a BA.
- Unlike basic BA, the IBA assigns movement schemes according to each bat's location in the solution space.
- The TSP has served extensively as a benchmark for classical, recent, bio-inspired, and hybrid optimization techniques.
3 Bat Algorithm
The basic BA models microbat echolocation through population-based movement, local search, and adaptive loudness and pulse-rate parameters. Solutions are iteratively generated, evaluated, and accepted until termination.
- BA uses echolocation-inspired rules in which bats adjust pulse frequency and emission rate according to prey proximity.
- Each bat represents a candidate solution, with velocity, frequency, pulse rate, and loudness initialized alongside the objective function.
- The algorithm updates every bat's velocity and position each generation to generate new solutions.
- The algorithm selects promising solutions, performs local random-walk search, and conditionally accepts new solutions.
- After accepted improvements, loudness decreases and pulse rate increases; this update uses constants α and γ, set to 0.98 in the study.
4 The Traveling Salesman Problem
The TSP and ATSP seek minimum-cost tours through all nodes exactly once, differing in whether travel costs are symmetric. Both are NP-Hard and widely used as discrete-optimization benchmarks.
- Both problems are NP-Hard and are widely used as benchmarking problems for discrete optimization algorithms.
- TSP and ATSP are complete-graph routing problems whose vertices represent system nodes and arcs represent their interconnections.
- In symmetric TSP, traveling costs are equal in both directions; ATSP permits directional cost differences.
- A valid tour starts and ends at the same node, visits every node once, and minimizes total route cost.
- Solutions use a permutation encoding that records the order in which nodes are visited.
5 Our Improved Discrete Bat Algorithm for the TSP and ATSP
The paper adapts bat-algorithm movements and parameters to discrete TSP and ATSP solutions, then improves movement selection by matching move size to each bat’s distance from the swarm’s best solution.
- 5.1 Discrete Bat Algorithm for the TSP and ATSP: The classic BA requires modification because TSP and ATSP are combinatorial rather than continuous optimization problems.
- 5.1 Discrete Bat Algorithm for the TSP and ATSP: The discrete BA represents each bat as a feasible TSP or ATSP route and evaluates solutions by total traveling cost.
- 5.1 Discrete Bat Algorithm for the TSP and ATSP: The discrete versions omit frequency and redefine velocity using the Hamming distance between a bat and the swarm’s best bat.Velocity is treated as a random number between 1 and that Hamming distance, which counts noncorresponding sequence elements.
- 5.1 Discrete Bat Algorithm for the TSP and ATSP: Each bat generates neighbors through 2-opt or 3-opt moves, examining vi neighbors and selecting the best current movement.The 2-opt removes two arcs, whereas 3-opt removes three arcs and has greater complexity.
- 5.2 Our proposed improvement for the discrete Bat Algorithm: The improved BA changes the uniform movement pattern so each bat moves differently according to its position relative to the best bat.The improvement distinguishes bats with large and small vi values and assigns different neighborhood moves accordingly.
- 5.2 Our proposed improvement for the discrete Bat Algorithm: Bats far from the best solution perform large 3-opt moves, while bats in promising positions perform short 2-opt moves.The threshold is vi greater than n/2 for a large move and vi less than n/2 for a short move, where n is the number of instance nodes.
- 5.2 Our proposed improvement for the discrete Bat Algorithm: Using different neighborhood structures throughout execution enhances exploration capacity and improves result quality, according to the paper.
6 Experimentation
The experimentation evaluates the improved bat algorithm (IBA) on 37 TSP and ATSP instances against basic bat algorithms and five metaheuristics using comparative, statistical, and convergence analyses. IBA generally achieves stronger solution quality, robustness, convergence, and acceptable runtimes.
- IBA versus basic BA: IBA met or outperformed both basic discrete BA versions in 100% of cases, with statistically significant differences in 90% of confrontations.The authors attribute this advantage to switching among neighborhood structures during execution.
- Comparison with literature techniques: 81.81% of TSP instances and 73.33% of ATSP instances favored IBA over ESA, GA, and IDGA, while IBA reached optimal solutions in 59.45% of all instances.IBA was worse in only two TSP and two ATSP instances in the aggregate comparison.
- Robustness and runtime: IBA had lower standard deviations than the other metaheuristics, indicating a narrower range of solution quality and greater reported robustness.The authors associate this robustness with reliability in real environments.
- Robustness and runtime: Runtime differences were not remarkable: IBA was slightly better than ESA, similar to DGA, while GA was fastest and all execution times were considered acceptable.The reported runtime comparison therefore favors solution quality without identifying a major execution-time disadvantage for IBA.
- Comparison with literature techniques: IBA outperformed DFA and DICA in 67.56% of instances, including 70.27% against DFA and 83.78% against DICA.It also reached optimal solutions more often than both comparison methods.
- Statistical and convergence analysis: Friedman and Holm analyses found significant differences among methods, with IBA ranked best and significantly better than the compared techniques in most reported cases.For ATSP, Holm’s test found IBA significantly better than GA, IDGA, ESA, and DICA, but not significantly better than DFA.
- Statistical and convergence analysis: IBA outperformed ESA and DFA in convergence on 62.85% of instances, performing better than ESA especially for problems with approximately 100 nodes or fewer.The authors state that this can yield better results with fewer objective-function evaluations.
7 Conclusions and Further Work
The paper presents the first discrete Bat Algorithm for TSP and ATSP and an improved version whose movement patterns depend on each bat’s location in the solution space. Across 37 instances, the Improved Bat Algorithm outperformed the alternatives in most cases, but the conclusions are not generalizable to other discrete problems.
- The paper presents the first Discrete Bat Algorithm for solving the Traveling Salesman Problem and the Asymmetric Traveling Salesman Problem.
- The Improved Bat Algorithm gives bats different movement patterns depending on their locations in the solution space.This improvement adds a form of “intelligence” to the bats.
- 37 instances were used to compare the Improved Bat Algorithm with two basic bat algorithms and five other metaheuristics.The comparisons also included Student’s t-test, Holm’s test, and Friedman test analyses.
- The Improved Bat Algorithm outperformed all other alternatives, with improvements significant in most cases.
- The conclusions cannot be generalized to other discrete problems beyond the standard TSP and ATSP benchmarks.Future work includes applying the method to capacitated and richer vehicle-routing problems and comparing it with exact methods and commercial solvers.