Admi Syarif, AS and Anggraini, Dian and Muludi, Kurnia and Wamiliana, Wamiliana (2020) Peer Review: Comparing Various Genetic Algorithm Approaches for Multiple-choice Multi-dimensional Knapsack Problem (mm-KP). Intelligent Networks and Systems Society.

4. ijies20_nilai.pdf

Download (2MB) | Preview
Official URL:


One of the essential and well-known classes of combinatorial optimization problems commonly studies by researchers in the last five decades is called the Knapsack Problem (KP). Many variants of KP have been introduced for different real-world applications. Among them, the multiple-choice multi-dimensional Knapsack Problem (mm- KP) is the most complex model with an NP-hard problem. Several authors have reported the robustness of heuristics for mm-KP; irrespective of its advantages, no method currently has the ability to solve the problem optimally all time. This paper aims to determine the best GA strategy and evaluate the performance of several heuristic algorithms to solve mm-KP. We investigate the use of two techniques that are included in the GA approach. The first, two different strategies are adopted to handle infeasible chromosomes, namely penalty and repairing procedure. Second, we develop a new-simple local search to improve the quality of the solution found. Experimental studies on the 13 (thirteen) Benchmark instances are conducted to evaluate the effectiveness of the approach based on solutions quality, the number of the optimal solution reached, and average errors. The results showed that hr-GA tends to reach optimal/nearoptimal solutions. Furthermore, the results from studies on heuristic algorithms also show that hr-GA is a promising approach, with local search used to immensely improve the quality.

Item Type: Other
Subjects: T Technology > TA Engineering (General). Civil engineering (General)
Divisions: Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA) > Prodi Ilmu Komputer
Depositing User: DR Admi Syarif
Date Deposited: 01 Apr 2021 01:45
Last Modified: 01 Apr 2021 01:45

Actions (login required)

View Item View Item