Foraging-inspired Optimisation Algorithms

Preface......Page 3
Contents......Page 5
1.1 What Does This Book Cover?......Page 13
1.2 The Diversity of Life......Page 15
1.2.1 Foraging Interactions......Page 18
1.4 Choice of Foraging Strategy......Page 19
1.5 Payoffs of Foraging Strategies......Page 24
1.6 Alternative Approaches to Foraging......Page 26
1.7 Structure of Book......Page 29
Perspectives on Foraging......Page 30
2.1 Optimal Foraging Theory......Page 32
Currency......Page 33
Constraints......Page 34
Optimal Diet Model......Page 35
2.1.3 Critiques of OFT......Page 36
2.3 Foraging as a Game......Page 37
2.3.1 Hawk–Dove Game......Page 39
2.4 Predator–Prey Models......Page 40
Lotka–Volterra Predator–PreyModel......Page 41
2.5.2 Lévy Flight Foraging Hypothesis......Page 44
2.5.4 Navigation......Page 46
Common Navigation Strategies......Page 47
Long-Distance Navigation......Page 48
2.6.2 Biological Networks and Algorithmic Design......Page 51
2.7 Summary......Page 53
3.1 An Internal Model of Foraging......Page 54
3.2 The Perceptual World......Page 56
3.3 Sensory Modes......Page 57
3.3.1 Vision......Page 59
The Visual System in Humans and Others......Page 60
Uses of Visual Systems......Page 61
Other HearingMechanisms......Page 62
3.3.3 Chemoreception......Page 63
Chemical Trail Marking......Page 64
Hydrodynamic Sensing......Page 65
3.3.5 Electroreception......Page 66
Magnetoreception and Bird Migration......Page 67
3.3.7 Multisensory Capabilities......Page 68
3.4 Cost of Sensory Capabilities......Page 69
The Expensive-Tissue Hypothesis......Page 70
3.5 Summary......Page 71
4.1 Learning......Page 73
4.1.1 Memory......Page 74
Associative and Nonassociative Learning......Page 76
4.2 Social Learning......Page 77
Social Learning Mechanisms......Page 78
Teaching......Page 79
Rogers’ Paradox......Page 80
4.2.2 Social Learning Strategies......Page 81
What Does Social Learning Mean in Foraging Inspired Optimisation Algorithms?......Page 82
Cost of Learning......Page 83
The Tradeoff......Page 84
Social Recognition......Page 85
4.4.2 Aggregation and Dispersion Economies......Page 86
4.4.3 Influence of Social Setting on Individual Behaviour......Page 87
Intentional and Unintentional Communication......Page 88
How Is Information Communicated to Fellow Foragers?......Page 89
4.6 Summary......Page 90
Foraging Algorithms for Optimisation......Page 91
5.1 Characterising an Optimisation Problem......Page 93
Multiobjective Optimisation......Page 94
5.2 Categorising Foraging-Inspired Algorithms......Page 95
5.2.1 Tree of Life......Page 96
5.2.3 Sensory Mechanisms......Page 97
5.2.4 Memory Mechanisms......Page 98
Communication Mechanisms......Page 99
Communication Network Topology......Page 100
Stochastic Weight Selection......Page 101
Stochastic Decision-Making Within an Algorithm......Page 102
Exploration and Exploitation......Page 103
5.3 A Metaframework for Foraging-Inspired Algorithm Design......Page 104
Swarm Foraging......Page 106
5.5 Summary......Page 107
Vertebrates......Page 108
6 Mammal......Page 110
6.1.1 Pack Behaviour of Grey Wolves......Page 111
6.1.2 Wolf Pack Search......Page 113
Algorithm......Page 114
Operationalising the Algorithm......Page 115
Boids Simulation......Page 117
6.1.5 Other Pack-Hunting Approaches Observed in Nature......Page 118
6.1.6 Whale Optimisation Algorithm......Page 119
Algorithm......Page 120
6.2 Spider Monkey Foraging......Page 121
6.2.1 Spider Monkey Optimisation Algorithm......Page 124
Global Leader Phase......Page 125
Local Leader Decision Phase......Page 126
Global Leader Decision Phase......Page 127
Parameters......Page 130
Comparison with Other Heuristics......Page 131
Echolocation......Page 132
Eavesdropping on Echolocation Calls......Page 133
6.3.1 Bat Algorithm......Page 134
Generation of New Solution......Page 135
Local Search......Page 136
Parameters......Page 137
6.4 Summary......Page 138
7 Bird......Page 140
7.1 Cuckoo Brood Parasitism......Page 141
Generation of New Nest Sites......Page 142
7.1.2 Extensions of Canonical Algorithm......Page 143
7.2 Raven Roosting and Foraging Behaviours......Page 144
Description of Algorithm......Page 146
Discussion......Page 148
7.3 Summary......Page 149
8 Aquatic......Page 150
8.1.2 How Do Fish Schools Make Decisions?......Page 151
8.2 Fish School Search Algorithm......Page 152
Individual Movement......Page 153
Collective–InstinctiveMovement......Page 154
Collective–VolitiveMovement......Page 155
8.3 Fish Algorithm......Page 156
Distributed-Perception Influence......Page 157
Individual-Perception Influence......Page 158
8.3.2 Discussion......Page 159
8.4.1 Algorithm......Page 160
Movement Induced by Other Individuals......Page 161
Random Diffusion......Page 163
Enhancing Algorithm Performance......Page 164
8.4.2 Variants of the Canonical Algorithm......Page 165
8.5 Electrolocation in Fish......Page 166
8.5.1 Active Electrolocation......Page 167
8.6 Summary......Page 168
Invertebrates......Page 170
9.1 Ant Foraging......Page 172
9.2 Recruitment Pheromones and Foraging......Page 173
Ant Mill......Page 175
9.2.2 Pheromone Signalling Behaviours......Page 176
9.3 Overview of Ant Foraging Algorithms......Page 177
9.4 Ant Algorithms for Discrete Optimisation......Page 178
Pheromone Matrix as a History......Page 179
Constructing Protosolutions......Page 180
Updating Pheromone Trails......Page 182
Variations on Canonical AS......Page 183
MAX-MIN Ant System......Page 184
Pheromone Update in ACS......Page 185
9.8 API Algorithm......Page 186
Move Operators......Page 187
Main Loop of Algorithm......Page 188
9.8.2 Discussion......Page 192
Applying the CACS Algorithm......Page 193
Algorithm......Page 195
Nest Site Selection by Temnothorax Ants......Page 198
Group Decision Making When Individual Ants Make Differing Quality Assessments......Page 200
9.12 Summary......Page 201
10.1 Honeybee Recruitment Dance......Page 203
Regulation of the Dance......Page 204
10.2.1 Bees Algorithm......Page 205
Neighbourhood Shrinkage......Page 206
Parameters......Page 207
Local Search Step......Page 208
10.2.4 Discussion......Page 210
10.3.1  Individual Perception......Page 211
10.3.3 Private Information......Page 213
10.3.4 Discussion......Page 214
Site Discovery......Page 215
Selection of Final Site......Page 216
10.4.1 Bee Nest Site Selection Optimisation Algorithm......Page 217
10.5 Summary......Page 219
11.1 Firefly Flash Signalling......Page 220
Uses of Light Signals by Fireflies......Page 221
Attractiveness......Page 222
11.2.1 Parameter Setting......Page 224
11.3 Glow-Worm Swarm Algorithm......Page 225
Sensor Range......Page 226
Luminescence Update......Page 227
Location Update......Page 228
Local Decision Range Update......Page 229
11.4 Bioluminescent Swarm Optimisation Algorithm......Page 230
Local Search......Page 231
Algorithm......Page 232
11.5 Summary......Page 233
12.1 Spider Foraging......Page 235
12.1.1 The Sensory World of Spiders......Page 236
Colonial Behaviour......Page 237
12.2 Social Spider Optimisation Algorithm......Page 238
Position Update......Page 240
12.2.2 Parameter Setting......Page 241
12.2.3 Discussion......Page 242
Foraging Process......Page 243
12.4 Antlion Optimisation Algorithm......Page 244
Operationalising the Algorithm......Page 246
12.5 Summary......Page 249
13.1 Description of C. elegans......Page 250
Learning......Page 251
13.3.1 Travelling Salesman Problem......Page 252
13.3.2 Algorithm......Page 253
Modelling Toxin Avoidance......Page 255
Dauer State......Page 257
13.3.3. Parameter Setting......Page 258
13.4 Summary......Page 259
Nonneuronal Organisms......Page 260
14 Bacterial & Viral......Page 263
14.1 Chemotaxis in E. coli Bacteria......Page 265
14.2 Bacteria Chemotaxis Algorithm......Page 267
14.2.1 Two-Dimensional Case......Page 268
New Direction......Page 269
Combination of Steps......Page 270
New Direction......Page 271
14.3 Bacterial Foraging Optimisation Algorithm......Page 272
Chemotaxis Loop......Page 273
Reproduction Cycle......Page 276
Parameter Values for the BFOA......Page 277
AlgorithmIn the BCF algorithm, a population......Page 278
Self-Adaptive Chemotactic Step......Page 279
Discussion......Page 281
14.5 Bacterial Colony Foraging Optimisation Algorithm......Page 282
14.6 Viral Algorithms......Page 283
14.6.1 Viral Life Cycle......Page 284
Are Viruses Alive?......Page 285
14.6.2 Viral-Inspired Optimisation Algorithms......Page 286
Virus Evolutionary Genetic Algorithm......Page 287
14.6.3 Communication Among Viruses......Page 289
14.7 Summary......Page 290
15 Slime Mould & Fungal......Page 292
15.1 Groupings of Slime Moulds......Page 293
15.2.1 Mobility......Page 294
15.2.3 Spatial Memory......Page 295
15.2.4 Foraging and Risk......Page 296
15.2.7 Slime Mould Foraging Behaviours: a Summary......Page 297
Solving Maze Problems......Page 298
Reproducing Human-Designed Transport Networks......Page 299
Robot Control Using Physarum polycephalum......Page 300
Tero Model......Page 301
Canonical Physarum Algorithm for Shortest Path......Page 302
Description of Improved Physarum polycephalum Algorithm......Page 304
15.4.2 Physarum-Based Ant Colony System......Page 306
Algorithm......Page 307
Parameters......Page 309
15.5.1 Life Cycle of Dictyostelium discoideum......Page 310
15.5.2 Overview of Algorithm......Page 311
15.5.3 Algorithm......Page 312
Aggregation......Page 313
Mound Formation......Page 315
Fruiting Body and Dispersal......Page 316
15.4.4 Discussion......Page 317
15.6.1 Fungal Foraging Behaviours......Page 319
15.6 Fungi......Page 318
Growth Behaviour......Page 320
15.7.1 Innate Growth Behaviour in Three-dimensional Environments......Page 321
FUNnet......Page 323
15.7.3 Fungal Search Algorithm......Page 324
15.9 Summary......Page 325
16.1 Plants and Animals......Page 326
16.1.2 Learning......Page 327
How Could Plants Encode Learning?......Page 328
16.1.3 Growth......Page 329
16.2.1 Light Reception......Page 330
16.2.2 Chemoreception......Page 331
16.2.3 Touch......Page 332
Vibration......Page 333
16.2.5 Magnetoreception......Page 334
16.3.1 Photosynthesis......Page 335
Root Structure......Page 337
Required Resources......Page 338
Self Versus Nonself Discrimination in Root Networks......Page 339
Kin Recognition in Root Networks......Page 340
Dispersal Mechanisms......Page 341
16.3.5 Pollination......Page 342
16.5 Plant Propagation Algorithms......Page 343
16.5.1 Invasive Weed Optimisation Algorithm......Page 345
Seed Dispersal......Page 346
16.5.2 Foraging Weed Colony Optimisation......Page 347
16.5.3 Paddy Field Algorithm......Page 349
Pollination......Page 350
Global Pollination Step......Page 351
Parameters and Algorithm......Page 352
Discussion......Page 353
16.5.6 Seed-Based Plant Propagation Algorithm......Page 354
Algorithm......Page 356
Discussion......Page 357
16.6.1 Plant Growth Simulation Algorithm......Page 359
The Algorithm......Page 360
Variants on the Plant Growth Simulation Algorithm......Page 362
Morphogen Concentration......Page 363
Selection Mechanism......Page 364
Algorithm......Page 365
16.7.1 Root Growth Algorithm......Page 366
Growth of Root Tips......Page 367
Local Search......Page 368
Main Algorithm......Page 369
16.7.2 Root Growth Optimiser Algorithm......Page 370
Branching......Page 371
Inhibition Mechanism......Page 372
Algorithm......Page 373
16.8 Summary......Page 374
Formal Models of Foraging Algorithms......Page 376
17.1 Optimal Foraging Algorithm......Page 378
17.1.2 Leaving the Local Optimal Solution to Continue the Search......Page 379
17.1.3 Verifying if the Obtained Solution Is Better......Page 380
17.2.1 Algorithm......Page 381
Scanning......Page 383
Ranging......Page 385
17.3 Predatory Search Algorithm......Page 386
17.3.1 Algorithm......Page 387
17.4 Predator–Prey Optimisation Algorithm......Page 389
Initialisation......Page 390
Implementation of Movement......Page 391
17.5 Animal Migration Optimisation Algorithm......Page 392
Changes in Population......Page 393
Discussion......Page 394
17.6 Summary......Page 396
Evolving a Foraging Strategy......Page 397
18 Evolving Foraging Algorithms......Page 399
The Model......Page 400
Evolving a Strategy......Page 401
18.2 Understanding Real-World Foraging......Page 402
18.3 Robotics......Page 404
Multirobot Systems......Page 405
18.3.2 Foraging Behaviours in Swarm Robotics......Page 406
18.4 Summary......Page 409
Foraging Algorithms Future......Page 410
19.1 Is Foraging Equivalent to Optimisation?......Page 412
19.1.2 Reinventing the Wheel......Page 413
19.2.1 The Tree of Life......Page 414
19.2.4 Social Learning......Page 415
19.2.5 Combining Private and Public Information......Page 416
19.2.6 Group Decision Making......Page 417
19.2.9 Stochastic Mechanisms in Foraging Algorithms......Page 418
19.3 Concluding Remarks......Page 419
Refs......Page 421
Index......Page 455