Genetic Algorithms and Evolutionary Computation - Böcker

As genetic algorithms (GAs) become increasingly popular, they are applied to difficult problems that may require considerable computations. In such cases, parallel implementations of GAs become necessary to reach high-quality solutions in reasonable times. But, even though their mechanics are simple, parallel GAs are complex non-linear algorithms that are controlled by many parameters, which are not well understood. This text is about the design of parallel GAs. It presents theoretical developments that improve our understanding of the effect of the algorithm's parameters on its search for quality and efficiency. These developments are used to formulate guidelines on how to choose the parameter values that minimize the execution time while consistently reaching solutions of high quality. The book can be read in several ways, depending on the readers' interests and their previous knowledge about these algorithms. Newcomers to the field should find the background material in each chapter useful to become acquainted with previous work, and to understand the problems that must be faced to design efficient and reliable algorithms.Potential users of parallel GAs that may have doubts about their practicality or reliability may be more confident after reading this book and understanding the algorithms better. Those who are ready to try a parallel GA on their applications may choose to skim through the background material, and use the results directly without following the derivations in detail. These readers will find that using the results can help them to choose the type of parallel GA that best suits their needs, without having to invest the time to implement and test various options. Once that is settled, even the most experienced users dread the long and frustrating experience of configuring their algorithms by trial and error. The guidelines contained herein should shorten dramatically the time spent tweaking the algorithm, although some experimentation may still be needed for fine-tuning. The text should be suitable as a secondary text for a graduate level

OmeGA, or the ordering messy genetic algorithm, combines contemporary advances in competent GA technology to solve scheduling and other permutation problems. Competent GAs are those designed for principled solutions of hard problems, quickly, reliably and accurately. Permutation and scheduling problems are difficult combinatorial optimization problems with commercial importance across a variety of industries. This book approaches these subjects systematically and clearly. The first part of the book presents a description of messy GAs along with an innovative adaptation of the method to ordering problems. The second part of the book investigates the algorithm on boundedly difficult test functions, showing principled scale up as problems become harder and longer. Finally, the book applies the algorithm to a test function drawn from the literature of scheduling.

This text is devoted to a new paradigm for evolutionary computation, named estimation of distribution algorithms (EDAs). This class of algorithms generalizes genetic algorithms by replacing the crossover and mutation operators with learning and sampling from the probability distribution of the best individuals of the population at each iteration of the algorithm. Working in such a way, the relationships between the variables involved in the problem domain are explicitly and effectively captured and exploited. The book is clearly divided into three parts. Part I is dedicated to the foundations of EDAs. In this part, after introducing some probabilistic graphical models - Bayesian and Gaussian networks - a review of existing EDA approaches is presented, as well as some new methods based on more flexible probabilistic graphical models. A mathematical modelling of discrete EDAs is also presented. Part II covers several applications of EDAs in some classical optimization problems: the travelling salesman problem, the job scheduling problem, and the knapsack problem. EDAs are also applied to the optimization of some well-known combinatorial and continuous functions.Part III presents the application of EDAs to solve some problems that arise in the machine learning field: feature subset selection, feature weighting in K-NN classifiers, rule induction, partial abductive inference in Bayesian networks, partitional clustering, and the search for optimal weights in artificial neural networks.

Anticipatory Learning Classifier Systems describes the state of the art of anticipatory learning classifier systems-adaptive rule learning systems that autonomously build anticipatory environmental models. An anticipatory model specifies all possible action-effects in an environment with respect to given situations. It can be used to simulate anticipatory adaptive behavior. Anticipatory Learning Classifier Systems highlights how anticipations influence cognitive systems and illustrates the use of anticipations for (1) faster reactivity, (2) adaptive behavior beyond reinforcement learning, (3) attentional mechanisms, (4) simulation of other agents and (5) the implementation of a motivational module. The book focuses on a particular evolutionary model learning mechanism, a combination of a directed specializing mechanism and a genetic generalizing mechanism. Experiments show that anticipatory adaptive behavior can be simulated by exploiting the evolving anticipatory model for even faster model learning, planning applications, and adaptive behavior beyond reinforcement learning. Anticipatory Learning Classifier Systems gives a detailed algorithmic description as well as a program documentation of a C++ implementation of the system.

