Sanchez / Schillaci / Squillero Evolutionary Optimization: the µGP toolkit

1. Auflage 2011
ISBN: 978-0-387-09426-7
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 178 Seiten

This book describes an award-winning evolutionary algorithm that outperformed experts and conventional heuristics in solving several industrial problems. It presents a discussion of the theoretical and practical aspects that enabled ?GP (MicroGP) to autonomously find the optimal solution of hard problems, handling highly structured data, such as full-fledged assembly programs, with functions and interrupt handlers.For a practitioner, ?GP is simply a versatile optimizer to tackle most problems with limited setup effort. The book is valuable for all who require heuristic problem-solving methodologies, such as engineers dealing with verification and test of electronic circuits; or researchers working in robotics and mobile communication. Examples are provided to guide the reader through the process, from problem definition to gathering results.For an evolutionary computation researcher, ?GP may be regarded as a platform where new operators and strategies can be easily tested.MicroGP (the toolkit) is an active project hosted by Sourceforge: http://ugp3.sourceforge.net/

Autoren/Hrsg.

Sanchez, Ernesto

Schillaci, Massimiliano

Squillero, Giovanni

Inhaltsverzeichnis

1;Preface;6
2;Contents;9
3;Chapter 1 Evolutionary computation;12
3.1;1.1 Natural and artificial evolution;12
3.2;1.2 The classical paradigms;15
3.3;1.3 Genetic programming;18
4;Chapter 2 Why yet another one evolutionary optimizer?;19
4.1;2.1 Background;19
4.2;2.2 Where to draw the lines;20
4.3;2.3 Individuals;21
4.4;2.4 Problem specification;23
4.5;2.5 Coding Techniques;24
5;Chapter 3The µGP architecture;26
5.1;3.1 Conceptual design;27
5.2;3.2 The evolutionary core;27
5.2.1;3.2.1 Evolutionary Operators;28
5.2.2;3.2.2 Population;29
5.3;3.3 The Evolutionary Cycle;30
5.3.1;3.3.1 Genetic operator selection;30
5.3.2;3.3.2 Parents selection;31
5.3.3;3.3.3 Offspring Generation;32
5.3.4;3.3.4 Individual Evaluation and Slaughtering;33
5.3.5;3.3.5 Termination and Aging;33
6;Chapter 4 Advanced features;35
6.1;4.1 Self adaptation for exploration or exploitation;35
6.1.1;4.1.1 Self-adaptation inertia;36
6.1.2;4.1.2 Operator strength;36
6.1.3;4.1.3 Tournament size;37
6.2;4.2 Escaping local optimums;37
6.2.1;4.2.1 Operator activation probability;38
6.2.2;4.2.2 Tuning the elitism;38
6.3;4.3 Preserving diversity;39
6.3.1;4.3.1 Clone detection, scaling and extermination;40
6.3.2;4.3.2 Entropy and delta-entropy computation;40
6.3.3;4.3.3 Fitness holes;41
6.3.4;4.3.4 Population topology and multiple populations;42
6.4;4.4 Coping with the real problems;43
6.4.1;4.4.1 Parallel fitness evaluation;44
6.4.2;4.4.2 Multiple fitness;45
7;Chapter 5 Performing an evolutionary run;46
7.1;5.1 Robot Pathfinder;48
7.2;5.2 µGPSettings;50
7.3;5.3 Population Settings;52
7.4;5.4 Library of Constraints;56
7.5;5.5 Launching the experiment;60
7.6;5.6 µGP Extractor;62
8;Chapter 6 Command line syntax;64
8.1;6.1 Starting a run;64
8.2;6.2 Controlling messages to the user;65
8.3;6.3 Getting help and information;66
8.4;6.4 Controlling logging;66
8.5;6.5 Controlling recovery;67
8.6;6.6 Controlling evolution;68
8.7;6.7 Controlling evaluation;69
9;Chapter 7 Syntax of the settings file;71
9.1;7.1 Controlling evolution;72
9.2;7.2 Controlling logging;74
9.3;7.3 Controlling recovery;75
10;Chapter 8 Syntax of the population parameters file;77
10.1;8.1 Strategy parameters;77
10.1.1;8.1.1 Base parameters;78
10.1.2;8.1.2 Parameters for self adaptation;81
10.1.3;8.1.3 Other parameters;84
11;Chapter 9 Syntax of the external constraints file;86
11.1;9.1 Purposes of the constraints;86
11.2;9.2 Organization of constraints and hierarchy;87
11.3;9.3 Specifying the structure of the individual;92
11.4;9.4 Specifying the contents of the individual;95
12;Chapter 10 Writing a compliant evaluator;101
12.1;10.1 Information from µGP to the fitness evaluator;101
12.2;10.2 Expected fitness format;102
12.2.1;10.2.1 Good Examples;103
12.2.2;10.2.2 Bad Examples;104
13;Chapter 11 Implementation details;106
13.1;11.1 Design principles;106
13.2;11.2 Architectural choices;107
13.2.1;11.2.1 The Graph library;108
13.2.2;11.2.2 The Evolutionary Core library;110
13.2.3;11.2.3 Front end;117
13.3;11.3 Code organization and class model;117
14;Chapter 12 Examples and applications;128
14.1;12.1 Classical one-max;128
14.1.1;12.1.1 Fitness evaluator;129
14.1.2;12.1.2 Constraints;131
14.1.3;12.1.3 Population settings;133
14.1.4;12.1.4 µGP settings;135
14.1.5;12.1.5 Running;136
14.2;12.2 Values of parameters and their influence on the evolution: Arithmetic expressions;137
14.2.1;12.2.1 De Jong 3;137
14.2.2;12.2.2 De Jong 4 Modified;142
14.2.3;12.2.3 Carrom;143
14.3;12.3 Complex individuals’ structures and evaluation: Bit-counting in Assembly;149
14.3.1;12.3.1 Assembly individuals representation;149
14.3.2;12.3.2 Evaluator;152
14.3.3;12.3.3 Running;154
15;Appendix A Argument and option synopsis;155
16;Appendix B External constraints synopsis;171
17;References;179