Transcript Slide 1 - Boris Burdiliak

Evolutionary Design (2)
Boris Burdiliak
Topics


Representation
Multiple objectives
Representation – Introduction


EA are based on natural evolution
evolution provides a quick and easy way
to solve difficult problems (scheduling,
machine learning, ordering problems, data
mining, control, design optimisation)
Representation – Problems



traditional implementations of evolutionary
search suffer from the same drawbacks as
all conventional search algorithms
they rely on a good parameterization to
find a good solution
evolution is limited by the representation it
can modify
Explorative evolution



evolution can search for good search
spaces, even as it searches within a space
dimensionality of a space, the
parameterization, the representation of
solutions
solutions = inventions, not improvements
Exploring the Explorer


what is evolution doing when it
explores/optimises?
fixed-length parameterization


evolution = optimisation
parameters define a set of components

explores new ways of constructing a solution
A Framework for Expl. Evolution

EA



GA/GP (genotype/phenotype distinction)
EA/ES (no distinction)
prob.: multiple objectives, premature
convergence, changing fitness functions
Genotype Representation


defines the search space(defines components)
prob.: dissimilar problems are close to e.o.,
disruption of inheritance
A Framework for Expl. Evolution 2

Embryogeny






Phenotype Representations


mapping process from genotype to phenotype
provide the mechanism for constructing whole solutions from
components
external: programmer writes the software that performs the
mapping
explicit: every step of growth process explicitly held as a part of
genotype, and evolved
implicit: set of rules (encoded as bin. strings in genotype)
allow direct evaluation of fitness function
Fitness functions

provide evaluation score for every solution
Multi objectives

optimise function F(x) under additional
constraints, i.e.




max {x} F(x)
g_1(x,p) <= 0, … g_l(x,p) <= 0
p(p_1,…,p_u) – real-valued parameters
relative importance, interactions of
objectives (also contradictory)
Pareto optimisation



Def: We will say that a point xD Paretodominates a point yD with respect to function
F, denoted yx, if {i=1..k} (f_i(y) f_i(x)) and
at least one of inequalities is strict
We say that point x_pD is Pareto-optimal or
non-dominated (for a given function F) if there is
no point yD that Pareto-dominates x.
Set FD is called Pareto front with respect to
function F if every element x F is Pareto optimal
with respect to function F
Selection phase


not all elements from the Pareto front are of a
good fitness value
Pareto tournament


Pareto sort



standard tournament selection (best individual
according to Pareto ordering)
sort according to Pareto ordering
if both ind. are dominant, sort acc. to fitness value
Pareto truncation

choose parent only among the non-dominated
#of non-dominated elements





population size = 100
standard tournament (size 2)
averaged over 50 runs
optimising 3 parameters
non-dominated elements





after
after
after
after
50 runs: cca 42%
150 runs: >50%
350 runs: almost 70%
500 runs: cca 85%
Pareto front is too large
Pareto ranking

Def: Pareto rank r in a set X={x_1,…,x_n}
is assigned in a following way


(xX) r(x) 1
("x{x_1,…x_n}) ("y{x_1,…,x_n} \ {x})
if (r(x)=r(y) x > y) r(x) r(x)+1
 if (r(x)=r(y) x < y) r(y) r(y)+1

Conclusions




requirement is for methods that can work
with a qualitative in addition to a
quantitative characterization of importance
preference methods
fuzzy set methods
agent based systems which model humanbased solution evaluation process
Fuzzy preferences


transforming qualitative relationships between
objectives in multi-objectives optimization into
quantitative attributes
characterisations for every 2 objectives:






much less important <<
less important <
equally important ==
don’t care #
more important >
much more important >>
Don’t care relation


don’t care is treated exactly as equally
important
hesitations

weak preference


can not decide: a > b and a ==b, being sure that
not (b > a)
incomparability

can not decide: a > b and b > a
Method used



k objectives – k(k-1)/2 questions -> construct
the fuzzy preference relation R
compute complete oredering on A using the
relation graph G=(A,R)
define relations:





== equally important
< is less important
<< is much less important
~ not important
! important
Algorithm

set of objectives O
construct the equivalence classes C_i
(relation ==), choose one element x_i
from each class X={x_1,…,x_m}

…

for each xi compute weight w(xi)

Weighted Pareto method



Definition of non-dominated vector
Definition of w-non-dominanace
Definition of (w, tau)-non-dominance

THE END