Syarif, Admi and Angraini, Dian and Muludi, Kurnia and Wamiliana, Wamiliana and Gen, Mitsuo (2020) Comparing Various Genetic Algorithm Approaches for Multiple-choice Multi-dimensional Knapsack Problem (mm-KP). The International Journal of Intelligent Engineering and Systems (IJIES), 13 (5). ISSN 2185-3118 (eISSN), 2185-310X (pISSN)
|
Text
JI_1_IJIES_2020 - Vol 13_No 5_compressed.pdf Download (459kB) | Preview |
Abstract
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: | Article |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
| Divisions: | Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA) > Prodi Sistem Informasi |
| Depositing User: | Kurnia Muludi |
| Date Deposited: | 04 Nov 2021 01:13 |
| Last Modified: | 04 Nov 2021 01:13 |
| URI: | http://repository.lppm.unila.ac.id/id/eprint/34955 |
Actions (login required)
 |
View Item |