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

Date

2017-10-01

Author

Arin, Arif
Rabadi, Ghaith

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

214
views

0
downloads

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.

Subject Keywords

General Engineering, General Computer Science

URI

https://hdl.handle.net/11511/65817

Journal

COMPUTERS & INDUSTRIAL ENGINEERING

DOI

https://doi.org/10.1016/j.cie.2016.10.022

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

A robust bi-objective mathematical model for disaster rescue units allocation and scheduling with learning effect Tirkolaee, Erfan Babaee; Aydin, Nadi Serhan; Ranjbar-Bourani, Mehdi; Weber, Gerhard Wilhelm (Elsevier BV, 2020-11-01) This paper proposes a novel bi-objective mixed-integer linear programming (MILP) model for allocating and scheduling disaster rescue units considering the learning effect. When a natural phenomenon (e.g., earthquake or flood) occurs, the presented decision support model is expected to help decision-makers of emergency relief centers to provide efficient planning for rescue units to minimize the total weighted completion time of rescue operations, as well as the total delay in rescue operations. The problem ...
A unifying grid approach for solving potential flows applicable to structured and unstructured grid configurations Cete, A. Ruhsen; Yuekselen, M. Adil; Kaynak, Uenver (Elsevier BV, 2008-01-01) In this study, an efficient numerical method is proposed for unifying the structured and unstructured grid approaches for solving the potential flows. The new method, named as the "alternating cell directions implicit - ACDI", solves for the structured and unstructured grid configurations equally well. The new method in effect applies a line implicit method similar to the Line Gauss Seidel scheme for complex unstructured grids including mixed type quadrilateral and triangle cells. To this end, designated al...
A Content-Boosted Collaborative Filtering Approach for Movie Recommendation Based on Local and Global Similarity and Missing Data Prediction Özbal, Gozde; Karaman, Hilal; Alpaslan, Ferda Nur (Oxford University Press (OUP), 2011-09-01) Most traditional recommender systems lack accuracy in the case where data used in the recommendation process is sparse. This study addresses the sparsity problem and aims to get rid of it by means of a content-boosted collaborative filtering approach applied to a web-based movie recommendation system. The main motivation is to investigate whether further success can be obtained by combining 'local and global user similarity' and 'effective missing data prediction' approaches, which were previously introduce...
AN INTERACTIVE APPROACH FOR A DUAL CONSTRAINT JOB SHOP SCHEDULING PROBLEM KONDAKCI, S; GUPTA, RM (Elsevier BV, 1991-01-01) Until recently, heuristic dispatching rules were the only practical means to solve the job shop scheduling problem. Currently, a promising direction in job shop scheduling is interactive scheduling. In this study an interactive scheduling approach is developed for a dual-constraint dynamic job shop production environment. The approach is used by a number of subjects in an experiment. The performance of the subjects is compared with that of dispatching rules based on tardiness and other measures relevant...
Parallel Scalable PDE Constrained Optimization Antenna Identification in Hyperthermia Cancer Treatment Planning SCHENK, Olaf; Manguoğlu, Murat; CHRİSTEN, Matthias; SATHE, Madan (Springer Science and Business Media LLC, 2009-01-01) We present a PDE-constrained optimization algorithm which is designed for parallel scalability on distributed-memory architectures with thousands of cores. The method is based on a line-search interior-point algorithm for large-scale continuous optimization, it is matrix-free in that it does not require the factorization of derivative matrices. Instead, it uses a new parallel and robust iterative linear solver on distributed-memory architectures. We will show almost linear parallel scalability results for t...

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, pp. 706–720, 2017, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/65817.