Grammar-based generation of stochastic local search heuristics through automatic algorithm configuration tools

Franco Mascia and Manuel López-Ibáńez and Jérémie Dubois-Lacoste and Thomas Stützle

1 Reproducing the results of on the 1BPP

In Tables 1–4, we present the results obtained by our re-implementation of the evolutionary algorithm proposed by (Burke et al., 2012).

Table 1: Results on the Uniform500 family of instances when trained on the families in the first column.
Family Mean Standard deviation Minimum Maximum
Huniform500 0.336842105263158 0.0375228780468975 0.284210526315789 0.436842105263158
Huniform1000 0.383333333333333 0.0958303828933066 0.289473684210526 0.810526315789474
Hscholl 0.810350877192982 0.304475118178332 0.326315789473684 1.25789473684211
Htriples 0.824736842105263 0.146667701464175 0.721052631578947 1.47368421052632

Table 2: Results on the Uniform1000 family of instances when trained on the families in the first column.
Family Mean Standard deviation Minimum Maximum
Huniform500 0.507719298245614 0.0883048814816165 0.415789473684211 0.778947368421053
Huniform1000 0.564210526315789 0.172939612747001 0.394736842105263 1.38421052631579
Hscholl 1.48140350877193 0.72440730524882 0.484210526315789 3.12631578947368
Htriples 1.32666666666667 1.77288291438761 0.810526315789474 10.6684210526316

Table 3: Results on the Scholl family of instances when trained on the families in the first column.
Family Mean Standard deviation Minimum Maximum
Huniform500 1.40888888888889 0.443806054926137 0.888888888888889 2.6
Huniform1000 1.74703703703704 0.512331404602989 1.16666666666667 2.65555555555556
Hscholl 0.888148148148148 0.00578700510846876 0.877777777777778 0.9
Htriples 1.28037037037037 0.0754542555836438 1.18888888888889 1.64444444444444

Table 4: Results on the Triples family of instances when trained on the families in the first column.
Family Mean Standard deviation Minimum Maximum
Huniform500 5.37280701754386 4.75371065470931 1 19.5684210526316
Huniform1000 3.13947368421053 2.88479889543664 1 12.2052631578947
Hscholl 5.20175438596491 4.22125546202518 1.03684210526316 16.1842105263158
Htriples 1 0 1 1

2 Mean distance from lower bound obtained on 1BPP

Figures 1–6 compare the results for the 1BPP on the instance families Scholl, Triples, Uniform500, Uniform1000, Uniform2000 and Uniform4000. For each family, different methods are used to explore the design space described by the grammar and generate an efficient algorithm for the instances in the training set. The algorithm is evaluated by averaging the distance from the lower bound on ten runs on ten test instances. The whole training and testing procedure is repeated 30 times, and the results of the distribution of the 30 results obtained for each method are presented in the boxplots in the figures.

PIC

Figure 1: Mean distance from lower bound obtained by the heuristics generated by each tuning method on Scholl family of instances for 1BPP.

PIC

Figure 2: Mean distance from lower bound obtained by the heuristics generated by each tuning method on Triples family of instances for 1BPP.

PIC

Figure 3: Mean distance from lower bound obtained by the heuristics generated by each tuning method on Uniform500 family of instances for 1BPP.

PIC

Figure 4: Mean distance from lower bound obtained by the heuristics generated by each tuning method on Uniform1000 family of instances for 1BPP.

PIC

Figure 5: Mean distance from lower bound obtained by the heuristics generated by each tuning method on Uniform2000 family of instances for 1BPP.

PIC

Figure 6: Mean distance from lower bound obtained by the heuristics generated by each tuning method on Uniform4000 family of instances for 1BPP.

Table 5: Mean distance from lower bound obtained by the heuristics generated by each tuning method for the 1BPP. The standard deviation is indicated in parentheses.
Family evolutionary random irace-ge rand-ge irace-param3 irace-param5 rand-param5 evolutionarymi randommi
Scholl 0.84 (0.16) 0.91 (0.21) 0.77 (0.12) 0.88 (0.22) 0.76 (0.08) 0.77 (0.10) 0.89 (0.18) 0.85 (0.14) 0.75 (0.00)
Triples 1.06 (0.05) 1.06 (0.03) 1.06 (0.02) 1.06 (0.02) 1.06 (0.03) 1.05 (0.03) 1.06 (0.03) 1.07 (0.03) 1.07 (0.02)
Uniform500 0.57 (0.35) 0.56 (0.24) 0.39 (0.08) 0.44 (0.13) 0.39 (0.07) 0.36 (0.03) 0.48 (0.14) 0.39 (0.03) 0.47 (0.06)
Uniform1000 0.87 (0.25) 1.27 (1.37) 0.73 (0.11) 0.84 (0.21) 0.70 (0.07) 0.71 (0.08) 0.92 (0.19) 0.88 (0.18) 0.99 (0.13)
Uniform2000 1.39 (0.42) 1.18 (0.14) 1.12 (0.24) 1.34 (0.31) 1.11 (0.21) 1.08 (0.20) 1.39 (0.27) 1.36 (0.11) 1.40 (0.05)
Uniform4000 2.89 (1.10) 2.95 (0.62) 2.54 (0.42) 3.20 (0.73) 2.50 (0.25) 2.34 (0.35) 3.46 (0.57) 3.57 (0.76) 2.39 (0.00)

