Page 183 - Biomimetics : Biologically Inspired Technologies
P. 183

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




                    Genetic Algorithms in Optimization Models                                   169

                    5.4.4 Calculating Diversity

                    Genetic diversity can be measured by calculating the distances between population members. The
                    distance between any two members is defined as the number of genes with different values. For
                    example, the distances between the members of the initial population in the post office, for example

                                         1                             0001011
                                         2                             0010110
                                         3                             0101001
                                         4                             0101100
                                         5                             1010010

                    are:
                                                #1     #2     #3    #4     #5

                                         #1     0      4      2      4      4
                                         #2     4      0      6      4      2
                                         #3     2      6      0      2      6
                                         #4     4      4      2      0      6
                                         #5     4      2      6      6      0

                    The total distance is 80. The expected distance between any two different combinations is 60/
                    17   3.53, therefore the expected sum of (20) distances between members of a population of 5 (all
                    different from one another) is 1200/17   70.59. This means that the randomly generated starting
                    population (with a total distance of 80) is more genetically diverse than expected. When the genetic
                    algorithm progresses, distances tend to decrease, therefore genetic diversity (total distance) de-
                    creases as well. The five best combinations in Table 5.2 have a total distance of 56, that means less
                    diversity than average. Note that the lowest possible diversity is 40. A population consisting of the
                    last five combinations in Table 5.2 has a distance of ‘‘2’’ between any two different members, and
                    thus a sum of 40. Since all population members are different from each other, the minimum possible
                    distance between any two different population members is ‘‘2’’ and thus 40 is the lowest possible
                    sum of distances for a population of 5.
                      When higher genetic diversity is maintained, convergence of the population is slowed down and
                    more generations are required. Therefore, the run time of the algorithm increases. It is therefore
                    important to balance both the advantages of achieving greater diversity and the disadvantages of
                    increased run time.


                                  5.5  APPLICATION: BALANCING A TURBINE ENGINE

                    In Chapter 4 of this book, Lipson describes various applications of genetic algorithms mainly in the
                    field of robotics. We describe here an engineering application and demonstrate the effectiveness of
                    genetic algorithms.
                      The turbine balancing problem, suggested by Laporte and Mercure (1988), is a good example of
                    the effectiveness of genetic algorithms. Consider the manufacturing of a turbine engine, such as a
                    hydro turbine or a jet engine, with n blades. The blades are inserted into equally spaced slots. To
                    function properly, the turbine must be balanced. If all blades are identical, the turbine engine is
                    balanced. In reality, there are slight variations in the weights of different blades, therefore, the
                    turbine is not perfectly balanced. Suppose that the weights are designed to be 5 kg each and
                    the variations across blades are in the order of magnitude of milligrams. The problem is to find the
                    ‘‘correct’’ assignment of blades into slots so that the turbine will be as balanced as possible.
                      Let the blades’ deviation from the ideal weight be: d i for i ¼ 1, . .., n. The angles of the slots are:
                    2 i
                    n  for i ¼ 1, ... , n. Let blade p(i)(p denotes a permutation) be installed in slot i. A perfectly
                    balanced turbine will satisfy:
   178   179   180   181   182   183   184   185   186   187   188