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: