Page 185 - Biomimetics : Biologically Inspired Technologies

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

Genetic Algorithms in Optimization Models 171

Many pairs of offices will have zero interaction whereas others may have a negative interaction
(such as in planning a military base, top secret intelligence offices should be as far as possible from
the cafeteria or other frequently visited offices). Planning a keyboard of 26 letters (Burkard and
Offermann, 1977) is a QAP. The interactions are the probabilities of typing a letter following
another letter, and the distances are the distances between the letter-keys on the keyboard. Different
languages require different key configurations (even for the same letters). Planning an airplane
dashboard (Drezner, 1980) requires consideration of the frequency that a pilot uses an instrument in
conjunction with another instrument as the interaction factor. The wiring problem of an electronic
board or the construction of a computer chip are additional examples of QAPs, where the wiring
distance between components that send signals to one another has to be minimized (Steinberg,
1961). For a discussion of QAP applications, see Cela (1998).
The QAP is considered one of the most complicated combinatorial optimization problems.
Algorithms that guarantee finding the optimal solution are very inefficient. Only recently have
problems of up to n ¼ 36 facilities (blades in our example) been optimally solved. Anstreicher et al.
(2002) solved a problem with n ¼ 30 facilities using multiple computers requiring a total computer
time of over 6 years. The number of permutations (ignoring identical solutions due to symmetry) is
n!. For n ¼ 20, evaluating all of the permutations will take over 77,000 years if every permutation
is evaluated in a millionth of a second. Therefore, a large body of research focuses on heuristic
algorithms. There are several proposed genetic algorithms for the solution of the QAP (Fleurent and
Ferland, 1994; Tate and Smith, 1995; Ahuja et al., 2000; Drezner, 2003, 2005b).
The best available hybrid genetic algorithms for the solution of QAP problems are Drezner
(2003, 2005c). The merging procedure of the parents is the same in both algorithms. It is referred to
as the cohesive merging procedure (Drezner, 2003). The algorithms differ in the improvement
algorithm applied to the offspring before it is considered for inclusion in the population. For
complete details, see Drezner (2005b).

5.5.1 A Turbine Balancing Example

We randomly generated a turbine-balancing problem with 20 blades. For simplicity, we multiply
the cosine values by 10,000 and round them off to the nearest integer. The data are given in Table
5.4. We add the sum of the squares of the d i to the objective function. Because of rounding-off,
errors introduced by rounding the cosine values, the best found solution is negative ( 1,550).

Table 5.4 Parameters of the Turbine Blade Problem
i cos 2pi 10,000
d i
n
1 4 9,511
2 3 8,090
3 0 5,878
4 2 3,090
5 5 0
6 2 3,090
7 5 5,878
8 3 8,090
9 6 9,511
10 6 10,000
11 8 9,511
12 6 8,090
13 5 5,878
14 1 3,090
15 2 0
16 8 3,090
17 10 5,878
18 1 8,090
19 8 9,511
20 9 10,000