Genetic Algorithm based Approach to Solve Non Fractional (0/1) Knapsack Optimization Problem
|
10.5120/17601-8200 |
Vikas Thada and Shivali Dhaka. Article: Genetic Algorithm based Approach to Solve Non Fractional (0/1) Knapsack Optimization Problem. International Journal of Computer Applications 100(15):21-26, August 2014. Full text available. BibTeX
@article{key:article,
author = {Vikas Thada and Shivali Dhaka},
title = {Article: Genetic Algorithm based Approach to Solve Non Fractional (0/1) Knapsack Optimization Problem},
journal = {International Journal of Computer Applications},
year = {2014},
volume = {100},
number = {15},
pages = {21-26},
month = {August},
note = {Full text available}
}
Abstract
In this paper we solve the non fractional knapsack problem also known as 0-1 knapsack using genetic algorithm. The usual approaches are greedy method and dynamic programming. Its an optimization problem where we try to maximize the values that can be put into a knapsack under the constraint of its weight. We solve the problem using genetic algorithm in matlab using gatool. In this research work different selection schemes have been used like roulette wheel, tournament selection, Stochastic selection etc. Following the introduction of genetic algorithm and knapsack problem, formulation of 0-1 knapsack problem in genetic algorithm is presented. Experimental results using various selection schemes have been analyzed and comparison of genetic algorithm technique is done with greedy method and dynamic programming optimizing techniques.
References
- B. Klabbankoh, O. Pinngern. "applied genetic algorithms in information retrieval" Proceeding of IEEE ,pp. 702-711,Nov 2004
- S. S. Satya and P. Simon, "Review on Applicability of Genetic Algorithm to Web Search," International Journal of Computer Theory and Engineering, vol. 1, no. 4, pp. 450-455, 2009.
- Shokouhi, M. ; Chubak, P. ; Raeesy, Z " Enhancing focused crawling with genetic algorithms"Vol: 4-6, pp. 503-508,2005.
- M. A. Kauser, M. Nasar, S. K. Singh, "A Detailed Study on Information Retrieval using Genetic Algorithm", Journal of Industrial and Intelligent Information vol. 1, no. 3, pp. 122-127 Sep 2013.
- J. R. Koza, " Survey Of Genetic Algorithms And Genetic Programming", Proceedings of the Wescon, pp. 589-595,1995
- V. Thada, V. Jaglan, "Use of Genetic Algorithm in Web Information Retrieval", International Journal of Emerging Technologies in Computational and Applied Sciences, vol. 7,no. 3,pp. 278-281, Feb,2014