Information Technology Reference
In-Depth Information
Feedback phase
, the new solved instances are incorporated into the characterization process
for increasing the selection quality. The relationship learned in the knowledge base is
improved with a new set of solved instances and is used again in the prediction phase.
Fig. 3. Phases of the algorithm selection methodology
Initial training phase
The steps of this phase are shown in Figure 4 In step 1 (Characteristics Modeling) indices are
derived for measuring the influence of problem characteristics on algorithm performance
(see Equations 1 to 5). In step 2 (Statistical Sampling) a set of representative instances are
generated with stratified sampling and a sample size derived from survey sampling. In step
3 (Characteristics Measurement) the parameter values of each instance are transformed into
indices. In step 4 (Instances Solution) instances are solved using a set of heuristic algorithms.
In Step 5 (Clustering) groups are integrated in such a way that they are constituted by
instances with similar characteristics, and for which an algorithm outperformed the others.
Finally, in step 6 (Classification) the identified grouping is learned into formal classifiers.
Fig. 4. Steps of the initial training phase
We propose five indices to characterize the instances of BPP:
Instance size p
expresses a relationship between instance size and the maximum size solved,
where,
n
is the number of items,
maxn
is the maximum size solved
