Evolutionary Computation with Biogeography-based Optimization

Haiping Ma, Shangai University, China. Dan Simon, Professor, Cleveland State University, USA.

Chapter 1 The Science of Biogeography 1

1.1 Introduction 1

1.2 Island biogeography 3

1.3 Influence factors for biogeography 6

Chapter 2 Biogeography and Biological Optimization 11

2.1 A mathematical model of biogeography 11

2.2 Biogeography as an optimization process 16

2.3 Biological optimization 19

2.3.1 Genetic algorithms 19

2.3.2 Evolution strategies 20

2.3.3 Particle swarm optimization 21

2.3.4 Artificial bee colony algorithm 22

2.4 Conclusion 23

Chapter 3 A Basic BBO Algorithm 25

3.1 BBO definitions and algorithm 25

3.1.1 Migration 26

3.1.2 Mutation 27

3.1.3 BBO implementation 27

3.2 Differences between BBO and other optimization algorithms 35

3.2.1 BBO and genetic algorithms 35

3.2.2 BBO and other algorithms 36

3.3 Simulations 37

3.4 Conclusion 44

Chapter 4 BBO Extensions 45

4.1 Migration curves 45

4.2 Blended migration 49

4.3 Other approaches to BBO 51

4.4 Applications 56

4.5 Conclusion 59

Chapter 5 BBO as a Markov Process 61

5.1 Markov definitions and notations 61

5.2 Markov model of BBO 72

5.3 BBO convergence 79

5.4 Markov models of BBO extensions 90

5.5 Conclusions 99

Chapter 6 Dynamic System Models of BBO 103

6.1 Basic notation 103

6.2 Dynamic system models of BBO 105

6.3 Applications to benchmark problems 119

6.4 Conclusions 122

Chapter 7 Statistical Mechanics Approximations of BBO 123

7.1 Preliminary foundation 123

7.2 Statistical mechanics model of BBO 128

7.2.1 Migration 128

7.2.2 Mutation 134

7.3 Further discussion 141

7.3.1 Finite population effects 141

7.3.2 Separable fitness functions 142

7.4 Conclusions 143

Chapter 8 BBO for Combinatorial Optimization 145

8.1 Traveling salesman problem 147

8.2 BBO for the TSP 148

8.2.1 Population initialization 148

8.2.2 Migration in the TSP 150

8.2.3 Mutation in the TSP 157

8.2.4 Implementation framework 159

8.3 Graph coloring 163

8.4 Knapsack problem 165

8.5 Conclusion 167

Chapter 9 Constrained BBO 169

9.1 Constrained optimization 170

9.2 Constraint-handling methods 172

9.2.1 Static penalty methods 172

9.2.2 Superiority of feasible points 173

9.2.3 The eclectic evolutionary algorithm 174

9.2.4 Dynamic penalty methods 174

9.2.5 Adaptive penalty methods 176

9.2.6 The niched-penalty approach 177

9.2.7 Stochastic ranking 178

9.2.8 ε-level comparisons 178

9.3 BBO for constrained optimization 179

9.4 Conclusion 185

Chapter 10 BBO in Noisy Environments 187

10.1 Noisy fitness functions 188

10.2 Influence of noise on BBO 190

10.3 BBO with re-sampling 193

10.4 The Kalman BBO 196

10.5 Experimental results 199

10.6 Conclusion 201

Chapter 11 Multi-objective BBO 203

11.1 Multi-objective optimization problems 204

11.2 Multi-objective BBO 211

11.2.1 Vector evaluated BBO 211

11.2.2 Non-dominated sorting BBO 213

11.2.3 Niched Pareto BBO 216

11.2.4 Strength Pareto BBO 218

11.3 Real-world applications 223

11.3.1 Warehouse scheduling model 223

11.3.2 Optimization of warehouse scheduling 229

11.4 Conclusion 231

Chapter 12 Hybrid BBO Algorithms 233

12.1 Opposition-based BBO 234

12.1.1 Opposition definitions and concepts 234

12.1.2 Oppositional BBO 236

12.1.3 Experimental results 238

12.2 BBO with local search 240

12.2.1 Local search methods 240

12.2.2 Simulation results 245

12.3 BBO with other EAs 247

12.3.1 Iteration-level hybridization 247

12.3.2 Algorithm-level hybridization 250

12.3.3 Experimental results 254

12.4 Conclusion 256

Appendices 259

Appendix A Unconstrained Benchmark Functions 261

Appendix B Constrained Benchmark Functions 265

Appendix C Multi-objective Benchmark Functions 289

Bibliography 309

Index 325