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, vol.112, pp.706-720, 2017 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 112
  • Publication Date: 2017
  • Doi Number: 10.1016/j.cie.2016.10.022
  • Journal Name: COMPUTERS & INDUSTRIAL ENGINEERING
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.706-720
  • Keywords: 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
  • Middle East Technical University Affiliated: Yes

Abstract

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.