Memetic algorithms and hyperheuristics applied to a multiobjectivised two-dimensional packing problem

Packing problems are <Emphasis Type="SmallCaps">np-hard problems with several practical applications. A variant of a <Emphasis Type="SmallCaps">2d Packing Problem (2<Emphasis Type="SmallCaps">dpp) was proposed in the <Emphasis Type="SmallCaps">gecco 2008 competition session. In this paper, Memetic Algorithms (<Emphasis Type="SmallCaps">mas) and Hyperheuristics are applied to a multiobjectivised version of the 2<Emphasis Type="SmallCaps">dpp. Multiobjectivisation is the reformulation of a mono-objective problem into a multi-objective one. The main aim of multiobjectivising the 2<Emphasis Type="SmallCaps">dpp is to avoid stagnation in local optima. First generation <Emphasis Type="SmallCaps">mas refers to hybrid algorithms that combine a population-based global search with an individual learning process. A novel first generation <Emphasis Type="SmallCaps">ma is proposed, and an original multiobjectivisation method is applied to the 2<Emphasis Type="SmallCaps">dpp. In addition, with the aim of facilitating the application of such first generation <Emphasis Type="SmallCaps">mas from the point of view of the parameter setting, and of enabling their usage in parallel environments, a parallel hyperheuristic is also applied. Particularly, the method applied here is a hybrid approach which combines a parallel island-based model and a hyperheuristic. The main objective of this work is twofold. Firstly, to analyse the advantages and drawbacks of a set of first generation <Emphasis Type="SmallCaps">mas. Secondly, to attempt to avoid those drawbacks by applying a parallel hyperheuristic. Moreover, robustness and scalability analyses of the parallel scheme are included. Finally, we should note that our methods improve on the current best-known solutions for the tested instances of the 2<Emphasis Type="SmallCaps">dpp. Copyright Springer Science+Business Media New York 2014