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

precisely greediness is tempered by not taking always the locally optimal deci-
sion, but by making random decisions within a certain short list of candidate de-
cisions (e.g., the k best decisions for some k , fixed in advance or reactively learnt
[19,17]; other procedures exist though). This random selection of candidates can
be substituted by an evolutionary approach, as shown in [8] for the Golomb
ruler problem. The idea here is to consider a n -integer string

s 1 , ··· ,s n

,where
s i > 0; s i would thus indicate that when taking the i -th decision, the s i -th best
candidate should be taken (notice therefore that 1 , ··· , 1 would correspond to
the purely greedy solution).
The representation of solutions combine both aspects, i.e., a permutation of
the objects

. Hence, the
interpretation of a certain solution is therefore: pick object p 1 and place it in the
s 1 -th place where it fits, counting from bottom to top and from left to right; the
object p 2 and so on. In order to count candidate places, objects are firstly tried
in the original orientation, and then rotated by 90 o . If the object fits in both
ways, each orientation is given a different index. Therefore, the EA has control
on which position an object is placed, and with which orientation.

p 1 , ··· ,p n and a greedy-control sequence s 1 , ··· ,s n

3.2 Adding Human Guidance

The addition of human-guidance to the evolutionary optimization process leads
to interactive evolutionary computation (IEC). IEC basically consists of a com-
putational model that promotes the communication between a human user and
an automated evolutionary algorithm (aEA). This intervention of the human
user is required when some aspect of the algorithm cannot be algorithmically
construed. A typical example is the use of a human expert to provide subjective
fitness evaluation of candidate solutions. This does not exhaust the possibili-
ties though; the user can also modify the genetic contents of the population, or
change dynamically some aspect of the algorithm.
One of the most typical problems IEC has to deal with is the fatigue of
the human user. The latter cannot be forced to continuously supply feedback,
since otherwise she would be soon fatigued and the quality of the feedback would
sharply decrease. To alleviate this fatigue, our approach conceives the interaction
as a purely asynchronous feature, i.e., the human-guided EA (hgEA) behaves as
an aEA and hence is capable of working without user intervention. However,
it is also capable of being interrupted by the user who can interact with the
algorithm and resume the search subsequently.
In our approach interaction can take many forms as anticipated above: the
user can inspect statistical information of the population (frequencies of each
allele, correlation of an allele with fitness, etc.), as well as individual solutions,
and take decisions such as manually select solutions for breeding, and change
operators and parameters, just to cite a few. In this particular application we
have focused on the capability for dynamically changing the range of values each
gene can take. More precisely we concentrate on the greedy-control part and let
the user specify online the range of values these genes can take. By doing so, the
user is capable of adjust the greediness of the genotype-to-phenotype mapping,