The Learner Imperialist Competitive Approach to Solve the Quadratic Assignment Problem

The Quadratic Assignment is a NP-Complete problem, and deterministic algorithms can only solve smaller instances of the problem (at most in size of 21). Thus, developing of Meta heuristic approaches for the problem is worth considering. In this paper, two algorithms have been proposed. The first method is a kind of ICA algorithm and the second one is a hybrid approach which is based on the ICA as well as Object Migration Learning Automaton. Generally, in basic ICA, weaker countries (solutions) are assimilated into stronger solutions as time goes by; therefore, the algorithm may be stuck in local optimum solutions. However, the global optimums can be obtained by exploring the search space; indeed, the learning automaton used in the proposed hybrid method has this responsibility. A number of instances of the standard library of QAPLIB have been used to evaluate performance of the algorithms; in fact, most of these samples are real engineering problems. Experimental results indicate that the newly developed hybrid method is capable of generating highly suitable solutions which a large majority of them are optimal or near optimal; consequently, this algorithm is an effective way to solve the QAP problem.