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

• A 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.

Figure optionsDownload as PowerPoint slide