Page 182 - Biomimetics : Biologically Inspired Technologies
P. 182
Bar-Cohen : Biomimetics: Biologically Inspired Technologies DK3163_c005 Final Proof page 168 6.9.2005 12:11pm
168 Biomimetics: Biologically Inspired Technologies
5. The process continues until the number of generations reaches a prespecified limit. Note that once
the optimal solution is a member of the population, it can never be removed from it, because no
offspring can be ‘‘superior.’’ So, the optimal combination (now #4 in the population) will stay in the
population until we stop the evolution process and will be the best population member and thus the
solution.
6. Observe the evolutionary process. The fittest survives and the quality of population members
improves throughout the generations. There is no guarantee that the optimal solution will be
detected, but experience shows that the evolutionary process is very efficient and results in very
good solutions.
5.4.2 Illustrating the Steepest Descent Algorithm
A steepest descent approach is a search procedure that checks all ‘‘nearby’’ solutions in the
neighborhood. We define the neighborhood as the set of all combinations for which one ‘‘1’’ is
moved to another variable with a ‘‘0’’ value (thus retaining three ‘‘1’’s in the combination). Every
combination has 12 neighbors. Suppose that the offspring is 0101010 with an objective function of
41.14 (see Table 5.2). The neighbors of 0101010 along with their objective function values are
listed in Table 5.3. For example, combination 1001010 was obtained by moving the ‘‘1’’ from
second place to first place.
The best neighbor is 1101000 with an objective function of 33.35. Since 33.35 is lower than
41.14 (the original value of the objective function), the change is accepted. The steepest descent
continues until there is no improved combination in the neighborhood. Such a steepest descent
algorithm may or may not find the optimal solution.
5.4.3 Illustrating a Mutation
Suppose that the offspring 0101010 is selected for a mutation. A mutation is moving one ‘‘1’’ to
another place to replace a ‘‘0.’’ It is equivalent to selecting one of the 12 neighboring members (see
Table 5.3) as the mutated offspring. The mutation may or may not improve the value of the
objective function. On occasion, the value of the objective function deteriorates. Reviewing
Table 5.3, one finds that 5 out of 12 possible mutations improve the offspring (i.e., have an
objective function value lower than 41.14) while 7 of the 12 possible mutations are harmful.
Therefore, randomly performing a mutation on 0101010, there is a 5/12 ¼ 41.7% probability
that the offspring is improved. Some researchers suggest that only improving mutations should be
accepted, while the majority has the opinion that every mutation should be accepted, as is the case
in nature.
Table 5.3 The Neighbors of 0101010
Combination Objective
1001010 39.39
0011010 43.79
0001110 46.07
0001011 46.07
1100010 32.73
0110010 46.83
0100110 47.41
0100011 35.80
1101000 33.35
0111000 41.95
0101100 44.90
0101001 39.11