# Hybrid Biogeography-Based Optimization for Integer Programming

Authors: Zhi-Cheng Wang; Xiao-Bei Wu
Journal: The Scientific World Journal
 (2014)

---

## Abstract

Biogeography-based optimization (BBO) is a relatively new bioinspired heuristic for global optimization based on the mathematical models of biogeography. By investigating the applicability and performance of BBO for integer programming, we find that the original BBO algorithm does not perform well on a set of benchmark integer programming problems. Thus we modify the mutation operator and/or the neighborhood structure of the algorithm, resulting in three new BBO-based methods, named BlendBBO, BBO_DE, and LBBO_LDE, respectively. Computational experiments show that these methods are competitive approaches to solve integer programming problems, and the LBBO_LDE shows the best performance on the benchmark problems.


---

## Body

## 1. Introduction

An integer programming problem is a discrete optimization problem where the decision variables are restricted to integer values. In computer science and operations research, a remarkably wide range of problems, such as project scheduling, capital budgeting, goods distribution, and machine scheduling, can be expressed as integer programming problems [1–6]. Integer programming also has applications in bioinspired computational models such as artificial neural networks [7, 8].The general form of an integer programming model can be stated as(1)
min
⁡
f
(
x
→
)
s
.
t
.
x
→
∈
S
→
⊆
Z
D
,
where x
→ is a D-dimensional integer vector, Z
D is a D-dimensional discrete space of integers, and S
→ is a feasible region that is not necessarily bounded. Any maximization version of integer programming problems can be easily transformed to a minimization problem.One of the most well-known deterministic approaches for solving integer programming problems is the branch-and-bound algorithm [9]. It uses a “divide-and-conquer” strategy to split the feasible region into subregions, obtaining for each subregion a lower bound by ignoring the integrality constraints and checking whether the corresponding solution is a feasible one; if so, the current solution is optimum to the original problem; otherwise recursively split and tackle the subregions until all the variables are fixed to integers.However, integer programming is known to beNP-hard [10], and thus the computational cost of deterministic algorithms increases very rapidly with problem size. In recent years, evolutionary algorithms (EA), which are stochastic search methods inspired by the principles of natural biological evolution, have attracted great attention and have been successfully applied to a wide range of computationally difficult problems. These heuristic algorithms do not guarantee finding the exact optimal solution in a single simulation run, but in most cases they are capable of finding acceptable solutions in a reasonable computational time.Genetic algorithms (GA) are one of the most popular EA, but the encoding of the integer search space with fixed length binary strings as used in standard GA is not feasible for integer problems [11]. Many other heuristics, such as evolutionary strategy (ES) [12], particle swarm optimization (PSO) [13], and differential evolution (DE) [14], are initially proposed for continuous optimization problems. However, they can be adapted to integer programming by embedding the integer space into the real space and truncating or rounding real values to integers, and the applicability and performance of such approach are demonstrated by experimental studies.Kelahan and Gaddy [15] conducted an early study that performs random search in integer spaces in the spirit of a (
1
+
1
)
-ES; that is, at each iteration a child solution vector is generated by adding a random vector to the parent vector, and the better one between the parent and the child is kept for the next generation. Rudolph [11] developed a (
μ
+
λ
)
-ES based algorithm, which uses the principle of maximum entropy to guide the construction of a mutation distribution for arbitrary search spaces.Laskari et al. [16] studied the ability of PSO for solving integer programming problems. On their test problems, PSO outperforms the branch-and-bound method in terms of number of function evaluations (NFE), and PSO exhibits high success rates even in cases where the branch-and-bound algorithm fails. Improved versions of PSO, including the quantum-behaved PSO which is based on the principle of state superposition and uncertainty [17] and barebones PSO which is based on samples from a normal distribution and requires no parameter tuning [18], have also been applied and shown to be efficient alternatives to integer programming problems.Omran and Engelbrecht [19] investigated the performance of DE in integer programming. They tested three versions of DE and found that the self-adaptive DE (SDE) requiring no parameter tuning is the most efficient and performs better than PSO.In this paper, we propose three algorithms for integer programming based on a relatively new bioinspired method, namely, biogeography-based optimization (BBO). We modify the mutation operator of the original BBO to enhance its exploration or global search ability and adopt a local neighborhood structure to avoid premature convergence. Experimental results show that our methods are competitive approaches to solving integer programming problems.


