Performance evaluation of Genetic Algorithm (GA) with Repairing Strategy on Knapsack Problem

Abstract

Knapsack Problem (KP) is known as one of combinatorial optimization problem that maximizes the amount of value (profit/ priority) of some of the items chosen to put in a sack or a bag without exceeding its capacity. KP has been applied in many fields: cargo loading, budget control, financial management and etc. In addition, KP is also included in NP-Hard problem. Several research have been conducted using some heuristic method to solve it. Some of these methods are Branch and Bound, Greedy Algorithms, Dynamic Programming, and Genetic Algorithms.

However, when using GA, the feasibility of chromosome is one of critical issue. Most of optimization problem has constraint functions that will change the feasibility of solution. GA has some strategies to handle this case on the evaluation step. Evaluation not only calculates chromosome’s fitness value, but also handles the infeasible chromosomes presence. There’re rejecting strategies, repairing strategies, and penalty strategy.This paper develops a strategy GA approach with chromosome repairing strategy. In order to see the performance of the algorithm, we have done numerical experiment with several test problems taken on certain literature. In addition, this study will also give variations in GA parameter to determine the efficiency and effectiveness of the algorithm.