Transcript Introduction to Evolutionary Computation 1

Introduction to
Evolutionary Computing I
A.E. Eiben
Free University Amsterdam
http://www.cs.vu.nl/~gusz/
with thanks to the EvoNet Training Committee and its “Flying Circus”
Contents






Historical perspective
Biological inspiration:

Darwinian evolution (simplified!)

Genetics (simplified!)
Motivation for EC
The basic EC Metaphor
What can EC do: examples of application areas
Demo: evolutionary magic square solver
A.E. Eiben, Introduction to EC I
2
EvoNet Summer School 2002
Fathers of evolutionary computing
Gregor Mendel 1822 – 1884
“Father of genetics”
Charles Darwin 1809 – 1882
“Father of the evolution theory”
John von Neumann 1903 – 1957
“Father of the computer”
A.E. Eiben, Introduction to EC I
Alan Mathison Turing 1912 – 1954
“Father of the computer”
3
EvoNet Summer School 2002
The dawn of EC
• 1948, Turing
proposes “genetical or evolutionary search”
• 1962, Bremermann
optimization through evolution and recombination
• 1964, Rechenberg
introduces evolution strategies
• 1965, L. Fogel, Owens and Walsh
introduce evolutionary programming
• 1975, Holland
introduces genetic algorithms
A.E. Eiben, Introduction to EC I
4
EvoNet Summer School 2002
Since then…
• 1985: first international conference (ICGA)
• 1990: first international conference in Europe (PPSN)
• 1993: first scientific EC journal (MIT Press)
• 1997: launch of European EC Research Network (EvoNet)
And today:
• 3 major conferences, 10 – 15 small / related ones
• 3 scientific core EC journals + 2 Web-based ones
• 750-1000 papers published in 2001 (estimate)
• EvoNet has over 150 member institutes
• uncountable (meaning: many) applications
• uncountable (meaning: ?) consultancy and R&D firms
A.E. Eiben, Introduction to EC I
5
EvoNet Summer School 2002
Natural Evolution





Given a population of reproducing individuals
Fitness: capability of an individual to survive and reproduce in an
environment (caveat: “inverse” measure)
Phenotypic variability: small, random, apparently undirected
deviation of offspring from parents
Natural selection: reproductive advantage by being well-suited to an
environment (survival of the fittest)
Adaptation: the state of being and process of becoming suitable
w.r.t. the environment
Evolution 1: Open-ended adaptation in a dynamically changing world
Evolution 2: Optimization according to some fitness-criterion
A.E. Eiben, Introduction to EC I
6
EvoNet Summer School 2002
Natural Genetics




The information required to build a living organism is
coded in the DNA of that organism
Genotype (DNA inside) determines phenotype (outside)
Small variations in the genetic material give rise to
small variations in phenotypes (e.g., height, eye color)
Genetic differences between parents and children are
due to mutations/recombinations
Fact 1: For all natural life on earth, the genetic code is the same
Fact 2: No information transfer from phenotype to genotype
(Lamarckism wrong)
A.E. Eiben, Introduction to EC I
7
EvoNet Summer School 2002
Motivation for EC
Nature has always served as a source of inspiration for
engineers and scientists
The best problem solver known in nature is:


the (human) brain that created “the wheel, New York, wars and
so on” (after Douglas Adams’ Hitch-Hikers Guide)
the evolution mechanism that created the human brain (after
Darwin’s Origin of Species)
Answer 1  neurocomputing
Answer 2  evolutionary computing
A.E. Eiben, Introduction to EC I
8
EvoNet Summer School 2002
Motivation for EC 2




