Parallel Island-Based Multiobjectivised Memetic Algorithms for a 2D Packing Problem


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.