Week 8 Flashcards
(27 cards)
Why MOEAs?
Many real world problems exist with multiple objectives
Engineering problems are often multi-objective
Useful in industry to see trade-off between costs and benefits of solutions.
How do we get EAs to perform multi-objective computation?
Generational GA
Revised objective function - multiple objectives
Revised selection criteria - domination criterion
Revised visualisation - pareto-optimal curves
What is domination criterion?
A solution a is said to dominate another solution b if it is at least as good as b in every dimension and better than b in at least one dimension.
What is the pareto-front?
Given a domination criterion, we know the best solutions will lie along a curve consisting of non-dominated points. Known as the pareto-optimal front or the pareto front.
Desirable characteristics of the pareto front
Evenly spaced solutions
Covering the largest possible area of the front.
What is discrimination in multiple objectives
Instead of having single fitness function, we have multiple fitnesses
Best solutions lie on pareto front
To discriminate between the rest of the solutions we use ranking methods
Ranking method
Determine the pareto-front, assign it to rank 1, remove it from population, assign the next pareto front to rank 2, and so on.
Alternative ranking method
Rank based on the number of solutions that dominate the solution - e.g. rank 0 = non dominated
rank 1 = one solution dominates, etc
How do we tell the difference between two solutions which are non-dominated?
A new selection operator
Problem with Pareto Domination tournament selection
Cannot pick winners between solutions in the same rank
Selection pressure is not sufficient, so a randomly selected comparison set is introduced.
‘Select 2 random individuals a&b and a separate comparison set c from the population. If a or b is non-dominated with respect to c, select.
If a and b have the same domination, tiebreak.
How do we tiebreak for individuals with the same domination?
Choose the one from the less dense area. As it represents a wider range.
What is niching?
When tiebreaking, use a niche radius around the point, the number of points within this radius is the niche count. The solution with the smallest niche count is chosen.
New parameter- niche radius.
What is crowding distance?
Sum the manhattan distance of the point from the 2 nearest points.
How does NSGAII work?
Initial population N
Select, crossover, mutate -> 2N.
Fast ND sort into ranks
Sort by crowding distance and discard everything beyond N.
Elitist vs Non-elitist MOGAs
Elitist has superseded non-elitist.
Elitist requires no extra parameters e.g. niche sizes.
Executes and converges faster
Can prematurely converge on certain problems.
Can we use single objective GAs for multiple objectives?
Yes, by weighting each objective, we can optimise for different points on the pareto curve.
You have to do a separate GA run for each point.
Final shape of the curve not defined for MOGAs.
Computing machinery vs human ability
Computers outperform us in certain domains
Complex calculations,
Memory task
We can do:
Perception
Reasoning
Learning.
Architecture of computers vs brain
Computers, very fast serial machines
Brain is slower but very parallel
Key aspects of a computer
Can perform tasks sequentially incredibly quickly
Doesn’t make mistakes (most of the time, pentium floating point errors)
Memory and processing are separated
Large capacity of storing information indefinitely
Key aspects of humans
Distributed architecture
Ability to learn
Ability to generalise
Structures responsible for memory/processing are not necessarily separated
Will forget unimportant information over time.
Brain structure
100 billion neurons
Each connected to 10k others
Neurons communicate through synapses - effectively a configurable chemical junction between neurons
What are neurons?
Systems for signal processing and memory
Connectionism was proposed based on research in neuroscience about how the information is processed, stored and communicated among neurons.
A brain is composed of billions of cells (neurons) which interact with each other
What are neurons composed of?
Dendritic tree - receive signals
Cell body - process signals
Axon - transmit signals
How do neurons function
Neuron receives electrical activity from other neurons along its dendrites
The axon produces a pulse based on the strength of the incoming pulse
This is then passed to other neurons connected to this one.
