Hybridizing Bat Algorithm With Local Discrete Search For Dynamic Traveling Salesman Problem
Authors: Wong Yuan Ling and Jason Teo Tze Wi
Dynamic optimization problems have become increasingly popular to solve in computational science. As real world problems are becoming more complex day by day, dynamic optimization problems have become an alternative platform for the application of heuristics methods. A higher class of heuristics, called metaheuristics has been a popular choice in solving optimization problems because of their ability to adapt to uncertainties and is not biased to any specific problem. One of the well-known classes of metaheuristics is swarm intelligence, inspired by the behavior of animal swarm in the nature. Ant Colony System and Particle Swarm Optimization are two instances of swarm intelligence. Bat algorithm on the other hand is one of the latest swarm intelligence proposed. It has been applied to many continuous and discrete problem domains. In this research, we will attempt to apply hybrid bat algorithm with local search to solve a well-established dynamic combinatorial problem, which is the dynamic traveling salesman problem (DTSP). The experiments included in this thesis are the parameter tuning of the bat algorithm parameters and then using those parameters to determine the optimal settings. The settings are then used in the bat algorithm framework to compare with other metaheuristics such as ACO and ACO with local search. As we have proposed two variants of the bat algorithm, we found that from the experiments, the second proposed variant which is the bat algorithm with natural frequency performs better compared to the bat algorithm with the original proposed frequency across all benchmarks and dynamic test cases.
However, the proposed algorithms were still unable to outperform the conventional ACO and hybridized ACO algorithms. Nevertheless, their performances are enhanced by the hybridization of the 2-Opt local search.