A Hybrid Parallel Multi-Objective Genetic Algorithm for 0/1 Knapsack Problem
Sudhir B. Jagtap, Subhendu Kumar Pani, Ganeshchandra Shinde
DOI: 10.4236/jsea.2011.45035   PDF    HTML     4,981 Downloads   9,326 Views   Citations


In this paper a hybrid parallel multi-objective genetic algorithm is proposed for solving 0/1 knapsack problem. Multi-objective problems with non-convex and discrete Pareto front can take enormous computation time to converge to the true Pareto front. Hence, the classical multi-objective genetic algorithms (MOGAs) (i.e., non- Parallel MOGAs) may fail to solve such intractable problem in a reasonable amount of time. The proposed hybrid model will combine the best attribute of island and Jakobovic master slave models. We conduct an extensive experimental study in a multi-core system by varying the different size of processors and the result is compared with basic parallel model i.e., master-slave model which is used to parallelize NSGA-II. The experimental results confirm that the hybrid model is showing a clear edge over master-slave model in terms of processing time and approximation to the true Pareto front.

Share and Cite:

S. Jagtap, S. Pani and G. Shinde, "A Hybrid Parallel Multi-Objective Genetic Algorithm for 0/1 Knapsack Problem," Journal of Software Engineering and Applications, Vol. 4 No. 5, 2011, pp. 316-319. doi: 10.4236/jsea.2011.45035.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] T. Al-Somani and K. Qureshi, “Reliability Optimization Using Genetics Algorithms,” M. Sc. Thesis, King Abdul-Aziz University, Saudi Arabia, 2000.
[2] J. Branke, H. Schmeck, K. Deb and M. S Reddy, “Parallelizing Multi-Objective Evolutionary Algorithms: Cone Separation,” Congress on Evolutionary Computation, Vol. 2, 2004, pp. 1952-1957.
[3] E. Cantu-Paz, “A Survey of Parallel Genetic Algorithms,” Calculateurs Paralleles, Vol. 10, No. 2, 1998, pp. 141- 171.
[4] K. Deb, A. Pratap, S. Agrawal and T. Meyarivan, “A Fast and Elitist Multi-objective Genetic Algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, Vol. 6, No. 2, 2002, pp. 182-197. doi:10.1109/4235.996017
[5] C. Grosan, “How to Compare the Multi-Objective Evolutionary Algorithms Performances?” Zilele Academice Clujene, Vol. 4, No. 2, 2003, pp. 82-87.
[6] F. Streichert, H. Ulmer and A. Zell, “Parallelization of Multi-Objective Evolutionary Algorithms Using Clustering Algorithms,” In: C. A. Coello, A. H. Aguirre and E. Zitzler, Eds., Evolutionary Multi-Criterion Optimization, Springer, Berlin/Heidelberg, Vol. 3410, 2005, pp. 92-107. doi:10.1007/978-3-540-31880-4_7
[7] E. Zitzler, K. Deb and L. Thiele, “Comparison of Multi-Objective Evolutionary Algorithms: Empirical Results,” Institution Swiss Federal Institute of Technology (ETH), Zurich, Vol. 3, No. 2, 1999, pp. 192-197.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.