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

Jagtap, Sudhir B.; Pani, Subhendu Kumar; Shinde, Ganeshchandra
May 2011
Journal of Software Engineering & Applications;May2011, Vol. 4 Issue 5, p316
Academic Journal
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.


Related Articles

  • An Improved Genetic Algorithm Based on Adaptive Repair Operator for Solving the Knapsack Problem. Gupta, Sunanda; Garg, M. L. // Journal of Computer Science;2009, Vol. 5 Issue 8, p544 

    Problem statement: Knapsack problem is a typical NP complete problem. During last few decades, Knapsack problem has been studied through different approaches, according to the theoretical development of combinatorial optimization. Approach: In this study, modified evolutionary algorithm was...

  • Meta-heuristics for Multidimensional Knapsack Problems. Zhibao Mian // International Proceedings of Computer Science & Information Tech;2012, Vol. 39, p40 

    In this research, we present the use of genetic algorithms and constraint handling techniques used in genetic algorithms to solve Multidimensional Knapsack Problems (MKP). We also investigate and compare how the use of different genetic algorithm operators and parameters could obtain different...

  • Multivariant Optimization Algorithm for the 0-1 Knapsack Problem. LIU Lan Juan; LI Bao Lei; ZHANG Qin Hu; LV Dan Jv; SHI Xin Lin; LI Jing Jing // Applied Mechanics & Materials;2014, Issue 556-562, p3514 

    In this paper, a novel heuristic algorithm named Multivariant Optimization Algorithm (MOA) is presented to solve the 0-1 Knapsack Problem (KP). In MOA, multivariant search groups (locate and global search groups) execute the global exploration and local exploitation iteratively to locate the...

  • Using the idea of expanded core for the exact solution of bi-objective multi-dimensional knapsack problems. Mavrotas, George; Figueira, José Rui; Antoniadis, Alexandros // Journal of Global Optimization;Apr2011, Vol. 49 Issue 4, p589 

    We propose a methodology for obtaining the exact Pareto set of Bi-Objective Multi-Dimensional Knapsack Problems, exploiting the concept of core expansion. The core concept is effectively used in single objective multi-dimensional knapsack problems and it is based on the 'divide and conquer'...

  • Neural, Genetic, And Neurogenetic Approaches For Solving The 0-1 Multidimensional Knapsack Problem. Deane, Jason; Agarwal, Anurag // International Journal of Management & Information Systems;2013 1st Quarter, Vol. 17 Issue 1, p43 

    The multi-dimensional knapsack problem (MDKP) is a well-studied problem in Decision Sciences. The problem's NP-Hard nature prevents the successful application of exact procedures such as branch and bound, implicit enumeration and dynamic programming for larger problems. As a result, various...

  • A parallel genetic algorithm based on OpenCL in resolving 0/1 knapsack problems. Long CHANG; Lin SHI // Advanced Materials Research;2014, Issue 1030-1032, p1633 

    This paper mainly focused on 0/1 knapsack problems based on the genetic algorithm (GA). According to characteristics of the individual independence in GA, a parallel segmentation method was presented using the OpenCL technology in resolving the 0/1 knapsack problems. Moreover, the local memory...

  • SHELF SPACE OPTIMIZATION USINGMETAHEURISTIC ALGORITHMS. Bilsel, Murat; Batuhan Ayhan, M.; Bulkan, Serol // International Journal of Information, Business & Management;May2013, Vol. 5 Issue 2, p210 

    Efficient allocation of shelves in retail is essential to gain and maintain competitiveness. Shelf Space Allocation Problem (SSAP) is an extension of the knapsack problem; the objective is determination of the products and their locations on shelves to maximize expected profit. Various factors...

  • An Algorithm for the Solution of 0-1 Loading Problems. Ingargiola, Giorgio; Korsh, James F. // Operations Research;Nov/Dec75, Vol. 23 Issue 6, p1110 

    An enumerative algorithm is presented for the solution of 0-1 many-knapsack or loading problems. It is based on the principle that before a search is attempted as many decisions as possible should be made about inclusion or exclusion of objects from the knapsacks. This is accomplished by the...

  • The Multidimensional 0-1 Knapsack Problem—Bounds and Computational Aspects. Fréville, Arnaud; Hanafi, SaÏd // Annals of Operations Research;Oct2005, Vol. 139 Issue 1-4, p195 

    The multidimensional 0-1 knapsack problem (MKP) is a resource allocation model that is one of the most well-known integer programming problems. During the last few decades, an impressive amount of research on the 0-1 knapsack problem has been published in the literature, and efficient...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics