Information Technology Reference
In-Depth Information
[14] are actually based on this fact, and attempt to process the group structure
of solutions. On the other hand, another very common feature of evolutionary
approaches to this problem is trying to incorporate some kind of placement
heuristic. For example, in the Bottom-Left-Fill (BLF) heuristic [15] objects are
suitably ordered and then placed in the bottommost leftmost position (see Fig.
1). Other approaches such as Best-Fit (BF) [16] try to select the best object
(if any) to be placed in each position, starting from the bottommost leftmost
one. BLF heuristics are very well suited to combinations with metaheuristic ap-
proaches finding adequate orderings of the objects to be fed to the the placement
heuristic. This has been for example the approach considered in [2] in the con-
text of genetic algorithms, simulated annealing and hill climbing. As to the BF
heuristic, it has been used by [17] in the context of GRASP and variable neigh-
borhood search. As show in next section, the approach presented in this work
combines the BLF heuristic with an evolutionary GRASP procedure, further
enhanced by human intervention.
3 A Human-Guided Hybrid Evolutionary Approach
As anticipated in previous sections, there are two main ingredients in our evo-
lutionary approach: a purely algorithmic component based on an underlying
placement heuristic and an evolutionarily-driven greedy decoder, and a human-
guided aspect. Let us describe these two elements separately.
3.1 The Hybrid Algorithm
The metaheuristic algorithm (which we will refer to as 'automated' henceforth,
to distinguish it from its human-guided counterpart), combines ideas of permu-
tational decoders and GRASP-based decoders. Essentially, we consider the two
key elements that drive the functioning of a basic placement heuristic, namely
the ordering of objects and the ordering of free slots where they can be accom-
modated. The permutational aspect is similar to the approach used in [2], that
is, an evolutionary algorithm (EA) is used to evolve good object-orderings to be
fed to a placement heuristic (BLF in our case). If this were the unique compo-
nent of the algorithm, the EA would manage a population of solutions, each of
which would be a permutation of elements
. However, this representa-
tion is unable to capture the possibility of object rotations (or at least deprives
the EA of control over this feature, that would be then hardwired within the
placement heuristic). A simple way to allow direct evolutionary control over this
might be to augment chromosomes with a
n
-bit string indicating the orientation
of each object. We have however opted for a more general approach based on
GRASP-like decoders.
To understand this decoder, let us firstly recall that GRASP (greedy ran-
domized adaptive search procedures [18]) are construction techniques that build
solutions incrementally, using a greedy heuristic as guidance mechanism. More
{
1
,
ยทยทยท
,n
}
Search WWH ::
Custom Search