Adaptive operator selection with reinforcement learning

Durgut R., Aydin M. E., Atli I.

Information Sciences, cilt.581, ss.773-790, 2021 (SCI-Expanded, Scopus) identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 581
  • Basım Tarihi: 2021
  • Doi Numarası: 10.1016/j.ins.2021.10.025
  • Dergi Adı: Information Sciences
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Aerospace Database, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Communication Abstracts, Computer & Applied Sciences, INSPEC, Library, Information Science & Technology Abstracts (LISTA), Metadex, MLA - Modern Language Association Database, zbMATH, Civil Engineering Abstracts
  • Sayfa Sayıları: ss.773-790
  • Anahtar Kelimeler: Adaptive operator selection, Artificial bee colony, Clustering-based Q-learning, Q-learning, Reinforcement learning
  • İstanbul Ticaret Üniversitesi Adresli: Hayır

Özet

Operator selection plays a crucial role in the efficiency of heuristic-based problem solving algorithms, especially, when a pool of operators is used to let algorithms dynamically select operators to produce new candidate solutions. A sequence of selected operators forms up throughout the search which impacts the success of the algorithms. Successive operators in a bespoke sequence can be complementary and therefore diversify the search while randomly selected operators are not expected to behave in this way. State of art adaptive selection schemes have been proposed to select the best next operator without considering the problem state in the process. In this study, a reinforcement learning algorithm is proposed to embed in a standard artificial bee colony algorithm for taking the problem state on board in operator selection process. The proposed approach implies mapping the problem states to the best fitting operators in the pool so as to achieve higher diversity and shape up an optimum operator sequence throughout the search process. The experimental study successfully demonstrates that the proposed idea works towards higher efficiency. The state of art approaches are outperformed with respect to the quality of solution in solving Set Union Knapsack problem over 30 benchmarking instances.