Information Technology Reference
In-Depth Information
Training and FeedBack phase
The steps of this phase are shown in Figure 6. The objective is to feedback the system in
order to maintain it in a continuous training. For each new solved and characterized
instance, step 9 (Instance Solution) obtains the real best algorithm. Afterwards, step 10
(Patterns Verification) compares the result, if the prediction is wrong and the average
accuracy is beyond an specified threshold, then the classifiers are rebuilt using the old and
new dataset; otherwise the new instance is stored and the process ends.
Fig. 6. Steps of the training with feedback phase
5.1.3 Experimentation
For test purposes 2,430 random instances of the Bin-Packing problem were generated,
characterized and solved using the seven heuristic algorithms described in Section 5.1.1.
Table 1 shows a small instance set, which were selected from the sample.
Problem characteristic indices
Real best
algorithms
Instance
p b t f d
E1i10.txt
0.078
0.427 0.029 0.000 0.003 FFD,TA
E50i10.txt
0.556
0.003 0.679 0.048 0.199 BFD,ACO
E147i10.txt
0.900
0.002 0.530 0.000 0.033 TA
Table 1. Example of random intances with their characteristics and the best algorithms
The K-means clustering method was used to create similar instance groups. Four groups
were obtained; each group was associated with a similar instances set and an algorithm with
the best performance for it. Three algorithms had poor performance and were outperformed
by the other four algorithms. The Discriminant Analysis (DA) and C4.5 classification
methods were used to build the algorithm selector. We use the machine learning methods
available in SPSS version 11.5 and Weka 3.4.2, respectively. Afterwards, for validating the
system, 1,369 standard instances were collected [Ross 2002]. In the selection of the best
algorithm for all standard instances, the experimental results showed an accuracy of 76%
with DA and 81% with C4.5. This accuracy was compared with a random selection from the
