Admi Syarif, AS and Aristoteles, Aristoteles and Arianti, Dwiastuti and Riska, Malinda (2016) Peer Review: Performance evaluation of various genetic algorithm approaches for knapsack problem. Asian Research Publishing Network.
|
Text
5. arpn116_nilai.pdf Download (2MB) | Preview |
Abstract
Knapsack Problem (KP) is known as one of optimization problems that has taken great interest of researchers. It has been applied for many practical applications. Since it belongs to the class of NP-hard problems, most of researchers reported heuristic methods to solve it. Those include Branch and Bound, Greedy Algorithm, Genetic Algorithm and Dynamic Programming. In this paper, we focus on the performance evaluation of various Genetic Algorithm (GA) approaches to solve Knapsack Problem. We developed four different GA approaches with different strategies. The first, random penalty GA (rpGA) uses random strategy to generate chromosome and penalty strategy to handle infeasible chromosome. The second, directed penalty GA (dpGA) uses directed strategy to generate chromosome and penalty to handle infeasible chromosome. The third, random repairing GA (rrGA) uses random strategy to generate chromosome and repairing strategy to handle infeasible chromosome. The fourth, directed repairing GA (drGA) uses directed strategy to generate chromosome and repairing strategy to handle infeasible chromosome. In order to investigate the performance of those algorithms, we have done several numerical experiments by using different size Benchmark test problems given in literature. The effectiveness and the efficiency of the methods are also evaluated by varying GA parameters. Based on our experiments, it is shown that drGA was the best performance to give optimal solution within reasonable computational time. Keywords: knapsack problem, combinatorial optimization, evaluation strategy, genetic algorithm.
| Item Type: | Other |
|---|---|
| Subjects: | T Technology > T Technology (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 |
| URI: | http://repository.lppm.unila.ac.id/id/eprint/28339 |
Actions (login required)
 |
View Item |