A. J. Umbarkar; M. S. Joshi

0/1 Knapsack Problem using Diversity based Dual Population Genetic Algorithm

Full Text (PDF, 392KB), PP.34-40

Views: 0 Downloads: 0

Author(s)

A. J. Umbarkar ^1,* M. S. Joshi ²

1. Department of Information Technology, Walchand College of Engineering Sangli, MS, India

2. Department of Computer Engineering, Jawaharlal Nehru Engineering College, Aurangabad, MS, India

* Corresponding author.

DOI: https://doi.org/10.5815/ijisa.2014.10.05

Received: 4 Dec. 2013 / Revised: 10 Mar. 2014 / Accepted: 22 May 2014 / Published: 8 Sep. 2014

Index Terms

Dual Population Genetic Algorithm, DPGA, Genetic Algorithm, GA, Knapsack Problem, 0/1 knapsack problem, Evolutionary Algorithm, EA

Abstract

The 0/1 Knapsack Problem is an optimization problem solved using various soft computing methods. The solution to the 0/1 Knapsack Problem (KP) can be viewed as the result of a sequence of decisions. Simple Genetic Algorithm (SGA) effectively solves knapsack problem for large data set. But it has problems like premature convergence and population diversity. Dual Population Genetic Algorithm (DPGA) is an improved version of Genetic Algorithm (GA) with the solution to above problems. This paper proposes Dual Population GA for solving 0/1 knapsack Problem. Experimental results of knapsack on SGA and DPGA are compared on standard as well as random data sets. The experimental result shows DPGA performs better than knapsack on SGA.

Cite This Paper

A. J. Umbarkar, M. S. Joshi, "0/1 Knapsack Problem using Diversity based Dual Population Genetic Algorithm", International Journal of Intelligent Systems and Applications(IJISA), vol.6, no.10, pp.34-40, 2014. DOI:10.5815/ijisa.2014.10.05

Reference

[1]Rahman K. and Ahmed S. Performance Analysis of Genetic Algorithm for Solving the Multiple-Choice Multi-Dimensional Knapsack Problem. International Journal of Recent Trends in Engineering, 2009, vol. 2, no. 2.

[2]http://www.informatics.indiana.edu/fil/CAS/PPT/Davis/sld029.html, 12th August, 2013.

[3]Park T. and Ruy K. A Dual-Population Genetic Algorithm for Adaptive Diversity Control. IEEE transactions on evolutionary computation, December 2010, vol. 14, no. 6: 865-884.

[4]Ebrahimzadeh R. and Jampour M. Chaotic Genetic Algorithm based on Lorenz Chaotic System for Optimization Problems. International Journal of Intelligent Systems and Applications, 2013, Vol. 5( 5):19-24.

[5]Song, S., Kong L. and Cheng J. A Novel Particle Swarm Optimization Algorithm Model with Centroid and its Application. International Journal of Intelligent Systems and Applications, Vol.1 (1): 42-49.

[6]Umbarkar A. J. and Joshi M. S. Serial DPGA vs. Parallel Multithreaded DPGA: Threading Aspects. Proceedings of the International Conference on Soft Computing for Problem Solving (SocProS 2011), 2012: 39-50.

[7]Umbarkar A.J. and Joshi M.S. Dual Population Genetic Algorithm (GA) versus OpenMP GA for Multimodal Function Optimization. International Journal of Computer Applications, 2013, vol. 64: 29-36.

[8]Gordon V. and Wim BOhm A. P. A Note on the Performance of Genetic Algorithms on Zero-One Knapsack Problems. Proceeding of the 1994 ACM symposium on Applied computing, 1994: 194-195.

[9]Khuri S., Back T., and et.al. The Zero/One Multiple Knapsack Problem and Genetic Algorithms. Proceeding of the 1994 ACM symposium on Applied computing, 1994: 188-193.

[10]Sakawa M. and Kato K. Genetic algorithms with double strings for 0–1 programming problems. European Journal of Operational Research, 2003, 144: 581–597.

[11]Hristakeva, M. and Shrestha, D. Solving the 0-1 knapsack problem with genetic algorithms. In Proceedings of the 37th Midwest Instruction and Computing Symposium, Morris, MN, Apr. 2004.

[12]Julstrom B. Genetic and Greedy Genetic Algorithms for the Quadratic Knapsack Problem. Proceeding of the 7th annual conference on Genetic and evolutionary computation, 2005: 607-614.

[13]Lin F. Solving the knapsack problem with imprecise weight coefficients using genetic algorithms. European Journal of Operational Research, 2008, 185: 133–145.

[14]Hanxiao, S. Solution to 0/1 Knapsack Problem Based on Improved Ant Colony, Algorithm. 2006 IEEE International Conference on Information Acquisition, 2006, 1062-1066.

[15]João Alves M., Marla. MOTGA: A multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem. Computers & Operations Research, 2007, 34 (11): 3458–3470.

[16]Rohlfshagen P. ExGA II: An Improved Exonic Genetic Algorithm for the Multiple Knapsack Problems. Proceeding of the 9th annual conference on Genetic and evolutionary computation, 2007: 1357-1364.

[17]Zhao T. and Man Z. A CGS-MSM PGA based on Multi-Agent and its application in solving 0-1 Knapsack Problem. Proceeding of First International Conference on Intelligent Networks and Intelligent Systems, 2008. ICINIS '08, 2008: 73 - 76.

[18]Mohanty S. and Satapathy R. An evolutionary multiobjective genetic algorithm to solve 0/1 Knapsack Problem. Proceeding of 2nd IEEE International Conference on Computer Science and Information Technology, 2009. ICCSIT 2009: 397 – 399..

[19]Zhao J., Huang T., Pang F. and Liu Y. Genetic algorithm based on Greedy strategy in the 0-1 Knapsack Problem. Proceeding of 3rd International Conference on Genetic and Evolutionary Computing, 2009. WGEC '09, 2009: 105 – 107.

[20]Ahmed Z. and Younas I. A Dynamic Programming based GA for 0-1 Modified Knapsack Problem. International Journal of Computer Applications, 2011, 16(7):1–6.

[21]Singh, R.P. Solving 0-1 Knapsack problem using Genetic Algorithms. 2011 IEEE 3rd International Conference on Communication Software and Networks (ICCSN), 2011, 591-595.

[22]Tuo S., Yong L., and Deng F. A Novel Harmony Search Algorithm Based on Teaching-Learning Strategies for 0-1 Knapsack Problems. The Scientific World Journal (2014) 2014, 1-19.

[23]Umbarkar A. J. and Joshi M. S. Review of parallel genetic algorithm based on computing paradigm and diversity in search space. ICTACT Journal on Soft Computing, 2013, vol. 3: 615-622.

[24]Park T. Choe R. and Ruy K. Adjusting Population Distance for the Dual-Population Genetic Algorithm. Proceedings of the 20th Australian joint conference on Advances in Artificial Intelligence, 2007: 171-180.

[25]Sels V. and Vanhoucke M. A Hybrid Dual-Population Genetic Algorithm for the Single Machine Maximum Lateness Problem. Evolutionary Computation in Combinatorial Optimization, Lecture Notes in Computer Science, 2011, Volume 6622: 14-25.

[26]http://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/ p07_c.txt, 12th August, 2013.

[27]https://github.com/jkdeveyra/CMSC-170-Knapsack GA/tree/master/src/main/java/dataset, 12th August, 2013.

International Journal of Intelligent Systems and Applications (IJISA)