Biogeography-Based Optimization

Dan Simon Cleveland State University Fall 2008

Outline
1. 2. 3. 4. 5. 6. Biogeography Optimization Other Population-Based Optimizers Benchmark Functions & Results Sensor Selection & Results Conclusion
2

Biogeography
The study of the geographic distribution of biological organisms
Mauritius 1600s

Biogeography

Species migrate between islands via flotsam, wind, flying, swimming,

4

Biogeography
Habitat Suitability Index (HSI): Some islands are more suitable for habitation than others Suitability Index Variables (SIVs): Habitability is related to features such as rainfall, topography, diversity of vegetation, temperature, etc.
5

Biogeography
As habitat suitability improves:
The species count increases Emigration increases (more species exit the habitat) Immigration decreases (fewer species come into the habitat)

Biogeography
Ps = probability that habitat contains S species
S species at time t, and no migration occurred

Ps (t + t ) = Ps (t )(1 s t s t ) + Ps 1 (t )s 1t + Ps +1 (t ) s +1t
S1 species at time t, and 1 species immigrated S+1 species at time t, and 1 species emmigrated
7

Biogeography
Convert the difference equation into a differential equation
(s + s ) Ps + s +1 Ps +1 Ps = (s + s ) Ps + s 1 Ps 1 + s +1 Ps +1 (s + s ) Ps + s 1 Ps 1 S =0 S = 1, , S max 1 S = S max

(Smax+1) coupled differential equations that can be combined into a single matrix equation.
8

Biogeography
P = AP

1 0 (0 + 0 ) (1 + 1 ) 2 0 A= n 2 0 0

(n 1 + n 1 ) n (n + n ) n 1 0

Biogeography
Suppose E=I. Then k = Ek / n
k = E (1 k / n)
where k = species count, n = S max

10

Biogeography
0 1 1/ n 0 n / n 1 2 / n A = E 2 / n 1 n / n 0 0 1/ n 1 = EA' P = AP

So the population reaches equilibrium when P is equal to the eigenvector corresponding to the zero eigenvalue of A
11

Biogeography
v P ( ) = vi

v = [v1

v n +1 ]

n! (i = 1,..., ceil((n + 1) / 2)) vi = (n 1 i )!(i 1)! v n + 2 i (i = ceil((n + 1) / 2) + 1,..., n + 1)

12

Biogeography-Based Optimization
1. 2. 3. 4. 5. 6. 7. Initialize a set of solutions to a problem. Compute fitness (HSI) for each solution. Compute S, , and for each solution. Modify habitats (migration) based on , . Mutatation based on probability. Typically we implement elitism. Go to step 2 for the next iteration if needed.
13

Benchmark Functions
14 standard benchmark functions were used to evaluate BBO relative to other optimizers.
Ackley Fletcher-Powell Griewank Penalty Function #1 Penalty Function #2 Quartic Rastrigin Rosenbrock Schwefel 1.2 Schwefel 2.21 Schwefel 2.22 Schwefel 2.26 Sphere Step
14

Benchmark Functions
Functions can be categorized as Separable or nonseparable for example, (x+y) vs. xy Regular or irregular for example, sin x vs. abs(x) Unimodal or multimodal for example, x2 vs. cos x
15

Benchmark Functions
Penalty function #1: nonseparable, regular, unimodal

16

Benchmark Functions
f ( x) = [floor( xi + 0.5)]2 Step function:
i =1 n

separable, irregular, unimodal

17

Benchmark Functions
Rastrigin: f ( x) = 10n +

[ x
i =1

2 i

10 cos(2 xi )]

nonseparable, regular, multimodal

18

Benchmark Functions
f ( x) = [100( xi +1 xi2 ) 2 + ( xi 1) 2 ] Rosenbrock:
i =1 n 1

nonseparable, regular, unimodal

19

Benchmark Functions
Schwefel 2.22: f ( x) =

| x | + | x |
i =1 i i i =1

nonseparable, irregular, unimodal

20

Benchmark Functions
Schwefel 2.26: f ( x) =

x sin
i =1 i

| xi |

separable, irregular, multimodal

21

Optimization Algorithms
Ant colony optimization (ACO) Biogeography-based optimization (BBO) Differential evolution (DE) Evolutionary strategy (ES) Genetic algorithm (GA) Population-based incremental learning (PBIL) Particle swarm optimization (PSO) Stud genetic algorithm (SGA)
22

