Biogeography-based optimization (BBO) is a recently-developed heuristic algorithm that has shown impressive performance and efficiency over many standard benchmarks. The application of BBO is still limited because it was only developed four years ago. The objective of this chapter is to expand the application of BBO to large scale combinatorial problems. This chapter addresses the solution of combinatorial problems based on BBO combined with five techniques: (1) nearest neighbor algorithm (NNA), (2) crossover methods designed for traveling salesman problems (TSPs), (3) local optimization methods, (4) greedy methods, and (5) density-based spatial clustering of applications with noise (DBSCAN). This chapter also provides a discussion about the advantages and disadvantages for each of these five techniques when used with BBO, and describes the construction of a combinatorial solver based on BBO. In the end, a framework is proposed for large scale combinatorial problems based on hybrid BBO. Based on four benchmark problems, the experimental results demonstrate the quality and efficiency of our framework. On average, the algorithm reduces costs by over 69% for a 2152-city TSP compared to other methods: genetic algorithm (GA), ant colony optimization (ACO), nearest neighbor algorithm (NNA), and simulated annealing (SA). Convergence time for the algorithm is only 28.56 sec on a 1.73-GHz quad core PC with 6 GB of RAM . The algorithm also demonstrated good results for small and medium sized problems such as ulysses16 (16-city TSP, where we obtained the best performance), st70 (70-city TSP, where the second best performance was obtained), and rat575 (575-city TSP, where the second best performance was obtained).
TopIntroduction
Heuristic algorithms are well known for their robustness and easy application. With the sustainable development of modern computer hardware, the long computation time is no longer a critical bottleneck for heuristic algorithms. In contrast, researchers benefit from using heuristic algorithms because it is not necessary to have a good understanding of the problem’s structure. This is extremely helpful for industries which may have very complex systems.
Biogeography-based optimization (BBO) was first introduced in 2008 (Simon) making it a relatively young algorithm compared to others. But the performance of BBO on benchmark problems is better than many classical algorithms which have had many years of development. In BBO, the population is analogous to an archipelago, and each island in this archipelago is a possible solution to the optimization problem. From here on we refer to candidate solutions as solutions or individuals. The implementation of the algorithm is based on the following four terms - habitat suitability index (HSI), suitability index variable (SIV), immigration rate, and emigration rate. The HSI represents the goodness of the island, where a high HSI means that the solution represented by the island has relatively good performance on the optimization problem, and a low HSI means poor performance. Each SIV represents a solution feature (that is, an independent variable of an optimization solution) in an island. The immigration rate and emigration rate are important solution characteristics for migration, and are the features of BBO that distinguish it from other evolutionary algorithms. A high performing island has a high emigration rate and low immigration rate. Conversely, a low performing island has a low emigration rate and high immigration rate. The emigration rate indicates how likely a solution is to share its features with other solutions. The immigration rate indicates how likely a solution is to accept features from other solutions. For BBO, the method to create the next generation is to share the individuals' information with other individuals in the population. In BBO, this information sharing is called immigration and emigration, which involves updating the population by migrations between islands. The basic procedure of BBO is as follows in Box 1.
Box 1.
For each solution Hi in the population
For each SIV in the solution
Select solution Hi for immigration with probability proportional to immigration rate
If Hi is selected for immigration
Select Hj for emigration with probability proportional to emigration rate
Randomly select an SIV α from Hj
Replace a random SIV β in Hi with SIV α
end
end
end
Combinatorial problems are confirmed as NP-hard problems, and their huge search space determines their incompatibility with traditional mathematic methods. This makes them a perfect benchmark for heuristic algorithms. For the demonstration and simulation purposes of this chapter, the traveling salesman problem (TSP) will be used. Assume there exists a 100-city TSP. The total number of candidate solutions are 100! = 9.3326×10157. Therefore new methods must be developed for TSPs without using exhaustive search methods.
The reason we abandon exhaustive search is its high computational expense. But even with heuristic algorithms, the TSP is still very time consuming, and computational expense is still the top concern. Two general directions are proposed to increase the efficiency of BBO to decrease its computation time.
First is the modification of BBO algorithm. Four types of techniques are added to BBO: nearest neighbor algorithm, crossovers designed for TSPs, local optimization methods, and greedy methods. The idea is to search for the best combination of techniques to create a hybrid BBO in order to achieve the best balance between its computation time and performance.
The second direction modifies the problems by proposing a new framework for combinatorial problems. We will generate a framework based on a clustering algorithm, nearest neighbor algorithm, and parallel computing. The goal here is the same as in the previous goal, which is to achieve the best balance between computation time and performance for combinatorial problems.