Developing, analyzing, applying problem solving
methods a.k.a. algorithms is a central theme in
mathematics and computer science
Time for thorough problem analysis decreases
Complexity of problems to be solved increases
Consequence: robust problem solving technology
needed
Assumption:
Natural evolution is robust  simulated evolution is robust
A.E. Eiben, Introduction to EC I
9
EvoNet Summer School 2002
Evolutionary Computing:
the Basic Metaphor
EVOLUTION
PROBLEM SOLVING
Environment
Problem
Candidate Solution
Individual
Quality
Fitness
Fitness  chances for survival and reproduction
Quality  chance for seeding new solutions
A.E. Eiben, Introduction to EC I
10
EvoNet Summer School 2002
Classification of problem types
A.E. Eiben, Introduction to EC I
11
EvoNet Summer School 2002
What can EC do
• optimization
e.g. time tables for university, call center, or hospital
• design (special type of optimization?)
e.g., jet engine nozzle, satellite boom
• modeling
e.g. profile of good bank customer, or poisonous drug
• simulation
e.g. artificial life, evolutionary economy, artificial societies
• entertainment / art
e.g., the Escher evolver
A.E. Eiben, Introduction to EC I
12
EvoNet Summer School 2002
Illustration in optimization:
university timetabling
Enormously big search space
Timetables must be good, and
good is defined by a number
of competing criteria
Timetables must be feasible
and the vast majority of
search space is infeasible
NB Example from Napier Univ
A.E. Eiben, Introduction to EC I
13
EvoNet Summer School 2002
Illustration in design:
NASA satellite structure
Optimized satellite designs
to maximize vibration isolation
Evolving: design structures
Fitness: vibration resistance
Evolutionary “creativity”
A.E. Eiben, Introduction to EC I
14
EvoNet Summer School 2002
A.E. Eiben, Introduction to EC I
15
EvoNet Summer School 2002
Illustration in modelling:
loan applicant creditibility
British bank evolved creditability
model to predict loan paying
behavior of new applicants
Evolving: prediction models
Fitness: model accuracy on
historical data
Evolutionary machine learning
A.E. Eiben, Introduction to EC I
16
EvoNet Summer School 2002
Illustration in simulation:
evolving artificial societies
Simulating trade, economic
competition, etc. to calibrate
models
Use models to optimize
strategies and policies
Evolutionary economy
Survival of the fittest is universal
(big/small fish)
A.E. Eiben, Introduction to EC I
17
EvoNet Summer School 2002
Illustration in simulation 2:
biological interpetations
Incest prevention keeps evolution
from rapid degeneration
(we knew this)
Multi-parent reproduction, makes
evolution more efficient
(this does not exist on Earth in
carbon)
2nd sample of Life
A.E. Eiben, Introduction to EC I
18
EvoNet Summer School 2002
Illustration in art: the Escher evolver
City Museum The Hague (NL)
Escher Exhibition (2000)
Real Eschers + computer
images on flat screens
Evolving: population of pic’s
Fitness: visitors’ votes (interactive subjective selection)
Evolution for the people
A.E. Eiben, Introduction to EC I
19
EvoNet Summer School 2002
Demonstration: magic square


Given a 10x10 grid with a small 3x3 square in it
Problem: arrange the numbers 1-100 on the grid such
that
 all horizontal, vertical, diagonal sums are equal (505)
 a small 3x3 square forms a solution for 1-9
A.E. Eiben, Introduction to EC I
20
EvoNet Summer School 2002
Demonstration: magic square
Evolutionary approach to solving this puzzle:

Creating random begin arrangement

Making N mutants of given arrangement

Keeping the mutant (child) with the least error

Stopping when error is zero
A.E. Eiben, Introduction to EC I
21
EvoNet Summer School 2002
Demonstration: magic square
• Software by M. Herdy, TU Berlin
• Interesting parameters:
• Step1: small mutation, slow & hits the optimum
• Step10: large mutation, fast & misses (“jumps over” optimum)
• Mstep: mutation step size modified on-line, fast & hits optimum
• Start: double-click on icon below
• Exit: click on TUBerlin logo (top-right)
A.E. Eiben, Introduction to EC I
22
EvoNet Summer School 2002