Evolutionary algorithms (EAs) have grown into a mature field of research in optimization, and have proven to be effective and robust problem-solvers for a broad range of static real-world optimization problems. Yet, since they are based on the principles of natural evolution, and since natural evolution is a dynamic process in a changing environment, EAs are also well suited to dynamic optimization problems. This volume provides a survey on research in the area and shows how EAs can be used to: continuously and efficiently adapt a solution to a changing environment; find a trade-off between solution quality and adaptation cost; find robust solutions whose quality is insensitive to changes in the environment; and find flexible solutions that can be easily adapted when necessary. This resource should prove useful to researchers and professionals who are dealing with dynamic and stochastic optimization problems, and who are interested in applying local search heuristics, such as evolutionary algorithms.

Classical and Evolutionary Algorithms in the Optimization of Optical Systems presents research results in the field of classical and evolutionary algorithms and their application to the optimization of optical systems. This book, which is divided into four parts, illustrates the development of research from the classical least squares method of optimization and its numerous modifications to modern optimization methods that are based on analogies with nature such as genetic algorithms and evolution strategies. Part I describes the mathematical foundations of classical and evolutionary algorithms in the optimization of optical systems. Part II is dedicated to optical design fundamentals. Part III deals with the implementation of the classical and evolutionary algorithms in the program for the optimization of optical systems. Every chapter in this section includes a detailed description of the optimization method with the flow chart diagram. And finally, Part IV presents the results and the discussion of optimization of various types of objectives.Classical and Evolutionary Algorithms in the Optimization of Optical Systems is intended for researchers and post graduate students in the field of optical design who want to learn more about new optimization methods, such as genetic algorithms and evolution strategies, and for those who want to learn more about classical and evolutionary optimization methods and their application to the optimization of optical systems.

This text describes how Evolutionary Algorithm (EA) concepts can be applied to circuit and system design - an area where time-to-market demands are critical. EAs create an interesting alternative to other approaches since they can be scaled with the problem size and can be easily run on parallel computer systems. It presents several successful EA techniques and shows how they can be applied at different levels of the design process. Starting on a high-level abstraction, where software components are dominant, several optimization steps are demonstrated, including DSP code optimization and test generation. Throughout the book, EAs are tested on real-world applications and on large problem instances. For each application the main criteria for the successful application in the corresponding domain are discussed. In addition, contributions from leading international researchers provide the reader with a variety of perspectives, including a special focus on the combination of EAs with problem specific heuristics.

Frontiers of Evolutionary Computation brings together eleven contributions by international leading researchers discussing what significant issues still remain unresolved in the field of Evolutionary Computation (EC). They explore such topics as the role of building blocks, the balancing of exploration with exploitation, the modeling of EC algorithms, the connection with optimization theory and the role of EC as a meta-heuristic method, to name a few. The articles feature a mixture of informal discussion interspersed with formal statements, thus providing the reader an opportunity to observe a wide range of EC problems from the investigative perspective of world-renowned researchers. These prominent researchers include: -Heinz Muhlenbein, -Kenneth De Jong, -Carlos Cotta and Pablo Moscato, -Lee Altenberg, -Gary A. Kochenberger, Fred Glover, Bahram Alidaee and Cesar Rego, -William G. Macready, -Christopher R. Stephens and Riccardo Poli, -Lothar M. Schmitt, -John R. Koza, Matthew J. Street and Martin A. Keane, -Vivek Balaraman, -Wolfgang Banzhaf and Julian Miller.Frontiers of Evolutionary Computation is ideal for researchers and students who want to follow the process of EC problem-solving and for those who want to consider what frontiers still await their exploration.

OmeGA: A Competent Genetic Algorithm for Solving Permutation and Scheduling Problems addresses two increasingly important areas in GA implementation and practice. OmeGA, or the ordering messy genetic algorithm, combines some of the latest in competent GA technology to solve scheduling and other permutation problems. Competent GAs are those designed for principled solutions of hard problems, quickly, reliably, and accurately. Permutation and scheduling problems are difficult combinatorial optimization problems with commercial import across a variety of industries. This book approaches both subjects systematically and clearly. The first part of the book presents the clearest description of messy GAs written to date along with an innovative adaptation of the method to ordering problems. The second part of the book investigates the algorithm on boundedly difficult test functions, showing principled scale up as problems become harder and longer. Finally, the book applies the algorithm to a test function drawn from the literature of scheduling.

