Integrating estimation of distribution algorithms versus Q-learning into Meta-RaPS for solving the 0-1 multidimensional knapsack problem

Arin A., Rabadi G.

COMPUTERS & INDUSTRIAL ENGINEERING, cilt.112, ss.706-720, 2017 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 112
  • Basım Tarihi: 2017
  • Doi Numarası: 10.1016/j.cie.2016.10.022
  • Dergi Adı: COMPUTERS & INDUSTRIAL ENGINEERING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.706-720
  • Anahtar Kelimeler: Machine learning, Estimation of distribution algorithms, Q-learning, Meta-RaPS, 0-1 multidimensional knapsack problem, PARTICLE SWARM OPTIMIZATION, MACHINE SCHEDULING PROBLEM, ANT COLONY OPTIMIZATION, MULTIOBJECTIVE ESTIMATION, TABU SEARCH, EVOLUTIONARY ALGORITHM, EFFECTIVE HEURISTICS, GENETIC ALGORITHMS, LOCAL SEARCH, DESIGN
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

Finding near-optimal solutions in an acceptable amount of time is a challenge when developing sophisticated approximate approaches. A powerful answer to this challenge might be reached by incorporating intelligence into metaheuristics. We propose integrating two methods into Meta-RaPS (Metaheuristic for Randomized Priority Search), which is currently classified as a memoryless metaheuristic. The first method is the Estimation of Distribution Algorithms (EDA), and the second is utilizing a machine learning algorithm known as Q-Learning. To evaluate their performance, the proposed algorithms are tested on the 0-1 Multidimensional Knapsack Problem (MKP). Meta-RaPS EDA appears to perform better than Meta-RaPS Q-Learning. However, both showed promising results compared to other approaches presented in the literature for the 0-1 MKP. (C) 2016 Elsevier Ltd. All rights reserved.