A New Genetic Algorithm for the 0-1 Knapsack Problem
Küçük Resim Yok
Tarih
2016
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
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 choosing 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.
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 choosing 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.
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 choosing 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.
Açıklama
Anahtar Kelimeler
Mühendislik, Ortak Disiplinler
Kaynak
ACADEMIC PLATFORM-JOURNAL OF ENGINEERING AND SCIENCE
WoS Q Değeri
Scopus Q Değeri
Cilt
4
Sayı
3
