An improved genetic algorithm using adaptive mutation operator for the quadratic assignment problem

摘要

The quadratic assignment problem (QAP) is a NP-hard combinatorial optimization problem. Genetic algorithm (GA) is one of the best algorithms to deal with such difficult problems. This paper presents an improved GA for finding effective solution to the QAP. As starting with a good initial population leads faster convergence of GA, we use sequential sampling algorithm for generating initial population. In GA, crossover operator plays very important role and sequential constructive crossover (SCX) is found to be one of the best crossover operators for solving the QAP. We propose a restricted improvement of the SCX using a combined mutation operator. Also, an adaptive mutation operator is proposed to diversify the search space intelligently. Experimental results on some benchmark QAPLIB instances show the effectiveness of the improved algorithm.