Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Frontiers of evolutionary computation
Nội dung xem thử
Mô tả chi tiết
FRONTIERS OF
EVOLUTIONARY COMPUTATION
Genetic Algorithms and
Evolutionary Computation
Consulting Editor, David E. Goldberg
University of Illinois at Urbana-Champaign
Additional titles in the series:
Efficient and Accurate Parallel Genetic Algorithms, Erick Cantú-Paz ISBN: 0-
7923-7221-2
Estimation of Distribution Algorithms: A New Tool for Evolutionary
Computation, edited by Pedro Larrañaga, Jose A. Lozano ISBN: 0-7923-7466-5
Evolutionary Optimization in Dynamic Environments, Jürgen Branke ISBN: 0-
7923-7631-5
Anticipatory Learning Classifier Systems, Martin V. Butz ISBN: 0-7923-7630-7
Evolutionary Algorithms for Solving Multi-Objective Problems, Carlos A. Coello
Coello, David A. Van Veldhuizen, and Gary B. Lamont ISBN: 0-306-46762-3
OmeGA: A Competent Genetic Algorithm for Solving Permutation and
Scheduling Problems, Dimitri Knjazew ISBN: 0-7923-7460-6
The Design of Innovation: Lessons from and for Competent Genetic
Algorithms, David E. Goldberg ISBN: 1-4020-7098-5
Noisy Optimization with Evolution Strategies, Dirk V. Arnold ISBN: 1 -4020-
7105-1
Classical and Evolutionary Algorithms in the Optimization of Optical Systems,
Darko ISBN: 1-4020- 7140-X
Evolutionary Algorithms for Embedded System Design, edited by Rolf Drechsler,
Nicole Drechsler: ISBN: 1-4020- 7276-7
Genetic Algorithms and Evolutionary Computation publishes research monographs, edited
collections, and graduate-level texts in this rapidly growing field. Primary areas of coverage include
the theory, implementation, and application of genetic algorithms (GAs), evolution strategies (ESs),
evolutionary programming (EP), learning classifier systems (LCSs) and other variants of genetic and
evolutionary computation (GEC). Proposals in related fields
such as artificial life, adaptive behavior, artificial immune
systems, agent-based systems, neural computing, fuzzy GENAGENAGENA
systems, and quantum computing will be considered for GENAGENAGENA
publication in this series as long as GEC techniques are part of Genetic Algorithms and
or inspiration for the system being described. Manuscripts Evolutionary Computation
describing GEC applications in all areas of engineering,
commerce, the sciences, and the humanities are encouraged. http://www.wkap.nl/prod/s/GENA
FRONTIERS OF
EVOLUTIONARY COMPUTATION
edited by
Anil Menon
ProductSoft, Inc.
Pittsburgh, Pennsylvania, USA
KLUWER ACADEMIC PUBLISHERS
NEW YORK, BOSTON, DORDRECHT, LONDON, MOSCOW
eBook ISBN: 1-4020-7782-3
Print ISBN: 1-4020-7524-3
©2004 Kluwer Academic Publishers
New York, Boston, Dordrecht, London, Moscow
Print ©2004 Kluwer Academic Publishers
Dordrecht
All rights reserved
No part of this eBook may be reproduced or transmitted in any form or by any means, electronic,
mechanical, recording, or otherwise, without written consent from the Publisher
Created in the United States of America
Visit Kluwer Online at: http://kluweronline.com
and Kluwer's eBookstore at: http://ebooks.kluweronline.com
Contents
List of Figures xi
List of Tables xiii
Preface xv
Contributing Authors xvii
1
Towards a Theory of Organisms and Evolving Automata 1
Heinz Mühlenbein
1 Introduction 1
2 Evolutionary computation and theories of evolution 3
3 Darwin’s continental cycle conjecture 5
4 The system view of evolution 7
5 Von Neumann’s self-reproducing automata 9
6 Turing’s intelligent machine 11
7 What can be computed by an artificial neural network? 13
8 Limits of computing and common sense 14
9 A logical theory of adaptive systems 16
10 The for creating artificial intelligence 19
11 Probabilistic logic 20
11.1 Von Neumann’s probabilistic logics 20
11.2 The conditional probability computer 21
11.3 Modern probabilistic logic 22
12 Stochastic analysis of cellular automata 24
12.1 The nonlinear voter model 24
12.2 Stochastic analysis of one dimensional SCA 26
13 Stochastic analysis of evolutionary algorithms 27
13.1 Boltzmann selection 29
13.2 Factorization of the distribution 29
13.3 Holland’s schema analysis and the Boltzmann distribution 31
14 Stochastic analysis and symbolic representations 33
15 Conclusion 33
vi FRONTIERS OF EVOLUTIONARY COMPUTATION
2
Two Grand Challenges for EC 37
Kenneth De Jong
1 Introduction 37
2 Historical Diversity 38
3 The Challenge of Unification 39
3.1 Modeling the Dynamics of Population Evolution 40
3.1.1 Choosing Population Sizes 40
3.1.2 Deletion Strategies 40
3.1.3 Parental Selection 40
3.1.4 Reproduction and Inheritance 41
3.2 Choice of Representation 42
3.3 Characteristics of Fitness Landscapes 42
4 The Challenge of Expansion 44
4.1 Representation and Morphogenesis 44
4.2 Non-random Mating and Speciation 45
4.3 Decentralized, Highly Parallel Models 45
4.4 Self-adapting Systems 45
4.5 Coevolutionary Systems 46
4.6 Inclusion of Lamarckian Properties 46
4.7 Modeling Evolutionary Systems 47
5 Summary and Conclusions 47
3
Evolutionary Computation: Challenges and duties 53
Carlos Cotta and Pablo Moscato
1 Introduction 53
2 Challenge #1: Hard problems for the paradigm – Epistasis and
Parameterized Complexity 55
3 Challenge #2: Systematic design of provably good recombina
tion operators 58
4 Challenge #3: Using Modal Logic and Logic Programming
methods to guide the search 62
4.1 Example 1 63
4.2 Example 2 64
5 Challenge #4: Learning from other metaheuristics and other
open challenges 67
6 Conclusions 69
4
Open Problems in the Spectral Analysis of Evolutionary Dynamics 73
Lee Altenberg
1 Optimal Evolutionary Dynamics for Optimization 76
1.1 Spectral Conditions for Global Attraction 78
1.2 Spectral Conditions for Rapid First Hitting Times 78
1.3 Rapid Mixing and Rapid First Hitting Times 80
1.4 Some Analysis 82
1.5 Transmission Matrices Minimizing 85
1.6 Rapid First Hitting Time and No Free Lunch Theorems 87
2 Spectra for Finite Population Dynamics 87
2.1 Wright-Fisher Model of Finite Populations 88
Contents vii
2.2 Rapid First Hitting Time in a Finite Population 90
3 Karlin’s Spectral Theorem for Genetic Operator Intensity 92
3.1 Karlin’s Theorem illustrated with the Deceptive Trap
Function 93
3.2 Applications for an Extended Karlin Theorem 95
3.3 Extending Karlin’s Theorem 96
3.4 Discussion 98
4 Conclusion 99
5
and Adaptive Memory Metaheuristics
Gary A. Kochenberger, Fred Glover, Bahram Alidaee and Cesar Rego
Solving Combinatorial Optimization Problems via Reformulation 103
1 Introduction 104
2 Transformations 105
3 Examples 106
4 Solution Approaches 108
4.1 Tabu Search Overview 108
5 Computational Experience 109
6 Summary 110
6
Problems in Optimization 115
William G. Macready
1 Introduction 115
2 Foundations 116
3 Connections 120
4 Applications 125
5 Conclusions 127
7
EC Theory - “In Theory” 129
Christopher R. Stephens and Riccardo Poli
8
Asymptotic Convergence of Scaled Genetic Algorithms 157
Lothar M. Schmitt
1 Notation and Preliminaries 162
1.1 Scalars and vectors 162
1.2 Matrices and operator norms 163
1.3 Stochastic matrices 164
1.4 Creatures and populations 167
2 The Genetic Operators 168
2.1 Multiple-spot mutation 169
2.2 Single-cutpoint regular crossover 171
2.3 The fitness function and selection 174
3 Convergence of Scaled Genetic Algorithms to Global Optima 177
3.1 The drive towards uniform populations 177
3.2 Weak ergodicity 179
3.3 Strong ergodicity 180
viii FRONTIERS OF EVOLUTIONARY COMPUTATION
3.4 Convergence to global optima. 182
3.5 The Vose-Liepins version of mutation-crossover 186
4 Future Extensions of the Theory 187
4.1 Towards finite-length analysis on finite-state machines 187
4.2 Estimates for finite-length genetic algorithms à la Catoni 188
4.3 Adding sampling noise 189
4.4 Further analogy with simulated annealing: parallelism
and sparse mutation 189
4.5 Analysis from inside-out and outside-in 190
4.6 Non-monotone and self-adapting annealing sequences 191
4.7 Discrete vs. continuous alphabets 192
5 Appendix — Proof of some basic or technical results 192
9
of Genetic and Evolutionary Computation
John R. Koza, Matthew J. Streeter and Martin A. Keane
The Challenge of Producing Human-Competitive Results by Means 201
1 Turing’s Prediction Concerning Genetic and Evolutionary Com
putation 202
2 Definition of Human-Competitiveness 202
3 Desirable Attributes of the Pursuit of Human-Competitiveness 203
3.1 Utility 203
3.2 Objectivity 204
3.3 Complexity 204
3.4 Interminability 206
4 Human-Competitiveness as a Compass for Theoretical Work 206
5 Research Areas Supportive of Human-Competitive Results 207
6 Promising Application Areas for Genetic and Evolutionary Com
putation 207
7 Acknowledgements 208
10
Case Based Reasoning 211
Vivek Balaraman
1 Introduction 211
2 Case-Based Reasoning 213
3 Case Memory as an Evolutionary System 216
3.1 A Simple Model of ECM 217
3.1.1 Case-Base 217
3.1.2 Environment 217
3.1.3 Generate Solution 218
3.1.4 Evaluate 219
3.2 Reorganize 219
3.3 Discussion 219
4 Hybrid Systems 224
4.1 Type A - CBR as a memory, EA as the optimizer 225
4.2 Type B - EA as CBR System Parameter Optimizers 226
4.3 Discussion 227
5 Evolving Higher Levels 229
5.1 Schemas 229
5.2 A brief aside on levels of higher expertise 231
Contents ix
5.3 Towards memory based reasoning 232
5.3.1 C-Schemas as Building Blocks 233
6 Conclusions 237
11
The Challenge Of Complexity 243
Wolfgang Banzhaf and Julian Miller
1 GP Basics and State of the Art 245
2 The Situation in Biology 248
3 Nature’s way to deal with complexity 249
4 What we can learn from Nature? 254
5 A possible scenario: Transfer into Genetic Programming 256
6 Conclusion 258
Author Index 261
Index 267
This page intentionally left blank
4.1 The Deceptive Trap fitness landscape for three loci with
two alleles. 94
List of Figures
4.2 There is only one attractor at each value but an ‘error
catastrophe’ is evident for
94
4.3 The mean fitness of the population at the global attractor
as a function of mutation rate. It decreases in accord
with Karlin’s theorem. 95
10.1 CBR problem solving process 214
10.2 Simple model of evolutionary case memory at generation
218
10.3 ECM as optimizers
223
10.4 Type A: EA Using CBR
225
10.5 TypeB: CBR Using EA
226
10.6 Experiences lead to schema which in turn index new ex
periences 232
11.1 The variation selection loop of GP and other artificial
evolutionary systems. 246
11.2 The primary operations of GP, mutation and crossover,
as applied to programs represented by sequences of in
structions. The instructions are coded as integer numbers. 247
xii FRONTIERS OF EVOLUTIONARY COMPUTATION
11.3 Single cell and multi-cellular system. The environment
of a genome is primarily the cell in which it is residing.
Control is exerted both by the cell and its environment
via substances (black dots) diffusing around in intra- and
extracellular space. The genome in turn tries to influence its environment by providing orders to produce certain substances. If a multi-cellular being is constructed
a division and differentiation process is set into motion
which leads to a number of cells with a boundary to the
outside environment. The organism is the primary environment of a cell, with intra- and extra- organismal
message transfer via molecules (black dots). 250
11.4 Transcription and translation as two important steps in
the process of mapping information from genotype to
phenotype. 252
11.5 The network of data flow on registers as one example
of program phenotype. The corresponding program is
listed in the text as a linear sequence of instructions.
Adopted from (Brameier, 2003) 257
List of Tables
1.1 Major transitions in evolution; Maynard (Smith and Szathmary, 1995) 4
9.1 Eight criteria for saying that an automatically created result is human-competitive 203
This page intentionally left blank