Transcript Diversity Preservation in Evolutionary Algorithms

Diversity Preservation in
Evolutionary Algorithms
Jiří Kubalík
Intelligent Data Analysis Group
Department of Cybernetics
CTU Prague
EAs and Premature Convergence

Evolutionary cycle
Homogeneous population

Premature convergence - as the population gets homogeneous,
only a little new can be evolved and EA converges to suboptimal
solution.

Causes of premature convergence:

‹#›
improper representation and genetic operators, improper selection
pressure, insufficient population size, deception
Diversity Preservation in EAs
GA with Limited Convergence (GALCO)

Motivation


Realization





‹#›
to maintain a diversity of the evolved population and extend the
explorative power of the algorithm
Convergence of the population is allowed up to specified extent
Convergence at individual positions of the representation is controlled
Convergence rate
 specifies a maximal difference in the frequency of ones and zeroes in
every column of the population
 ranges from 0 to PopSize/2
Principal condition
 at any position of the representation neither ones nor zeroes can
exceed the frequency constraint
Specific way of modifying the population genotype
Diversity Preservation in EAs
GALCO: Algorithm
1.
Generate initial population
2.
Choose parents
3.
4.
Create offspring
if (offspring > parents)
then
replace parents with offspring
else{
find(replacement)
replace_with_mask(child1, replacement)
find(replacement)
replace_with_mask(child2, replacement)
5.
‹#›
}
if (not finished) then go to step 2
Diversity Preservation in EAs
GALCO: replace_with_mask
Mask – vector of integer counters; stores a number of 1s for
each bit of the representation
50
‹#›
Diversity Preservation in EAs
Static Test Problems


‹#›
Multimodal problem

Deceptive problem

Hierarchical problem
Royal Road Problem
Diversity Preservation in EAs
GALCO: Finding Optimal c
‹#›
multimodal
deceptive
royal road
hierarchical
Diversity Preservation in EAs
GALCO: Comparison with SGA
multimodal
royal road
‹#›
deceptive
hierarchical
Diversity Preservation in EAs
GALCO: Multimodal Optimization
Initial population
SIGA
with
‹#›
replace_with_mask
without
Diversity Preservation in EAs
GALCO: Multimodal Optimization (cnd.)
Initial population
‹#›
GALCO
SGA
Diversity Preservation in EAs
GA with Real-coded Binary Rep.

Motivation


Realization


real coded binary representation
Effect

‹#›
using redundant representation, where many different genotypes
map to the same phenotype would increase the explorative power
of the EA and decrease the probability of getting stuck in a local
optimum
population can not converge to the homogeneous state so that the
premature convergence can not take place
Diversity Preservation in EAs
GARB: Representation

Pseudo-binary representation – binary gene values coded by real
numbers from the interval 0.0, 1.0
Example:
ch1 = [0.92 0.07 0.23 0.62]
ch2 = [0.65 0.19 0.41 0.86]
interpretation(ch1)=interpretation(ch2)=[1001]

Gene strength – gene’s stability measure
 The closer the real value is to 0.5 the weaker the gene is
„one-valued genes“: 0.92 > 0.86 > 0.65 > 0.62
 „zero-valued genes“: 0.07 > 0.19 > 0.23 > 0.41

‹#›
Diversity Preservation in EAs
GARB: Gene-strength Adaptation

Every offspring gene is adjusted depending on
its interpretation
 the relative frequency of ones at given position in the population


Vector P[] stores the population statistic
Ex.: P[0.82 0.17 0.35 0.68]
 82% of ones at the first position,
17% of ones at the second position,
35% of ones at the third position,
68% of ones at the fourth position.
‹#›
Diversity Preservation in EAs
GARB: Gene-strength Adaptation cnd.

Zero-valued gene:
gene’ = gene + c*(1.0-P[i])
gene’ = gene – c*P[i]

One-valued gene
gene’ = gene + c*(1.0-P[i])
gene’ = gene – c*P[i]
‹#›
weakening
strengthening
strengthening
weakening

c stands for a maximal gene-adaptation step: c (0.0,0.2

Gene value interpreted with above-average frequency at given position
in the chromosome is weakened, the other one is strengthened.
Diversity Preservation in EAs
GARB: Gene-Strength Adaptation cnd.

Effect

if some allele begines to prevail in the population,
1.
2.
3.

‹#›
the corresponding genes are weakened in subsequent
generations,
at some point they are moved to the other side of the
threshold 0.5,
so that they change their interpretation and the frequency of the
allele decreases.
frequency of a given allele is controled by contradictory pressures

the convergence to optimal solution pressure and

the population diversity preservation pressure
Diversity Preservation in EAs
GARB: Boosting-up the Exploitation

Genotype of promising solutions should be stabilized for subsequent
generations
 in order to disable rapid changes in their genotype interpretation

Newly generated solutions that are better than their parents
 all genes are rescaled (strengthened) - zero-valued genes are set to
be close to 0.0 and one-valued genes are set to be close to 1.0
Ex.:
ch = (0.71, 0.45, 0.18, 0.57)

ch’= (0.97, 0.03, 0.02, 0.99)

Effect

‹#›
Genes survive with uchanged interpretation through more generations.
Diversity Preservation in EAs
GARB: Algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
‹#›
begin
initialize(OldPop)
repeat
calculate P[] from OldPop
repeat
select Parents from OldPop
generate Children
adjust Children genes
evaluate Children
if Child is better than Parents
then rescale Child
insert Children to NewPop
until NewPop is completed
switch OldPop and NewPop
until termination condition
end
Diversity Preservation in EAs
GARB: Results on Static Problems
1500
deceptive
2304
1400
GARB
SGA
2000
GARB
SGA
1350
1300
0
fitness
100
hierarchical
1500
200
300
400
500
f itness ev aluations (x1000) 1000
500
0
-700
100
200
300
400
f itness ev aluations
(x1000)
-800
fitness
fitness
1450
500
GARB
SGA
multimodal
F101
-900
-955
0
‹#›
100
200
300
400
f itness ev aluations (x1000)
Diversity Preservation in EAs
500
Single Gene Diversity Monitoring
Hierarchical problem
F101
‹#›
Diversity Preservation in EAs
GARB: Tracking Moving Optimum
Moving optimum
‹#›
Population diversity
Diversity Preservation in EAs
GARB: Results on Knapsack Problem
Oscillating Knapsack Problem
‹#›

14 objects, wi=2i, i=0,...,13

f(x)=1/(1+|target - wixi|)

Target oscillates between two values 12643 and 2837, which
differ in 9 bits
Diversity Preservation in EAs
GARB: Recovering from Homog. State
DF3
‹#›
Knapsack problem
Diversity Preservation in EAs