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 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 112
  • Publication Date: 2017
  • Doi Number: 10.1016/j.cie.2016.10.022
  • Title of Journal : COMPUTERS & INDUSTRIAL ENGINEERING
  • 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

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.