 |
|
ISSN 1320-0682 | ||||
| Volume 3 | April 1996 | ||||
Fuchun Luan and Xin Yao
...Luan
Australian Seismological Centre, Australian Geological Survey Organisation,
GPO Box 378 Canberra, ACT 2601
...Yao
Computational Intelligence Group, School of Computer Science, University
College, The University of New South Wales, Australian Defence Force Academy
Canberra, ACT 2600
Email:fluan@agso.gov.au & xin@csadfa.cs.adfa.oz.au
This paper proposes a genetic algorithm-based approach to the lecture room assignment problem (LRAP). A two-dimensional chromosome representation is used in our genetic algorithm, which employs a column-based crossover operator in order to preserve potential "building blocks". Our algorithm has been tested on a real world case at the Australian Defence Force Academy where the lecture room assignment is currently done by a human domain expert. Our experimental results show that the GA results are better than those produced by the expert using the same set of constraints and criteria.
Every university in the world offers hundreds of units or subjects to its students. A subject is often composed of more than one lecture. Each lecture has to be assigned to a particular lecture room according to the size and time of the lecture. As the number of offered subjects becomes larger, the task of assigning lecture rooms becomes very tedious and difficult for a human expert due to the limited number of lecture rooms available. An optimal assignment is usually very hard to obtain. This paper describes a genetic algorithm-based approach to lecture room assignment, which can relieve human beings from the tedious manual task. From now on, we will use "subjects" to represent either "units" or "subjects" in this paper for the sake of convenience.
The lecture room assignment problem (LRAP) is related to the timetabling problem, but with different requirements and constraints. Firstly, assigning different lecture rooms to the same subject often causes a lot of confusion among students and lecturers, and thus should be avoided whenever possible. It is strongly preferable to assign the same lecture room to two or more lectures of the same subject which are scheduled in different teaching periods. Second, the number of students enrolled in a subject must be smaller or equal to the number of seats available in the assigned lecture room. A close match between the two is always preferred in order to improve the effectiveness of teaching. For example, having 10 students sitting in a lecture theatre of 120 seats should be discouraged. The teaching effectiveness would be low in such cases. The utilisation of the space is also low. These requirements make the LRAP a very difficult constrained combinatorial optimisation problem. It can be shown that the LRAP is NP-hard [3].
Ideally, an optimal solution to the LRAP is one in which lecture rooms are maximally utilised with no conflicts; that is, no two lectures will be assigned to the same room at the same time. The simplest approach to solve the LRAP is to employ exhaustive search, which will guarantee the optimality of the final solution. However, the sheer size of the search space for real world applications rules out this option. In fact, any algorithm which tries to find the exact globally optimal solution will be impractical due to its unbearably long computation time. An approximate algorithm has to be found instead.
Genetic algorithms (GAs) are a class of robust and powerful search algorithms applicable to a wide range of problems with little prior knowledge [4], [9]. They are particularly good at global search and can deal with complex and multimodal search landscapes. GAs have been successfully applied to a great variety of problems including timetabling, job assignment and travelling salesman problems [4], [7], [8], [1]. However, to our best knowledge, a GA-based approach to the LRAP has not been reported.
In this paper, we describe a GA-based approach to the LRAP. We use a two-dimensional chromosome to represent a lecture room assignment and use a column-based crossover to preserve potentially good "building blocks". In our current implementation, columns represent teaching periods. We have applied our GA system to the real world LRAP at the Australian Defence Force Academy, where lecture room assignment is currently done by a human expert. Our experimental results have shown that the GA system is quite effective in producing high-quality assignments. In fact, results produced by the GA system are significantly better than those produced by the human expert under the same set of criteria.
We will use a real example at the Australian Defence Force Academy to illustrate the requirements and constraints for a proper lecture room assignment. In the second semester of 1995, ADFA offered 152 subjects which were scheduled in 343 lectures. Subjects were taught in one to twelve lectures per week. There are 22 lecture rooms located at the north and south lecture complex at the ADFA for lecturing purpose. The lecture size is defined by the enrolment in the subject and the room size is the lecture room's seating capacity. The size of enrolment for the 152 subjects in question, range from 2 to 208 students. The seating capacity of the lecture rooms range from 14 to 200 (Table 1). Only one subject has the size of enrolment greater than the largest lecture room in ADFA. It is treated as if its enrolment size equalled to the largest lecture room. Due to historical reasons, the lectures had to be fixed into certain teaching periods of a week day. Each working day is divided into 11 teaching periods; thus, there are 55 teaching periods in a week - see Table 1.
There are some constraints for the LRAP at ADFA.
These restrictions create some difficulty for GA applications. For example, the range and choice for crossover and mutation have to be based on a teaching period in order to produce feasible offspring. Some sort of procedure has to be employed to insure that the constraints are complied with. This may degrade the performance of the GA system, meaning that more computing time is required than would otherwise be the case. The process for producing new children by a GA operation may have to be repeated or abandoned because the offspring may violate the constraints.
Let I = {1,2,..., m} be a set of lecture rooms, and let J = {1,2,..., n} be a set of teaching periods. The size of the lecture rooms are {r1, r2, ... rm} and the size of a lecture assigned to room i during period j is lij. The LRAP considered in this paper can be formulated as minimising a cost function. The cost consists of two parts: the part due to the difference between the size of lecture and that of lecture room, and the part due to the assignment of same lectures to different lecture rooms in different teaching periods. The mathematical formulation of the LRAP is shown in Figure 1.
Figure 1: Equations 1, 2 and 3
Where nlr is the number of unique combinations of subject and lecture room, nl is the number of subjects, and A is an adjustable coefficient for the size of award/penalty. The relative importance of cost 1 and cost 2 can be controlled by the size of this factor A. For example, if we want to reduce cost 2 associated with the number of the same lectures assigned to different rooms, we should increase the size of factor A. On the other hand, if a close match between subject enrolment size and lecture room seating capacity is wanted, a relatively small A should be used (see Tables 2 and 3).
Genetic algorithms are search algorithms based on the mechanics of natural selection and natural genetics [4]. They combine the principle of survival of the fittest among string structures with a structured yet randomised information exchange to form a search algorithm with some of the innovative flair of human search. In every generation, a new set of artificial creatures (strings) is created using bits and pieces of the fitter individuals of the previous generation. While randomised, genetic algorithms are no simple random walk. They efficiently exploit historical information to speculate on new search points with expected improved performance. In this sense, GAs are guided random search techniques [2].
In GA, a potential solution to a problem is represented as a set of parameters which are joined together to form a string of values known as a chromosome. A good representation scheme is important for a GA since GAs search relies heavily on crossover, which is effective only when there are building blocks in the representation. The representation also affects the design of various genetic operators and constraint-handling by the GA. The main steps of a GA can be summarised as follows:
A different, and probably better, way to view GAs is to formulate them as generate-and-test algorithms, where genetic operators are nothing but perturbation operators used to generate potentially better solutions and selection is the process of testing whether the generated solutions are good or not [9]. The generate-and-test view of GAs provide a unified framework for investigating GAs along with other classical generate-and-test algorithms in artificial intelligence.
In our GA implementation for LRAP, each individual chromosome is a two-dimensional array (table) of the number of teaching periods by the number of lecture rooms. Each entry of the array represents the lecture which is offered at that teaching period and occupies that lecture room. An empty entry means that no lecture has been assigned to that room at the time. For each teaching period, the number of offered lectures is known and fixed. But assignment of lectures to rooms can be changed in order to minimise the cost function mentioned above. In the following discussion, we will use the normal GA term "chromosome" to represent "table" for the LRAP.
We used a cost function to measure how close the match between the enrolment size and the size of assigned lecture room, and whether the two or more lectures of the same subject are assigned the same lecture room. The former is determined by the difference between the size of enrolment and that of the assigned lecture room. The latter is represented by an award/penalty term. If the same lecture room is assigned to different lectures of the same subject, an award is given (that is, the fitness value will be increased). Otherwise, a penalty is given.
Due to the requirements and constraints of the LRAP, special GA operators are designed to work on the two-dimensional chromosomes. Crossover is applied by swapping two corresponding teaching periods between two parents. Mutation is applied only within a teaching period; that is, by changing the assignment in that teaching period. The roulette wheel selection and elitism are used in our implementation.
An individual solution in the searching space for the LRAP is an array of the number of periods multiplied by the number of lecture rooms - 55x22 in this case. A conceptual representation is shown in Figure 2. In this two-dimensional array, the number of elements in a given teaching period is fixed with each individual position within the period flexible subject to the constraint that the lecture size must be less than or equal to the room size.
Figure 2: Representation of an individual chromosome, where p1,
p2 ..., p55 are
teaching periods; r1, r2 ..., r22 are lecture rooms, and s1, s2 ... are
subjects.
"-" indicating no lecture.
To guarantee that all individual solutions comply with the hard requirement for the LRAP, the initial population is generated at random using the following steps.
In our GA system for the LRAP, the fitness of a chromosome is the inverse of the cost defined in Equation (1). Cost1 in Equation (1) is implemented by the square of the difference between the enrolment size and the lecture room size. For example, class size 93 and 106 allocated in room of sizes 150 and 200 would be better treated than allocated to room size of 200 and 150 respectively; that is, (93-150)**2+(106-200)**2 is less than (93-200)**2+(106-150)**2. Cost2 is implemented by adding/subtracting a fixed amount A, say 10 or 100, to/from the total cost according to whether or not all lectures of a subject are assigned to the same lecture room. The factor A can be used as a mechanism to either achieve a better result for minimising the size difference or to minimise the number of subjects for which repeated lectures in different teaching periods are assigned to different lecture rooms.
Although a variety of selection schemes can be employed in GAs [8], we have chosen the most common proportionate selection scheme - roulette wheel selection - due to its simplicity and effectiveness for our LRAP. The elitist strategy which always copies the best chromosome to the next generation is also used. With roulette wheel selection scheme, each chromosome is allocated a sector of a roulette wheel with the angle subtended by the sector at the centre of the wheel equalling the chromosome's fitness. The chromosome will be selected for producing offspring if a randomly generated number falls in the sector corresponding to the chromosome.
The crossover proposed in this paper is quite different from those used to manipulate linear strings. It is implemented by swapping two corresponding teaching periods between two individuals. In order to preserve the potential "building blocks", we use a column-based crossover operator (Figure 3) which swaps two corresponding columns. It is possible to generalize this "one-point" crossover to multiple-point ones where more than one column is swapped.
Figure 3: Crossover in the GA system for the LRAP (symbols as
in the text).
Mutation in our GA implementation is the permutation of lecture assignment within a teaching period (Figure 4). For each teaching period, two sites (representing two lecture rooms) are randomly selected for mutation. Only mutations which satisfy all constraints are allowed. This sometimes requires many tries and therefore is computationally expensive. A retry threshold after which no mutation is performed can be implemented to deal with possibly long mutation time.
Figure 4: Mutation in the GA system for the LRAP (symbols as in
the text).
Several sets of different GA parameters, including crossover and mutation probabilities, have been used to test our GA system for the LRAP using the real world data for Semester 2 of 1995 and Semester 1 of 1996 at ADFA. The number of subjects and lectures offered in Semester 1 of 1996 is substantially less than Semester 2 of 1995 (subjects: 91 versus 152; lectures: 195 versus 342). Using the same set of GA parameters, the results for the smaller data set of Semester 1 of 1996 is better and computation time required is less than that for semester 2 of 1995, apparently due to the relatively small searching space and less conflict. The following discussion will be based on the results for Semester 2 of 1995.
The results for Semester 2 of 1995 using a factor 10 and 100 for A in the cost calculation are shown in Table 2 and Table 3 respectively, together with the results for the current human expert's assignment calculated using the same formula. Experiments with some parameter sets were run more than once on a few different computers. In such cases, the final results were all the same except the difference in computation time due to the processing power and load of the computers. It has been demonstrated that the generally recommended parameter set of crossover rate 0.6 and mutation rate 0.01 [5], [6] works quite well for our LRAP.
Figure 5 shows a typical run of the GA system. A dramatic reduction in the cost for room size difference (that is, cost1) in the first 1000 generations can be observed. A near linear decrease in cost of room size difference then follows. However, the reduction in cost2 due to the assignments of same lectures to different lecture rooms is relatively slow. The total cost is still reducing after 10000 generation.
Figure 5: The result from a typical run of GA system.
(P_crossover = 0.6, P_mutation = 0.01, and A=10).
Since we have not come across LRAP solved by any automatic methods, we can only compare our results to those produced by the human experts. It is quite clear that GA always produces better results than the human expert (Tables 2 and 3) after 10,000 generations using a population of 100.
As crossover occurs between two corresponding teaching periods of the two parents, it always produces feasible offspring from feasible parents. However, this is not the case for random mutation where constraints may be violated, resulting in either repeating operation or abandoning of the result.
From Table 2 and Table 3, it can be seen that the factor A in the cost function as described in Equation (1) to (3) is a good mechanism for balancing minimisation of cost1 and cost2. If we want to reduce the number of lectures which have been assigned to different rooms during different periods, a large value of A is desirable (Table 3). This will meet the second criterion better, as described in the introduction section. On the other hand, if a close match between lecture size and lecture room size is preferred, a small value of A would be more desirable.
We have presented a GA-based system for the LRAP. The system is capable of producing good assignment results with little domain knowledge. Our experimental results show that our approach performs satisfactorily in solving the LRAP. The results produced by the GA are far superior than the those produced by the human expert according to the same set of criteria. This shows that the GA-based approach is effective and practical in solving the real world LRAP. It can relieve the human expert from the tedious manual assignment task. The system we have implemented would be a very useful tool to solve universities' lecture room assignment problems and problems such as conference room and sporting venue assignment problems.
The authors are grateful to Professor Charles Newton and Mr Arto Levonpera for making the ADFA data sets available.
Solving Real World Lecture Room Assignment Problems by Genetic Algorithms
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html luanyao.
The translation was initiated by Pam Milliken on Thu Jan 16 14:23:58 EST 1997