Experimental Results

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

Note: These results are not claimed to be state of the art. Better results could probably be found with different parameter settings, less strict time limits etc. This was not what we were invstigating here.
Note: Entries in the table where both "dist. to feas." and "gens" are zero occur because our construction heuristics were able to find a feasible solution in the initial population.
Note: When choosing a winner, ties were broken by selecting the crossover rate that found its solution in the least number of seconds. If this still caused a tie the winning point was divided equally between them.