A comparative analysis of memory using and memory less algorithms for Quadratic Assignment Problem

Several real life problem in areas like parallel computing, distributed computing, facilities location, and combinatorial data analysis can be modeled as Quadratic Assignment Problem (QAP). It belongs to the N-P Hard class of problems. Large instances of these problems cannot be solved with exact method in reasonable amount of time. Approximation methods and soft computing approaches are therefore applied to obtain the optimal solution to these problems in polynomial time. Meta-heuristics being approximation methods are used to find the solution to the instances of these problems in reasonable time. In this paper, we have presented a comparative study of meta-heuristic algorithms: Genetic Algorithm, Simulated Annealing, Local Search, Evolution Strategy, Tabu Search and Variable Neighborhood Search to solve the dre110 instance of the Quadratic Assignment Problem. We have analyzed the results in terms of the execution time and the solution quality obtained. The results show that Variable Neighbor hood Search has the best solution quality but high execution time while Local Search is a close competitor with a sub-optimal solution in reasonable time in comparison to other meta-heuristic algorithms to solve the QAP.