A hybrid genetic algorithm for the Quadratic Assignment Problem
M. Vázquez, L. Darrell Whitley · 2000
A heuristic technique that combines a genetic algorithm with a Tabu Search algorithm is applied to the Quadratic Assignment Problem (QAP). The hybrid algorithm improves the results obtained through the application of each of these algorithms separately. The QAP is a NP-hard problem and instances of size n> 15 are still considered intractable. The results of our experiments suggest that CHC combined with TS (CHC+TS), and a TS with elitist backtracking algorithm are able to obtain good near optimal solutions within 0.75 % of the best-known solutions. CHC+TS produces the best-known solution in 12 of the 16 QAPLIB problems tested, where n ranges from 10 to 256. 1