Evolutionary Computation with Biogeography-Based Optimization

ISBN-13: 9781848218079 / Angielski / Twarda / 2017 / 344 str.

Mehmet Ergezer; Dan Simon

Opis

Evolutionary computation algorithms are employed to minimize functions with large number of variables. Biogeography-based optimization (BBO) is an optimization algorithm that is based on the science of biogeography, which researches the migration patterns of species. These migration paradigms provide the main logic behind BBO. Due to the cross-disciplinary nature of the optimization problems, there is a need to develop multiple approaches to tackle them and to study the theoretical reasoning behind their performance. This book explains the mathematical model of BBO algorithm and its variants created to cope with continuous domain problems (with and without constraints) and combinatorial problems.

Spis treści

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