Geri Dön

A stagnation aware cooperative breakout local search algorithm for the quadratic assignment problem on a multi-core architecture

Çok çekirdekli bir mimari üzerinde karesel atama problemi için iş birliği yapan durgunluk bilinçli yerel arama kaçış algoritması

PDF İndir

  1. Tez No: 442122
  2. Yazar: YAĞMUR AKSAN
  3. Danışmanlar: PROF. DR. AHMET COŞAR
  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: Karesel Atama Problemi, BLS-OpenMP-QAP, BLS, OpenMP, En iyileme, Quadratic Assignment Problem, BLS-OpenMP-QAP, BLS, OpenMP, Optimization
  7. Yıl: 2016
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Ü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ı: 103

Özet

Karesel Atama Problemi (KAP) çeşitli gerçek hayat uygulamalaryla birlikte en zorlu çözümü polinom zamanl olmayan (NP) kombinatoriyal en iyileme problemlerinden biridir. Yerleşim tasarım, zaman planlamas ve havaalanndaki uçaklara kaplarn atanmas KAP'n ilgi çekici uygulamalarndan bazlardr. Bu tezde, KAP problem örneklerinin daha önce aranan permütasyonlarnn benzerlik kontrolü için uyarlanm³ Levenshtein uzaklk ölçüsünü kullanarak yeni bir yerel arama sezgiseli olan yerel arama kaç³ (BLS) algoritmasnn yeteklerini geliştirdik. Buna ek olarak, önerilen algoritma, BLS-OpenMP-QAP(Karesel Atama Problemi için Açk Çoklu-³leme ile Yerel Arama Kaç³ Algoritmas), OpenMP proglama yaklaşmn kullanan güncel çok çekirdekli mimarilerin eş zamanlı hesaplama yaklaşım kullanr. KAP'n en iyi çözümü için durgunluk bilinçli arama çeşitli yörüngeleriyle birtakım çekirdekler üzerinde daha önce tesvi pit edilen yerel en iyinin benzerliği göz önüne alınarak eş zamanlı olarak çalıştırılır. Arama alanının keşfi başlangıç noktalarn akllca seçerek ve i³lemcilerin/i³ parçacıklarnın says kadar uygunluk de§erlendirmelerini hzlandrarak geliştirilir. BLS-OpenMp-QAP algoritmas KAP kütüphanesi setindeki 59 problem örne§i üzerinde çalıştrıldı ve sonuçlar örneklerden 57 tanesini tam olarak çözebildi §ini gösterdi. Algoritma için ortalamada toplam sapma 0.019% olarak elde edildi, böylece literatürdeki en iyi algoritmalar arasnda oldu§u bildirilebilir.

Özet (Çeviri)

The quadratic assignment problem (QAP) is one of the most challenging NPHard combinatorial optimization problems with its several real life applications. Layout design, scheduling, and assigning gates to planes at an airport are some of the interesting applications of the QAP. In this thesis, we improve the talents of a recent local search heuristic Breakout Local Search Algorithm (BLS) by using adapted Levenshtein Distance metric for similarity checking of the previously explored permutations of the QAP problem instances. In addition to this, the proposed algorithm, BLS-OpenMP-QAP (Breakout Local Search Algorithm with Open Multi-Processing for Quadratic Assignment Problem), makes use of the parallel computation paradigm of the contemporary multi-core architectures using OpenMP programming paradigm. The stagnation-aware search for the (near-)optimal solution of the QAP is executed concurrently on several cores with diversied trajectories while considering the similarity of the already dev tected local optima. The exploration of the search space is improved by selecting the starting points intelligently and speeding-up the tness evaluations as many as the number of the processors/threads. The BLS-OpenMP-QAP algorithm is executed on 59 problem instances of the QAP library benchmark and the results shows that it is able to solve 57 of the instances exactly. The overall deviation for the algorithm is obtained as 0.019% on the average; therefore, it can be reported to be among the best algorithms in the literature.

Benzer Tezler

  1. Tez No

    769967

    Karma frekanslı zaman serilerinin modellenmesi: Büyük veri örneği

    Modeling of mixed frequency time series: Big data example

    GÖZDE BOZKURT

    Doktora

    Türkçe

    Türkçe

    2022

    EkonometriMarmara Üniversitesi

    Ekonometri Ana Bilim Dalı

    PROF. DR. ŞEVKET IŞIL AKGÜL

  2. Tez No

    366664

    Marriage and divorce in early twentieth century Ottoman society: The Law of Family Rights of 1917

    Erken yirminci yüzyıl Osmanlı toplumunda evlilik ve boşanma: 1917 Aile Hukuku Kararnamesi

    NİHAN ALTINBAŞ

    Doktora

    İngilizce

    İngilizce

    2014

    Hukukİhsan Doğramacı Bilkent Üniversitesi

    Tarih Ana Bilim Dalı

    YRD. DOÇ. MEHMET AKİF KİREÇCİ

  3. Tez No

    871837

    Değer-inanç-norm teorisi bağlamında bencillik değerleri ile sürdürülebilir davranışlar arasındaki ilişki

    The relationship between selfishness values and sustainable behavior in the context of value-belief-norm theory

    NAZİME EBRU ÖZKUL ARIKAN

    Doktora

    Türkçe

    Türkçe

    2024

    İşletmeHacettepe Üniversitesi

    İşletme Ana Bilim Dalı

    PROF. DR. PINAR BAŞGÖZE

  4. Tez No

    2202

    Endüstri etkisinde bir kentsel sistemin dinamik büyüme modeli

    Dynamic growth model of an urban system under the in fluence of industrial growth

    GÜLDEN ERKUT

    Doktora

    Türkçe

    Türkçe

    1986

    Şehircilik ve Bölge Planlamaİstanbul Teknik Üniversitesi

    PROF. DR. ORHAN GÖÇER

  5. Tez No

    648522

    Manet için öncelik farkındalıklı yeni bir yönlendirme protokolü

    A new routing protocol with priority awareness for manet

    ÖZGÜR ÖZKAYA

    Yüksek Lisans

    Türkçe

    Türkçe

    2020

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYalova Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ABDULKADİR TEPECİK

Geri Dön