Foraging-inspired Optimisation Algorithms

Description

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