Solving the Quadratic Assignment Problem by the Repeated Iterated Tabu Search Method
- PDF / 94,312 Bytes
- 4 Pages / 594 x 792 pts Page_size
- 113 Downloads / 200 Views
SOLVING THE QUADRATIC ASSIGNMENT PROBLEM BY THE REPEATED ITERATED TABU SEARCH METHOD UDC 519.854
P. V. Shylo
Abstract. A new repeated iterated tabu search for the quadratic assignment problem is developed. A comparative study of this algorithm and the best existing algorithms for solving this problem has shown its competitiveness with respect to both its performance and quality of solutions. Keywords: quadratic assignment problem, tabu search, computing experiment, comparative study of algorithms. The quadratic assignment problem (QAP) was first formulated in [1]. It has numerous practical applications connected with the placement of different objects, balancing of turbines, image analysis, etc. [1–7]. The QAP being considered is an NP-hard discrete optimization problem and, moreover, computationally very difficult. Note also that the traveling salesman problem is its particular case. PROBLEM STATEMENT An informal statement of the quadratic assignment problem is as follows. n objects are given that should be placed at n different locations (points of destination). Magnitudes of resource flows a ij between objects i and j , i, j = 1, ¼ , n , and distances brs between locations r and s, r, s = 1, ¼ , n , are known. It is required to distribute objects between locations so that the sum of distances multiplied by the corresponding flows is minimal. Hence, the mathematical statement of QAP can be formulated as follows: find n
n
min f ( p ) = å å a ij bp i p j ,
pÎP n
i =1 j =1
where A = [ a ij ] and B = [ brs ] are square matrices of order n , P n is the set of all permutations of {1, ¼ , n}, and p i specifies the number of the location of an object i . Quadratic assignment problems can be exactly solved only in the case of small dimensions. The test problem from [7] with 36 variables is not exactly solved until now. Hence, the development and investigation of new and improvement of existing approximation algorithms for solving QAP are topical. PROPOSED ALGORITHM The computational complexity of QAP is conditioned by a large amount of computations (of order of O ( n 2 )) necessary for obtaining the value of the objective function and investigating the neighborhood of the current solution. Note that a solution in algorithms for solving QAP is usually represented in the form of some permutation p ÎP n , and its neighborhood N ( p ) includes all permutations obtained by exchanging locations between all pairs of objects. Thus, the neighborhood contains C n2 + 1 permutations, and the amount of computation equal to about O ( n 4 ) is required to obtain V. M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine, [email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 2, March–April, 2017, pp. 163–167. Original article submitted December 22, 2016. 308
1060-0396/17/5302-0308 ©2017 Springer Science+Business Media New York
values of their objective functions. When n ³ 100 , the execution of at least n 2 local search iterations already becomes a difficult computational
Data Loading...
