Parallel evolutionary algorithms for quadratic assignment problem

Abstract

Karesel Atama Problemi (KAP) en zor birleşimsel problemlerden birisidir. Literatürde KAP'ni çözmek için birçok yaklaşım önerilmiştir. Genetik algoritmalar doğadan ilham alan, makul bir zaman aralığında iyi sayılabilecek çözümler üreten metasezgisellerdir. Ancak geniş boyutlu problemler için yetersiz kalabilirler. Bunun sebebi bu algoritmaların üzerinde çalıştığı arama uzayının çok genişlemesi ve algoritmanın bu arama uzayının belirli bölümlerini gözden kaçırabilmesidir. Bu tez çalışmasında, ada modeli olarak tanımlanan bir modeli standart sıralı genetik algoritmayı çözüm kalitesi yönünden geliştirmek için kullanılmıştır. Sonuçlar, önerilen algoritmanın, en temel 2-adalı model ile dahi, KAP örneklerinde 3 kat daha iyi çözüm bulabildiğimi göstermiştir. Önerilen algoritma test edilmiş ve bazı parametrelerine ince ayar yapılarak çözüm kalitesi daha da arttırılmıştır. Ayrıca değişik parametrelerin sonuç kalitesine etkileri gözlemlenmiştir.Sonuçta, önerilen algoritma yeterince iyi konfigürasyonlarla KAP örneklerini literatürdeki en iyi çözümlere %3 yakınlıkta çözebilme düzeyine çıkabilmiştir.

Quadratic Assignment Problem (QAP) is one of the most difficult combinatorial problems. There are many approaches proposed in literature to solve QAP. Genetic algorithms are nature inspired metaheuristics which can create good enough solutions in reasonable time. But for large size problems, they may be insufficient. This is due to search space they operate becomes too large and algorithm starts to miss out some parts. In this thesis, island model genetic algorithms are used to enhance a standard sequential genetic algorithm in terms of solution quality. Results show that, even with the most basic 2 island model, the proposed algorithm is able to obtain 3 times better results when solving QAP instances. The proposed algorithm is tested and fine-tuned for some of the parameters to enhance the algorithm even further. It is also observed that, different parameters effect solution quality. Ultimately, the proposed algorithm is able to come up with good enough configurations that can solve QAP instances up to 3% gap compared to the best-known solutions in the literature.