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.

Keyword

Multiple knapsack problem, Genetic algorithm, Greedy approach.

Cite this article

Refference

[1][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.

[2][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.

[3][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.

[4][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.

[5][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.

[6][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.

[7][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.

[8][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.

[9][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.

[10][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.

[11][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.

[12][12]Farhan AS, Tareq WZ, Awad FH. Solving N queen problem using genetic algorithm. International Journal of Computer Applications. 2015; 122(12):11-4.

[13][13]https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_multiple/knapsack_multiple.html. Accessed 26 May 2018.