PARALLEL GENETIC ALGORITHM AND SIMULATED ANNEALING FOR QUADRATIC ASSIGNMENT PROBLEM

Abstract

Optimization Techniques seek to minimize or maximize a real function by systematically choosing the values of real variables from within an allowed set. It is broad field of study comprising of a variety of methods like linear programming, newton raphson etc to heuristic approaches ranging from the simplest nearest neighbor approach to modern evolutionary algorithms like Genetic Algorithms, Particle Swarm Optimization, Ant Colony Optimization, and Bees Algorithm etc. These techniques are applied to problems of both continuous and discrete domains. Our work focuses on Genetic Algorithm and Simulated Annealing technique for combinatorial problems of discrete nature. These algorithms are tested on several instances of Quadratic Assignment Problem (QAP). This problem is NP-hard and even small instances may require long computation time. For this reason, we propose the parallel versions for these algorithms. Parallelization is achieved using message passing techniques of MPI library. The implementation of proposed algorithms and all its pre-requisites are coded using C programming language. Speedups obtained by the parallel versions of these algorithms have been studied. Results show that Genetic Algorithm performs better than Simulated Annealing in parallel scenarios.