Samenvatting

Summary Evolutionary Computing (X_400111)

0 keer verkocht

Instelling
Vrije Universiteit Amsterdam (VU)

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...

[Meer zien]

Laatste update van het document: 4 maanden geleden

Voorbeeld 4 van de 49 pagina's

Bekijk voorbeeld

Heel boek samengevat? Nee
Wat is er van het boek samengevat? Chapters 1 to 10, 12, 13, 17
Geupload op 25 oktober 2024
Bestand laatst geupdate op 29 oktober 2024
Aantal pagina's 49
Geschreven in 2023/2024
Type Samenvatting

€9,99

In winkelwagen

Opslaan

100% tevredenheidsgarantie
Direct beschikbaar na je betaling
Lees online óf als PDF
Geen vaste maandelijkse kosten

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

Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:

Bewezen kwaliteit door reviews

Studenten hebben al meer dan 850.000 samenvattingen beoordeeld. Zo weet jij zeker dat je de beste keuze maakt!

In een paar klikken geregeld

Geen gedoe — betaal gewoon eenmalig met iDeal, creditcard of je Stuvia-tegoed en je bent klaar. Geen abonnement nodig.

Direct to-the-point

Studenten maken samenvattingen voor studenten. Dat betekent: actuele inhoud waar jij écht wat aan hebt. Geen overbodige details!

Veelgestelde vragen

Wat krijg ik als ik dit document koop?

Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.

Tevredenheidsgarantie: hoe werkt dat?

Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.

Van wie koop ik deze samenvatting?

Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper alexandranelis1. Stuvia faciliteert de betaling aan de verkoper.

Zit ik meteen vast aan een abonnement?

Nee, je koopt alleen deze samenvatting voor €9,99. Je zit daarna nergens aan vast.

Is Stuvia te vertrouwen?

4,6 sterren op Google & Trustpilot (+1000 reviews)

Afgelopen 30 dagen zijn er 70713 samenvattingen verkocht

Opgericht in 2010, al 15 jaar dé plek om samenvattingen te kopen

Begin nu gratis

Laatst bekeken door jou

Samenvatting ·

(0)

Samenvatting Duurzame ontwikkeling H5-H8

Tentamen (uitwerkingen) ·

(0)

Samenvatting

Summary Evolutionary Computing (X_400111)

Document informatie

Onderwerpen

Gekoppeld boek

Meer samenvattingen voor studieboek

Geschreven voor

Verkoper

Voorbeeld van de inhoud