Admi Syarif, AS and Anggraini, Dian and Kurnia Muludi, KM and Wamiliana, Wamiliana and Gen, Mitsuo (2020) Comparing Various Genetic Algorithm Approaches for Multiple-choice Multi-dimensional Knapsack Problem. international Journal of Intelligent Engineering & System, 13 (5). pp. 455-462. ISSN 2185-3118
|
Text
Comparing Various Genetic Algorithm Approaches.pdf Download (463kB) | 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 (mmKP) 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 |
| Divisions: | Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA) > Prodi Matematika |
| Depositing User: | WAMILIANA |
| Date Deposited: | 16 Oct 2020 02:40 |
| Last Modified: | 16 Oct 2020 02:40 |
| URI: | http://repository.lppm.unila.ac.id/id/eprint/24317 |
Actions (login required)
 |
View Item |