Author, Institution: Dovilė Verenė, Kaunas University of Technology
Science area, field of science: Natural Sciences, Informatics, N009
Scientific Supervisor: Prof. Dr. Alfonsas Misevičius (Kaunas University of Technology, Natural Sciences, Informatics, N009)
Dissertation Defence Board of Informatics Science Field:
Prof. Habil. Dr. Rimantas Barauskas (Kaunas University of Technology, Natural Sciences, Informatics, N009) – chairperson
Prof. Habil. Dr. Gintautas Dzemyda (Vilnius University, Natural Sciences, Informatics, N009)
Prof. Dr. Vacius Jusas (Kaunas University of Technology, Natural Sciences, Informatics, N009)
Prof. Dr. Olga Kurasova (Vilnius University, Technological Sciences, Informatics Engineering, T007)
Assoc. Prof. Dr. Agnė Paulauskaitė–Tarasevičienė (Kaunas University of Technology, Natural Sciences, Informatics, N009)
The doctoral dissertation is available at the library of Kaunas University of Technology (K. Donelaičio g. 20, Kaunas).
The dissertation defence was held remotely.
Annotation:
In this dissertation, a genetic-hierarchical (GH) algorithm (GHA) and its variants for the solution of the quadratic assignment problem (QAP) are investigated. The main distinguishing aspect of the proposed algorithm is that this is a novel algorithm with the original, hierarchical architecture. In particular, the genetic algorithm is combined with the so-called hierarchical iterated tabu search (HITS) procedure.
The following are the main parts of the GH algorithm: initial population construction; selection of parents for crossover procedure; crossover procedure; local improvement of the offspring; mutation; population replacement; population restart. The HITS algorithm, in turn, consists of the candidate solution acceptance, solution local improvement, and solution perturbation.
The genetic algorithm operates with high-quality population. To ensure the outstanding quality of the population, the initial population is constructed by using the HITS algorithm with an increased number of improving iterations. To eliminate the stagnation of genetic process, the population restarts are employed.
The GH algorithm is computationally tested on various QAP benchmark instances from the online library QAPLIB. In particular, different crossover and mutation procedures, as well as various configurations of GHA were examined. The results of the experiments demonstrate the promising performance of GHA. It is also seen that the GH algorithm appears to be superior to other heuristic algorithms.
