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

Abstract

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 algoritmalar içerisinde KAP'ın çözümü için önerilen en iyi algoritmalar arasında olduğunu göstermektedir