Information Technology Reference
In-Depth Information
heuristic strategy is incorporated in an ant colony algorithm to select the heuristic that best
adjust one of its control parameter.
5.1 Selection of metaheuristics using meta-learning
In this section a methodology based on Meta-Learning is presented for characterizing
algorithm performance from past experience data. The characterization is used to select the
best algorithm for a new instance of a given problem. The phases of the methodology are
described and exemplified with the well known one-dimensional Bin-Packing problem.
5.1.1 Algorithms for the solution of the Bin Packing Problem
The Bin Packing Problem (BPP) is an NP-hard combinatorial optimization problem, in
which the objective is to determine the smallest number of bins to pack a set of objects. For
obtaining suboptimal solutions of BPP, with less computational effort, we used
deterministic and non-deterministic algorithms. The algorithm performance is evaluated
with the optimal deviation percentage and the processing time (Quiroz, 2009).
The deterministic algorithms always follow the same path to arrive at the same solution. The
First Fit Decreasing (FFD) algorithm places the items in the first bin that can hold them. The
Best Fit Decreasing (BFD) places the items in the best-filled bin that can hold them. The
Match to First Fit (MFF) algorithm is a variation of FFD, wich uses complementary bins for
holding temporarily items. The Match to Best Fit (MBF) algorithm is a variation of BFD and,
like MFF uses complementary bins. The Modified Best Fit Decreasing (MBFD) partially pack
the bins in order to find a “good fit” item combination.
The Non-Deterministic Algorithms do not obtain the same solution in different executions,
but in many cases they are faster than deterministic algorithms. The Ant Colony
Optimization (ACO) algorithm builds a solution with each ant: it starts with an empty bin;
next, each new bin is filled with “selected items” until no remaining item fits in it; finally, a
“selected item” is chosen stochastically using mainly a pheromone trail (Ducatelle, 2001). In
the Threshold Accepting (TA) algorithm, a new feasible solution is accepted if the difference
with the previous solution is within a threshold temperature; the value of the temperature is
decreased each time until a thermal equilibrium is reached (Pérez, 2002).
5.1.2 Methodology
The methodology proposed for performance characterization and its application to
algorithm selection consists of three consecutive phases: Initial Training, Prediction and
Training with Feedback. Figure 3 depicts these phases.
In the
Initial Training Phase
, two internal processes build a past experience database: the
Problem Characterization Process obtains statistical indices to measure the computational
complexity of a problem instance and, the Algorithm characterization Process solves
instances with the available algorithms to obtain performance indices. The Training Process
finally builds a knowledge base using the Problem and Algorithms Database. This
knowledge is represented through a learning model, which relates the algorithms
performance and the problem characteristics. In the
Prediction Phase
, The relationship
learned is used to predict the best algorithm for a new given instance. In the
Training with
