Admi Syarif, AS and Aristoteles, AR and A. Dwiastuti, AD and R. Malinda, RM (2016) PERFORMANCE EVALUATION OF VARIOUS GENETIC ALGORITHM APPROACHES FOR KNAPSACK PROBLEM. ARPN Journal of Engineering and Applied Sciences, 11 (7). pp. 4713-4719. ISSN 1819-6608

Text Jurnal Int 2016 ARPN Journal of Engineering and Applied Sciences -aristoteles.pdf - Published Version Restricted to Registered users only Download (936kB) | Request a copy

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
Divisions:	Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA) > Prodi Ilmu Komputer
Depositing User:	Aristoteles Aristoteles
Date Deposited:	29 Dec 2016 01:06
Last Modified:	29 Dec 2016 01:06
URI:	http://repository.lppm.unila.ac.id/id/eprint/1329

Actions (login required)

View Item