A parallel evolutionary algorithm for quadratic assignment problem on graphics processing units

In this study, quadratic assignment problem, which is a hard combinatorial optimization problem, is examined to solve by a new approach. To reach the optimal results by using mathematical programming approaches cannot be possible even for some sorts of small and middle scaled problems in a reasonable time interval. Huge amounts of data are being progressed simultaneously by graphics processing units located on computers? graphics card. Therefore, a parallel evolutionary algorithm has been proposed to solve the quadratic assignment problem by using graphics processing units? simultaneously progressing property. This parallel algorithm and the sequential one on central processing units are tested and compared for 59 problems in literature. Best known solutions are obtained for 43 of these problems. Indeed, it is observed that the parallel algorithm works averagely 17 times and up to 51 times faster than sequentially one.Key Words: Quadratic assignment problem (QAP), evolutionary algorithms, parallel programming, graphics processing units (GPU), CUDA.