Karesel atama problemi için yeni bir özuyarlamalı paralel güçlü tabu-arama algoritması

Tansel DÖKEROĞLU

Makale detayları

Karesel atama problemi için yeni bir özuyarlamalı paralel güçlü tabu-arama algoritması

Yazarlar:

Tansel DÖKEROĞLU

Yayıncı:

Pamukkale University

Ana Başlıklar:

Uygulamalı fizik

Dergi:

Pamukkale University Journal of Engineering Sciences 2017 Vol.23 Issue 5, pp.559-565

Belge Tipi:

Makale

Yayın Tarihi:

10/2017

Belge Dili:

Türkçe

Document ID (Org No.):

2000576717

Sıklık:

İki Aylık

eISSN:

2147-5881

pISSN:

1300-7009

Özet:

 


With
this study, we propose a novel parallel robust tabu-search algorithm
(Parallel-Tabu-QAP) for the NP-Hard Quadratic Assignment Problem (QAP)of whose
instances having large number of location and facilites have not been reported
to be solved exactly so far. Parallel-Tabu-QAP algorithm that has two phases
optimizes the parameters of tabu-search algorithm in its first phase by using
genetic algorithms through generations. The individuals that have parameters of
the tabu-search are optimized in a population that is located on a master
processor. In the second phase, slave processors optimize the solution of the
problem by restarting their search process in case of stagnations. With its
stagnation prevention and parallel optimization talents, parallel-tabu-QAP
algorithm is observed to obtain better results than its sequential and
statically parameter-tuned counterparts. The algorithm has 0.05% deviation for
the benchmark tests performed on more than 100 problem instances. These
experimental results show that the parallel-tabu-QAP algoritm is one the best
performing techniques in its heuristics algorithms class when compared with
state-of-the-art QAP algorithms.

.

 


Bu
çalışma ile Karesel Atama Problemi (KAP) olarak bilinen ve çok sayıda konum ve
tesis içeren örnekler için en iyi çözümleri hala bulunamamış olan NP-zor bir
kombinatoriyal problem için yeni bir paralel sezgisel algoritma önerilmektedir
(paralel-tabu-KAP algoritması). İki safhası bulunan paralel-tabu-KAP
algoritması, genetik algoritma safhasında efendi işlemcide bulunan popülasyon
üzerinde sezgisel tabu-arama algoritmasının parametrelerini jenerasyonlar ile
eniyilerken, tabu-arama safhasında işçi işlemciler üzerinde verilen problemin
sonucunu farklı başlangıç noktaları ile eniyilemektedir. Yerel takılmaları, aramaya
başka noktalardan yeniden başlayarak engelleme özelliğine sahip olan
paralel-tabu-KAP algoritması, tek işlemci ile çalışan ve parametreleri statik
olarak önceden tanımlanmış olan versiyonlarına göre daha iyi sonuçlar elde
etmektedir. Yüzün üzerindeki bençmark problem ile yapılan deneyler
sonucunda,  ortalama %0.05’lik bir sapma elde
edilmiştir. Bu sonuçlar, paralel-tabu-KAP algoritmasının kendi sınıfındaki
sezgisel algoritmalar içerisinde KAP’ın çözümü için önerilen en iyi
algoritmalar arasında olduğunu göstermektedir.

.

Makale detayları

Karesel atama problemi için yeni bir özuyarlamalı paralel güçlü tabu-arama algoritması

Yazarlar: Tansel DÖKEROĞLU

Yayıncı: Pamukkale University

Ana Başlıklar: Uygulamalı fizik

Dergi: Pamukkale University Journal of Engineering Sciences 2017 Vol.23 Issue 5, pp.559-565

Belge Tipi: Makale

Yayın Tarihi: 10/2017

Belge Dili: Türkçe

Document ID (Org No.): 2000576717

Sıklık: İki Aylık

eISSN: 2147-5881

pISSN: 1300-7009

Sayı

Yazarlar:

Tansel DÖKEROĞLU

Yayıncı:

Pamukkale University

Ana Başlıklar:

Uygulamalı fizik

Dergi:

Pamukkale University Journal of Engineering Sciences 2017 Vol.23 Issue 5, pp.559-565

Belge Tipi:

Makale

Yayın Tarihi:

10/2017

Belge Dili:

Türkçe

Document ID (Org No.):

2000576717

Sıklık:

İki Aylık

eISSN:

2147-5881

pISSN:

1300-7009