Parallel hybrid genetic algorithms for solving Q3AP on computational Grids
Résumé
This paper deals with the resolution of the Quadratic 3-dimensional Assignment Problem hereafter referred to as Q3AP. Q3AP is an extension of the well-known Quadratic Assignment Problem (QAP) and of the Axial 3-Assignment Problem (A3AP). It finds its application amongst others in Hybrid Automatic Repeat reQuest (HARQ) error-control mechanism used in wireless communication systems. This problem is computationally NP-hard. As far as we know, the largest Q3AP instance size solved to optimality is 13 whereas practical Q3AP instance size can be of 8, 16, 32 or 64. Sequential exact methods such branch-and-bound or sequential metaheuristics are therefore not suited to solve large size instances for the excessive needed computation time. In this paper, we propose parallel hybrid genetic-based metaheuristics for solving the Q3AP. The parallelism in our methods is of two hierarchical levels. The first level is an insular model where a fixed number of genetic algorithms (GA) evolve independently on separate islands and periodically exchange genetic material. The second level is a parallel transformation of individuals in each GA. Implementation has been done using ParadisEO framework, and the experiments have been performed on GRID5000, the French nation-wide computational grid. The experimental results produced by our method were confronted with those reported in the literature. The optimum or the best so far known solutions have been reached in a reasonable computation time.