DefinePK

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.