Genetic Algorithms: Theory and Applications

1 FuzzyLogicLaboratoriumLinz-HagenbergGene ticAlgorithms: Theory andApplicationsLectureNotesThirdEdition Winter2003/2004by UlrichBodenhoferTel.:+4373224689194 Fax:+4373224681351E-mail: WWW: 2 PrefaceThis is a printed collection of the contents of the lecture Genetic Algo-rithms: Theory and Applications which I gave first in the winter semester1999/2000 at the Johannes Kepler University in sources were manifold: Chapters 1 and 2 were written originallyfor these lecture notes. All examples were implemented from third chapter is a distillation of the books of Goldberg [22] and Hoff-mann [26] and a handwritten manuscript of the preceding lecture on ge-netic algorithms which was given by Andreas St ockl in 1993 at the Jo-hannes Kepler University.

2 Chapters 4, 6, and 8 contain adaptations ofpreviously published material from my own master thesis and a series oflectures which was given by Francisco Herrera and myself at the SecondSummer School on Advanced Control at the Slovak Technical University,Bratislava, in summer 1997 [5], with the only exception of Subsection is a summary of Chapter 7 from Peter Haslinger s master thesis[24]. Chapter 5 was extracted from a recent book by my dear colleaguesO. Cord on, F. Herrera, F. Hoffman, and L. Magdalena [13]. Chapter 7was written originally, however, strongly influenced by A. Geyer-Schulz sworks and H. H orner s paper on his C++ GP kernel [29].I would like to thank all the students that attended my lectures on ge-netic algorithms so far, for contributing much to these lecture notes withtheir vivid, interesting, and stimulating questions, objections, and but not least, I want to express my sincere gratitude to SabineLumpi and Susanne Saminger for support in organizational matters, andPeter Bauer for Bodenhofer, October Basic Ideas and Introduction.

3 Definitions and Terminology ..122 A Simple Class of Genetic Operations on Binary Strings .. Selection .. Crossover .. Mutation .. Summary .. Examples .. A Very Simple One .. An Oscillating One-Dimensional Function .. A Two-Dimensional Function .. Global Smoothness versus Local Perturbations .. Discussion ..313 The Schema Theorem .. The Optimal Allocation of Trials .. Implicit Parallelism .. Building Blocks and the Coding Problem .. Example: The Traveling Salesman Problem .. Concluding Remarks ..514 Messy Genetic Algorithms .. Alternative Selection Schemes .. Adaptive Genetic Algorithms .. Hybrid Genetic Algorithms .. Self-Organizing Genetic Algorithms ..5756 CONTENTS5 GA Variants for Real-Valued Optimization Real-Coded GAs.

4 Crossover Operators for Real-Coded GAs .. Mutation Operators for Real-Coded GAs .. Evolutionary Strategies .. Recombination in ESs .. Mutation in ESs .. Selection and Sampling in ESs .. Evolutionary Programming .. Original EP .. D. B. Fogel s Modified EP .. Selection and Sampling in EP ..656 Tuning of Fuzzy Systems Using Genetic Tuning of Fuzzy Sets .. Coding Fuzzy Subsets of an Interval .. Coding Whole Fuzzy Partitions .. Standard Fitness Functions .. Genetic Operators .. A Practical Example .. The Fuzzy System .. The Optimization of the Classification System .. Concluding Remarks .. Finding Rule Bases with GAs ..847 Genetic Data Representation .. The Choice of the Programming Language.

5 Manipulating Programs .. Random Initialization .. Crossing Programs .. Mutating Programs .. The Fitness Function .. Fuzzy Genetic Programming (FGP) .. A Checklist for Applying Genetic Programming ..988 Classifier Introduction .. Holland Classifier Systems .. The Production System .. The Bucket Brigade Algorithm .. Rule Generation .. Fuzzy Classifier Systems of the Michigan Type .. Directly Fuzzifying Holland Classifier Systems .. Bonarini s ELF Method .. An Improved FCS .. Online Modification of the Whole Knowledge Base .119 Bibliography1218 CONTENTSList of A graphical representation of roulette wheel selection .. One-point crossover of binary strings .. The functionf2.. A surface plot of the functionf3.

6 The functionf4and its derivative .. Hypercubes of dimensions 1 4 .. A hyperplane interpretation of schemata forn= 3.. Minimal deceptive problems .. A messy coding .. Positional preference .. The cut and splice operation .. Piecewise linear membership function with fixed grid Simple fuzzy sets with piecewise linear membership Simple fuzzy sets with smooth membership functions .. A fuzzy partition withN= 4trapezoidal parts .. Example for one-point crossover of fuzzy partitions .. Mutating a fuzzy partition .. Magnifications of typical representatives of the four typesof pixels .. Clockwise enumeration of neighbor pixels .. Typical gray value curves corresponding to the four types . The linguistic variablesvande.

7 Cross sections of a function of type ( ) .. A comparison of results obtained by several different opti-mization methods .. A graphical representation of the results .. The tree representation of(+ (* 3 X) (SIN (+ X 1))) The derivation tree of (NOT (xORy)) ..91910 LIST An example for crossing two binary logical expressions .. An example for mutating a derivation tree .. Basic architecture of a classifier system of the Michigan The bucket brigade principle .. An example for repeated propagation of payoffs .. A graphical representation of the table shown in Figure . Matching a fuzzy condition .. The creation of fuzzy messages in the improved FCS .. The matching procedure of the modified fuzzy classifiersystem.

8 117 Chapter 1 Basic Ideas and ConceptsGrowing specialization and diversification have brought a host ofmonographs and textbooks on increasingly specialized topics. How-ever, the tree of knowledge of mathematics and related fields doesnot grow only by putting forth new branches. It also happens, quiteoften in fact, that branches which were thought to be completely dis-parate are suddenly seen to be IntroductionApplying mathematics to a problem of the real world mostly means, atfirst, modeling the problem mathematically, maybe with hard restrictions,idealizations, or simplifications, then solving the mathematical problem,and finally drawing conclusions about the real problem based on the so-lutions of the mathematical about 60 years, a shift of paradigms has taken place in somesense, the opposite way has come into fashion.

9 The point is that the worldhas done well even in times when nothing about mathematical modelingwas known. More specifically, there is an enormous number of highly so-phisticated processes and mechanisms in our world which have always at-tracted the interest of researchers due to their admirable perfection. To im-itate such principles mathematically and to use them for solving a broaderclass of problems has turned out to be extremely helpful in various disci-plines. Just briefly, let us mention the following three examples:11121. BASICIDEAS ANDCONCEPTSA rtificial Neural Networks (ANNs):Simple models of nerve cells (neu-rons) and the way they interact; can be used for function approxima-tion, machine learning, pattern recognition, etc. ( [38, 48]).

10 Fuzzy Control:Humans are often able to control processes for which noanalytic model is available. Such knowledge can be modeled math-ematically by means of linguistic control rules and fuzzy sets ( [32, 47]).Simulated Annealing:Robust probabilistic optimization method mim-icking the solidification of a crystal under slowly decreasing tem-perature; applicable to a wide class of problems ( [35, 45]).The fourth class of such methods will be the main object of study inthis lectures Genetic Algorithms (GAs).The world as we see it today, with its variety of different creatures, itsindividuals highly adapted to their environment, with its ecological bal-ance (under the optimistic assumption that there is still one), is the productof a three billion years experiment we call evolution, a process based onsexual and asexual reproduction, natural selection, mutation, and so on[14].