Testing of Hybrid Genetic Algorithms for Structured Quadratic Assignment Problems

Article type: Research Article

Authors: Misevičius, Alfonsas | Rubliauskas, Dalius

Affiliations: Department of Multimedia Engineering, Kaunas University of Technology, Studentų 50-400a/416a, LT-51368 Kaunas, Lithuania, e-mail: alfonsas.misevicius@ktu.lt | Department of Multimedia Engineering, Kaunas University of Technology, Studentų 50-401, LT-51368 Kaunas, Lithuania, e-mail: dalius@soften.ktu.lt

Abstract: In this paper, an efficient hybrid genetic algorithm (HGA) and its variants for the well-known combinatorial optimization problem, the quadratic assignment problem (QAP) are discussed. In particular, we tested our algorithms on a special type of QAPs, the structured quadratic assignment problems. The results from the computational experiments on this class of problems demonstrate that HGAs allow to achieve near-optimal and (pseudo-)optimal solutions at very reasonable computation times. The obtained results also confirm that the hybrid genetic algorithms are among the most suitable heuristic approaches for this type of QAPs.

Keywords: combinatorial optimization, quadratic assignment problem, heuristics, meta-heuristics, hybrid genetic algorithms

Journal: Informatica, vol. 20, no. 2, pp. 255-272, 2009