A variable neighbourhood search enhanced estimation of distribution algorithm for quadratic assignment problems
- PDF / 960,089 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 93 Downloads / 154 Views
A variable neighbourhood search enhanced estimation of distribution algorithm for quadratic assignment problems T. G. Pradeepmon1,2 · Vinay V. Panicker1 · R. Sridharan1 Accepted: 13 August 2020 © Operational Research Society of India 2020
Abstract Quadratic Assignment Problem (QAP) is one of the most complex combinatorial optimization problems. Many real-world problems such as printed circuit board design, facility location problems, assigning gates to airplanes can be modelled as QAP. Problems of size greater than 35 is not able to solve optimally using conventional optimization methods. This warrants the use of evolutionary optimization methods for obtaining optimal or near optimal solutions for QAPs. This work proposes a hybridization on a univariate Estimation of Distribution Algorithm, namely the Population Based Incremental Learning Algorithm (PBILA), with Variable Neighbourhood Search (VNS) for solving QAPs. The proposed algorithm is employed to solve benchmark instances of QAP and the results are reported. The results of this work reveals that PBILA on its own is not efficient for solving the QAPs. However, when hybridised with VNS, the algorithm performs well providing best known solutions for 95 test instances out of the 101 instances considered. For most of the test instances, the percentage deviation is less than one percentage. The overall average percentage deviation of the obtained solutions from the best-known solutions is 0.037%, which is a significant improvement when compared with stateof-the-art algorithms. Keywords Quadratic assignment problem · Estimation of distribution algorithms · Variable neighbourhood search
* Vinay V. Panicker [email protected] 1
Department of Mechanical Engineering, National Institute of Technology Calicut, Kozhikode, Kerala, India
2
Department of Mechanical Engineering, Muthoot Institute of Technology and Science, Ernakulam, Kerala, India
13
Vol.:(0123456789)
OPSEARCH
1 Introduction The Quadratic Assignment Problem (QAP) was introduced by Koopmans and Beckmann [61] as a model for the allocation of indivisible resources. Since then, the QAP has been used for modelling applications such as backboard wiring [91], economic problems [55], facility locations [44], turbine balancing [85], placement of electronic components [40], scheduling [78], typewriter keyboard and control panel design [58], university examination scheduling [4], hospital planning [56] and many more. In spite of the extensive research on this problem, QAP still remains as one of the hardest combinatorial optimization problems and is well known for its diverse applications [8, 38, 45]. Garey and Johnson [47] proved that QAP is NP-Hard and thus, there is no polynomial time algorithm that can solve the problem. QAP instances of size larger than 35 are considered to be very large and cannot be solved in reasonable computational time [8]. QAP is also proven to be very difficult to obtain an approximate solution for large instances with guaranteed performance [52]. The exact QAP solution algor
Data Loading...
