Population-based local search algorithms for cross-domain search
Berna Kiraz1, Fatma Corut Ergin21Department of Computer Engineering, Faculty of Engineering, Fatih Sultan Mehmet Vakif University, İstanbul, Türkiye2Department of Computer Engineering, Faculty of Engineering, Marmara University, İstanbul, Türkiye
Population-based local search is a meta-heuristic algorithm combining the principles of the population-based search and the local search. This study presents an extensive comparison of two population-based local search approaches, specifically, the steady state memetic algorithm (SSMA) and a population-based iterated local search (PILS). To the best of our knowledge, PILS is proposed first for cross-domain search. Both approaches are implemented in Hyper-heuristics Flexible Framework (HyFlex) which contains different operators for different problem domains. The operators used in PILS and SSMA are the ones defined in HyFlex and the operator selection is done using two heuristic selection methods, namely, Simple Random and Reinforcement Learning with Tournament selection. The performance of the proposed methods with the selection methods is assessed over nine problem domains in HyFlex. The results reveal the success of the presented approaches for the cross-domain search.
Keywords: Population-based Local Search, Memetic Algorithms, Hyper-heuristics, Iterated Local Search, Combinatorial OptimizationAlanlar-arası arama için popülasyona dayalı yerel arama algoritmaları
Berna Kiraz1, Fatma Corut Ergin21Fatih Sultan Mehmet Vakıf Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, İstanbul2Marmara Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, İstanbul
Popülasyona dayalı yerel arama, popülasyona dayalı arama ve yerel aramanın ilkelerini birleştiren meta-sezgisel bir algoritmadır. Bu çalışma, iki farklı popülasyona dayalı yerel arama yaklaşımının kapsamlı bir karşılaştırmasını sunmaktadır: kararlı durum memetik algoritma (SSMA) ve popülasyona dayalı iteratif yerel arama (PILS). PILS, bildiğimiz kadarıyla, alanlar arası arama için ilk önerilen yöntemdir. Her iki yaklaşım da farklı problem alanları için farklı operatörler içeren Hyper-heuristics Flexible Framework (HyFlex) üzerinde uygulanmıştır. PILS ve SSMA'da kullanılan operatörler, HyFlex'te tanımlanan operatörlerdir ve bu operatörler arasından seçim yapmak için Basit Rastgele ve Turnuva seçimi ile Pekiştirmeli Öğrenme yöntemleri kullanılmaktadır. Önerilen yöntemlerin her iki seçim yöntemiyle performansı HyFlex' teki dokuz farklı problem üzerinden değerlendirilmiştir. Sonuçlar, alanlar arası arama için sunulan yaklaşımların başarılı olduğunu ortaya koymaktadır.
Anahtar Kelimeler: Popülasyona dayalı yerel arama, Memetik algoritma, Üst-sezgiseller, Yinelemeli Yerel Arama, Kombinatoryal OptimizasyonManuscript Language: English