An improved hybrid optimization algorithm for the quadratic assignment problem

Abstract

In this paper, we present an improved hybrid optimization algorithm, which was applied to the hard combinatorial optimization problem, the quadratic assignment problem (QAP). This is an extended version of the earlier hybrid heuristic approach proposed by the author. The new algorithm is distinguished for the further exploitation of the idea of hybridization of the well‐known efficient heuristic algorithms, namely, simulated annealing (SA) and tabu search (TS). The important feature of our algorithm is the so‐called “cold restart mechanism”, which is used in order to avoid a possible “stagnation” of the search. This strategy resulted in very good solutions obtained during simulations with a number of the QAP instances (test data). These solutions show that the proposed algorithm outperforms both the “pure” SA/TS algorithms and the earlier author's combined SA and TS algorithm. Key words: hybrid optimization, simulated annealing, tabu search, quadratic assignment problem, simulation

Patobulintas hibridinis optimizavimo algoritmas kvadratinio paskirstymo uždaviniui

Santrauka. Šiame straipsnyje pasiūlytas patobulintas hibridinis euristinis optimizavimo algoritmas gerai žinomam, sudėtingam kombinatorinio optimizavimo uždaviniui, būtent, kvadratinio paskirstymo (KP) uždaviniui. Tai pagerinta autoriaus ankstesnio hibridinio algoritmo versija. Naujasis algoritmas pasižymi tuo, jog čia išplėtota efektyvių euristikų (atkaitinimo modeliavimo (AM) (angi. simulated annealing) ir tabu paieškos (TP) (angi. tabu search) “hibridizacijos” ideja. “Hibridizacija” remiasi vadinamąja iteracine schema: TP algoritmas panaudojamas kaip postanalizes procedūra AM algoritmo gautajam sprendiniui, savo ruožtu, AM algoritmas taikomas sprendinių sekai, gautai sprendiniu diversifikavimo/generavimo keliu. Svarbi pasiūlyto algoritmo savybė yra ir ta, kad jame realizuotas vadinamasis “šaltojo pakartotinio starto” principas, kurio paskirtis padėti išvengti galimų paieškos “stagnacijos” situacijų. Naujasis algoritmas išbandytas su KP uždavinio duomenimis iš testinių pavyzdžių bibliotekos QAPLIB. Gauti eksperimentų rezultatai liudija, jog nagrinėtiems KP uždavinio pavyzdžiams siūlomas algoritmas yra pranašesnis už ankstesnius atkaitinimo modeliavimo ir tabu paieškos algoritmus, taip pat už ankstesnį autoriaus hibridinį algoritmą.

First Published Online: 14 Oct 2010

Keyword : hybrid optimization, simulated annealing, tabu search, quadratic assignment problem, simulation