摘要:In this paper,a 2-level iterated tabu search (ITS) algorithm for the solution of the quadratic assignment problem (QAP) is considered.The novelty of the proposed ITS algorithm is that the solution mutation procedures are incorporated within the algorithm,which enable to diversify the search process and eliminate the search stagnation,thus increasing the algorithm’s efficiency.In the computational experiments,the algorithm is examined with various implemented variants of the mutation procedures using the QAP test (sample) instances from the library of the QAP instances – QAPLIB.The results of these experiments demonstrate how the different mutation procedures affect and possibly improve the overall performance of the ITS algorithm.
其他摘要:Šiame straipsnyje nagrinėjamas vadinamasis dviejų lygių iteracinis tabu paieškos (ITP) algoritmas kvadratinio paskirstymo (KP) uždaviniui.Algoritmo naujumas yra tas,jog į jį yra integruotos sprendinių mutavimo procedūros,kurių esminė paskirtis yra diversifikuoti paieškos procesą,išvengiant paieškos stagnacijos ir taip padidinant jos efektyvumą.Algoritmo veikimas išbandytas su įvairių tipų mutavimo procedūrų realizavimo variantais.Atlikti kompiuteriniai eksperimentai su KP uždavinio testavimo duomenų pavyzdžiais iš standartinių pavyzdžių bibliotekos QAPLIB.Pateikti eksperimentų rezultatai,kurie iliustruoja,kaip skirtingos prigimties mutavimo procedūros,esančios ITP sudėtyje,gali įvairiai paveikti algoritmo efektyvumą.