Abstract
Lexisearch and genetic algorithms are two different types of methods for solving combinatorial optimization problems. Lexisearch algorithm gives us exact optimal solution, whereas, genetic algorithms give heuristic solution to a problem. In this paper, a hybrid algorithm (LSGA) that combines lexisearch and genetic algorithms is developed to obtain heuristic solution to the quadratic assignment problem. The proposed algorithm uses lexisearch algorithm to generate initial population, self-adaptively three crossover operators, and randomly one of four mutation operators, restricted combined mutation operator as local search, and multi-parent sequential constructive crossover as immigration method. The self-adaptive crossover operator that consists of one-point crossover, swap path crossover and sequential constructive crossover can produce better solutions. Also, the random selection of a mutation operator effectively prevents LSGA from being stuck in local optimal zone. Further, the immigration method with combined mutation effectively generated very good chromosomes, which promotes the convergence rate and accuracy of the solution. Experimental results on four categories of benchmark QAPLIB instances show the effectiveness of the LSGA. Out of 35 instances 18 instances have been solved optimally, and for the remaining instances, solutions are very close to the optima. Finally, a comparative study has been carried out between LSGA and unified particle swarm optimization (UPSO) for the same instances. In terms of solution quality, LSGA outperformed UPSO for all category of instances. Also, in terms of computational time, except for seven instances, LSGA outperformed UPSO.