A Biogeography-Based Optimization with a Greedy Randomized Adaptive Search Procedure and the 2-Opt Algorithm for the Traveling Salesman Problem
Cheng-Hsiung Tsai, Yu‐Da Lin, Cheng-Hong Yang, Chien-Kun Wang, Li-Chun Chiang, Po-Jui Chiang
Abstract
We develop a novel method to improve biogeography-based optimization (BBO) for solving the traveling salesman problem (TSP). The improved method is comprised of a greedy randomized adaptive search procedure, the 2-opt algorithm, and G2BBO. The G2BBO formulation is derived and the process flowchart is shown in this article. For solving TSP, G2BBO effectively avoids the local minimum problem and accelerates convergence by optimizing the initial values. To demonstrate, we adopt three public datasets (eil51, eil76, and kroa100) from TSPLIB and compare them with various well-known algorithms. The results of G2BBO as well as the other algorithms perform close enough to the optimal solutions in eil51 and eil76 where simple TSP coordinates are considered. In the case of kroa100, with more complicated coordinates, G2BBO shows greater performance over other methods.