PowerPoint プレゼンテーション

A New Model of Distributed
Genetic Algorithm for Cluster
Systems: Dual Individual DGA
Tomoyuki HIROYASU
Mitsunori MIKI
Masahiro HAMASAKI
Yusuke TANIMURA
Doshisha University
Kyoto, Japan
Cluster,Hyper Cluster, GRID
Tasks
Job
A job of application should
be divided into some tasks
in several ways.
GRID
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
Distributed Genetic Algorithms (DGAs)
Simple GA
DGAs
Selection
Crossover
Mutation
Evaluation
In DGAs, the total population is
divided into sub populations.
Migration
In each sub population, a simple GA is performed.
Individuals are exchanged by migration.
Related work
There are several studies concerned with DGAs.
It is reported that DGAs have high searching ability.
“A survey of parallel distributed genetic algorithms”
E.Alba and J.M. Troya
“A survey of parallel genetic algorithms”
E.Cantu-Paz
“A Searching Ability of DGAs”
M. Miki, T. Hiroyasu, M. Kaneko and K. Hatanaka
The mechanism of DGAs
Simple GA
Solutions
are
converged
DGA
The solutions are converged in each island.
An Operation of migration keeps the diversity of the solutions
in a total population.
An optimal solution can be derived with smaller number of
total population size.
High searching ability
There are are several islands.
Can be divided into small tasks
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
Operations of DuDGAs
Selection
There are 4 individuals after the crossover (two parents and
two children).
One of the parents and one of the children are selected with
respect to their fitness values.
Migration
Migrated Individual is chosen randomly.
Migrated individual is copied and moved to the other islnads.
 The existed individual that has smaller fitness value is over
wrote by the migrated individual.
Overwrite
Copy
Parallerization of DGAs
Selection
Crossover
Mutation
Migration
Evaluation
Usually, each processor has one island.
By operation of migration, some individuals are moved.
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
fRastrigi n = 10n +  x2i – 10cos 2xi
n
i=1
fGriewank = 1 + 
n
Griewank
i=1
fR idge = 
x
N
Ridge
Rosenbrok
n
x2i
–  cos
4000 i = 1
j=1
j
fRosenbrok =  100 x
n
i=2
i
2
N
i=1
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
Number of function calls
140000
4
8
12
24
DuDGA
70000
0
F1
F2
F3
F4
DuDGA can find an optimum solution with small
number of function calls
Searching Transition
Evaluation Value
300
200bit Rastrigin
8 islands
250
24 islands
DuDGA
（120)
200
150
100
50
0
100
Generations
200
In the beginning of the searching, searching ability
of the DuDGA is low.
Transition of hamming distance
200bit Rastrigin
Hamming Distance
between the elite and
average individuals
120
8islands
100
24islands
DuDGA
（120)
diversity
80
60
40
20
0
200
400
600
Generations
800
1000
DuDGA can keep the diversity of the solutions
Searching mechanism of DuDGAs
Beginning of search
In this model, the individuals that are not good can
survive.
End of search
Because there are only two individuals in each island, the
solutions are converged quickly in the end of search.
This mechanism keeps the diversity of the solutions.
In the beginning, DuDGA is searching in global area and searching in
the local area in the end of the search.
Distributed effects of DuDGAs
2500
2000
Calculation time [s]
2 processors
1500
4 processors
1000
500
0
1 2
4
8
Num be r of pr oce s s ors
Total population size is constant.
16
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
Conclusions
Dual Individual Distributed Genetic
Algorithms (DuDGAs)
High searching ability
Some parameters needless to be set
There are many islands
DuDGAs can be divided into several tasks in many ways
DuDGAs will be applied to GRID
systems (may be CCGrid 2000).
Difficult problem for DuDGAs
• Goldberg problem
011
0
010
22
110
0
111
30
000
28
100
14
001
26
101
0
Fitness values
f(000)
f(001)
f(010)
f(100)
f(110)
f(101)
f(011)
f(111)
=
=
=
=
=
=
=
=
28
26
22
14
0
0
0
30

Download Report