Solution:

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.