Evolutionary Computation with Biogeography-based Optimization

8BBO for Combinatorial Optimization

Up until this point, this book has emphasized the framework and mathematical theory of BBO algorithms. In this chapter, we begin to discuss the applications of BBO. This chapter uses BBO to solve combinatorial optimization problems, which comprise a subset of mathematical optimization. Combinatorial optimization has important applications in many fields, including artificial intelligence, machine learning, auction theory and software engineering. Combinatorial optimization can be thought of as finding the optimal object from among a finite set of candidate objects:

[8.1]

where N_x is the cardinality of the search space. Theoretically, we can solve equation [8.1] by evaluating f(x) for all N_x possible solutions. But it is not feasible to check every possible solution when the combinatorial problem has a large search space.

Some classic combinatorial optimization problems include the traveling salesman problem, the knapsack problem, the minimum spanning tree problem and many others. Figure 8.1 shows an example of a one-dimensional knapsack problem: which boxes should be chosen to maximize the amount of money while still keeping the overall weight less than or equal to 15 kg? A combinatorial optimization problem could consider both the weight and volume of the boxes.

Figure 8.1. An example of a one-dimensional knapsack problem. For a color version ...