Geri Dön

Parallel evolutionary algorithms for quadratic assignment problem

İkinci derece atama problemi için paralel evrimsel algoritmalar

  1. Tez No: 486795
  2. Yazar: ALPER KIZIL
  3. Danışmanlar: YRD. DOÇ. DR. KORHAN KARABULUT
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2017
  8. Dil: İngilizce
  9. Üniversite: Yaşar Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    Türkçe

    2013

    Endüstri ve Endüstri MühendisliğiAnadolu Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. GÜRKAN ÖZTÜRK

  2. 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

    İngilizce

    2013

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. AHMET COŞAR

  3. 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

    Türkçe

    2013

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Kontrol ve Otomasyon Mühendisliği Ana Bilim Dalı

    PROF. DR. METİN GÖKAŞAN

    PROF. DR. SETA BOGOSYAN

  4. 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

    İngilizce

    2022

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektrik Mühendisliği Ana Bilim Dalı

    PROF. DR. AYDOĞAN ÖZDEMİR

    DR. ÖĞR. ÜYESİ OGUZHAN CEYLAN

  5. 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

    İngilizce

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. MEHMET HALİT SEYFULLAH OĞUZTÜZÜN

    PROF. DR. ADNAN YAZICI