Page 175 - Biomimetics : Biologically Inspired Technologies

Bar-Cohen : Biomimetics: Biologically Inspired Technologies DK3163_c005 Final Proof page 161 6.9.2005 12:11pm

Genetic Algorithms in Optimization Models 161

early convergence to a homogeneous population increases the probability that a necessary trait (for
the global optimum) will disappear from the population and the algorithm will terminate in a local
optimum rather than in the global one.
One simple way to retain greater genetic diversity is not to add to the population an offspring
that is identical to an existing population member. Even though it is rare to get two identical
combinations, if it happens and the two identical population members are selected as parents, they
will generate an identical offspring and before long all population members will be identical to this
member. If it is the best population member, it may be at the bottom of a ‘‘shallow’’ crater. If it is
not the best population member, the population may evolve into one with many identical members
and only a few better ones. The probability of generating better members under such circumstances
is significantly reduced, and the population may become stagnant.
The modifications listed below attempt to improve some aspects of the genetic algorithm. All
are rooted in biological or evolutionary processes:

1. The existence of different populations with movements between them (Parallel Genetic Algorithms
[PGA], Cantu-Paz, 1998).
2. Improving the creation of the starting population (compounded genetic, Drezner, 2005a).
3. Improving the newly generated offspring by using a local search such as a descent algorithm or tabu
search. The combination of a local search with a genetic algorithm is called a hybrid genetic
algorithm or a memetic algorithm (Moscato, 2002).
4. The introduction of mutations that affect the newly generated offspring (Spears, 2000).
5. Invasions of ‘‘foreign’’ combinations that affect the population (Goldberg, 1989).
6. Improving parent selection procedures by assigning two genders to population members (Drezner
and Drezner, 2005) or distance-based selection (Drezner and Marcoulides, 2003).
7. Improving the selection criteria for the removal of population members (Drezner, 2005b).
These modifications are discussed in detail below.

5.3.1 Parallel Genetic Algorithms

PGA allow for parallel populations of the same species with movements between them. They are
especially suited for parallel computing. Parallel GAs are easy to implement and they have great
potential for substantial improvement in search performance. For a review of PGA, see Cantu-Paz
(1998) and Cantu-Paz and Goldberg (2000).
Multiple-population GAs are more sophisticated, as they consist of several subpopulations
which occasionally are allowed to exchange individuals (movement). This exchange of individuals
is controlled by several parameters (Cantu-Paz, 1999):

. Movement rate determines how many individuals leave a population.
. Movement frequency (movement interval) determines how often a move occurs.
. Movement topology determines the destination of the move.
. Movement policy determines which individuals move (and are added) and which are replaced at the
receiving population.
Multiple-population PGA are known by different names. Sometimes they are known as ‘‘dis-
tributed’’ GAs, because they are usually implemented in distributed-memory Multiple Instruction
or Multiple Data (MIMD) computers. Since the computation to communication ratio can be
relatively high, they are occasionally called coarse-grained GAs.

5.3.2 Compounded Genetic Algorithms

The compounded genetic algorithm (Drezner, 2005a) is similar to the PGA. The difference is that in
the compounded genetic algorithm there is no movement between the isolated populations. Genetic