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

[img]
Preview
Text
jeas_0416_4013-2.pdf

Download (936kB) | Preview
Official URL: http://www.arpnjournal.com

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

Actions (login required)

View Item View Item