Cooperative parallel grouping genetic algorithm for the one-dimensional bin packing problem

Tayfun Kucukyilmaz*, Hakan Ezgi Kiziloz

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

27 Citations (Scopus)

Abstract

Evolutionary algorithms have been reported to be efficient metaheuristics for the optimization of several NP-Hard combinatorial optimization problems. In addition to their ability to solve difficult and complex problems in reasonable execution times, parallelized versions of evolutionary algorithms are reported to explore and exploit the problem search space more effectively than their sequential counterparts. The Island Model, where the population of a given run is divided into semi isolated subpopulations, is a popular parallelization approach for evolutionary algorithms such as Grouping Genetic Algorithms (GGA). Although the nature of GGAs is very suitable for coarse-grained parallel processing, designing an Island-parallel model for them is not a straightforward task. Selecting the communication topology, deciding migration and assimilation strategies, adjusting the migration rate and frequency, and using efficient diversification techniques are some of the important issues that needs to be covered in a successful Island-parallel Model. In this study, we propose a novel, scalable Island-parallel GGA (IPGGA) for the well-known combinatorial optimization Problem 1D Bin-Packing (1DBPP). We provide a thorough experimental evaluation of the parallel model and report significant improvements on the Hard28 problem instances by outperforming the state-of-the-art genetic algorithms. Additionally, we analyze and evaluate the parallelization parameters of IPGGA with an emphasis on problem search-space diversity and report several interesting results.

Original languageEnglish
Pages (from-to)157-170
Number of pages14
JournalComputers and Industrial Engineering
Volume125
DOIs
Publication statusPublished - Nov 2018
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2018 Elsevier Ltd

Fingerprint

Dive into the research topics of 'Cooperative parallel grouping genetic algorithm for the one-dimensional bin packing problem'. Together they form a unique fingerprint.

Cite this