CFP last date
21 October 2024
Reseach Article

Genetic Algorithm based Approach to Solve Non Fractional (0/1) Knapsack Optimization Problem

by Vikas Thada, Shivali Dhaka
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 100 - Number 15
Year of Publication: 2014
Authors: Vikas Thada, Shivali Dhaka
10.5120/17601-8200

Vikas Thada, Shivali Dhaka . Genetic Algorithm based Approach to Solve Non Fractional (0/1) Knapsack Optimization Problem. International Journal of Computer Applications. 100, 15 ( August 2014), 21-26. DOI=10.5120/17601-8200

@article{ 10.5120/17601-8200,
author = { Vikas Thada, Shivali Dhaka },
title = { Genetic Algorithm based Approach to Solve Non Fractional (0/1) Knapsack Optimization Problem },
journal = { International Journal of Computer Applications },
issue_date = { August 2014 },
volume = { 100 },
number = { 15 },
month = { August },
year = { 2014 },
issn = { 0975-8887 },
pages = { 21-26 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume100/number15/17601-8200/ },
doi = { 10.5120/17601-8200 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:30:02.902886+05:30
%A Vikas Thada
%A Shivali Dhaka
%T Genetic Algorithm based Approach to Solve Non Fractional (0/1) Knapsack Optimization Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 100
%N 15
%P 21-26
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
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
  1. B. Klabbankoh, O. Pinngern. "applied genetic algorithms in information retrieval" Proceeding of IEEE ,pp. 702-711,Nov 2004
  2. 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.
  3. Shokouhi, M. ; Chubak, P. ; Raeesy, Z " Enhancing focused crawling with genetic algorithms"Vol: 4-6, pp. 503-508,2005.
  4. 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.
  5. J. R. Koza, " Survey Of Genetic Algorithms And Genetic Programming", Proceedings of the Wescon, pp. 589-595,1995
  6. 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
Index Terms

Computer Science
Information Sciences

Keywords

Knapsack genetic algorithm