Hybrid Algorithm for Solving the Quadratic Assignment Problem

Abstract

This article is devoted to solving the quadratic assignment problem using a hybrid algorithm contains both genetic and evolutionary algorithms. The quadratic assignment problem is one of the fundamental problems of combinatorial optimization in the field of mathematical optimization, belonging to the category of object placement problem. The article provides a simple statement of this problem and its more detailed mathematical model. Since the quadratic assignment problem is NP-hard and even small input data can take large computational costs for an accurate algorithm, it is reasonable to use a hybrid heuristic approach to solve this problem. The article describes in detail the construction of a hybrid algorithm, the sequence of its steps, and the flowchart. Further, the article provides a graphical interface with the ability to adjust various parameters of the algorithm, allowing it to be optimally configured. The last part of the article covers a comparative analysis of the effectiveness of the resulting algorithm: comparing the accuracy of the developed hybrid algorithm with a new method of invasive weed optimization algorithm, comparing it with the best-known solutions for modern benchmarks. It was found that the hybrid algorithm shows a strong advantage in accuracy over the invasive weed optimization algorithm. Also, the hybrid algorithm was able to find a solution equal to the best known for the tai12a problem. For the tai15a problem, the algorithm showed a deviation of 0.2% from the best-known solution. For the rest of the considered benchmarks, the algorithm showed a deviation from the best solutions of no more than 4.2%, which proves the high efficiency of the created algorithm in comparison with the world's best solutions. In addition, this algorithm has a high economic value due to the wide application of the solution to the problem in practice, for example, in placement of factories or enterprises in places or in placement of associated electronic components on printed circuit boards or integrated circuits, etc.

Keywords

• quadratic assignment problem
• hybrid algorithm
• genetic algorithm
• genetic search method
• heuristic approach
• evolutionary algorithm
• invasive weed optimization algorithm