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

• 作者: Ganeshchandra Shinde Subhendu Kumar Pani Sudhir B. Jagtap
• 来源期刊: 软件工程与应用(英文)
• 学科: 工学
• 关键词: MULTI-OBJECTIVE Genetic Algorithm PARALLEL Processing Techniques NSGA-II 0/1 KNAPSACK Problem TRIGGER MODEL Cone Separation MODEL Island MODEL
• 年，卷（期）: 2011,（5）
• 页码范围: 316-319
• 页数: 4页
• 分类号: TP1

摘要

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.