On the Use of Human-Guided Evolutionary Algorithms for Tackling 2D Packing Problems - Foundations on Natural and Artificial Computation - page 354

Fig. 1. Example application of the Bottom-Left-Fill heuristic. The square does not fit
in the bottommost space at the right end of the figure, but does fit in the next empty
space in a bottom-left fashion. The right figure shows the arrangement after the square
has been placed.

in the use of a human expert to oversee the optimization process. This kind
of application is typically termed interactive evolutionary computation (IEC)
[9,10]. We prefer the term user-centric evolutionary computation [11] though,
since it captures not just interactivity but also the possibility for proactivity.
Be as it may, in this work we consider a human-guided approach in which the
user asynchronously interacts with the algorithm in order to tune the greediness
of the genotype-to-phenotype mapping, and use it as a proof of concept of the
applicability of this kind of approaches in this problem domain.

2 Problem Definition and Background

Let c = be a collection of n objects, each of them characterized by

its width w i and height h i . We have to arrange the objects within a larger rectan-
gle of fixed width W , such that (1) no two objects overlap, (2) they fit within the
width of the larger container, and (3) the height of the arrangement (largest dis-
tance between the base and top of two objects) is minimized. When creating the
arrangement, objects can be rotated by 90 o , and no guillotine-constraint exists
[1]. The so-defined problem naturally captures many manufacturing processes in
wood, glass, and paper industries, and even problems from other domains such
as processor allocation [12].
There have been numerous attempts at solving this kind of problem with
metaheuristics. Burke and Kendall [13] compared tabu search, simulated an-
nealing and genetic algorithms, and concluded the latter was outperformed by
the former. Indeed, cutting and packing problems are known to pose dicul-
ties to evolutionary approaches if these are unable to deal adequately with the
relevant information pieces contained in solutions. Grouping genetic algorithms

{ o 1 , ··· ,o n }