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                

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.

Keywords

Multi-Objective Genetic Algorithm, Parallel Processing Techniques, NSGA-II, 0/1 Knapsack Problem, Trigger Model, Cone Separation Model, Island Model

Conflicts of Interest

The authors declare no conflicts of interest.

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.