## 2. Biogeography-Based Optimization

Biogeography is the science of the geographical distribution of biological organisms over space and time. MacArthur and Wilson [20] established the mathematical models of island biogeography, which show that the species richness of an island can be predicted in terms of such factors as habitat area, immigration rate, and extinction rate. Inspired by this, Simon [21] developed the BBO algorithm, where a solution vector is analogous to a habitat, the solution components are analogous to a set of suitability index variables (SIVs), and the solution fitness is analogous to the species richness or habitat suitability index (HSI) of the habitat. Central to the algorithm is the equilibrium theory of island biogeography, which indicates that high HSI habitats have a high species emigration rate and low HSI habitats have a high species immigration rate. For example, in a linear model of species richness (as illustrated in Figure 1), a habitat H
i’s immigration rate λ
i and emigration rate μ
i are calculated based on its fitness f
i as follows:
(2)
λ
i
=
I
(
f
max
⁡
-
f
i
f
max
⁡
-
f
min
⁡
)
μ
i
=
E
(
f
i
-
f
min
⁡
f
max
⁡
-
f
min
⁡
)
,
where f
max
⁡ and f
min
⁡ are, respectively, the maximum and minimum fitness values among the population and I and E are, respectively, the maximum possible immigration rate and emigration rate. However, there are other nonlinear mathematical models of biogeography that can be used for calculating the migration rates [22, 23].Figure 1
A linear model of emigration and immigration rates of a habitat.Migration is used to modify habitats by mixing features within the population. BBO also has a mutation operator for changing SIV within a habitat itself and thus probably increasing diversity of the population. For each habitatH
i, a species count probability P
i computed from λ
i and μ
i indicates the likelihood that the habitat was expected a priori to exist as a solution for the problem. In this context, very high HSI habitats and very low HSI habitats are both equally improbable, and medium HSI habitats are relatively probable. The mutation rate of habitat H
i is inversely proportional to its probability:
(3)
π
i
=
π
max
⁡
(
1
-
P
i
P
max
⁡
)
,
where π
max
⁡ is a control parameter and P
max
⁡ is the maximum habitat probability in the population.Algorithm1 describes the general framework of BBO for a D-dimensional global numerical optimization problem (where l
d and u
d are the lower and upper bounds of the dth dimension, respectively, and rand is a function that generates a random value uniformly distributed in [
0,1
]).Algorithm 1:The original BBO algorithm.
(1) Randomly initialize a population ofn solutions (habitats);
(2)while stop criterion is not satisfied do
(3)for
i
=
1
to
n
do
(4)  Calculateλ
i, μ
i, and π
i according to f
i;
(5)for
i
=
1
to
n
do
(6)for
d
=
1
to
D
do
(7)
if
rand
(
)
<
λ
i
then //migration
(8)Select a habitat H
j with probability ∝
μ
j;
(9)
H
i
,
d
←
H
j
,
d;
(10)for
i
=
1
to
n
do
(11)  for
d
=
1
to
D
do
(12) if
rand
(
)
<
π
i
then //mutation
(13)
H
i
,
d
←
l
d
+
rand
(
)
×
(
u
d
-
l
d
);
(14)  Evaluate the fitness values of the habitats;
(15)  Updatef
max
⁡
,
P
max
⁡, and the best known solution;
(16)return the best known solution.Typically, in Line 8 we can use a roulette wheel method for selection, the time complexity of which isO
(
n
). It is not difficult to see that the complexity of each iteration of the algorithm is O
(
n
2
D
+
n
O
(
f
)
), where O
(
f
) is the time complexity for computing the fitness function f.


## 3. Biogeography-Based Heuristics for Integer Programming

In BBO, the migration operator provides good exploitation ability, while the broader exploration of the search space is mainly based on the mutation operator. Simon [21] suggested that π
max
⁡ should be set to a small value (about 0.01), which results in low mutation rates. However, when being applied to integer programming, we need to use higher mutation rates to improve the exploration of search space. According to our experimental studies, when π
max
⁡ is set to about 0.25~0.3, the BBO algorithm exhibits the best performance on integer programming problems.Note that the migration operator does not violate the integer constraints, and the rounding of real values to integers is required only after mutations (Line 13 of Algorithm1). Nevertheless, even using a higher mutation rate, the performance of BBO is far from satisfactory for integer programming. This is mainly because random mutation operator does not utilize any information of the population to guide the exploration of search space. In this work, we introduce two other mutation operators to BBO, which results in three variants of BBO for integer programming.


