Parallel evolutionary algorithms for quadratic assignment problem
İkinci derece atama problemi için paralel evrimsel algoritmalar
- Tez No: 486795
- Danışmanlar: YRD. DOÇ. DR. KORHAN KARABULUT
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- Dil: İngilizce
- Üniversite: Yaşar Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 125
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- Karesel atama problemi için grafik işlem birimleri üzerinde paralel bir evrimsel algoritma
A parallel evolutionary algorithm for quadratic assignment problem on graphics processing units
ERDENER ÖZÇETİN
Yüksek Lisans
Türkçe
2013
Endüstri ve Endüstri MühendisliğiAnadolu ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. GÜRKAN ÖZTÜRK
- Distributed database design with integer linear programming and evolutionary hybrid algorithms
Sayısal lineer programlama ve buluşsal hibrit algoritmalar ile dagıtık veritabanı tasarımı
UMUT TOSUN
Doktora
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. AHMET COŞAR
- Dizel motorların modellenmesi,modele dayalı hava yolu ve emisyon kontrolörü geliştirilmesi / uygulanması
Modeling of diesel engines, development and application of model based airpath and emission controllers
BÜLENT ÜNVER
Doktora
Türkçe
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
PROF. DR. METİN GÖKAŞAN
PROF. DR. SETA BOGOSYAN
- Parallel evolutionary computation for distribution system planning and operation
Dağıtım şebekesi planlama ve işletmesi için paralel evrimsel algoritmalar
SOHEIL YOUNESI
Yüksek Lisans
İngilizce
2022
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. DR. AYDOĞAN ÖZDEMİR
DR. ÖĞR. ÜYESİ OGUZHAN CEYLAN
- Multi-objective evolutionary algorithms for multi-label classification supported by deep auto-encoder on image and video data
Çok etiketli sınıflama ̇için çok amaçlı evrimsel algoritmaların derin otokodlayıcı desteği ̇ile resim ve video verilerine uygulanması
GİZEM NUR KARAGÖZ
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET HALİT SEYFULLAH OĞUZTÜZÜN
PROF. DR. ADNAN YAZICI