A great deluge and tabu search hybrid with two-stage memory support for quadratic assignment problem

• DOI: 10.1016/j.asoc.2015.06.061
• Publication Date: 2015-07-29T18:14:09Z
• Authors: Adnan Acan; Ahmet Ünveren
• Keywords: Benchmark (surveying); Combinatorial search; Guided Local Search

Graphical abstractDisplay Omitted HighlightsA hybrid method combining great deluge and tabu search algorithms is proposed.This hybrid is supported with a two-stage external memory.First stage of acts as a short term memory that is frequently updated.Second stage acts as a long term memory that is updated less frequently.Elements of the second stage are maximally dissimilar in variable space. A two-stage memory architecture is maintained within the framework of great deluge algorithm for the solution of single-objective quadratic assignment problem. Search operators exploiting the accumulated experience in memory are also implemented to direct the search towards more promising regions of the solution space. The level-based acceptance criterion of the great deluge algorithm is applied for each best solution extracted in a particular iteration. The use of short- and long-term memory-based search supported by effective move operators resulted in a powerful combinatorial optimization algorithm. A successful variant of tabu search is employed as the local search method that is only applied over a few randomly selected memory elements when the second stage memory is updated. The success of the presented approach is illustrated using sets of well-known benchmark problems and evaluated in comparison to well-known combinatorial optimization algorithms. Experimental evaluations clearly demonstrate that the presented approach is a competitive and powerful alternative for solving quadratic assignment problems.