ACO Ackley Fletcher Griewank Penalty 1 Penalty 2 Quartic Rastrigin Rosenbrock Schwefel 1.2 Schwefel 2.21 Schwefel 2.22 Schwefel 2.26 Sphere Step 182 1013 162

BBO 100 100 117

DE 146 385 272 5862 1176 397 253 391 227 290 137 250 302

ES 197 494 696

GA 197 415 516

PBIL 232 917 2831

PSO 192 799 1023

SGA 103 114 100

2.2E7 1.2E4 9.7E4 1.3E6 2.5E5 2.8E7 2.1E6 100 5.0E5 715 3213 454 1711 202 161 688 108 1347 248 262 100 102 100 100 100 118 100 112 4.2E4 1.1E4 5.4E5 6.4E4 100 7008 536 716 425 162 1094 140 910 813 2850 421 428 166 184 500 142 906 551 4.8E4 8570 634 1861 606 265 861 177 2785 3271 470 516 592 179 665 142 1000 1161 100 134 100 110 146 142 100 109 100
23

Average performance of 100 simulations (n = 50)

Aircraft Engine Sensor Selection

Health estimation Better maintenance Better control performance

24

Aircraft Engine Sensor Selection

What sensors should we use? Measure pressures, temperatures, speeds A total of 11 sensors; some can be duplicated Estimate efficiencies and airflow capacities Optimize a combination of estimation accuracy and financial cost Use a Kalman filter for health estimation
25

Aircraft Engine Sensor Selection

Suppose we want to pick N objects out of K classes while choosing from each class no more than M times. Example: We have red balls, blue balls, and green balls (K=3). We want to pick 4 balls (N=4) with each color chosen no more than twice (M=2). 6 Possibilities: {B, B, G, G}, {R, B, G, G}, {R, B, B, G}, {R, R, G, G}, {R, R, B, G}, {R, R, B, B}
26

Aircraft Engine Sensor Selection

Pick N objects out of K classes while choosing from each class no more than M times. q(x)= (1 + x + x2 + + xM)K = 1 + q1 x + q2 x2 + + xMK Multinomial theorem: The number of unique combinations is equal to qN (order independent)

27

Aircraft Engine Sensor Selection

Pick 20 objects out of 11 classes while choosing from each class no more than 4 times. q(x) = (1 + x + x2 + x3 + x4)11 = 1 + + 3,755,070 x20 + 21 hours of CPU time for an exhaustive search. So we need a quick suboptimal search strategy.
28

Aircraft Engine Sensor Selection

ACO BBO DE ES GA PBIL PSO SGA Mean 8.22 8.01 8.06 8.15 8.04 8.18 8.14 8.02 Best 8.12 7.19 7.60 8.05 8.02 8.80 8.06 8.02 Average and best performance over 100 Monte Carlo simulations. Computational savings = 99.99% (21 hours 8 seconds).

29

Conclusion
A new biologically-motivated optimizer Paper and Matlab code is at http://academic.csuohio.edu/simond/bbo

30

Future Work
Applications Convergence Dynamic/noisy fitness functions Extinction is not the same as emigration Take island proximity into account Model species populations (demographics) Species age affects extinction and emigration
31

Future Work
Migration curves are probably convex, and vary between islands Continuous BBO Connections between BBO and other Eas Migration varies with species mobility Predator/prey relationships Population sizes Constrained BBO Multiobjective BBO
32

Future Work
Number of islands Combination with other EAs
Tabu search, particle swarm optimization, use of global information, etc. Local memory of past performance for each island Fuzzy fitness functions
33

34

Other optimization methods

Ant colony optimization: Based on the pheromone deposition of ants

35

Other optimization methods

Differential evolution: Based on simple difference-based modification of solutions
olu ti exi stin gs on

so

lu tio n

e renc diffe
36

ne

existing solutions

Other optimization methods

Evolutionary Strategy: Based on multiple parents contributing to offspring

The most fit offspring become the next generation of parents

37

Other optimization methods

Genetic algorithms: Based on natural selection in biological evolution

crossover point

selection

parents

children
38

Other optimization methods

Particle swarm optimization: Based on the swarming behavior of birds, fish, etc.
Each particle (solution) learns from its neighbors and adjusts itself accordingly

39