Page 176 - Biomimetics : Biologically Inspired Technologies

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

162 Biomimetics: Biologically Inspired Technologies

algorithms are applied in two phases, generating the starting population for phase 2 by repeating
genetic algorithms in phase 1. This mimics evolving parallel populations at several isolated
locations. The best species in each location are moved to a common location thus creating a
‘‘high quality’’ starting population. Suppose that a population of P members is applied in phase 2.
Genetic algorithms are run K times in phase 1 using K randomly generated starting populations (it is
convenient but not necessary to have integer P/K). The population size of the phase 1 genetic
algorithm should be at least P/K. The best P/K population members of each run are compiled to
construct the starting population for phase 2. Phase 2 genetic algorithm is run once. It is recom-
mended that a ‘‘quick’’ genetic algorithm is used for phase 1 and an ‘‘effective’’ and possibly
‘‘slow’’ genetic algorithm is used for phase 2.
For example, if a population of P ¼ 100 members is required for phase 2, phase 1 is run K ¼ 20
times (each with a population of at least five members), the best P/K ¼ 5 population members are
selected from each run and compiled to create a starting population for phase 2.
Note that the best solution found in phase 1 by any of the runs can only be improved by the
compounded genetic algorithm because the best solution found during phase 1 is a member of the
starting population of phase 2 and can only be removed from the population by better solutions.

5.3.3 Hybrid Genetic Algorithms

Hybrid genetic algorithms (also referred to as memetic algorithms, Moscato, 2002) employ an
improvement algorithm on the newly established offspring before considering it for inclusion in the
population. This is analogous to training the offspring to improve its fitness just like training dogs to
follow orders or teaching pupils in order to enhance their knowledge. One may apply a steepest
descent or a tabu search procedure on every offspring before considering it for inclusion in the
population. Even a simple approach may ‘‘correct’’ a few traits in the offspring and provide an
improved solution. The hybrid modification tends to accelerate the convergence of the population
because offspring tend to be more similar to one another.
Since such an improvement algorithm can be time consuming, one has to balance the benefit of
employing an improvement algorithm against the time required to do it.

5.3.4 Mutations

Mutations in the formation of offspring occur quite frequently in nature. Most mutations are not
beneficial to the species and can, in fact, be rather harmful. However, on rare occasions, a mutation
is beneficial to the species and improves the offspring. It can be argued that evolution could not
have succeeded without mutations. Mutations may create new beneficial traits that did not exist
before. If a trait is beneficial to the species, the offspring will be ‘‘more fit,’’ will be more likely to
produce better offspring, and will stay in the population longer.
The common way to apply mutations (Spears, 2000) is to occasionally (e.g., 10% of the time, a
parameter of the approach) introduce, by randomly selecting, a new gene in the newly created
offspring (by changing its value).

5.3.5 Invasions

Throughout the history of mankind, invasion of foreign tribes has been quite common, that is ‘‘the
Barbarian invasions.’’ Such invasions increase the gene pool of the local tribe and may lead to a
more advanced population. Following this phenomenon some researchers (Goldberg, 1989) suggest
that occasionally, new randomly generated combinations are added to the population, replacing
below average population members, mimicking an invasion. This ‘‘new blood’’ may generate better
and improved offspring and may introduce new traits that are not found in the population (the local
tribe). Such invasions tend to enhance the genetic diversity of the population with the positive