Page 184 - Biomimetics : Biologically Inspired Technologies
P. 184
Bar-Cohen : Biomimetics: Biologically Inspired Technologies DK3163_c005 Final Proof page 170 6.9.2005 12:11pm
170 Biomimetics: Biologically Inspired Technologies
X 2 i
n
d p(i) cos ¼ 0
n
i¼1
X 2 i
n
d p(i) sin ¼ 0
n
i¼1
Since it may be impossible to achieve a perfect balance, the objective is to minimize the length of
the resultant vector, whose square is:
! 2 ! 2
X 2 i X 2 i
n
n
d p(i) cos þ d p(i) sin (5:4)
n n
i¼1 i¼1
by selecting the best permutation p(i).
Expression (5.4) can be simplified as follows:
! !
n
X 2 i 2 X 2 i 2 XX 2 i 2 j 2 i 2 j
n
n
n
d p(i) cos þ d p(i) sin ¼ d p(i) d p(j) cos cos þ sin sin
n n n n n n
i¼1 i¼1 i¼1 j¼1
XX 2 (i j)
n
n
¼ d p(i) d p(j) cos
n
i¼1 j¼1
X X X 2 (i j)
n
n 1
n
2
¼ d þ2 d p(i) d p(j) cos
i
i¼1 i¼1 j¼iþ1 n
P
n
2
Since d is constant, the objective is to minimize
i
i¼1
X X 2 (i j)
n
n
d p(i) d p( j) cos (5:5)
n
i¼1 j6¼i¼1
The turbine engine example is a symmetric quadratic assignment problem (QAP). The QAP was
first proposed by Koopmans and Beckmann (1957) and is well researched (Burkard, 1990; Taillard,
1991, 1995; Burkard et al., 1997; Cela, 1998; Rendl, 2002). The general QAP formulation is as
follows. Given two n n matrices (a ij ) and (b ij ), find a permutation p(i) which minimizes:
X X
n
n
a p(i)p( j) b ij
i¼1 j¼1
A symmetric problem fulfills a ij ¼ a ji and b ij ¼ b ji . In our turbine balancing problem a ij ¼ d i d j
2 (i j)
except a ii ¼ 0; and b ij ¼ cos except b ii ¼ 0.
n
There are many applications for the QAP. For example, planning the layout of an office
complex. There are n planned offices and n employees to be assigned to them. The interaction
between any two employees (a ij ) and the physical distance between any two offices (b ij ) are known.
The problem is to assign employees to offices such that those who interact extensively are as close
as possible to each other. The objective is to find the best assignment of employees to offices so that
the sum of the products of the interactions and the distances is minimized. A variant of this setting is
incorporating the probability that a customer of this complex needs to visit two or more offices to
complete the service. The objective in this case is to minimize the total distance to the customer.