Experimental Results
The three tables below show the results of experiments with different crossover rates described in the paper "An Application of the Grouping Genetic Algorithm towards University Course Timetabling". To be published in the proceedings of the 5th International Conference on Evolutionary Computation in Combinatorial Optimisation (EvoCop 2005), Lausanne, Swizerland, March 2005.
Just to recap, all experiments described in the paper used the following evolution scheme:
We used a steady-state evolution scheme with a population of size ps. At each step, two parents were selected using binary tournament selection with parameter ts. Two offspring were then created with crossover rate cr. These were then mutated and inserted back into the population, in turn, over the least fit individual. If there was more than one least-fit individual we chose between these randomly. At each step ir individuals were also chosen randomly and inversion was applied. During the run we kept track of the fittest solution found so far - this was the algorithm’s final output. The algorithm stopped when a feasible solution was found or when a predefined time limit was reached. In our experiments we set ps=50, ts=0.9, mr=3, and ir=4. Strict time limits for the instance sets small, medium and big were imposed and set to 30, 200 and 800 seconds respectively. All trials were carried out on a PC using a Pentium 4 2.40GHz with 512MB RAM.
Here are the results.....................
Small Instances.
Crossover Rate | 0.0 | 0.25 | 0.5 | 0.75 | 1.0 | |||||
Instance | Dist. to Feas. | Gens. | Dist. to Feas. | Gens. | Dist. to Feas. | Gens. | Dist. to Feas. | Gens. | Dist. to Feas. | Gens. |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5 | 5 | 12961 | 5 | 9880 | 6 | 7846 | 6 | 6436 | 6 | 2061 |
6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
8 | 12 | 12475 | 13 | 10648 | 15 | 8822 | 16 | 6343 | 19 | 2338 |
9 | 6 | 12869 | 4 | 11571 | 6 | 10346 | 6 | 8947 | 8 | 7858 |
10 | 2 | 12878 | 0 | 8660 | 0 | 2665 | 0 | 2743 | 0 | 1383 |
11 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
12 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
13 | 2 | 13062 | 3 | 11964 | 0 | 8304 | 2 | 9947 | 2 | 9824 |
14 | 17 | 11396 | 17 | 9683 | 20 | 7655 | 18 | 5468 | 20 | 4913 |
15 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
16 | 0 | 8440 | 0 | 5480 | 0 | 1156 | 0 | 424 | 0 | 456 |
17 | 2 | 12753 | 1 | 10442 | 1 | 9384 | 2 | 6958 | 0 | 2372 |
18 | 4 | 12788 | 4 | 10102 | 3 | 7814 | 3 | 2656 | 5 | 1061 |
19 | 8 | 12291 | 3 | 10325 | 7 | 8726 | 5 | 8080 | 8 | 6051 |
20 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Total Dist. to Feas. |
58 |
50 |
58 |
57 |
68 |
|||||
# Winners |
2 |
3 |
3 |
0.5 |
1.5 |
Medium Instances.
Crossover Rate | 0.0 | 0.25 | 0.5 | 0.75 | 1.0 | |||||
Instance | Dist. to Feas. | Gens. | Dist. to Feas. | Gens. | Dist. to Feas. | Gens. | Dist. to Feas. | Gens. | Dist. to Feas. | Gens. |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 0 | 110 | 0 | 85 | 0 | 114 | 0 | 249 | 0 | 31 |
3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 2 | 39504 | 0 | 1838 | 0 | 1438 | 0 | 12208 | 1 | 1972 |
5 | 9 | 39596 | 8 | 30683 | 10 | 18056 | 9 | 18710 | 9 | 10566 |
6 | 15 | 35711 | 19 | 26132 | 17 | 21473 | 16 | 15598 | 15 | 7844 |
7 | 46 | 35304 | 45 | 29542 | 42 | 24640 | 41 | 21727 | 42 | 15786 |
8 | 21 | 39380 | 22 | 31244 | 27 | 28816 | 22 | 22426 | 22 | 6580 |
9 | 39 | 35299 | 30 | 30835 | 42 | 25902 | 31 | 18454 | 35 | 11666 |
10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
11 | 12 | 34490 | 22 | 25424 | 23 | 18296 | 14 | 12676 | 16 | 8202 |
12 | 0 | 22759 | 4 | 22167 | 0 | 977 | 0 | 617 | 0 | 785 |
13 | 23 | 32187 | 27 | 25538 | 30 | 19809 | 28 | 14086 | 29 | 3304 |
14 | 4 | 35088 | 0 | 13151 | 0 | 3528 | 1 | 8455 | 4 | 3268 |
15 | 16 | 29542 | 15 | 25527 | 13 | 16476 | 10 | 5982 | 20 | 1058 |
16 | 53 | 30032 | 55 | 24146 | 50 | 17844 | 52 | 12428 | 72 | 2232 |
17 | 21 | 33292 | 23 | 26757 | 26 | 20826 | 24 | 17323 | 28 | 2062 |
18 | 40 | 31747 | 26 | 26254 | 40 | 19945 | 16 | 13919 | 15 | 8671 |
19 | 53 | 28787 | 64 | 22581 | 51 | 16456 | 58 | 13393 | 54 | 2689 |
20 | 26 | 30577 | 31 | 26201 | 15 | 19632 | 26 | 14118 | 39 | 2144 |
Total Dist. to Feas. | 380 |
391 |
386 |
348 |
401 |
|||||
# Winners | 6 |
3 |
5 |
2 |
1 |
Large Instances.
Crossover Rate | 0.0 | 0.25 | 0.5 | 0.75 | 1.0 | |||||
Instance | Dist. to Feas. | Gens. | Dist. to Feas. | Gens. | Dist. to Feas. | Gens. | Dist. to Feas. | Gens. | Dist. to Feas. | Gens. |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 4 | 41699 | 0 | 4688 | 0 | 1729 | 2 | 1127 | 4 | 699 |
3 | 0 | 722 | 0 | 1298 | 0 | 556 | 0 | 284 | 0 | 163 |
4 | 32 | 39281 | 32 | 25184 | 32 | 11487 | 32 | 805 | 32 | 567 |
5 | 31 | 39959 | 31 | 23840 | 31 | 7965 | 31 | 854 | 31 | 603 |
6 | 90 | 32862 | 90 | 23077 | 90 | 11541 | 90 | 981 | 90 | 561 |
7 | 150 | 36574 | 150 | 24533 | 150 | 15850 | 150 | 3957 | 150 | 593 |
8 | 36 | 39438 | 35 | 32621 | 36 | 25554 | 36 | 1308 | 36 | 645 |
9 | 26 | 38330 | 26 | 26612 | 26 | 1279 | 26 | 778 | 26 | 592 |
10 | 36 | 39725 | 36 | 23343 | 36 | 5858 | 36 | 911 | 36 | 588 |
11 | 43 | 40739 | 43 | 27032 | 43 | 12017 | 43 | 1170 | 43 | 616 |
12 | 4 | 38083 | 5 | 11665 | 5 | 1295 | 5 | 890 | 5 | 633 |
13 | 26 | 36519 | 23 | 19221 | 25 | 4538 | 25 | 824 | 24 | 623 |
14 | 11 | 39674 | 8 | 10704 | 11 | 1573 | 11 | 934 | 11 | 659 |
15 | 120 | 35137 | 121 | 24144 | 121 | 16466 | 123 | 4061 | 121 | 601 |
16 | 120 | 29301 | 129 | 18928 | 132 | 9698 | 131 | 5571 | 135 | 341 |
17 | 275 | 25781 | 271 | 13856 | 283 | 5726 | 293 | 2110 | 328 | 260 |
18 | 202 | 26660 | 199 | 15224 | 200 | 9169 | 202 | 6071 | 220 | 338 |
19 | 267 | 30205 | 268 | 18280 | 262 | 13548 | 275 | 3936 | 285 | 350 |
20 | 188 | 31458 | 188 | 20786 | 186 | 16558 | 196 | 2115 | 207 | 567 |
Total Dist. to Feas. | 1661 | 1655 | 1669 | 1707 | 1784 | |||||
# Winners | 5.4 | 7.4 | 3.4 | 1.4 | 1.4 |