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
   177   178   179   180   181   182   183   184   185   186   187