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

2017-10-01
Arin, Arif
Rabadi, Ghaith
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.

Citation Formats
A. Arin and G. Rabadi, “Integrating estimation of distribution algorithms versus Q-learning into Meta-RaPS for solving the 0-1 multidimensional knapsack problem,” COMPUTERS & INDUSTRIAL ENGINEERING, vol. 112, pp. 706–720, 2017, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/65817.