### 3.1. A Blended Mutation Operator

In the first variant, namely, BlendBBO, we use a blended mutation operator, which is motivated by the blended crossover operator used by Mühlenbein and Schlierkamp-Voosen [24] in GA and by Ma and Simon [25] in constrained optimization. In our approach, if a component of vector H
i is subject to mutate, we first select another vector H
j with probability ∝
μ
j and then use the following equation to work out the new value of the component:
(4)
H
i
,
d
=
round
(
α
H
i
,
d
+
(
1
-
α
)
H
j
,
d
)
,
where α is a random value uniformly distributed in [
0,1
]. Note that if the dth dimension of the search space has a bound, (4) will never result in a value outside the bound.Moreover, we employ an elitism mechanism in solution update (as used in ES [12, 26]): the migration operator always generates a new vector H
i
′ for each existing vector H
i (rather than directly changing H
i); if H
i
′ is better than H
i, no mutation will be applied and H
i
′ directly enters to the next generation; otherwise the mutation operator is applied to H
i. This not only decreases the required NFE but also increases the convergence speed of the algorithm. The algorithm flow of BBO with the blended mutation is presented in Algorithm 2.Algorithm 2:The BBO with the blended mutation for integer programming.
(1) Randomly initialize a population ofn solutions (habitats);
(2)while stop criterion is not satisfied do
(3)for
i
=
1
to
n
do
(4)  Calculateλ
i, μ
i, and π
i according to f
i;
(5)for
i
=
1
to
n
do
(6)  LetH
i
′
=
H
i;
(7)for
d
=
1
to
D
do
(8)
if
rand
(
)
<
λ
i
then //migration
(9)Select a habitat H
j with probability ∝
μ
j;
(10)
H
i
,
d
′
←
H
j
,
d;
(11)if
f
(
H
i
)
<
f
(
H
i
′
)
then
H
i
←
H
i
′;
(12)else
(13)
for
d
=
1
to
D
do
(14)if
rand
(
)
<
π
i
then //mutation
(15)
Let
α
=
rand
(
) and select a habitat H
j with probability ∝
μ
j;
(16)
H
i
,
d
←
round
(
α
H
i
,
d
+
(
1
-
α
)
H
j
,
d
);
(17)  Evaluate the fitness values of the habitats;
(18)  Updatef
max
⁡
,
P
max
⁡, and the best known solution;
(19)return the best known solution.


### 3.2. DE Mutation Operator

The second variant, namely, BBO_DE, replaces the random mutation operator with the mutation operator of DE, which mutates a vector component by adding the weighted difference between the corresponding components of two randomly selected vectors to a third one:(5)
H
i
,
d
=
round
(
H
r
1
,
d
+
F
(
H
r
2
,
d
-
H
r
3
,
d
)
)
,
where r
1, r
2, and r
3 are three unique randomly selected habitat indices that are different to i, and F is a constant scaling coefficient.DE is well known for its good exploration ability, and the combination of BBO migration and DE mutation achieves a good balance between exploitation and exploration. BBO_DE also uses our new solution update mechanism described above. Therefore, the algorithm flow of BBO_DE simply replaces Lines 15 and 16 of Algorithm2 with the DE mutation operation described by (5).


### 3.3. Local Topology of the Population

