Parallel Evolutionary
Multi-Criterion Optimization
for Block Layout Problems
○ Shinya Watanabe
Tomoyuki Hiroyasu
Mitsunori Miki
Intelligent Systems Design Laboratory，
Doshisha University，Japan
Doshisha Univ., Japan
Background (1)
●ＥＭＯ・・・・
Ｅｖｏｌｕｔｉｏｎａｒｙ Ｍｕｌｔｉ－ｃｒｉｔｅｒｉｏｎ Optimizations
（Ex. VEGA,MOGA,NPGA…etc）
• Some of EMO can derive the good pareto optimum
solutions.
• EMO need high calculation cost.
SW-HUB
Parallel Computing
Evolutionary algorithms have potential parallelism.
PC Cluster Systems become very popular.
Doshisha Univ., Japan
Background (2)
●Parallel ＥＭＯ Algorithms
• Some parallel models for EMO are proposed
– There are few studies for the validity on parallel model.
• Divided Range Multi-Objective Genetic Algorithms
(DRMOGA)
– it is applied to some test functions and it is found that this
model is effective model for continuous multi-objective
problems.
DRMOGA hasn’t been applied to discrete problems.
Purpose
The purpose of this study is
to find the effectiveness of DRMOGA.
Doshisha Univ., Japan
Multi-Criterion Optimization Problems(1)
●Multi-Criterion Optimization Problems (MOPs)
In the optimization problems, when there are several objective functions,
the problems are called multi-objective or multi-criterion problems.
Design variables
Weak pareto optimal solutions
Objective function
f2(x)
X={x1, x2, …. , xn}
F={f1(x), f2(x), … , fm(x)}
Feasible region
Pareto optimal solutions
Constraints
Gi(x)<0 ( i = 1, 2, … , k)
f1(x)
Doshisha Univ., Japan
Multi-objective GA (1)
・Multi-objective GA
Like single objective GA , genetic operations such as
evaluation, selection, crossover, and mutation, are repeated.
5th
generation
1st generation
f2(x)
10th generation
30th generation
Pareto optimal solutions
f 1 (x)
50th generation
Doshisha Univ., Japan
DGA model
Distributed GAs
A population is divided
into subpopulations
(islands)
SGA is performed on
each subpopulation
Migration
Migration is performed
for some generations
1 island / 1PE
Exchange of individuals
Doshisha Univ., Japan
f(x)
2
f2(x)
Divided Range Multi-Objective GA(1)
Division 1
Division 1
f1(x)
f2(x)
Division 2
Division 2
Pareto Optimum solution
Min
Max
f1(x)
1st
f1(x)
The individuals are sorted by the values of focused objective function.
2nd The N/m individuals are chosen in sequence.
3rd SGA is performed on each sub population.
4th After some generations, the step is returned to first Step
Doshisha Univ., Japan
Formulation of Block Layout Problems
・Block Layout Problems with Floor Constraints
(Sirai 1999)
Objects
Block Packing method
n
f1=ΣΣcij dij
３
４
６
１
n
i=1
j=1
f2=Total Area S
７
where
５
２
n:number of blocks
cij: flow from block i to block j
dij: distance from block i to block j
：Dead Space
Doshisha Univ., Japan
Numerical Example
• Application models
– SGA , DGA , DRMOGA
• Layout problems
– 13, 27blocks
• Parameter
GA parameter
Number of individuals
crossover rate
mutation rate
migration interval
(resorted interval)
migration rate
terminal condition
value
100 (total 1600)
1.0
0.05
20
20
0.2
300generation
ex)13 blocks
Block No. vertical horizontal
1
18
24
2
36
18
3
18
42
4
42
18
5
36
42
6
24
36
7
24
54
8
30
36
9
48
18
10
36
24
11
36
36
12
54
24
13
36
30
Doshisha Univ., Japan
Cluster system for calculation
Spec. of Cluster (16
nodes)
Processor
PentiumⅡ(Deschutes)
Clock
# Processors
Main memory
Network
(100Mbps)
Communication
OS
Compiler
400MHz
1 × 16
128Mbytes × 16
Fast Ethernet
TCP/IP, MPICH 1.1.2
Linux 2.2.10
gcc (egcs-2.91.61)
Doshisha Univ., Japan
13
Results of 13 Blocks case
Real weak pareto solutions
DGA
DRMOGA
Doshisha Univ., Japan
13
Results of 13 Blocks case (SGA)
Local optimum solutions
Real weak pareto solutions
Doshisha Univ., Japan
Results of 27 Blocks case
27
A
B
DGA
DRMOGA
Doshisha Univ., Japan
27
(f_1, f_2) = (38446, 49920)
A
(f_1, f_2) = (42739, 43264)
B
Doshisha Univ., Japan
Results
• Most of the solutions were weak-pareto solutions.
These problems have little trade-off
relationships between the objective functions.
• SGA, DGA and DRMOGA are applied to the
layout problems
– There are small difference between the results of three
methods.
– When results of DRMOGA compared with those of DGA, there
isn’t big advantage.
– SGA sometimes could not find the real weak pareto solutions.
Doshisha Univ., Japan
Results
f2(x)
Division 1
Division 2
f2(x)
f 1(x)
The individuals can’t be divided into
two division by the value of the focused
objective function(f2(x)).
Can’t exchange individuals enough.
f 1(x)
Doshisha Univ., Japan
Conclusion
• The DRMOGA was applied to discrete problems ;
The block layout problems.
The results of DRMOGA were compared with those of SGA and DGA
– The test problems didn’t have definitely pareto
solutions.
– The searching ability of DGA and DRMOGA were
almost same in numerical examples.
– The mechanism of DRMOGA didn’t work effectively
in these problems.
– SGA may be caught by local minimum.
Doshisha Univ., Japan
~アルゴリズムの流れ~
①
初
期
個
体
生
成
②
個
体
を
各
島
に
分
配
③
終
了
判
定
④
評
価
・
選
択
・
交
叉
⑤
総
個
体
数
を
調
べ
る
⑥
全
体
シ
ェ
ア
リ
ン
グ
⑦
終
了
⑦へ
Doshisha Univ., Japan
Divided Range Multi-Objective GA(2)
f2(x)
f2(x)
f2(x)
・DGA( Island model)
=
+
f1(x)
f1(x)
f1(x)
f2(x)
f2(x)
f2(x)
・DRMOGA
=
+
f1(x)
f1(x)
f1(x)
Doshisha Univ., Japan
Results of 10 Blocks case
(DRMOGA)
A
B
Local optimum set
Real weak pareto set
Doshisha Univ., Japan
A
B
Doshisha Univ., Japan
Results of 10 Blocks case
DGA
SGA
Doshisha Univ., Japan
• Why are the results in this presentation different from the results
in the paper?
– In first, we selected GA parameters with no consideration. But we
investigated more suitable GA parameters, and in this presentation, we
used new GA parameters. That’s why this results Is different from results in
paper.
• What do you aim in this presentation?
– Main purpose in this study is to investigate the effectiveness of DRMOGA
for Block layout problems. To my regret, this problem isn’t suitable for
multi-criterion problems and we can’t get good results.
• How do you think about meaning of this presentation?
– In other discrete problem, the effectiveness of DRMOGA hasn’t been
researched yet. And I think that in the problem that has obviously tradeoff relationships, DRMOGA will get good results. Because in that
problems , the characteristics of DRMOGA can work effectively.
Doshisha Univ., Japan
Multi-objective GA (2)
Squire EMO
•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
Doshisha Univ., Japan
13
(f_1, f_2) = (838544, 14238)
(f_1, f_2) = (879179, 13560)
Doshisha Univ., Japan
Configuration of GA
• Expression of solutions
• Genetic operations
Selection
Crossover
Mutation
Pareto reservation strategy
PMX method
2 bit substitution method
Doshisha Univ., Japan
Calculation Time
Case
13blocks
27blocks
method Calculation time(sec)
SGA
DGA
DRMOGA
SGA
DGA
DRMOGA
1.08E+03
1.73E+01
2.02E+01
1.37E+03
5.28E+01
5.61E+01
Doshisha Univ., Japan
27
Results of 27 Blocks case
SGA
Doshisha Univ., Japan
© Copyright 2024 ExpyDoc
