(Publisher of Peer Reviewed Open Access Journals)
Navigation

International Journal of Advanced Technology and Engineering Exploration (IJATEE)

ISSN (Print):2394-5443    ISSN (Online):2394-7454
Volume-5 Issue-45 August-2018
Full-Text PDF
DOI:10.19101/IJATEE.2018.545018
Paper Title : Applying greedy genetic algorithm on 0/1 multiple knapsack problem
Author Name : Vinod Jain and Jay Shankar Prasad
Abstract :

Knapsack problem is a well-known optimization problem in computer science. It has many application areas in science and engineering. Knapsack problem can be solved using genetic algorithm. Multiple knapsack problem (MKP) is a special form of knapsack problem in which items are to be placed in more than one knapsack. Many researchers solve MKP problem using different techniques such as ant colony optimization (ACO), particle swarm optimization (PSO) and genetic algorithm (GA). The objective of this paper is to solve MKP problem using GA in an efficient manner. In this paper MKP is solved using greedy genetic algorithm. The proposed genetic algorithm uses greedy approach in its selection and reproduction operations of GA. The proposed greedy genetic algorithm is implemented on a standard data set and results ensure that the proposed greedy algorithm performs better than the standard genetic algorithm.
Keywords : Multiple knapsack problem, Genetic algorithm, Greedy approach.
Cite this article : Vinod Jain and Jay Shankar Prasad, " Applying greedy genetic algorithm on 0/1 multiple knapsack problem " , International Journal of Advanced Technology and Engineering Exploration (IJATEE), Volume-5, Issue-45, August-2018 ,pp.292-296.DOI:10.19101/IJATEE.2018.545018
References :
[1]Umbarkar AJ, Joshi MS, Sheth PD. Dual population genetic algorithm for solving constrained optimization problems. International Journal of Intelligent Systems and Applications. 2015; 7(2):34-40.
[Crossref] [Google Scholar]
[2]Pal SK, Rai CS, Singh AP. Comparative study of firefly algorithm and particle swarm optimization for noisy non-linear optimization problems. International Journal of Intelligent Systems and Applications. 2012; 4(10):50-7.
[Crossref] [Google Scholar]
[3]Xiao-hua X, Liang M, Ai-bing N. Competitive decision algorithm for multiple-choice knapsack problem based on reduction. In international conference on computer modeling and simulation 2010 (pp. 344-8). IEEE.
[Crossref] [Google Scholar]
[4]Kobayashi K, Tadaki K, Kasahara M, Tsujii S. A knapsack cryptosystem based on multiple knapsacks. In international symposium on information theory and its applications 2010 (pp. 428-32). IEEE.
[Crossref] [Google Scholar]
[5]Salman FS, Kalagnanam JR, Murthy S, Davenport A. Cooperative strategies for solving the bicriteria sparse multiple knapsack problem. Journal of Heuristics. 2002; 8(2):215-39.
[Crossref] [Google Scholar]
[6]Godrich H, Petropulu AP, Poor HV. Sensor selection in distributed multiple-radar architectures for localization: a knapsack problem formulation. IEEE Transactions on Signal Processing. 2012; 60(1):247-60.
[Crossref] [Google Scholar]
[7]Kumaraguruparan N, Sivaramakrishnan H, Sapatnekar SS. Residential task scheduling under dynamic pricing using the multiple knapsack method. Innovative Smart Grid Technologies.2012:1-6.
[Crossref] [Google Scholar]
[8]Rahim S, Khan SA, Javaid N, Shaheen N, Iqbal Z, Rehman G. Towards multiple knapsack problem approach for home energy management in smart grid. In international conference on network-based information systems 2015 (pp. 48-52). IEEE.
[Crossref] [Google Scholar]
[9]Li J, Li W, Wang H. The multiple knapsack problem with compatible bipartite graphs. International symposium on operations research and its applications in engineering, technology and management 2015(pp. 1-7). IEEE.
[Crossref] [Google Scholar]
[10]Jain V, Prasad JS. Solving travelling salesman problem using greedy genetic algorithm GGA. International Journal of Engineering and Technology. 2017; 9(2):1148-54.
[Crossref] [Google Scholar]
[11]Prasad JS, Jain V. An optimized algorithm for solving travelling salesman problem using greedy cross over operator. International conference on computing for sustainable global development 2016 (pp. 2981-4). IEEE.
[Google Scholar]
[12]Farhan AS, Tareq WZ, Awad FH. Solving N queen problem using genetic algorithm. International Journal of Computer Applications. 2015; 122(12):11-4.
[Google Scholar]
[13]https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_multiple/knapsack_multiple.html. Accessed 26 May 2018.