Anticipatory Learning Classifier Systems describes the state of the art of anticipatory learning classifier systems-adaptive rule learning systems that autonomously build anticipatory environmental models. An anticipatory model specifies all possible action-effects in an environment with respect to given situations. It can be used to simulate anticipatory adaptive behavior. Anticipatory Learning Classifier Systems highlights how anticipations influence cognitive systems and illustrates the use of anticipations for (1) faster reactivity, (2) adaptive behavior beyond reinforcement learning, (3) attentional mechanisms, (4) simulation of other agents and (5) the implementation of a motivational module. The book focuses on a particular evolutionary model learning mechanism, a combination of a directed specializing mechanism and a genetic generalizing mechanism. Experiments show that anticipatory adaptive behavior can be simulated by exploiting the evolving anticipatory model for even faster model learning, planning applications, and adaptive behavior beyond reinforcement learning. Anticipatory Learning Classifier Systems gives a detailed algorithmic description as well as a program documentation of a C++ implementation of the system.

Evolutionary Algorithms (EAs) have grown into a mature field of research in optimization, and have proven to be effective and robust problem solvers for a broad range of static real-world optimization problems. Yet, since they are based on the principles of natural evolution, and since natural evolution is a dynamic process in a changing environment, EAs are also well suited to dynamic optimization problems. Evolutionary Optimization in Dynamic Environments is the first comprehensive work on the application of EAs to dynamic optimization problems. It provides an extensive survey on research in the area and shows how EAs can be successfully used to continuously and efficiently adapt a solution to a changing environment, find a good trade-off between solution quality and adaptation cost, find robust solutions whose quality is insensitive to changes in the environment, find flexible solutions which are not only good but that can be easily adapted when necessary. All four aspects are treated in this book, providing a holistic view on the challenges and opportunities when applying EAs to dynamic optimization problems. The comprehensive and up-to-date coverage of the subject, together with details of latest original research, makes Evolutionary Optimization in Dynamic Environments an invaluable resource for researchers and professionals who are dealing with dynamic and stochastic optimization problems, and who are interested in applying local search heuristics, such as evolutionary algorithms.

Evolutionary Algorithms for Embedded System Design describes how Evolutionary Algorithm (EA) concepts can be applied to circuit and system design - an area where time-to-market demands are critical. EAs create an interesting alternative to other approaches since they can be scaled with the problem size and can be easily run on parallel computer systems. This book presents several successful EA techniques and shows how they can be applied at different levels of the design process. Starting on a high-level abstraction, where software components are dominant, several optimization steps are demonstrated, including DSP code optimization and test generation. Throughout the book, EAs are tested on real-world applications and on large problem instances. For each application the main criteria for the successful application in the corresponding domain are discussed. In addition, contributions from leading international researchers provide the reader with a variety of perspectives, including a special focus on the combination of EAs with problem specific heuristics.Evolutionary Algorithms for Embedded System Design is an excellent reference for both practitioners working in the area of circuit and system design and for researchers in the field of evolutionary concepts.