The original BBO uses a fully connected topology; that is, all the individual solutions are directly connected in the population and can migrate with each other. But such a global topology is computationally intensive and is prone to premature convergence. To overcome this problem, our third variant replaces the global topology with a local one. One of the simplest local topologies is the ring topology, where each individual is directly connected to two other individuals [27, 28]. But here we employ a more generalized local topology, the random topology, where each individual has K immediate neighbors that are randomly selected from the population and K is a control parameter [28].In consequence, whenever an individual vectorH
i is to be immigrated, the emigrating vector is chosen from its neighbors rather than the whole population, based on the migration rates. The neighborhood structure can be saved in an n
×
n matrix L: if two habitats H
i and H
j are directly connected then L
(
i
,
j
)
=
1; otherwise L
(
i
,
j
)
=
0. It is easy to see that the complexity of each iteration of the algorithm is O
(
n
K
D
+
n
O
(
f
)
).Storn and Price [14] have proposed several different strategies on DE mutation. The scheme of (5) is denoted as DE/rand/1. Another scheme is named DE/best/1, which always chooses the best individual of the population as H
r
1 in (5). Omran et al. [29] extended it to the DE/lbest/1 scheme, which uses a ring topology and always chooses the better neighbor of the vector to be mutated.In our approach, BBO migration and DE mutation share the same local random topology. That is, eachH
i individual has K neighbors, and at each time an H
j is chosen from the neighbors with probability ∝
μ
j to participate in the mutation such that
(6)
H
i
,
d
=
round
(
H
j
,
d
+
F
(
H
r
2
,
d
-
H
r
3
,
d
)
)
.Moreover, if the current best solution has not been improved after everyn
p generation (where n
p is a predefined constant), we reset the neighborhood structure randomly.The third variant is named LBBO_LDE, and it also uses the same solution update mechanism as the previous two variants.


## 3.1. A Blended Mutation Operator

In the first variant, namely, BlendBBO, we use a blended mutation operator, which is motivated by the blended crossover operator used by Mühlenbein and Schlierkamp-Voosen [24] in GA and by Ma and Simon [25] in constrained optimization. In our approach, if a component of vector H
i is subject to mutate, we first select another vector H
j with probability ∝
μ
j and then use the following equation to work out the new value of the component:
(4)
H
i
,
d
=
round
(
α
H
i
,
d
+
(
1
-
α
)
H
j
,
d
)
,
where α is a random value uniformly distributed in [
0,1
]. Note that if the dth dimension of the search space has a bound, (4) will never result in a value outside the bound.Moreover, we employ an elitism mechanism in solution update (as used in ES [12, 26]): the migration operator always generates a new vector H
i
′ for each existing vector H
i (rather than directly changing H
i); if H
i
′ is better than H
i, no mutation will be applied and H
i
′ directly enters to the next generation; otherwise the mutation operator is applied to H
i. This not only decreases the required NFE but also increases the convergence speed of the algorithm. The algorithm flow of BBO with the blended mutation is presented in Algorithm 2.Algorithm 2:The BBO with the blended mutation for integer programming.
(1) Randomly initialize a population ofn solutions (habitats);
(2)while stop criterion is not satisfied do
(3)for
i
=
1
to
n
do
(4)  Calculateλ
i, μ
i, and π
i according to f
i;
(5)for
i
=
1
to
n
do
(6)  LetH
i
′
=
H
i;
(7)for
d
=
1
to
D
do
(8)
if
rand
(
)
<
λ
i
then //migration
(9)Select a habitat H
j with probability ∝
μ
j;
(10)
H
i
,
d
′
←
H
j
,
d;
(11)if
f
(
H
i
)
<
f
(
H
i
′
)
then
H
i
←
H
i
′;
(12)else
(13)
for
d
=
1
to
D
do
(14)if
rand
(
)
<
π
i
then //mutation
(15)
Let
α
=
rand
(
) and select a habitat H
j with probability ∝
μ
j;
(16)
H
i
,
d
←
round
(
α
H
i
,
d
+
(
1
-
α
)
H
j
,
d
);
(17)  Evaluate the fitness values of the habitats;
(18)  Updatef
max
⁡
,
P
max
⁡, and the best known solution;
(19)return the best known solution.


## 3.2. DE Mutation Operator

The second variant, namely, BBO_DE, replaces the random mutation operator with the mutation operator of DE, which mutates a vector component by adding the weighted difference between the corresponding components of two randomly selected vectors to a third one:(5)
H
i
,
d
=
round
(
H
r
1
,
d
+
F
(
H
r
2
,
d
-
H
r
3
,
d
)
)
,
where r
1, r
2, and r
3 are three unique randomly selected habitat indices that are different to i, and F is a constant scaling coefficient.DE is well known for its good exploration ability, and the combination of BBO migration and DE mutation achieves a good balance between exploitation and exploration. BBO_DE also uses our new solution update mechanism described above. Therefore, the algorithm flow of BBO_DE simply replaces Lines 15 and 16 of Algorithm2 with the DE mutation operation described by (5).


