Solving Quadratic Assignment Problems With An Improved Genetic Algorithm

A lot of applications, for instance, the facilities layout problem and the design of backboard wiring, are belonged to the quadratic assignment problem. For the large size quadratic assignment problems, it is infeasible to get the optimal values using the exact algorithms. So applying the heauristic algorithms to get the optimal or suboptimal values is an important research area. For the quadratic assignment problem, the genetic algorithm is one of the promising ones. However, its defect of premature convergence influences its computational results. Considering above, we research the facilities layout problem of a Guangdong Shoes-Manufacturing Plant, propose and apply a new genetic algorithm to the facilities layout module of the design system for the production lines optimization.After descriptions of the two models and applications of the quadratic assignment problem, the thesis gives an overview of algorithms for the quadratic assignment problmen in recent years. Then some typical exact algorithms and approximate algorithms are introduced in details, including dynamic programming, branch and bound, cutting plane method, tabu search, ant system, and genetic algorithm. Next the genetic algorithm, focusing on the chariteristics, priciples and implementation, is analysed systemly. Finally, a new improved genetic algorithm based on a new selection mechanism, called kindered-protected genetic algorithm, is proprosed with its concrete implemetion given. After these, the computational results running on QABLIB cases by the kindred-protected genetic algorithm are compared with other recent literatures. And the kindred-protected genetic algorithm is applied to develop the facilities layout module of the design system for the production lines optimization.It is easily known that the kindred-protected genetic algorithm shows its promising performace on cases of the quadratic assignment problem. Meanwhile, the application of the kindred-protected genetic algorithm in the facilities layout module impove the production efficiency and reduce the production cost.