Transcript Evolutionary Computation Application

Evolutionary
Computation
Application
Peter Andras
[email protected]
www.staff.ncl.ac.uk/
peter.andras/lectures
Overview
1. Application principles
2. Problem definition
3. Evolutionary solution
4. Summary and questions
Application principles
Problem domains:
• hard discrete optimisation problems (e.g.,
complex combinatorial optimisation)
• very hard continuous optimisation
problems (e.g., problems with high
combinatorial complexity)
• evolutionary simulations
Application principles
Speed:
• evolutionary optimisation is usually slow
• if there are simple ways of finding the
optimal solutions those should be preferred
Application principles
Complex programming:
• evolutionary optimisation needs relatively
complex programming (encoding, genetic
operators, performance evaluation,
offspring generation, etc.)
Application principles
Off-line application:
• if the objective is to apply evolutionary
optimisation to find an optimal solution of a
problem, off-line application is preferred
Application principles
Simulation games:
• ideas and methods form evolutionary
optimisation can fit very well to simulation
games, where these can be applied directly
Problem definition
World of problems:
• finding the right parameters of the problems;
• finding the effective ranges of the parameters;
• finding a good problem representation;
Problem definition
Generating the problem world:
• problem population with good random
sampling of the parameter domains;
• regime dependent problem world niches;
Problem definition
Problem:
• health resource allocation in a labyrinth
Problem definition
Optimisation problem:
• given the risks of moving within the
labyrinth, how to locate the health resources
to allow passing through the labyrinth, but
without making this easy
Problem definition
Simple labyrinth: can be solved explicitly
Complex labyrinth: hard to solve, and more
interesting to play with
Problem definition
Solving the complex labyrinth problem:
• good place for evolutionary optimisation
Evolutionary solution
Encoding:
• the labyrinth is given
• the risks associated to labyrinth positions
are given;
• the locations of the resources are encoded
by their positions
• chromosome: (x1,y1), …, (xn,yn)
Evolutionary solution
Crossover operator:
Evolutionary solution
Mutation operator:
mutations
Evolutionary solution
Performance evaluation:
• several trials of simulated players
• the simulated players try to go through
the labyrinth and we monitor their health
amount
• we determine the performance for each
resource allocation pattern from the
population of solutions
Evolutionary solution
Directed operators:
• monitoring the health amount changes in
areas of the labyrinth we can guide the
mutation and crossover operators to improve
areas where the performance is not close
enough to the desired one
Evolutionary solution
Mating potential determination:
Mating potential
Performance
Evolutionary solution
Parent selection:
• each potential parent is assigned a
mating potential
• randomly select parents
• randomly set a limit for the potential
parent, if its mating potential is bigger
than that, the parent is selected
• after each time when a parent is selected
its mating potential is decreased
Evolutionary solution
Evolution:
• a population of potential solutions
(resource allocation patterns) is generated
• the population evolves using the genetic
operators, performance evaluation, parent
selection and offspring generation
Evolutionary solution
How does it work ?
Average performance
Variance of performance
Summary
• evolutionary optimisation is very time consuming
• off-line application is preferred for optimisation
for computer games
• it may be applied to evolutionary simulation
• the problem world should be well defined and
should sample the relevant ranges of the parameters
• appropriate genetic encoding, genetic operators,
performance evaluation, mating potential
determination and parent selection should be found
Questions
1. Are the proteins the building blocks of the DNA ?
2. Is it true that animals may develop new organs
under evolutionary pressures ?
3. Are the behaviours of an animal determined by its
genes ?
4. Is it true that evolutionary optimisation is slow ?
5. Are the genes of a solution individual randomly
changed by the application of crossover ?
6. Is it good if the variance of the performances is
very low from the beginning of the evolutionary
optimisation ?