## 3.3. Local Topology of the Population

The original BBO uses a fully connected topology; that is, all the individual solutions are directly connected in the population and can migrate with each other. But such a global topology is computationally intensive and is prone to premature convergence. To overcome this problem, our third variant replaces the global topology with a local one. One of the simplest local topologies is the ring topology, where each individual is directly connected to two other individuals [27, 28]. But here we employ a more generalized local topology, the random topology, where each individual has K immediate neighbors that are randomly selected from the population and K is a control parameter [28].In consequence, whenever an individual vectorH
i is to be immigrated, the emigrating vector is chosen from its neighbors rather than the whole population, based on the migration rates. The neighborhood structure can be saved in an n
×
n matrix L: if two habitats H
i and H
j are directly connected then L
(
i
,
j
)
=
1; otherwise L
(
i
,
j
)
=
0. It is easy to see that the complexity of each iteration of the algorithm is O
(
n
K
D
+
n
O
(
f
)
).Storn and Price [14] have proposed several different strategies on DE mutation. The scheme of (5) is denoted as DE/rand/1. Another scheme is named DE/best/1, which always chooses the best individual of the population as H
r
1 in (5). Omran et al. [29] extended it to the DE/lbest/1 scheme, which uses a ring topology and always chooses the better neighbor of the vector to be mutated.In our approach, BBO migration and DE mutation share the same local random topology. That is, eachH
i individual has K neighbors, and at each time an H
j is chosen from the neighbors with probability ∝
μ
j to participate in the mutation such that
(6)
H
i
,
d
=
round
(
H
j
,
d
+
F
(
H
r
2
,
d
-
H
r
3
,
d
)
)
.Moreover, if the current best solution has not been improved after everyn
p generation (where n
p is a predefined constant), we reset the neighborhood structure randomly.The third variant is named LBBO_LDE, and it also uses the same solution update mechanism as the previous two variants.


## 4. Computational Experiments

