Divided Range Genetic Algorithms in Multiobjective

Divided Range Genetic
Algorithms in Multiobjective
Optimization Problems
Tomoyuki HIROYASU
Mitsunori MIKI
Sinya WATANBE
Doshisha University
Topics
•Multi objective optimization problems
•Genetic Algorithms
•Parallel Processing
Divided Range Genetic Algorithms (DRGAs)
What is
Optimization Problems ?
Design variables X={x1, x2, …. , xn}
Objective function F
Constraints
Gi(x)<0 ( i = 1, 2, … , k)
Multi objective optimization problems
Design variables X={x1, x2, …. , xn}
Objective function F={f1(x), f2(x), … , fm(x)}
Constraints
Gi(x)<0 ( i = 1, 2, … , k)
Pareto dominant
C
A
F2
B
F1
better
Pareto Solutions
Cost
better
Ranking
5
2
F2
3
1
1
1
F1
better
Genetic Algorithms
Evaluation
Crossover
Selection
Mutation
Multi point searching methods
I=K+1 I=K
I=1
I=0
F2
F1
better
GAs
in multi objective optimization
•VEGA Schaffer (1985)
•VEGA+Pareto optimum individuals Tamaki (1995)
•Ranking Goldberg (1989)
•MOGA Fonseca (1993)
•Non Pareto optimum Elimination Kobayashi (1996)
•Ranking + sharing Srinvas (1994)
•Others
Parallerization of
Genetic Algorithms
•Evaluation
Micro-grained model
•Population
Coarse-grained model
Island model
Island 1
f2 (x)
f2(x)
f2 (x)
Distributed Genetic Algorithm
f 1(x)
Island 2
f1(x)
f 1(x)
・Cannot perform the efficient search
・Need a big population size in each island
Divided Range
Genetic Algorithms
(DRGA)
F2
F1
Divided Range
Genetic Algorithms
(DRGA)
F2
F1
Genetic Algorithms in
Multi objective optimization
•Expression of genes
Vector
•Crossover
Gravity crossover
•Selection
Rank 1 selection with sharing
•Terminal condition
When the movement of
the Pareto frontier is very
small
Numerical examples
Tamaki et al. (1995)
Veldhuizen and Lamount (1999)
Example 1
Objective functions
f1  x1  x2
2
1
f2   x1  x2 1
2
Constraints
1
13
x1  x 2   0
6
2
5x1  x 2  30  0 x2  0
x1  0
1
15
x1  x2   0
2
2
Example 2
Objective functions
f1  2x1  x2
f2  x 2
Constraints
x  x2  0
2
1
x2  1  0
x1  0
Example 3
Objective functions
f1  2 x1
f2  x1 (1 x 2 )  5
Constraints
x1  1 0 4  x1  0
x2  1  0 2  x 2  0
Example 4
Objective functions
f1  0.5(x1  x2 ) sin(x1  x2 )
2
2
2
2
(3x1  2x2  4)2 (x1  x 2  1)2
f2 

 15
Constraints
8
27
1
x1  3
2
2
f3  2
 1.1exp(x1  x 2 )
2
x2  3
x1  x2  1
Distributed Genetic Algorithms
Used parameters
SGA DGA DRGA
Cro ss o ver
1 .0
rate
Mu tatio n
0 .0
rate
Nu mb er o f
5
is lan ds
Mig rati o n i nt erval
5
(So rt in terv al )
Mig rati o n
0 .1
rate
Population size and
the sharing range
cas e
Cas e 1
Cas e 2
Cas e 3
Cas e 7
Cas e 5
p op u latio ns hari ng
ran ge
s ize
50
25
10 0
50
20 0
100
50 0
250
1 0 00
500
Evaluation methods
•Pareto optimum individuals
•Error
•Cover rate
(smaller values arebetter ( E>0)
(index of diversity, 0<C<1)
•Number of function calls
(smaller values are better)
•Calculation time
(smaller values are better)
Results(example 1)
Pareto optimum solutions
DGA
DRGA
Results(example 1)
Error
4.0
Error
3.0
2.0
Single
1.0
0.0
DGA
DRGA
0
1
2 3
Cases
4
5
Number of function calls
Results(example 1)
Number of function calls
8.0E+04
6.0E+04
Simple
4.0E+04
DGA
2.0E+04
0.0E+00
DRGA
0
1
2
3
Cases
4
5
Results(example 1)
Calculation time
Calculation time [s]
150.0
100.0
Simple
50.0
DGA
0.0
DRGA
0
1
2 3 4
Cases
5
Results(example 2)
Pareto optimum solutions
DGA
DRGA
Results(example 2)
Cover rate
1.0
Cover rate
0.8
0.5
Simple
DGA
DRGA
0.2
0.0
0
1
2
3 4
Cases
5
Number of function calls
Results(example 2)
Number of function calls
5.0E+05
4.0E+05
3.0E+05
2.0E+05
Simple
1.0E+05
DGA
0.0E+00
DRGA
0
1
2 3 4
cases
5
Results(example 3)
Pareto optimum solutions
DGA
DRGA
Results(example 4)
Pareto optimum solutions
SGA
DRGA
Results(example 4)
Cover rate
1.0
Cover rate
0.8
0.6
Simple
0.4
DGA
0.2
0
1
2 3 4
Cases
5
DRGA
Number of function calls
Results(example 4)
Number of function calls
1.2E+04
1.0E+04
7.5E+03
5.0E+03
Simple
2.5E+03
DGA
0.0E+00
DRGA
0
1
2 3
Cases
4
5
How DRGA works well?
+
f1(x)
+
f1(x)
f2(x)
f2(x)
f2(x)
=
f1(x)
・DRGA
f1(x)
f2(x)
f2(x)
f2(x)
・DGA
=
f1(x)
f1(x)
Conclusions
In this study, we introduced the new model of genetic
algorithm in the multi objective optimization problems:
Distributed Genetic Algorithms (DRGAs).
DRGA is the model that
•is suitable for the parallel processing.
•can derive the solutions with short time.
•can derive the solutions that have high accuracy.
•can sometimes derive the better solutions compared to the
single island model.

Download Report