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.
   179   180   181   182   183   184   185   186   187   188   189