Precision Push Algorithm For The Quadratic Assignment Problem

Quadratic assignment problem is one of the most famous problems in combination and optimization. It synthesizes a large group of typical characteristics of the problem in combination and optimization and also exists in a wide application field, including hospital layout, backboard wiring and keyboard layout. QAP belong to the NP-Hard problems, which can't be solved in polynomial time. With the enlargement of the scale of problem instances, the solution space makes the characteristic of exploding up, is unlike solved with general methods. Therefore, research on heuristics for the quadratic assignment problem (QAP) has become the hotline of computer science for a long time.For complicated NP-Hard problem, if the same heuristic algorithm is applied to different QAP problem instances, its performance may exist great differences, so it is extremely important for designing algorithm and solving problem to know the differences from a theory point. The analysis of fitness landscape developed in recent years is an effective method for studying the structure of problem instances and the essence of difficulty optimization. It can be used to design algorithm and improve the optimal performance through analyzing the structure of fitness landscape of QAP. Furthermore, most heuristics are based on local search, which views a solution as a point in the fitness landscape, and searches for better solutions in the neighborhood of the current solution. Therefore, the ruggedness coefficient of the fitness landscape is essential for performance of heuristics.In this paper, we generated a series of new instances with different numeric precisions for a given QAP instance, by conducting transformation of the flow matrix. Ruggedness coefficients of the fitness landscapes for those new instances gradually decline along with the decrease of numeric precision. Since the difference is minor between instances with adjacent numeric precisions, and it is easier to obtain high quality solutions for instances with low numeric precisions, therefore instances with high numeric precisions can be guided by solutions of instances with low numeric precisions. Due to such property, a meta-heuristic called precision push algorithm (PPA) is then proposed in this paper. The PPA attempts to decrease the hardness of a QAP instance in such a way, that we transform searching process of the original instance into iterative processes for a series of new instances with precisions from low to high. Extensively wide experimental results showed that the PPA achieved better performance than RTS, GH, SA, HAS-QAP and AntSimulated algorithms in terms of solution quality.