Page 173 - Biomimetics : Biologically Inspired Technologies

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

Genetic Algorithms in Optimization Models 159

newly elected combination (i.e., evaluating all combinations in the new neighborhood, etc.). The
algorithm terminates when there is no better combination in the neighborhood.
2. Tabu search (Glover, 1986; Glover and Laguna, 1997) is based on artificial intelligence. The search
starts as a steepest descent algorithm but continues after the steepest descent algorithm has been
terminated. Unlike the steepest descent, tabu search may take upward moves in the hope that a
sequence of upward moves will lead to a better downward move and eventually to a better solution.
The direction of the search is determined by the recent history of moves that are ‘‘memorized.’’
Once a move is performed, the reverse move (i.e., moving back to the previous combination) is
forbidden for some iterations (hence the name tabu which can also be spelled taboo), thus pushing
the search away from previous combinations. Imagine a search on a plane with many craters. One
of these craters is the deepest one, and that one is the desired solution (the global optimum). The
steepest descent performs only downward moves and may land at a shallow crater (a local optimum)
and not at the global one. Tabu search attempts to get out of a shallow crater in the hope of getting
into a better one. Therefore, when the steepest descent algorithm terminates at a bottom of a crater,
upward moves are taken in tabu search while sliding back into the same crater is disallowed with the
hope of sliding into deeper craters and eventually reaching the global optimum.
3. Simulated annealing (Kirkpatrick et al., 1983) simulates the annealing of metals from a very hot
liquid phase to a cool solid phase. Borrowing the metaphor of the plane full of craters, simulated
annealing is like a ‘‘bouncing’’ rubber ball which we hope will settle at the deepest crater because
it is more difficult to get out of it. The cooling of the temperature means that the ‘‘height’’ of the
bounce diminishes as the process continues.
4. The ant colonies metaheuristic (Colorni et al., 1992; Dorigo and Gambardella, 1997; Gambardella
et al., 1999) is based on the behavior of ants when they find a food source (the optimal solution).
Ants return to their nest discharging pheromone. Other ants follow the pheromone and eventually
form a line leading to the food source. The premise of the algorithm is that more pheromone will be
discharged on the way to the food source than on the way to other points in the plane.
5. Genetic algorithms (Holland, 1975; Goldberg, 1989; Reeves, 1993) simulate evolution and survival
of the fittest (attributed to Charles Darwin even though Alfred Russell Wallace discovered it first).
A population (made of individual combinations) evolves over time (generations). Pairs of popula-
tion members (combinations) mate and produce an offspring (two combinations are merged to
produce a new combination — details below). Good offspring are kept in the population whereas
unfit population members are discarded (the survival of the fittest). The population evolves, and at
the end of the process, the population usually consists of fairly good solutions (without a guarantee
that the optimal solution is found). Details of genetic algorithms follow.

5.2 THE FRAMEWORK OF GENETIC ALGORITHMS

In nature, while two dandelions or two squirrels may look the same to us, no two individuals of any
species are identical (including human identical twins, Segal, 2000); some are larger, some healthier,
some faster, some more aggressive in behavior, and the number of traits that distinguish individuals is
seemingly limitless. In any environment, some traits are naturally selected, making an individual
more fit, thus able to live longer and produce viable offspring. The fittest individuals will thus produce
more offspring than the less fit, and thus certain traits are naturally selected in any population over
time. A well-known example is that of the peppered moth in England during the industrial revolution.
This moth is light colored with black spots (hence its name), and rests on lichen-covered trees of the
same coloring. Birds prey upon the moth, therefore good camouflage is critical for survival as those
individuals that stand out are quickly spotted and eaten. With theindustrial revolution and the burning
of coal, the trees became dark in color from the release of pollutants into the air. Those moths that
were slightly darker in color, survived more successfully than the slightly lighter colored individuals.
Thus in this case, ‘‘fitness’’ was related to the ability of an individual to blend with the environment,
that is coloring (among other traits). The darker colored moths had higher survival rates and
lived longer, and as a result produced more offspring. Thus the next generation was, on average,
relatively darker in color. After several generations, most of the peppered moths were dark in the