|written 5 months ago by||• modified 5 months ago|
|written 5 months ago by|
Parallelizing Genetic Algorithms:
GAS is naturally suited to parallel implementation and a number of approaches to parallelization has been explored.
Coarse grain approaches to parallelization subdivide the population into somewhat distinct groups of individuals, called demes.
Each deme is assigned to a different computational node and a standard GA search is performed at each node. Communication and cross-fertilization between demes occur less frequently than within demes.
Transfer between demes occur through migration, in which individuals from one deme are copied or transferred to other demes.
This process is modeled after the kind of cross-fertilization that might arise between physically separated subpopulations of biological species.
One benefit of such approaches is that it reduces the crowding problem often encountered in nonparallel GAS, in which the system falls into a local optimum due to the early appearance of a genotype that comes to dominate the entire population.
In contrast to coarse-grained parallel implementations of GAS, fine-grained implementations typically assign one processor per individual in the population.
Recombination then takes place among neighboring individuals. Several different types of neighborhoods have been proposed, ranging from planar grids to torus.