GENETIC ALGORITHM WITH INVASIONS FOR THE QUADRATIC ASSIGNMENT PROBLEM

In this paper, we propose an improved genetic algorithm with invasions for solving one of the hard combinatorial optimization problems, the quadratic assignment problem (QAP). Invasions are used to achieve high degree of diversity within populations and increase the robustness of the genetic process. This, in turn, allows to withstand the premature convergence and stagnation (stalled evolution). In addition, very compact populations are enabled which allow saving both the computational time and memory resources. The algorithm was examined on the QAP instances taken from the publicly available electronic library of the QAP instances - QAPLIB. The obtained results demonstrate that our new modification of the genetic algorithm is superior to other types of genetic algorithms.