Summary

Summary Evolutionary Computing (X_400111)

0 purchase

Course
Evolutionary Computing (X_400111)

Institution
Vrije Universiteit Amsterdam (VU)

Book
Introduction to Evolutionary Computing

This is a summary of all lectures used in the course Evolutionary Computing given to students following a master in Artificial Intelligence or Business Analytics. This summary closely follows the book 'Introduction to Evolutionary Computing' written by A.E. Eiben (lecturer of the course) and J.E. S...

[Show more]

Last document update: 5 months ago

Preview 4 out of 49 pages

View example

Summarized whole book? No
Which chapters are summarized? Chapters 1 to 10, 12, 13, 17
Uploaded on October 25, 2024
File latest updated on October 29, 2024
Number of pages 49
Written in 2023/2024
Type Summary

business analytics
artificial intelligence
evolutionary computing
summary

Book Title:Introduction to Evolutionary Computing

Author(s):A.E. Eiben, J.E. Smith

Edition:Unknown
ISBN:9783662499856
Edition:2

Institution
Vrije Universiteit Amsterdam (VU)
Education
Artificial Intelligence
Course
Evolutionary Computing (X_400111)

$11.14

Add to cart

Save

100% satisfaction guarantee
Immediately available after payment
Both online and in PDF
No strings attached

Evolutionary Computing
Chapter 0 Evolutionary problem solving
- Fitness (evolution)  chances for survival and reproduction
- Quality (problem solving)  chance for seeding new solutions
- Evolvable objects (phenotypes) > genetic code (genotypes) > reproduction > fitness >
selection

Chapter 1 Problems to be solved
Problems
1. Black box model (input, model, output  one is unknown)
 Optimization
- Model and desired output is known
- Task is to find inputs
 Modelling
- Input and desired output is known
- Task is to find model
 Simulation
- Input and model are known
- task is to find output

2. Search problems: collection of all objects of interest including the desired solution
 Search problems = define search spaces
 Problem-solvers = move through search spaces (to find a solution)

3. Optimisation vs constraint satisfaction
 Objective function = a way of assigning a value to a possible solution that
reflects its quality on scale
 Constraint = binary evaluation telling whether a given requirement holds or not

4. NP problems
 Problem type depending on the problem only
 Hardness/complexity classified:
1. Class P  solved in polynomial time
2. Class NP
- Not necessarily solved in polynomial time
- Any solution can be verified within
polynomial time by some algorithm (P subset of NP)
3. Class NP-Complete
- Some NP (other NP can be reduced by algorithm running in
polynomial time)

, 4. Class NP-hard
- As hard as any problem in NP-complete
- Solution cannot necessarily be verified within polynomial time

Chapter 2 The origins
Darwin Evolution
Definition: population consists of a diverse set of individuals
1. Survival of the fittest
 All environments have finite resources
 Individuals that compete for the resources most effectively have increased
chance of reproduction
2. Diversity drives change  Phenotypic traits
 Physical and behavioural differences that affect response to environment
 Unique to each individual, partly as a result of random changes
 Lead to higher chances of reproduction
 Can be inherited
3. Summary:
 Combinations of traits that are better adapted tend to increase representation
in population
- Individuals are “units of selection”
 Variations occur through random changes yielding constant source of diversity,
coupled with selection means that:
- Population is the “unit of evolution”

D. Dennet  ‘If you have variation, heredity, and selection, then you must get evolution’

Adaptive landscape metaphor
- Population with n traits as existing in a n+1-dimensional space (landscape) with heigh
corresponding to fitness
- Each individual (phenotype) represents a single point on the landscape
- Population is therefore a “cloud” of points, moving on the landscape over time as it
evolves (adaptation)
- Genetic drift:
 Random variations in feature distribution
 (+ or -) arising from sampling error
 Can cause the population “melt down” hills, thus crossing valleys and leaving
local optima

Genetics, genes and the genome
- Genotype (DNA inside) determines phenotype (outside)
- The mapping genes  phenotypic traits are very complex
 Pleiotropy: one gene may affect many traits
 Polygeny: many genes may affect one trait
- Ontogenesis = process of differential behaviours during development (after
fertilization)

,Chapter 3 What is an Evolutionary Algorithm?
Common model of evolutionary processes
1. Population of individuals
2. Individuals have fitness
3. Reproduction/variation operators
 Mutation
 Recombination (a.k.a. crossover)
4. Selection towards higher fitness
 ‘Survival of the fittest’
 ‘Mating of the fittest’
5. Fitness of population increases over time

Two pillars of evolution / competing forces
1. Push towards novelty
 Increase population  diversity by variation:
- Mutation
- Recombination
 Variation operators act on individual level
2. Push towards quality
 Decrease population  diversity by selection:
- Of parents
- Of survivors
 Selection operators act on population level

General scheme of EAs vs. pseudo-code

Main EA Components
1. Representation:
 Role: provides code for candidate solutions that can be manipulated by variation
operators
 Phenotype
- Object in original problem context, the outside
- Encoding (repres.): phenotype to genotype (not necessarily one to one)
 Genotype
- Code to denote that object, the inside
- Decoding (inverse repres.): genotype to phenotype (must be one to one)
Loci = fixed positions of genes in chromosomes
Allele = value of gene

, 2. Evaluation / fitness function
 Role:
- Fitness function: represents the task to solve, the requirements to adapt
to
- Enables selection
- Provides basis for comparison
 Quality function of objective function
 Assigns a single real-valued fitness to each phenotype which performs basis for
selection
- So the more discrimination (different values) the better
 Usually talk about fitness being maximized (some can be posed as minimisation
problems, but conversion is trivial)

3. Population
 Role: holds the candidate solution of the problem as individuals (genotypes)
 Population is:
- a multiset of individuals
- the basic unit of evolution (populations is evolving, not the individuals)
 Selection operators act on population level
 Variation operators act on individual level
 Diversity of population refers to number of different fitness values or
phenotypes or genotypes present

4. Selection
 Role:
- Identifies individuals to become parents / to survive
- Pushes population towards higher fitness
 Parent selection: usually probabilistic / stochastic
- Can help escape from local optima
- High quality solutions more likely to be selected than low quality solutions
- Even the worst in current population usually has non-zero probability of
being selected
 Survivor selection (a.k.a. replacement) often deterministic
- Fitness based: rank parents + offspring and take best
- Age based: make as many offspring as parents and delete all parents
 Sometimes a combination of stochastic and deterministic:
- Elitism: the best n individuals always survive (deterministic rule)

5. Variation operators
 Role: generate new candidate solutions
 Usually divided into two types according to their arity (number of inputs)
- arity 1: mutation operators
- arity > 1: recombination operators
- arity = 2: typically called crossover
- arity > 2: multi-parent reproduction, is possible, not used often
 Most EAs use both recombination and mutation
 Variation operators must match the given representation

The benefits of buying summaries with Stuvia:

Guaranteed quality through customer reviews

Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.

Quick and easy check-out

You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.

Focus on what matters

Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!

Frequently asked questions

What do I get when I buy this document?

You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.

Satisfaction guarantee: how does it work?

Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.

Who am I buying these notes from?

Stuvia is a marketplace, so you are not buying this document from us, but from seller alexandranelis1. Stuvia facilitates payment to the seller.

Will I be stuck with a subscription?

No, you only buy these notes for $11.14. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

70073 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy study notes for 15 years now

Start selling

Summary

Summary Evolutionary Computing (X_400111)

Document information

Subjects

Connected book

Written for

Seller

Content preview