Admi Syarif, AS and Anggraini, 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). pp. 455-462. ISSN 2185-3118 (eISSN), 2185-310X (pISSN)
|
Text
0. JI_Terindeks_1_IJIES 2020 - Full.pdf Download (9MB) | 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: | T Technology > T Technology (General) |
| Divisions: | Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA) > Prodi Ilmu Komputer |
| Depositing User: | DR Admi Syarif |
| Date Deposited: | 07 Sep 2020 07:58 |
| Last Modified: | 15 Jun 2021 07:03 |
| URI: | http://repository.lppm.unila.ac.id/id/eprint/23902 |
Actions (login required)
 |
View Item |