Transcript 20001002-hiroyasu

A New Model of Parallel
Distributed Genetic Algorithms
for Cluster Systems: Dual
Individual DGAs
Tomoyuki HIROYASU
Mitsunori MIKI
Masahiro HAMASAKI
Yusuke TANIMURA
Doshisha University
Kyoto, Japan
Aim of this study
Optimization methods
 Finding the best routings of the network
 Designing structures
 Constructing systems
New model of DGAs
Genetic Algorithms
 Island model (DGAs)
 Master Slave
 Cellular
Dual Individual DGAs
(DGAs)
 Easy to divide into
tasks in several ways
 High searching ability
Dual Individual DGAs (DuDGAs)
DuDGA
There are two individuals in
each island
High searching ability
The high validity of the solutions
because there are numbers of islands.
Easiness to set up
Crossover rate=1.0
Mutation rate= 0.5
Parallerization of DuDGAs
Selection
Crossover
Island
Mutation
Evaluation
In DuDGA, an island is moved by migraion.
Test functions and used parameters
DuDGA and DGAs (4, 8, 12, 24 islands)
are applied to each test function.
F1=200bit Rastrigin
F2=50bit Rosenbrock
F3=100bit Griewank
F4=100bit Ridge
Number of
islands
Population size
120 4,8,12,24
Migration rate
0.5
Migration interval
240
0.3
5
Crossover rate
1.0
Mutation rate
1/L
Terminal condition
After 5000 generation
Test Functions
Rastrigin
n
fRast rigin = 10n +  x2i – 10cos 2xi
i=1
n
fGriewank = 1 + 
Griewank
i=1
N
Ridge
Rosenbrok
n
x2i
–
cos
4000 
i=1
x
i=1
j=1
n
j
fRosenbrok =  100 x
i=2
i
2
N
fRidge = 
xi
2
i– 1
– xi
2
+ xi – 1
2
Cluster system for calculation
Spec. of Cluster (16 nodes)
Processor
Clock
# Processors
Main memory
Network
(100Mbps)
Communication
OS
Compiler
PentiumⅡ(Deschutes)
400MHz
1 × 16
128Mbytes × 16
Fast Ethernet
TCP/IP, MPICH 1.1.2
Linux 2.2.10
gcc (egcs-2.91.61)
Searching ability (covering rate)
Covering rate( it is the success rate of finding the
optimum of each problem in 20 trials.)
1.0
4
8
12
24
DuDGA
0.5
F1
F2
F3
DuDGA has high searching ability.
F4
Distribution and parallel effects of DuDGAs
Speed Up Rate
25
20
15
10
5
1
5
10
15
The number of processors
Speed up rate is the relation between the calculation time of one processor
model and that of multi processor model.
Therefore, this rate has the factor of the model distribution effects and the
parallel effects of DuDGAs