A Self-adaptive Nature-Inspired Procedure for Solving the Quadratic Assignment Problem
The quadratic assignment problem has been traditionally introduced as a mathematical model related to economic activities, modeling many real-world problems from making optimal arrangement of machines in factories to finding the best location of departments within plants. The biological systems consist of self-adaptive mechanisms, and such self-adaptivity can inspire computer scientists to use the same mechanism in their algorithms. In this paper, a self-adaptive search procedure is presented for solving the quadratic assignment problem, exploring the structure of the problem through regular interchanges of facilities made by a linear assignment technique. The relationship between different aspects of the quadratic assignment problem and the proposed self-adaptive mechanism is mainly related to the intelligence needed to change the location of facilities based on the feedback received from the system. In the employed local search procedure, whenever the number of suggested interchanges is high, some facilities are enforced not to participate in swaps. A key point with making such enforcement is that the employed linear assignment uses all previous information and prevents recalculation. By using a simple mathematical concept in linear programming, the length of the cycles in an interchange is adaptively decreased until the cycle consists of only two facilities. The result of computational experiments on the benchmark instances indicates that the procedure performs in the level of current state-of-the-art procedures.