Experimental Results
The three tables below show breakdowns of the results of some of the experiments described in 'Lewis, R., and B. Paechter. (2007) "Finding Feasible Timetables Using Group-Based Operators". IEEE Transactions on Evolutionary Computation, vol. 11(3), pp. 397-413.'
Here, we show a breakdown of the results of our experiments when the grouping genetic algorithm (with tuned parameters and using fitness function f5) is compared against the heuristic-search algorithm (using mr = 1 and heuristic search limit = 1000), within the specified time limits. See the paper for further details of these experiments. The associated graphs (whose plots are also shown in the above publication) show, for each algorithm, the average distance to feasibility per second with twenty runs on each of the twenty instances; that is, each line is an average of four hundred individual runs.
Small Instance Set
|
Distance to Feasibility. Average of 20 runs and best of 20 runs (the latter is parenthesised) |
||
| Instance# | Grouping GA* | Heuristic Search Algorithm |
| 1 | 0 (0) | 0 (0) |
| 2 | 0 (0) | 0 (0) |
| 3 | 0 (0) | 0 (0) |
| 4 | 0 (0) | 0 (0) |
| 5 | 1.05 (0) | 0 (0) |
| 6 | 0 (0) | 0 (0) |
| 7 | 0 (0) | 0 (0) |
| 8 | 6.45 (4) | 1 (0) |
| 9 | 2.5 (0) | 0.15 (0) |
| 10 | 0.1 (0) | 0 (0) |
| 11 | 0 (0) | 0 (0) |
| 12 | 0 (0) | 0 (0) |
| 13 | 1.25 (0) | 0.35 (0) |
| 14 | 10.5 (3) | 2.75 (0) |
| 15 | 0 (0) | 0 (0) |
| 16 | 0 (0) | 0 (0) |
| 17 | 0.25 (0) | 0 (0) |
| 18 | 0.7 (0) | 0.2 (0) |
| 19 | 0.15 (0) | 0 (0) |
| 20 | 0 (0) | 0 (0) |
| Average & std dev | 1.1475
& 2.66
(0.35 & 1.1) |
0.2225
& 0.63
(0.0 & 0.0) |
| Num of instances where optimal solutions were found in all twenty runs | 11 | 15 |
| >=95% chance of the results coming from a significantly different underlying distribution, according to a Wilcoxon signed rank test? - YES | ||
Medium Instance Set
|
Distance to Feasibility. Average of 20 runs and best of 20 runs (the latter is parenthesised) |
||
| Instance# | Grouping GA** | Heuristic Search Algorithm |
| 1 | 0 (0) | 0 (0) |
| 2 | 0 (0) | 0 (0) |
| 3 | 0 (0) | 0 (0) |
| 4 | 0 (0) | 0 (0) |
| 5 | 3.95 (0) | 0 (0) |
| 6 | 6.2 (0) | 0 (0) |
| 7 | 41.65 (34) | 18.05 (14) |
| 8 | 15.95 (9) | 0 (0) |
| 9 | 24.55 (17) | 9.7 (2) |
| 10 | 0 (0) | 0 (0) |
| 11 | 3.2 (0) | 0 (0) |
| 12 | 0 (0) | 0 (0) |
| 13 | 13.35 (3) | 0.5 (0) |
| 14 | 0.25 (0) | 0 (0) |
| 15 | 4.85 (0) | 0 (0) |
| 16 | 43.15(30) | 6.4 (1) |
| 17 | 3.55 (0) | 0 (0) |
| 18 | 8.2 (0) | 3.1 (0) |
| 19 | 9.25 (0) | 3.15 (0) |
| 20 | 2.1 (0) | 11.45 (3) |
| Average & std dev | 9.01
& 12.78
(4.7 & 10.0) |
2.62
& 4.88
(1.0 & 3.1) |
| Num of instances where optimal solutions were found in all twenty runs | 6 | 13 |
| >=95% chance of the results coming from a significantly different underlying distribution, according to a Wilcoxon signed rank test? - YES | ||
Large Instance Set
|
Distance to Feasibility. Average of 20 runs and best of 20 runs (the latter is parenthesised) |
||
| Instance# | Grouping GA*** | Heuristic Search Algorithm |
| 1 | 0 (0) | 0 (0) |
| 2 | 0.7 (0) | 0 (0) |
| 3 | 0 (0) | 0 (0) |
| 4 | 32.2 (30) | 20.5 (8) |
| 5 | 29.15 (24) | 38.15 (30) |
| 6 | 88.9 (71) | 92.3 (77) |
| 7 | 157.3 (145) | 168.5 (150) |
| 8 | 37.8 (30) | 20.75 (5) |
| 9 | 25 (18) | 17.5 (3) |
| 10 | 38 (32) | 39.95 (24) |
| 11 | 42.35 (37) | 26.05 (22) |
| 12 | 0.85 (0) | 0 (0) |
| 13 | 19.9 (10) | 2.55 (0) |
| 14 | 7.25 (0) | 0 (0) |
| 15 | 113.95 (98) | 10 (0) |
| 16 | 116.3 (100) | 42 (19) |
| 17 | 266.55 (243) | 174.9 (163) |
| 18 | 194.75 (173) | 179.25 (164) |
| 19 | 266.65.95 (253) | 247.35 (232) |
| 20 | 183.15 (165) | 164.15 (149) |
| Average & std dev | 81.0
& 86.33
(71.5 & 80.3) |
62.195
& 78.52
(52.3 & 72.6) |
| Num of instances where optimal solutions were found in all twenty runs | 2 | 5 |
| >=95% chance of the results coming from a significantly different underlying distribution, according to a Wilcoxon signed rank test? - YES | ||
Notes
* Using recombination rate = 0.1, mutation rate = 1, heuristic search limit = 100, and population size 5.
** Using recombination rate = 0.7, mutation rate = 1, heuristic search limit = 2, and population size 10.
*** Using recombination rate = 0.25, mutation rate = 1, heuristic search limit = 0, and population size 50.
In our tests, these parameter settings were the best performing settings with the GGA, for each of the instance sets, with this particular fitness function.
In the graphs, the lines show, at each second, the distance to feasibility of the best solution found so far in the run.
- Last updated 11 May 2006 -