Transcript Matt Johnson`s Multi-Objective EA slides

MOEAs
University of Missouri - Rolla
Dr. T’s Course in Evolutionary Computation
Matt D. Johnson
November 6, 2006
Main Topics




Multi Objective Evolutionary Algorithms
Example Problem – ZDT1
T-MOEA
Preliminary Results
MOEAs



Multi Objective Evolutionary Algorithms
Based on the concept of the standard EA, but
with multiple objectives to optimize
Some of the objectives may conflict with one
another
Fitness vs. Dominance


In a standard EA, an individual A is said to be
better than an individual B if A has a higher
fitness value than B
In a MOEA, an individual A is said to be better
than an individual B if A dominates B (Deb)
Dominance

A solution x1 is said to dominate a solution x2 if
both conditions below are true:
The solution x1 is no worse than x2 in all objectives
 The solution x1 is strictly better than x2 in at least
one objective (Deb)


If x1 dominates x2 (x1 ≤ x2), it can be said that
x2 is dominated by x1
 x1 is non-dominated by x2
 x1 is non-inferior to x2 (Deb)

Pareto Optimality


Non-dominated set: Among a set of solutions P,
the non-dominated set of solutions P’ are those
that are not dominated by any member of the
set P (Deb)
Globally Pareto-optimal set: The non-dominated
set of the entire feasible search space S is the
globally Pareto-optimal set (Deb)
Deterioration


Deterioration occurs when individuals in the
current solution are dominated by individuals
that existed in the solution set previously, but
have since been terminated
Even “elitist” algorithms can suffer from this
condition
Defeating Deterioration


Efficiency Preservation: Property of accepting a
new individual only if it dominates an existing
individual in the population
Negative Efficiency Preservation: An individual
is deleted from the population only if it is being
replaced by a superior individual.
Example Problem: ZDT1

Zitzler-Deb-Thiele’s Test Problems


Minimize f1(x)
Minimize f2(x) = g(x) h(f1(x), g(x))
ZDT1: Pareto Optimal Solution
ZDT1
1.2
1
f2
0.8
0.6
0.4
0.2
0
0
0.2
0.4
0.6
f1
0.8
1
1.2
MOEA Goals



Find the Globally Pareto-Optimal set of
solutions
Would like as many solutions as possible
Even distribution of solutions
NSGA-II



A Fast and Elitist Multiobjective Genetic
Algorithm: NSGA-II
Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal,
T. Meyarivan
Each generation bounded by a fast
nondominated sort - O(MN2)
NSGA-II

Steps before main loop begins
Initialize population P0
 Sort P0 on the basis of nondomination
 Fitness of an individual is equal to an individuals
nondomination level
 Binary Tournament Selection
 Mutation and recombination create an offspring
population Q0

NSGA-II

Primary loop
Rt = Pt + Qt (t = generation)
 Sort Rt on the basis of nondomination
 Create Pt+1 by adding individuals from each level of
Rt until Pt+1 is of size N
 Create Qt+1 by applying Binary Tournament
Selection, Mutation, and Recombination to Pt+1
 Increment t

Epsilon MOEA




A Fast Multi-objective Evolutionary Algorithm
for Finding Well-Spread Parto-Optimal
Solutions
Kalyanmoy Deb, Manikanth Mohan and Shikar
Mishra
Steady State, Elitist, Does not suffer from
deterioration
Uses epsilon dominance (fuzzy dominance)
Epsilon MOEA



Uses two populations
An individual is only deleted when it is replaced
with a superior individual
Uses an identification array B which consists of
abbreviated objective values, creating containers
– only one individual may occur in a container
Motivation for T-MOEA



Faster – avoid duplicating work (sorting the
population again and again, even when it has not
changed that much)
Simpler – existing algorithms are difficult to
explain and understand
Object Oriented – existing algorithms can be
implemented in an OO manner, but are not
specifically designed that way
Motivation for T-MOEA





Greater flexibility
Multiple selection approaches
Control size and number of nondomination
levels
Elitist
No deterioration
T-MOEA Algorithm


Initialization
while termination condition is false do
Parent Selection
 Recombination and Mutation
 Insertion


end while
Data Structure



Most EAs and MOEAs use a “pool” of
individuals
T-MOEA calls for a vector of Binary Search
Trees
No duplicate individuals allowed
Selection – select1



Parents will be selected from the top level
If all individuals in a level have been selected
and more are needed, the next lower level is
used
If more parents are needed and all levels have
been exhausted, selection is random in the entire
population
Selection – select2


Designed for higher selection pressure
All parents are selected from the top level
Selection – select3

Randomly select individuals in the population
Recombination and Mutation



Problem specific
Operations are handled within the “Individual”
object
Will sometimes use a mutation size that
decreases as the number of generations
increases
Insert

Check to see if the new individual x belongs in
the top level
If x strongly dominates, insert x into a new level
above
 If x weakly dominates, remove dominated
individuals and insert
 If x is equivalent, insert
 Else, try next lower level

Objective Truncation



Suppose each objective function value is a real
number in the range [0, 1]
When an individual is inserted into the data
structure, it is compared using less than and
equivalency operators
These operators will multiply the objective
values by say, 100, and then truncate before
doing the comparison
Tree Behavior



Duplicate individuals are not allowed in a tree
Standard Binary Search Tree
Insertion depends on less than and equivalency
operators of the individual object
Metrics - Convergence



Calculate a Pareto Optimal solution set
Calculate the distance from an individual in the
population to the closest individual in the
solution set
The convergence metric is the average of these
distances
Metrics - Diversity




Draw a Voronoi Diagram of a population
The Voronoi Diagram will “Decompose space
into regions around each point such that all the
points in the region around pi are closer to pi
than they are to any other point in S”
In a perfectly distributed solution, region will
have the same area
The standard deviation of the areas is the metric
ZDT1 Results
EPSMOEA
Avg Conv
NSGA2
T-MOEA
0.001620596 0.002414274 0.000398675
StdDv Conv 0.000164577 0.000365921 3.36481E-05
Avg Divrs
0.000828195 0.001078336 0.000894804
StdDv Divrs 0.002586758 0.004802443 0.001620805
Parameters








PopSize:100
LevelSize: 100
NumLevels: 4
NumChildren: 100
NumGens: 200
Select1: true
F1_FACTOR: 100
F2_FACTOR: 500
Questions?