Efficient genetic algorithms using simple genes exchange local search policy for the quadratic assignment problem

In this paper, we describe an approach for solving the quadratic assignment problem (QAP) that is based on genetic algorithms (GA). It will be shown t hat a standard canonical GA (SGA), which involves genetic operators of sele ction, reproduction, crossover, and mutation, tends to fall short of the de sired performance expected of a search algorithm. The performance deteriora tes significantly as the size of the problem increases. To address this syn drome, it is common for GA-based techniques to be embedded with determinist ic local search procedures. It is proposed that the local search should inv olve simple procedure of genome reordering that should not be too complex. More importantly, from a computational point of view, the local search shou ld not carry with it the full cost of evaluating a chromosome after each mo ve in the localized landscape. Results of simulation on several difficult Q AP benchmarks showed the effectiveness of our approaches.