A New Genetic Algorithm for the 0-1 Knapsack Problem

In this paper, The 0-1 Knapsack Problem (KP) which occurs in many different applications is studied and a new genetic algorithm to solve the KP is proposed. In our methodology, n items are represented by n genes on a bit array that compactly stores the values 0 or 1. When calculating fitness values of items, coefficients of items whose values are 1 in the bit array are summed. Roulette wheel method is used for chosing parents; in this way it is provided that strong individuals produce more children. Crossover is applied in such a way  that roulette wheel is rotated on genes with the same index of parents, that the dominant parent can transfer its genes to the child. Mutation is applied for randomly chosen 25% genes and this process is repeated for the number of individuals. The algorithm is written in C programming language and is tested on randomly generated instances. In order to find the optimal solutions of these problems, a program that has been written by dynamic programming technique is used. It is seen that the algorithm yields optimal solutions for all instances.