We test the three variants of BBO on a set of integer programming benchmark problems, which are taken from [16, 30, 31] and frequently encountered in the relevant literature. The details of the benchmark problems are described in the Appendix. For comparison, we also implement the basic BBO, DE, and SDE [19] for integer programming. The branch-and-bound method is not included for comparison, because it has shown that DE outperforms branch-and-bound on most test problems [16, 19].For all the six algorithms, we use the same population sizen
=
50 and run them on each problem for 40 times with different random seeds. The migration control parameters are set as I
=
E
=
1 for BBO, BlendBBO, BBO_DE, and LBBO_LDE, and the mutation control parameter π
max
⁡ is set to 0.01 for BBO and 0.25 for BlendBBO (BBO_DE and LBBO_LDE do not use this parameter). Empirically, the neighborhood size K and the threshold of nonimprovement generations n
p are both set to 3 for LBBO_LDE. The other parameters with regard to DE and SDE are set as suggested in [14, 32].The first two problemsF
1 and F
2 are high-dimensional problems. For F
1, we, respectively, consider it in 10 and 30 dimensions. Table 1 presents the success rates (SR) and required NFE of the algorithms to achieve the optimum in 10 dimensions, and Figure 2 presents the corresponding convergence curves of the algorithms. As we can see, the original BBO fails to solve the problem, and the SR of BlendBBO is only 20%. The four algorithms utilizing the DE mutation operator can guarantee the optimal result on the 10-dimensional problem, among which LBBO_LDE shows the best performance, and the other three algorithms have similar performance, but the result of BBO_DE is slightly better than DE and SDE.Table 1
SR and required NFE of the algorithms onF
1 in 10 dimensions.
Method
SR
Best
Worst
Mean
Std
BBO
0%
NA
NA
NA
NA
BlendBBO
20%
1946
2215
2080.50
190.21
DE
100%
3200
4100
3777.50
239.78
SDE
100%
3050
4050
3762.40
265.23
BBO_DE
100%
3102
3964
3674.80
269.07
LBBO_LDE
100%
2061
2694
2493.75
145.59Figure 2
The convergence curves of the algorithms onF
1 in 10 dimensions, where the vertical axis represents the objective value and the horizontal axis represents the number of generations.Table2 and Figure 3, respectively, present the results and the convergence curves of the algorithms on F
1 in 30 dimensions. On this high-dimensional problem, BBO, BlendBBO, and DE all fail to obtain the optimum, SDE and BBO_DE, respectively, have SR of 85% and 90% for obtaining the optimum, and only our LBBO_LDE can always guarantee the optimum.Table 2
SR and required NFE of the algorithms onF
1 in 30 dimensions.
Method
SR
Best
Worst
Mean
Std
BBO
0%
NA
NA
NA
NA
BlendBBO
0%
NA
NA
NA
NA
DE
0%
NA
NA
NA
NA
SDE
85%
7850
11350
9301.00
1130.10
BBO_DE
90%
6765
9752
8204.25
920.39
LBBO_LDE
100%
5923
7071
6471.60
272.29Figure 3
The convergence curves of the algorithms onF
1 in 30 dimensions, where the vertical axis represents the objective value and the horizontal axis represents the number of generations.From the convergence curves we can also find that the BBO algorithm converges very fast at the early stage, but thereafter its performance deteriorates because it is ineffective to explore other potentially promising areas of the search space. By combining with the DE mutation operator, our hybrid BBO methods inherit the fast convergence speed of BBO, at the same time taking advantage of the exploration ability of DE.ForF
2, we, respectively, consider it in 5 and 15 dimensions, the experimental results of which are, respectively, presented in Tables 3 and 4 and the convergence curves of which are presented in Figures 4 and 5. The results are similar to those of F
1: for the low dimensional problem, SDE, BBO_DE, and LBBO_LDE are efficient; for the high-dimensional problem, only LBBO_LDE can guarantee the optimum; the performance LBBO_LDE is the best while that of BBO is the worst; SDE performs better than DE and BBO_DE performs slightly better than SDE, and BlendBBO outperforms BBO but is worse than the algorithms with the DE mutation operator.Table 3
SR and required NFE of the algorithms onF
2 in 5 dimensions.
Method
SR
Best
Worst
Mean
Std
BBO
10%
3663
5168
4415.50
1064.20
BlendBBO
55%
1154
1545
1363.36
121.94
DE
95%
1500
2100
1797.37
188.91
SDE
100%
1450
2600
2022.35
368.17
BBO_DE
100%
1773
2669
2336.65
258.22
LBBO_LDE
100%
1058
1898
1451.20
214.48Table 4
SR and required NFE of the algorithms onF
2 in 15 dimensions.
Method
SR
Best
Worst
Mean
Std
BBO
0%
NA
NA
NA
NA
BlendBBO
2.5%
4815
4815
4815
NA
DE
95%
5300
6650
5978.95
335.95
SDE
95%
5000
6400
5698.32
389.24
BBO_DE
97.5%
5030
6210
5639.11
362.69
LBBO_LDE
100%
3488
4528
4188.30
300.77Figure 4
The convergence curves of the algorithms onF
2 in 5 dimensions, where the vertical axis represents the objective value and the horizontal axis represents the number of generations.Figure 5
The convergence curves of the algorithms onF
2 in 15 dimensions, where the vertical axis represents the objective value and the horizontal axis represents the number of generations.F
3 is a 5-dimensional problem more difficult than F
2. As we can see from the results shown in Table 5, BBO and BlendBBO always fail on the problem, and DE, SDE, and LBBO_LDE can guarantee the optimum. The required NFE of DE is slightly better than SDE and LBBO_LDE, but LBBO_LDE converges faster than DE, as shown in Figure 6.Table 5
SR and required NFE of the algorithms onF
3.
Method
SR
Best
Worst
Mean
Std
BBO
0%
NA
NA
NA
NA
BlendBBO
0%
NA
NA
NA
NA
DE
100%
2050
2950
2490.00
262.38
SDE
100%
2500
4050
3260.00
638.05
BBO_DE
10%
4810
5246
5028.00
308.30
LBBO_LDE
100%
1758
4181
2958.85
849.24Figure 6
The convergence curves of the algorithms onF
3, where the vertical axis represents the objective value and the horizontal axis represents the number of generations.F
4 is a relatively easy problem, on which even the worst BBO has an SR of 75%, and all the other algorithms can guarantee the optimum. LBBO_LDE is the best one in terms of both NFE and convergence speed, as shown in Table 6 and Figure 7.Table 6
SR and required NFE of the algorithms onF
4.
Method
SR
Best
Worst
Mean
Std
BBO
75%
477
3429
1726.87
1020.19
BlendBBO
100%
258
552
424.50
85.34
DE
100%
300
650
420.00
93.75
SDE
100%
250
600
520.00
129.65
BBO_DE
10%
59
1058
632.30
277.77
LBBO_LDE
100%
236
525
400.60
72.20Figure 7
The convergence curves of the algorithms onF
4, where the vertical axis represents the objective value and the horizontal axis represents the number of generations.The remaining three test problems are also relatively easy. The experimental results are presented in Tables7, 8, and 9, and the convergence curves are shown in Figures 8, 9, and 10, respectively. As we can clearly see, the four algorithms with the DE mutation operator can always obtain the optima on these problems, and LBBO_LDE shows the best performance.Table 7
SR and required NFE of the algorithms onF
5.
Method
SR
Best
Worst
Mean
Std
BBO
0%
NA
NA
NA
NA
BlendBBO
25%
1223
2676
1842
692.53
DE
100%
1200
1700
1445.00
140.39
SDE
100%
1100
1750
1550.50
196.45
BBO_DE
100%
2473
4498
3681.25
620.36
LBBO_LDE
100%
1012
1874
1532.35
249.46Table 8
SR and required NFE of the algorithms onF
6.
Method
SR
Best
Worst
Mean
Std
BBO
45%
140
1989
1150.22
678.16
BlendBBO
80%
178
635
455.81
128.81
DE
100%
200
550
392.50
140.39
SDE
100%
200
500
405.20
103.72
BBO_DE
100%
196
995
708.50
198.38
LBBO_LDE
100%
183
511
410.05
86.37Table 9
SR and required NFE of the algorithms onF
7.
Method
SR
Best
Worst
Mean
Std
BBO
60%
167
3403
1714.75
986.18
BlendBBO
70%
262
721
459.50
149.00
DE
100%
350
600
480.00
76.78
SDE
100%
300
650
451.00
89.33
BBO_DE
100%
479
1327
978.40
311.11
LBBO_LDE
100%
249
614
389.45
96.08Figure 8
The convergence curves of the algorithms onF
5, where the vertical axis represents the objective value and the horizontal axis represents the number of generations.Figure 9
The convergence curves of the algorithms onF
6, where the vertical axis represents the objective value and the horizontal axis represents the number of generations.Figure 10
The convergence curves of the algorithms onF
7, where the vertical axis represents the objective value and the horizontal axis represents the number of generations.In summary, our LBBO_LDE outperforms the other algorithms on all of the test problems. Generally speaking, the original BBO converges fast at first, but it is easy to be trapped by the local optima. BlendBBO alleviates the dilemma to a certain degree, but the DE mutation operator is more effective than the blended mutation operator, as demonstrated by our experimental results. By combining BBO and DE, the BBO_DE algorithm provides an efficient alternative to popular methods such as SDE. The local topology used in LBBO_LDE further improves the search ability and suppresses the premature convergence, especially on high-dimensional problems where the performance of DE and SDE deteriorates quickly. Therefore, LBBO_LDE is a very competitive heuristic method for solving integer programming problem.


## 5. Conclusion

In this paper we develop three algorithms for integer programming based on the BBO heuristic. The BlendBBO uses a blended mutation operator, BBO_DE integrates the DE mutation operator, and LBBO_LDE further uses a local neighborhood structure for selecting individuals for migration and mutation. Experimental results show that LBBO_LDE has the best performance on a set of benchmark integer programming problem.In general, the LBBO_LDE algorithm with local neighborhood sizeK of 3~5 is efficient on the test problem, but none of the values can provide the best performance on all the problems. Currently we are studying a mechanism that dynamically adjusts the neighborhood size as well as other control parameters according to the search state [33]. Moreover, the test problems considered in the paper only have bounds for decision variables but do not include other constraints, and we are extending the proposed approach to solve more complex constrained optimization problems, including multiobjective ones [34–36]. We also believe that our approach can be adapted to effectively handle other kinds of combinatorial optimization problems, such as 0-1 integer programming and permutation-based optimization.



---

*Source: 672983-2014-06-03.xml*