Transgenetic Algorithms for the Multi-objective Quadratic Assignment Problem
Carolina Paula de Almeida, Richard A. Gonçalves, Elizabeth Ferreira Gouvêa Goldbarg, Marco C. Goldbarg, Myriam Delgado · 2014
The multi-objective Quadratic Assignment Problem (mQAP) is a hard optimization problem with many real-world applications, such as in hospital layouts. The main purposes of this paper are: (1) the investigation of hybrid algorithms combining Transgenetic Algorithms and Evolutionary Multi-objective Optimization (EMO) frameworks to deal with mQAP and (2) to compare the ability of EMO algorithms based on Pareto dominance with those based on decomposition to deal with the mQAP. Transgenetic Algorithms (TAs) are evolutionary algorithms based on cooperation as the main evolutionary strategy. Two hybrid algorithms are proposed to deal with the mQAP: NSTA (TA + NSGA-II) and MOTA/D (TA + MOEA/D). To analyze the performance of the proposed algorithms, non-parametric statistical tests and multi-objective quality indicators are used. The proposed algorithms are compared with NSGA-II and MOEA/D in 126 instances of the mQAP. The results demonstrate the superiority of decomposition and transgenetic based algorithms, particularly in MOTA/D.