Table 6: Comparison of the methods through the Friedman test blocking on the instances of the six benchmark sets. ΔRα=0.95 gives the minimum difference in the sum of ranks between two methods that is statistically significant.
Family ΔRα=0.95  

Method (ΔR)

Scholl 11.27  

randommi (0), irace-param3 (0.5), irace-param5 (10.5), irace-ge (12), evolutionarymi (33), evolutionary (34), rand-param5 (54), rand-ge (55.5), random (61.5)

Triples Inf  

irace-param5 (0), irace-param3 (4), rand-param5 (7), rand-ge (8), random (13.5), irace-ge (13.5), randommi (15), evolutionarymi (19), evolutionary (23.5)

Uniform500 11.69  

irace-param5 (0), evolutionarymi (9.5), irace-param3 (17.5), irace-ge (19.5), randommi (32), rand-ge (39.5), rand-param5 (52.5), evolutionary (65.5), random (65.5)

Uniform1000 8.6  

irace-param3 (0), irace-param5 (3), irace-ge (12), rand-ge (33), evolutionarymi (37), evolutionary (44), rand-param5 (53), randommi (58), random (75)

Uniform2000 11.69  

irace-param5 (0), irace-param3 (1.5), irace-ge (7.5), random (25), rand-ge (33.5), rand-param5 (45), evolutionarymi (50), evolutionary (56.5), randommi (64.5)

Uniform4000 9.48  

irace-param5 (0), irace-param3 (16), randommi (17), irace-ge (22.5), evolutionary (35), random (43.5), rand-ge (58), rand-param5 (67), evolutionarymi (74)

3 Mean distance from lower bound obtained on PFSP-WT

The boxplots in Figure 7 and 8 present the results on the PFSP-WT of 30 experiments with the different methods described in the paper.

PIC

Figure 7: Mean relative percentage deviation obtained by the heuristics generated by each tuning method on 50x20 family of instances for PFSP-WT.

PIC

Figure 8: Mean relative percentage deviation obtained by the heuristics generated by each tuning method on 100x20 family of instances for PFSP-WT.

Table 7: Mean relative percentage deviation obtained by the heuristics generated by each tuning method for the 1BPP. The standard deviation is indicated in parentheses.
Family evolutionary random irace-ge rand-ge irace-param3 irace-param5 rand-param5 evolutionarymi randommi
50x20 25.47 (8.78) 23.05 (7.36) 17.01 (4.63) 19.81 (4.44) 16.62 (5.04) 16.84 (4.47) 22.40 (5.66) 20.88 (3.53) 20.84 (2.55)
100x20 5.37 (1.66) 5.18 (1.49) 3.88 (0.98) 4.78 (0.88) 3.43 (0.53) 3.81 (0.90) 4.47 (1.03) 4.39 (1.05) 4.08 (0.80)

Table 8: Comparison of the methods through the Friedman test blocking on the instances of the two benchmark sets. ΔRα=0.95 gives the minimum difference in the sum of ranks between two methods that is statistically significant.
Family ΔRα=0.95  

Method (ΔR)

50x20 16.3  

irace-ge (0), irace-param3 (1), irace-param5 (2), rand-ge (22), randommi (26), evolutionarymi (36), rand-param5 (47), random (48), evolutionary (52)

100x20 11.19  

irace-param3 (0), irace-ge (11), irace-param5 (11), randommi (28), evolutionarymi (37), rand-param5 (40), rand-ge (54), evolutionary (66), random (68)

References

   E. K. Burke, M. R. Hyde, and G. Kendall, “Grammatical evolution of local search heuristics,” IEEE Transactions on Evolutionary Computation, vol. 16, no. 7, pp. 406–417, 2012.

Resources

We make available the instances used in this study for the 1BPP and the PFSP-WT.