Syarif, Admi and Aristoteles, Aristoteles and Arianti, Dwiastuti and Riska, Malinda (2016) Performance Evaluation of Various Genetic Algorithm Approaches for Knapsack Problem. Asian Research Publishing Network, Journal of Engineering and Applied Sciences (ARPN JEAS), 11 (7). pp. 4713-4719. ISSN 1819-6608
 | There is a more recent version of this item available. |
|
Text
jeas_0416_4013-2.pdf Download (936kB) | 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: | Article |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science 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: | 08 Nov 2016 01:15 |
| Last Modified: | 08 Nov 2016 06:31 |
| URI: | http://repository.lppm.unila.ac.id/id/eprint/1079 |
Available Versions of this Item
- Performance Evaluation of Various Genetic Algorithm Approaches for Knapsack Problem. (deposited 08 Nov 2016 01:15) [Currently Displayed]
Actions (login required)
 |
View Item |