Noise is a common factor in most real-world optimization problems. Sources of noise can include physical measurement limitations, stochastic simulation models, incomplete sampling of large spaces, and human-computer interaction. Evolutionary algorithms are general, nature-inspired heuristics for numerical search and optimization that are frequently observed to be particularly robust with regard to the effects of noise.Noisy Optimization with Evolution Strategies contributes to the understanding of evolutionary optimization in the presence of noise by investigating the performance of evolution strategies, a type of evolutionary algorithm frequently employed for solving real-valued optimization problems. By considering simple noisy environments, results are obtained that describe how the performance of the strategies scales with both parameters of the problem and of the strategies considered. Such scaling laws allow for comparisons of different strategy variants, for tuning evolution strategies for maximum performance, and they offer insights and an understanding of the behavior of the strategies that go beyond what can be learned from mere experimentation.This first comprehensive work on noisy optimization with evolution strategies investigates the effects of systematic fitness overvaluation, the benefits of distributed populations, and the potential of genetic repair for optimization in the presence of noise. The relative robustness of evolution strategies is confirmed in a comparison with other direct search algorithms.Noisy Optimization with Evolution Strategies is an invaluable resource for researchers and practitioners of evolutionary algorithms.

Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation is devoted to a new paradigm for evolutionary computation, named estimation of distribution algorithms (EDAs). This new class of algorithms generalizes genetic algorithms by replacing the crossover and mutation operators with learning and sampling from the probability distribution of the best individuals of the population at each iteration of the algorithm. Working in such a way, the relationships between the variables involved in the problem domain are explicitly and effectively captured and exploited. This text constitutes the first compilation and review of the techniques and applications of this new tool for performing evolutionary computation. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation is clearly divided into three parts. Part I is dedicated to the foundations of EDAs. In this part, after introducing some probabilistic graphical models - Bayesian and Gaussian networks - a review of existing EDA approaches is presented, as well as some new methods based on more flexible probabilistic graphical models. A mathematical modeling of discrete EDAs is also presented. Part II covers several applications of EDAs in some classical optimization problems: the travelling salesman problem, the job scheduling problem, and the knapsack problem. EDAs are also applied to the optimization of some well-known combinatorial and continuous functions. Part III presents the application of EDAs to solve some problems that arise in the machine learning field: feature subset selection, feature weighting in K-NN classifiers, rule induction, partial abductive inference in Bayesian networks, partitional clustering, and the search for optimal weights in artificial neural networks. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation is a useful and interesting tool for researchers working in the field of evolutionary computation and for engineers who face real-world optimization problems. This book may also be used by graduate students and researchers in computer science. `... I urge those who are interested in EDAs to study this well-crafted book today.' David E. Goldberg, University of Illinois Champaign-Urbana.

As genetic algorithms (GAs) become increasingly popular, they are applied to difficult problems that may require considerable computations. In such cases, parallel implementations of GAs become necessary to reach high-quality solutions in reasonable times. But, even though their mechanics are simple, parallel GAs are complex non-linear algorithms that are controlled by many parameters, which are not well understood. Efficient and Accurate Parallel Genetic Algorithms is about the design of parallel GAs. It presents theoretical developments that improve our understanding of the effect of the algorithm's parameters on its search for quality and efficiency. These developments are used to formulate guidelines on how to choose the parameter values that minimize the execution time while consistently reaching solutions of high quality. Efficient and Accurate Parallel Genetic Algorithms can be read in several ways, depending on the readers' interests and their previous knowledge about these algorithms. Newcomers to the field will find the background material in each chapter useful to become acquainted with previous work, and to understand the problems that must be faced to design efficient and reliable algorithms. Potential users of parallel GAs that may have doubts about their practicality or reliability may be more confident after reading this book and understanding the algorithms better. Those who are ready to try a parallel GA on their applications may choose to skim through the background material, and use the results directly without following the derivations in detail. These readers will find that using the results can help them to choose the type of parallel GA that best suits their needs, without having to invest the time to implement and test various options. Once that is settled, even the most experienced users dread the long and frustrating experience of configuring their algorithms by trial and error. The guidelines contained herein will shorten dramatically the time spent tweaking the algorithm, although some experimentation may still be needed for fine-tuning. Efficient and Accurate Parallel Genetic Algorithms is suitable as a secondary text for a graduate level course, and as a reference for researchers and practitioners in industry.

7 69 6 A DESIGN APPROACH TO PROBLEM DIFFICULTY 71 1 Design and Problem Difficulty 71 2 Three Misconceptions 72 3 Hard Problems Exist 76 4 The 3-Way Decomposition and Its Core 77 The Core of Intra-BB Difficulty: Deception 5 77 6 The Core of Inter-BB Difficulty: Scaling 83 7 The Core of Extra-BB Difficulty: Noise 88 Crosstalk: All Roads Lead to the Core 8 89 9 From Multimodality to Hierarchy 93 10 Summary 100 7 ENSURING BUILDING BLOCK SUPPLY 101 1 Past Work 101 2 Facetwise Supply Model I: One BB 102 Facetwise Supply Model II: Partition Success 103 3 4 Population Size for BB Supply 104 Summary 5 106 8 ENSURING BUILDING BLOCK GROWTH 109 1 The Schema Theorem: BB Growth Bound 109 2 Schema Growth Somewhat More Generally 111 3 Designing for BB Market Share Growth 112 4 Selection Press ure for Early Success 114 5 Designing for Late in the Day 116 The Schema Theorem Works 6 118 A Demonstration of Selection Stall 7 119 Summary 122 8 9 MAKING TIME FOR BUILDING BLOCKS 125 1 Analysis of Selection Alone: Takeover Time 126 2 Drift: When Selection Chooses for No Reason 129 3 Convergence Times with Multiple BBs 132 4 A Time-Scales Derivation of Critical Locus 142 5 A Little Model of Noise-Induced Run Elongation 143 6 From Alleles to Building Blocks 147 7 Summary 148 10 DECIDING WELL 151 1 Why is Decision Making a Problem? 151