Population-based Local Search Algorithms for Cross-domain Search

Abstract

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.

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.