Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
|---|---|---|---|---|---|
Searching... | 30000010103704 | QA76.618 T65 2005 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
Evolutionary algorithms (EAs) is now a mature problem-solving family of heuristics that has found its way into many important real-life problems and into leading-edge scientific research. Spatially structured EAs have different properties than standard, mixing EAs. By virtue of the structured disposition of the population members they bring about new dynamical features that can be harnessed to solve difficult problems faster and more efficiently. This book describes the state of the art in spatially structured EAs by using graph concepts as a unifying theme. The models, their analysis, and their empirical behavior are presented in detail. Moreover, there is new material on non-standard networked population structures such as small-world networks.
The book should be of interest to advanced undergraduate and graduate students working in evolutionary computation, machine learning, and optimization. It should also be useful to researchers and professionals working in fields where the topological structures of populations and their evolution plays a role.
Author Notes
Marco Tomassini is a professor of Computer Science at the Information Systems Department of the University of Lausanne, Switzerland. He graduated in physical and chemical sciences in Mendoza, Argentina, and got a PhD degree in theoretical chemistry from the University of Perugia, Italy, working on computer simulations of condensed matter systems. His current research interests are centered around the application of biological ideas to artificial systems. He is active in evolutionary computation, especially spatially structured systems, genetic programming, and evolvable machines. He is also interested in machine learning, parallel cellular computing systems, and the dynamical properties of networked complex systems. He has been Program Chairman of several international events and has published many scientific papers and several authored and edited books in these fields.
Table of Contents
| 1 Setting the Stage for Structured Populations | p. 1 |
| 1.1 Useful Definitions for Graphs | p. 2 |
| 1.2 Main Graph Structures of Populations | p. 5 |
| 1.2.1 Island or Multipopulation Models | p. 6 |
| 1.2.2 Cellular Models | p. 7 |
| 1.2.3 Other Topologies | p. 8 |
| 2 Island Models | p. 11 |
| 2.1 History and Background | p. 11 |
| 2.2 Homogeneous and Heterogeneous Islands | p. 14 |
| 2.3 Theoretical Results | p. 14 |
| 2.4 Asynchronous Islands | p. 17 |
| 3 Island Models: Empirical Properties | p. 19 |
| 3.1 An Experimental Investigation | p. 19 |
| 3.2 Description of the Test Problems | p. 19 |
| 3.3 Multipopulation GP Parameters | p. 20 |
| 3.4 Performance Measures and Statistics | p. 21 |
| 3.5 Number of Subpopulations and Their Size | p. 23 |
| 3.5.1 Isolated Populations vs. Standard GP | p. 23 |
| 3.5.2 Communicating Islands vs. Standard GP | p. 27 |
| 3.6 Comparing Communication Topologies | p. 30 |
| 3.7 Migration Parameters | p. 33 |
| 3.8 Summary of Case Study | p. 37 |
| 3.9 The Role of Diversity | p. 37 |
| 3.9.1 Diversity Measures | p. 38 |
| 3.9.2 Experimental Results | p. 40 |
| 3.9.3 Summary | p. 44 |
| 3.10 Asynchronous Island Models | p. 44 |
| 3.10.1 Experimental Results | p. 46 |
| 4 Lattice Cellular Models | p. 53 |
| 4.1 Takeover Time | p. 54 |
| 4.2 Synchronous cEAs | p. 55 |
| 4.3 The Time Dimension: Asynchronous cEAs | p. 57 |
| 4.4 Models and Their Validation | p. 59 |
| 4.5 Mathematical Models | p. 59 |
| 4.5.1 Limitations of Logistic Modeling | p. 60 |
| 4.5.2 The Ring Structure | p. 62 |
| 4.5.3 The Torus Structure | p. 66 |
| 4.6 Experimental Validation | p. 70 |
| 4.6.1 Ring Structure | p. 70 |
| 4.6.2 Torus Structure | p. 73 |
| 4.7 Rectangular Toroidal Structures | p. 76 |
| 4.7.1 Validation of the Rectangular Toroidal Models | p. 78 |
| 4.8 Varying the Radius | p. 79 |
| 4.9 Summary | p. 80 |
| 5 Lattice Cellular Models: Empirical Properties | p. 85 |
| 5.1 cGA Case Study | p. 85 |
| 5.2 Varying the Lattice Shape | p. 86 |
| 5.3 Selection Pressure, Grid Shape and Time | p. 87 |
| 5.4 Test Suite | p. 88 |
| 5.4.1 Discrete Optimization Problems | p. 90 |
| 5.4.2 Experimental Analysis | p. 93 |
| 5.4.3 Continuous Optimization Problems | p. 96 |
| 5.4.4 Experimental Analysis | p. 97 |
| 5.5 Cellular Genetic Programming | p. 100 |
| 5.5.1 Experimental Results | p. 100 |
| 5.5.2 Fitness Evolution | p. 100 |
| 5.5.3 Diversity Evolution | p. 101 |
| 5.6 Summary | p. 104 |
| 6 Random and Irregular Cellular Populations | p. 107 |
| 6.1 Random Graphs | p. 108 |
| 6.2 Selection Intensity in Random Cellular Populations | p. 109 |
| 6.3 Experimental Results | p. 111 |
| 6.4 Small-World Networks | p. 113 |
| 6.4.1 Some Graph Statistics | p. 116 |
| 6.4.2 The Watts-Strogatz Model | p. 118 |
| 6.4.3 The Barabasi-Albert Model | p. 119 |
| 6.5 Selection Intensity in Small-World Networks | p. 120 |
| 6.5.1 Watts-Strogatz Model | p. 120 |
| 6.5.2 Barabasi-Albert Model | p. 122 |
| 6.6 Summary | p. 124 |
| 7 Coevolutionary Structured Models | p. 125 |
| 7.1 What Is Coevolution? | p. 125 |
| 7.2 Cooperative Coevolution | p. 126 |
| 7.3 Competitive Coevolution: Hosts and Parasites | p. 127 |
| 7.4 A Case Study: Coevolution of Cellular Automata | p. 130 |
| 7.4.1 Cellular Automata | p. 131 |
| 7.4.2 The Majority Task | p. 131 |
| 7.5 Artificial Evolution of CAs for the Majority Task | p. 133 |
| 7.5.1 Coevolving Uniform CAs for the Majority Task | p. 134 |
| 7.5.2 Coevolving Nonuniform CAs for the Majority Task | p. 137 |
| 7.5.3 Results for the Density Task | p. 139 |
| 7.6 Summary | p. 141 |
| 8 Some Nonconventional Models | p. 143 |
| 8.1 Nonconventional Island Models | p. 144 |
| 8.1.1 The Injection Island Model | p. 144 |
| 8.1.2 Islands with Variable Population Size | p. 145 |
| 8.2 Nonconventional Cellular Models | p. 151 |
| 8.2.1 The Patchwork Model | p. 152 |
| 8.2.2 Dynamic Neighborhoods in Cellular Evolution Strategies | p. 153 |
| A Implementation Notes | p. 157 |
| A.1 Computing Environment | p. 158 |
| A.1.1 MPI | p. 158 |
| A.2 Implementation of Island EAs | p. 159 |
| A.2.1 Synchronous Islands | p. 159 |
| A.2.2 Asynchronous Islands | p. 165 |
| A.2.3 Summary | p. 168 |
| A.3 Implementation of Lattice Cellular EAs | p. 168 |
| A.3.1 Synchronous Cellular EAs | p. 168 |
| A.3.2 Asynchronous Cellular EAs | p. 170 |
| A.4 Performance Measures and Speedup | p. 170 |
| A.5 A Remark on Pseudorandom Number Generators | p. 173 |
| References | p. 177 |
| Index | p. 189 |
