Paper Info
Title
Parallel island-based multiobjectivised memetic algorithms for a 2D packing problem
Abstract
Bin Packing problems are NP-hard problems with many practical applications. A variant of a Bin Packing Problem was proposed in the GECCO 2008 competition session. The best results were achieved by a mono-objective Memetic Algorithm (MA). In order to reduce the execution time, it was parallelised using an island-based model. High quality results were obtained for the proposed instance. However, subsequent studies concluded that stagnation may occur for other instances. The term multiobjectivisation refers to the transformation of originally mono-objective problems as multi-objective ones. Its main aim is to avoid local optima. In this work, a multiobjectivised MA has been applied to the gecco 2008 Bin Packing Problem. Several multiobjectivisation schemes, which use problem-dependent and problem-independent information have been tested. Also, a parallelisation of the multiobjectivised MA has been developed. Results have been compared with the best up to date mono-objective approaches. Computational results have demonstrated the validity of the proposals. They have provided benefits in terms of solution quality, and in terms of time saving.
Year
DOI
Venue
2011
10.1145/2001576.2001793
GECCO
Keywords
Field
DocType
mono-objective approach,execution time,mono-objective memetic algorithm,best result,mono-objective problem,multiobjectivised ma,proposed instance,bin packing problem,parallel island-based multiobjectivised memetic,multiobjectivisation scheme,high quality result,np hard problem,memetic algorithm,memetic algorithms
Memetic algorithm,Mathematical optimization,Packing problems,Local optimum,Computer science,Algorithm,Execution time,Set packing,Bin packing problem
Conference
Citations 
PageRank 
References 
16
0.57
20
Authors
3
Name
Order
Citations
PageRank
Carlos Segura121621.44
Eduardo Segredo27711.02
Coromoto León323125.71