Improved biogeography-based optimization for the traveling salesman problem

摘要

The traveling salesman problem (TSP) is one of the most classical combinatorial optimization problems and has attracted a lot of interests from researchers. Many studies have proposed various methods for solving the TSP. Biogeography-based optimization (BBO) is a novel evolutionary algorithm based on migration and mutation mechanism of species between the islands in biogeography. In this paper, we study the application of Biogeography-Based Optimization to solve the Traveling Salesman Problem. For this, we propose an improved hybridization of adaptive Biogeography-Based Optimization with differential evolution (DE) approach, namely IHABBO, to solve the TSP. According to the discrete and combination characteristics of TSP, migration operator and mutation operator of BBO are redesigned. In the new algorithm, modification probability and mutation probability are adaptively changed according to the relation between the cost of fitness function of randomly selected habitat and average cost of fitness function of all habitats last generation. The mutation operators based on DE algorithm and inverse operation are modified and the migration operators based on number of iterations are improved. Meanwhile, immigration rate and emigration rate based on cosine curve are modified. Hence it can generate the promising candidate solutions. The solution gained by IHABBO algorithm is compared with the solution gained by using the other evolution algorithms on two classical TSP. The results of simulation indicate that IHABBO algorithm for the TSP performs better, or at least comparably, in terms of the convergence and the quality of the final solutions. The comparison results with the other evolution algorithms show that IHABBO is very effective for TSP combination optimization.