Multi-Objective Optimization
Combinatorial Optimization problem
Travelling Salesman Problem: Visit n places while mimining
travel cost, start and end at a known source, assuming travel
cost between all places is known
Search - Complexity n! ???
DP - exponential : best by optimality
Greedy - n : best by complexity
better than greedy by optimality,
better than search by complexity
Problem - find optimal timing sequence for every light in all
traffic lights
Solution - do simulation for "all possible" combination of
values that traffic light can take
-- time is continuous - infinite combinations
-- discretize time to some resolution
complexity: (resolution)^(number of lights)
another problem: i do not know the resolution loss
Deterministic Games: Mario
Game board at any time: vertices
Key presses: edges
problem: time is continuous
complexity: (branching factor)^(game depth)
4^(a very high number)
Classic Search Algorithms
-- Generate all possible solutions and pick the best one,
complexity is "exponential", solution is optimal not possible
-- problem/time/world is continuous - discretization is
expensive by complxity or discretization loss
Greedy Algorithms
-- use some rules of thumb/heuristic in decision making
-- fast but not optimal
Gradient Descend
-- Take a random candidate solutionm
-- Move it in a direction opposite to gradient
-- At minima, gradient = 0, so movement = 0
-- What if there are discrete variables?
-- What if there is no gradient?
Administrative:
Attendance: 75% at all times
Marking Scheme:
Mid: 30
End: 40
Quizzes: 10*2
Attendance: 5
Assignments (evaluated in person) -- quiz: 5
Book: Multi-Objective Optimization using Evolutionary
Algorithms by Kalyanmoy Deb
Evolutionary Algorithms -- will be taught next semester
Grading
Syllabus:
Evolutionary Algorithms
(approximation algorithms/soft algorithms, iterative - improve
with time, multi-individual/multi-candidate)
Multi-Objective Problems and Algorithms
RAM Processor Touch Screen Cost
Dell 8 GB i5 No 70k
HP 16 GB i7 Yes 130k
Acer 12 GB i7 No 85k
Undisclosed 16 GB i7 Yes 165k -- makes no
sense
Undisclosed is not a part of my solution set
Multi-Objective Optimization:
The problem of multi-objective optimization is to find a set of
"diverse" non-dominating solutions (no solution dominates
the other).
-- A user is presented all solutions and only the user selects the
best out of all
Even for 2 objectives, I could have infinite non-dominating
solutions
Multi-Criterion Decision Making --- not a part of this course
Syllabus:
- Evolutionary Algorithms
- Multi-objective optimization
MID SEMESTER
- Evolutionary Algorithms applied to Multi-Objective
Optimization
--- Classic/Obvious Ways to solve the problem
--- Non Elitist Approaches
--- Elitist Approaches
Simulated Annealing
x = random solution
x_best = x
while stopping criterion (like maximum time)
x’ = x + noise
r ~ random number between 0 and 1
if f(x’)<f(x), x=x’
else if r < small probability, x=x’
if f(x)<f(x_best), x_best = x
return x_best
There is a very very small but non-zero probability of
escaping the local optima
Theoretically, as time tends to infinity, I go to global optima
Multi-Objective Optimization
aka Two space problem (Decision space and objective
space)
aka Vector Optimization problem (minimize vector F(x))
min fi(x)
or
min F(x)
x: decision variables [x1, x2, x3…, xn]
F(x)=Objective vector [f1(x), f2(x),…, fm(x)]
n decision variables
m objective functions
Bounds: LBi <= xi <= UBi
Inequality constraints: gj(x)<=0
Equality constraints hk(x)=o
x1 and x2
f1(x1) = 10, f2(x1) = 40
f1(x2) = 50, f2(x2) = 80
If I look at f1, x1 (10) is better than x2 (50)
If I look at f2, x1 (40) is better than x2 (80)
In all cases x1 is better than x2
x1 dominates x2
x1 dominates x2 iff
i) fi(x1)<=fi(x2) for all objective functions i
ii) fi(x1) < fi(x2) for at least one objective functions i
Exam Trick:
2-dimensional problems
Min-min problems
x1 dominates x2 iff x2 is at top right of x1
x1 is dominated by x2 iff x2 is at the bottom left of x1
f1(x1) = 40, f2(x1) = 100
f1(x2) = 80, f2(x2) = 60
objective 1: x1 (40) is better than x2 (80)
objective 2: x2 (60) is better than x1 (100)
neither x1 dominates x2, nor x2 dominates x1
x1 ~ x2
Given a set of individuals P, x1 is non-dominated within the
set of individuals P, iff no individual x2 in the population
dominates x1
Problem of multi-objective optimization is to give a set of
non-dominated solutions to a problem
Non-dominated solutions: Solutions where no two solutions
dominate each other.
min fi(x)
or
min F(x)
x: decision variables [x1, x2, x3…, xn]
F(x)=Objective vector [f1(x), f2(x),…, fm(x)]
n decision variables
m objective functions
Output is a set of diverse non-dominated solutions to a
problem (Pareto front)
Single-Objective Optimization
Multi-dimensional: 1000 dimensional space
Multi-modal: Too many hills and valleys
General Class: Evolutionary Computation
Specific Class: Genetic Algorithm
Selection: Number of times an individual gets selected for
mating
Fitter individuals, several times
Weaker individuals, never, die
Darvin’s theory of survival of the fittest: Individuals most
adaptive to change, produce more offsprings, and weaker ones
die
Crossover: Parents exchange genes to produce children
Mutation: Genetic Copying Error such that genes of children
are different from parents
Genetic Algorithm
Take a random population of individuals
While stopping criterion
Fitness evaluation
Selection (create a mating pool) – Darvin’s survival of fittest
Crossover (Xover) – parents produce children/mating
Mutation – add genetic errors
Child population is better than the parent
Or, the population adapts and gets better with time as judged
by the fitness function
Phenotype: Solution in the format relevant to solve the
problem
Genotype: Solution in the format suitable for optimization is
called genotype
Let there be B bits for xi (e.g. B=4)
Range of binary numbers possible = [0, 2B-1]
bmin=0
bmax=2B-1 (say, 15)
The upper bound and lower bound for decimal equivalent of xi
are known from problem statement
Lower bound: lmin (-1)
Upper bound: lmax (1)
I need to interpolate the range [bmin,bmax] linearly into
[lmin,lmax]
Linear interpolation formula
Convert(b) = lmin + (b - bmin)/(bmax – bmin) * (lmax – lmin)
At b=bmin, I get lmin
At b=bmax, I get lmax
Convert(5) = -1 + (5-0)/(15-0)*(1-(-1)) = -1+5/15*2
Convert(3) = -1 + (3-0)/(15-0)*(1-(-1)) = -1+3/15*2
Convert(12) = -1 + (12-0)/(15-0)*(1-(-1)) = -1+12/15*2
An ‘individual’ suitable for the problem for fitness assessment
(phenotype) is encoded in binary (genotype) – so for fitness
evaluation I convert genotype (binary) into phenotype
(problem-specific format/route/real number)
Expectation value of an individual is the probability that the
individual is selected for the mating process
Fitness-based Scaling: Expectation is proportional to fitness
(for a maximization problem)
Expectation is inversely proportional to fitness (for a
minimization problem)
Rank-based Scaling: Expectation is proportional to (inverse
of) ranks
In a rank based scaling, one extremely fit individual cannot
dominate the new population pools
- expectation is based on the order of fitness values not
their absolute fitness values
Selection pressure
A high selection pressure is a fitter individual getting selected
too many times and dominating the next generation
– leads to wrongly calling the current best as near global
optima
- convergence to local optima [Bad]
- quick convergence [Good]
In a low selection pressure every individual has nearly the
same chance of being selected
- an individual currently poor and near global optima
can improve and get to the global optima [Good]
- takes a very long time and does not converge [Bad]
Tournament Selection
Select 2 individuals for a match, with a probability P (high)
fitter individual wins and with a probability 1-P (low) weaker
individual wins
Tournament Size: number of individuals that participate in a
tournament from which 1 is selected – to select n individuals
play n such tournaments
Stochastic Universal Sampling
Select the 0th individual at r ~ U[0,1] (uniform distribution
between 0 and 1, same as Roulette Wheel Selection)
Selection of k individulas
ith individual is at a distance of [(1/k)*i + r] mod 1
Roulette Wheel
1 2 3 4 5 6 7
8 9 10 11 12 13 14
8 equally spaced selectors
Expected Selecto
Individual Value Start End r
1 0.095 0 0.095 number Selectors
2 0.124 0.095 0.219 1 0.776
3 0.114 0.219 0.333 2 0.901
4 0.086 0.333 0.419 3 0.026
5 0.105 0.419 0.524 4 0.151
6 0.076 0.524 0.6 5 0.276
7 0.019 0.6 0.619 6 0.401
8 0.057 0.619 0.676 7 0.526
9 0.01 0.676 0.686 8 0.651
10 0.029 0.686 0.714
11 0.133 0.714 0.848
12 0.067 0.848 0.914
13 0.048 0.914 0.962
14 0.038 0.962 1
Real Coded Genetic Algorithm
Mutation:
Uniform Mutation: Replace the ith gene of the parent by a
random real coded gene value – uniform distribution between
lower and upper bound
r ~ random number between 0 and 1
xi = LBi + r (UBi - LBi)
if r = 0, LBi, if r=1, xi = UBi
Non-Uniform Mutation:
The probability of a small change in gene value should be large
The probability of a large change in gene value should be small
yi = xi + r, r ~ N(0, sigma),
N – normal distribution
Sigma - mutation rate
Schema: Complete hypervolume in the decision
space that the complete population occupies at any
time
Exploitative Operator: Operator that aims to declare the
best based on the current limited knowledge and aims to
quickly converge
- Reduces computation time
- Can converge to local optima
Explorative Operator: Operator that aims to explore
newer areas of the search space and expand the search
space hypervolume in consideration by the schema.
- Slow (no convergence) – in fact population will
diverge
- I am less likely to get stuck at local optima
Exploitative Selection: Population (schema) shrinks
and new individuals are better (average objective
value improves)
Explorative Mutation: Population (schema) expands and
new areas are tried. The new population may be
better/worse or with the same average fitness
Explorative Crossover: Population (schema) expands and
new areas are tried. The new population may be
better/worse or with the same average fitness
Exploitation >> Exploration – population converges into an
optima
Exploration does its part in resisting the convergence such that
there is enough time to explore the global optima and leave
the local optima, such that population eventually converges
into the global optima
High mutation rate – explorative
High crossover rate – explorative
High number of individuals (for fixed number of generations)
– always better
High number of individuals (for fixed number of fitness
evaluations – I will have to reduce number of generations) –
explorative
High selection pressure - exploitative
Random search
Xbest = random
While stopping criterion
Xnew = random
If xnew better than xbest, xbest = xnew
return xbest
bad because I can only explore a tiny fraction of the entire
search space – in GA it is more guided
Schema Theory
Schema:
Population of all 4th years (general)
- Population of all girls (little more specific)
o Population of girls with spectacles (more specific)
o Population of girls without spectacles (more
specific)
- Population of all boys
- Population of late comers
Schema
1*** ****
0*** ****
To calculate fitness of the schema, generate n random samples
and calculate the fitness of the samples
1*** ****
10101010
10011001
11010110
10010111
------
average
Dominating gene: If you change 1st bit, the fitness suddenly
changes by a large amount on an average
Only a few samples can uncover the superiority of the 0 * * *
* * * * * over 1 * * * * * * * *
***1****
***0****
Non-Dominating gene: Change in this bit does not
significantly affect the fitness value, schema 2 is marginally
better than schema 1
Therefore, from a random sample of population it is not easy
to determine superiority of the 2nd compared to 1st
I will need too many samples to determine the superiority of
the second compared to first
Selection
Selects fitter individuals with a large probability and weaker
ones with a small probability
Population from above average schemas, lower order
schemas, smaller length gets selected exponentially higher
number of times
Order of a schema are the number of 0s and 1s in the schema.
Selection operator selects exponentially more number of
individuals from 0 * * * * * * * * as compared to 1 * * * * * *
**
Lower order schemas are too generic
Higher order schemas are too specific
If k is the size of the individual
o is the order
k-o are the *s
2^(k-o) is the number of individuals – many (not all) of them
may be represented in the population pool.
*1*1**1*=5
*****01*=1
Selection Operator: Order of schema will increase ->
exploitation
Increase 1s and 0s from *s, until population converges and all
bits have 0s and 1s and there are no *s
Schema
Initial population: * * * * * * * *
After 10th generation: * * * * 0 * * *
After 20th generation: 0 * * * 0 * * *
The hypercube has lost 2 dimensions
All individuals of this schema represent corners of a n-
dimensional hypercube, n=number of bits
****0***
****1***
High Mutation: High Exploration
- High convergence time
- Chances of convergence at the local optima are low
High selection pressure
- Small convergence time
- Changes of convergence at the local optima are high
Number of individuals
* * * * 0 * * * v/s * * * * 1 * * *
Using samples – population pool
I need to take enough number of samples so that I can clearly
decide which of the sub-schemas is better
That means my population size is dependent on the ability to
clearly/significantly determine the betterment of sub-schemas
Complexity: n log n
Complexity: number of fitness evaluations =
n G O(fitness evaluation)
n=number of individuals
G = number of generations (iterations)
Constraint Handling
Maximize number of orders delivered
Total fuel consumed - tank capacity <= 0
Time to deliver to customer c - max availability time for
the customer <= 0 [for all customers c]
Time to deliver to customer c – earliest availability time
for the customer >= 0 [for all customers c]
Total items carried <= total payload of the vehicle
Fitness function ‘ = actual fitness function + alpha *
SUM_OVER_j(magnitude by which the constraint j is
violated, 0 if not violated)
alpha>>1
Evolutionary pressures try to reduce the magnitude of
constraint violation
When feasible evolutionary pressures reduce the actual
objective value f(x)
Alpha is hard to set
Feasible over infeasible
A feasible solution is always better than infeasible
Among feasible, one with a better fitness is better
Among infeasible, one that has smaller constraint
violation is better
Fitness’(x) = fitness(x), if x is feasible
fmax + sum of constraint violation, if x is infeasible
fmax is the worst fitness of any solution in the current
population pool
Preserve Feasibility – Repair
Decoding stage
Diversity Preservation:
I need to find all modalities and local optima in that
modality
I need to prohibit convergence to local optima and
encourage convergence to global optima (using above)
Fitness Sharing: Share individuals among modalities or all
individuals share their fitness value with one another and the
neighbourdood density is used in fitness evaluation
F’ = (fitness) / (density) = (fitness) / (sharing value)
shareij = contribution of xj in the sharing or density count of xi
inversely proportional to d(xi,xj)
shareij = 1 – (d(xi,xj)/sigma_share)alpha, if d(xi,xj) <= sigma_share
0, if d(xi,xj) > sigma_share
f’(xi) = f(xi) / \sum_j (sharei,j)
Create evolutionary pressure to encourage good
solutions (numerator) and solutions in new areas
(denominator)
Crowding
Similar to GA, I apply selection, crossover, mutation, to
produce a child C.
Child replaces the individual most similar in the parent
population in a sampled population (which may not be the
same individual used to generate child c)
Distance between child and replaced individual will be
smaller than or equal to that of the biological parent
Convergence/Crowding/Decrease in schema hypervolume is
smaller
-- Leads to diversity preservation
Select a very small population for mating
Select a candidate population of size crowding factor. A
child c selects parents closest in the sampled candidate
population
Crowding factor or CF: parameter, size of the candidate
population to apply crowding.