Experimental Results

The three tables below show breakdowns of the results of some of the experiments described in Chapter VII, E  in 'Rhydian Lewis and Ben Paechter, "Finding Feasible Timetables using Group Based Operators". Technical Report NUS-2005-01, Centre for Emergent Computing, Edinburgh, Scotland, 2005.' Also accepted for publication in IEEE Trans in Evol. Comp.

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

- Last updated 11 May 2006 -