A Memetic Algorithm with a Novel Repair Heuristic for the Multiple-Choice Multidimensional Knapsack Problem

Jaeyoung Yang, Yong-Hyuk Kim and Yourim Yoon
Additional contact information
Jaeyoung Yang: Samsung Electronics, 129 Samsung-ro, Yeongtong-gu, Suwon-si 16677, Korea
Yong-Hyuk Kim: School of Software, Kwangwoon University, 20 Kwangwoon-ro, Nowon-gu, Seoul 01897, Korea
Yourim Yoon: Department of Computer Engineering, College of Information Technology, Gachon University, 1342 Seongnamdaero, Sujeong-gu, Seongnam-si 13120, Korea

Mathematics, 2022, vol. 10, issue 4, 1-15

Abstract: We propose a memetic algorithm for the multiple-choice multidimensional knapsack problem (MMKP). In this study, we focus on finding good solutions for the MMKP instances, for which feasible solutions rarely exist. To find good feasible solutions, we introduce a novel repair heuristic based on the tendency function and a genetic search for the function approximation. Even when the density of feasible solutions over the entire solution space is very low, the proposed repair heuristic could successfully change infeasible solutions into feasible ones. Based on the proposed repair heuristic and effective local search, we designed a memetic algorithm that performs well on problem instances with a low density of feasible solutions. By performing experiments, we could show the superiority of our method compared with previous genetic algorithms.

Keywords: multiple-choice multidimensional knapsack problem; memetic algorithm; genetic algorithm; repair heuristic (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/4/602/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/4/602/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:4:p:602-:d:750456

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().