Share This Article:

A Hybrid Parallel Multi-Objective Genetic Algorithm for 0/1 Knapsack Problem

Abstract Full-Text HTML Download Download as PDF (Size:353KB) PP. 316-319
DOI: 10.4236/jsea.2011.45035    4,017 Downloads   7,537 Views   Citations

ABSTRACT

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.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

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.

References

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

  
comments powered by Disqus

Copyright © 2018 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.