Hybrid Bird Mating Optimizer With Single-Based Algorithms for Combinatorial Optimization Problems

Abstract

Bird mating optimizer (BMO) is a population-based metaheuristic that has been recently extended to solve combinatorial optimization problems. Even though the algorithm shows promising performance in solving combinatorial optimization problems, it suffers from slow convergence and poor efficiency which leads to poor solution quality for some problem instances. This is due to the limited capability of BMO in exploiting the search space and identifying more promising regions. Therefore, in this work we propose a hybrid BMO with five single-based metaheuristics: hill-climbing, late acceptance hill-climbing, simulated annealing, iterated greedy heuristic and variable iterated greedy heuristic. Each of these algorithms is used inside the BMO to exploit the search space, and improve the quality of solution generated from the BMO population. This work also compares which one of these five is better for hybridizing with BMO. The performance of these algorithms is tested on two combinatorial problems: travelling salesman problem and berth allocation problem. Experimental results demonstrate that the hybrid algorithm is superior to BMO when applied to both problems and it improved the BMO by 1.13% for BAP and by 4.13% for TSP. Furthermore, the hybrid algorithm is able to match the best-known results for most of the instances. In addition, the proposed hybrid approaches perform well over both tested domains and obtain competitive results when compared to the best-known results that have previously been presented in the scientific literature.

Keywords

• Bird mating optimizer
• berth allocation problem
• travelling salesman problem
• combinatorial optimization
• hill climbing
• late-acceptance hill-climbing