Abstract: This study proposes a hybrid Simulated Annealing with solutions memory (SAM) to solve university course timetable problems. Simulated Annealing (SA) is one of the popular meta-heuristic algorithms for solving combinatorial optimization problems. However, SA could get trapped in local optimum, especially when the temperature becomes very low. In order to escape from this local optimum, this hybrid work tried to jump to another promising region using not accepted solutions saved in the memory .The computational results tested on ITC 2007 course timetabling benchmark datasets showed that SAM, can consistently produce good quality solutions, which are comparable to other approaches tested on ITC 2007 datasets.
INTRODUCTION
Timetabling is defined as “the allocation, subject to constraints, of given resources to objects being placed in space-time, in such a way as to satisfy as nearly as possible a set of desirable objectives” (Wren, 1996). This work focus on university course timetabling problem that assign a set of courses within a given number of rooms and time periods (McCollum and Ireland, 2006). Generating a course timetable manually often requires a lot of time, effort and usually it is hard to satisfy all constraints. Thus, automating the generation of course timetables is still a challenging task (McCollum and Ireland, 2006).
Many researchers have focused on solving this problem using meta-heuristics. The “Meta-heuristics are typically high-level strategies which guide an underlying, more problem specific heuristic, to increase their performance” (Blum and Roli, 2003). Some example of common mela-heuristics approaches are: ant colony optimization (Eley, 2007), genetic algorithms (Ueda et al., 2004), tabu search (Alvarez-Valdds et al., 2002), evolutionary search (Beligiannis et al., 2008) and Simulated Annealing (SA) (Abramson et al., 1999).
SA is one of the popular meta-heuristic algorithms due to its ease of implementation and ability to solve many combinatorial optimization problems. However, the disadvantages are that, it could still get trapped in local optimum and take longer time to find good quality solutions (Xinchao, 2011). Several researchers have tried to overcome this drawback. For examples, Azizi et al. (2009) proposed a hybrid simulated annealing with evolution-based diversification approach called SAMED to solve job shop scheduling problem. SAMED hybridized SA, three types of memories and GA based crossover component. The first two types of memories are short term memories (tabu list and seed memory list), while the third type is long term memory. SAMED used short term memory (tabu list) to temporarily save the accepted solutions to avoid the recycling; whilst the second short term memory (seed memory) is to keep track of the best solutions with lowest objectives functions for further improvement. The differences between our study with SAMED is in the memory part. We save the unaccepted solutions to jump to other promising region when the search got trapped in local optimum, whilst the SAMED save the best accepted solutions. Gao et al. (2006) presented a hybrid meta-heuristic algorithm by combined the characteristic of simulated annealing, genetic algorithm and chaos strategy to solve TSP problem. The experimental results showed that the hybrid meta-heuristic algorithm (CASAGA) is quite flexible with satisfactory results.
Kolonko (1999) investigated the cooling schedules for a wide range of examination timetabling problems and proposed that, very slow cooling schedule should be used. Thompson and Dowsland (1995) and Swarnkar and Tiwari (2004) hybridized SA with tabu search to avoid revisiting solutions. Jeon and Kim (2004) proposed UMOSA algorithm that use a strategy called the criterion scalarizing approach since the probability to accept new solution must take into account the distance between the old and the new move. Elmohamed et al. (1998) employed a simulated annealing with different cooling schedules (geometric, adaptive and adaptive with reheating). The experiment results showed that using SA with adaptive cooling schedules with reheating is able to generate competitive results comparing with other state-of-the-art techniques and outperformed other SA approaches. Therefore, the use of reheating function might be good to escape from local optimum, whilst the search could revisit the same local optimum again after several iterations. Nevertheless, The use of memory to save the not accepted solutions and reuse one of them when the search trapped in local optimum could avoid to re-trapped in the same local optimum again and escape from local optimum.
This study aims to solve the problem of trapping in local optimum especially when the temperature in SA are very low. The low temperature leads SA to accept only improved solutions. This means more chance to get trap in local optimum. The question is:
| • | How to escape from local optimum, if the search got trapped in it? |
Hybridize the simulated annealing with other techniques may be a reasonable good answer for the above question. However, this might not be efficient to deal with a bad solution structure that leads the search to get trapped in bad local optimum (very hard to escape). Therefore, this study aims to deal with this problem by saving several unaccepted solutions; and to reuse them when the search got trapped in the local optimum, in order to jump to other promising region.
The contribution of this work is to enhance the performance of SA by escaping from local optimum using solutions memory by saving non-accepted solutions and reuse it when the search got trapped in local optimum.
PROBLEM DESCRIPTION
The Curriculum-based Course Timetabling problem for the ITC-2007 is about the scheduling all lectures for a set of courses into a weekly timetable. Each lecture of a course must be assigned to periods and rooms in accordance to a given set of constraints. The employed method of determining the schedule must be able to satisfy the hard constraints and to minimize the soft constraints violations. This problem has four hard constraints H1-H4 and four soft constraints S1-S4 as follows (Gaspero et al., 2007):
Hard constraints:
H1: Lectures. All lectures of a course must be scheduled to a distinct periods
H2: Room Occupancy. Any two lectures cannot be assigned to the same period and the same room
H3: Conflicts. Lectures of courses in the same curriculum or taught by the same teacher cannot be schedule in the same period
H4: Availability. If the teacher of a course is not available at a given period, then no lectures of the course can be assigned to that period
Soft constraints:
S1: Room Capacity. For each lecture, the number of students attending the course should not be greater than the capacity of the room hosting the lecture
S2: Minimum Working Days. The lectures of a course should be spread into the given minimum number of days
S3: Room Stability. All lectures of a course should be scheduled at the same room. If this is impossible, the number of occupied rooms should be as few as possible
S4: Curriculum Compactness. For a given curriculum a violation is counted if there is one lecture not adjacent to any other lecture belonging to the same curriculum within the same day, which means the agenda of students should be as compact as possible
ALGORITHM
This work is divided into two stages. The first stage is to construct initial solution using constructive algorithms. At this stage, the feasible initial solution is constructed by satisfying all hard constraints (H1-H4) using sequential greedy heuristic as in Lu and Hao (2010). There is no guarantee that this greedy heuristic can always find feasible solution. Therefore, we used steepest decent to search for a feasible solution if the solution still not feasible. The second stage is to minimize soft constraints violations. At this stage, we used the enhanced Simulated Annealing with memory (SAM).
Simulated annealing with memory: SA has been widely used to solve combinatorial optimization problems. It accepts the new solution when the objective value is lower than or equals to the current one. There is a probability to accept worse quality solutions using probability acceptance criteria:
This probability function controls the acceptance of new solution, where Δf = f (s*)-f (s), the difference between the quality of new solution f (s*) and the current solution f (s). The current temperature, T1 is iteratively reduced according to the cooling schedule with a given cooling rate α for each iteration or level until this temperature reaches final minimum temperature, which is close to Zero, Tmin.
When the SA temperature becomes very low, the SA behaves like descent heuristic (accept only improve solution). Thus, the search might easily be trapped in local optimum. Therefore, this work will save several non-accepted solutions (Solm) in the memory during the search (before the non- improvement) and randomly employs one of these solutions when local optimum is met. The memory size is fixed and is updated by replacing the worst solutions in memory with new ones (Fig. 1).
Our SA algorithm involves: neighborhood structure, temperature, cooling schedule, termination criteria and memory.
The algorithm terminates when one of the three cases occurs:
| Case I: The minimum temperature Tmin closed to zero (frozen stage) (Tmin = 0.0001). | |
| Case II: Number of iterations. | |
| Case III: Timeout based on ITC 2007 course timetabling track 3 stopping condition. |
Let:
| • | Sol be an initial solution, |
| • | f (Sol) as the quality of Sol, |
| • | Sol* as the best found solution so far; |
| • | Iter as the total iterations number, |
| • | Citer as the current iteration, |
| • | T0 as the initial temperature, |
| • | TC as the current temperature, |
| • | |
| • | Mem as the memory that save the not accepted solution with length μ. |
| Fig. 1: | Proposed schematic representation of SA with memory |
| Fig. 2: | A pseudo-code for SAM |
The algorithm begins with a given initial solution. First, it generates n neighbors
from Ni neighborhood structures. The best (Sol1) and second
(Sol2) (based on the quality of solutions) are selected. The algorithm
accepts (Sol1) if its objective value is less than or equals the
current solution (Sol), whilse (Sol2) will be saved in the memory
(if the memory (Mem) is full replace the worst solution in Mem with (Sol2).
In case (Sol1) if (Sol) (i.e., the quality of Sol1 is
worse than Sol), the acceptance criteria (e(-Δ/T)) is applied.
If
When the non-improvement consecutive iterations are met, one solution is randomly selected from the Mem and a shaking procedure is applied on it to produce Solm. This will divert the search to other solution space, by randomly swap the highest penalties lecture with other lectures (free clash), when the difference Δ between the solution Solm and the current solution Sol is less than Costr (Eq. 1):
| (1) |
where, Iter is total iterations number, CIter is the current iterations, f (Sol) the current cost and Costr is the cost range to limit the cost value of Solm. Lu and Hao (2010) presented strategy called penalty guided perturbation to improve the best solution if the search cannot improve it. They employed the perturbation operator to reconstruct the obtained local optimum by selecting a number of the highly-penalized lectures randomly and applies swap or move. The difference between the proposed shaking procedure and (Lu and Hao, 2010) is in the ranking penalties of soft constraint violation. Lu and Hao (2010) ranked the lectures in non-increasing order according to their total penalties of soft constraint violations (for all soft constraints penalties). Whilst, the proposed shaking procedure assign the lectures in non-increasing way according to each soft constraint penalty independently, so that almost all lectures with high penalty will be involved in this shaking procedure during the search space.
Neighborhood structure: One of the important features of local search algorithm is the definition of its neighborhood (Lu and Hao, 2010). This study use three neighborhood structures denoted by NS1, NS2 and NS3. (Note: - all neighborhoods consider free clash):
NS1: Move one lecture from the current period to another
free position period.
NS2: Randomly swaps two different lectures from different
time slots and rooms.
NS3: Normally the selection mechanism in neighborhood structure
happens randomly (e.g:- select two lectures randomly which belongs to two different
rooms and slots). Thus, the search may need more time to reach good solution.
Hence, this study proposed neighborhood structure to minimize the random selection.
In NS3, the total soft constraints violations for each timeslot and
sum them up for all days in the week is calculated (Table 1)
and the highest penalty timeslot is swapped with randomly selected timeslot.
| Table 1: | Soft constraint violation for each period and time slot |
| Table 2: | Average penalty costs and CPU time for NS1, NS2 and NS3 neighborhood structures and their combinations over 35 independent runs |
Cooling schedule: The performance of SA depends heavily on the cooling schedule (Blum and Roli, 2003). This work used cooling scheme that was proposed by Lewis (2006) as follow:
where, β represents a parameter to control a value for λ. The resulting value for λ is used to influence the amount of concavity or convexity present in the cooling schedule. M represents the number of steps taken by temperature T0 to decrease to a value close to zero. In this experiment, the parameters are set based on the preliminary experiments, where T0 = 1500 and β- -0.99 as in Lewis (2006) study.
Experiment and result: This study test on 3 datasets instances categories. The first 4 instances (test 1-4) were previously used for the old version of the Curriculum-based Course Timetabling (CB-CTT) in the literature (Di Gaspero and Schaerf, 2006). The second 7 instances (DDS1-DDS7) proposed by Bonutti et al. (2008) and the third 21 competition instances from The Second International Timetabling Competition ITC 2007 track 3 (Gaspero et al., 2007). This work is programmed in vb.net 2010 on a PC Windows Vista platform with 2.10 GHz CPU and 4 GB RAM.
The experiment was first carried out to analyze the performance of the proposed neighborhood structure (NS3). Table 2 shows the results of the experiments that were carried out on the three neighborhoods and their different combinations. For comparison purpose, this experiment applied Steepest Descent (SD) with for the first 8 competition instances (Abramson et al., 1999). The average penalty cost and CPU time over 35 independent runs is reported in Table 2. From Table 2 one clearly finds that obtain much better quality solution. According to the results, starting from NS1 will decrees the costs and minimizes the CPU time more than from NS2. This result had encouraged this study to use this combination in the enhance SA.
Firstly, to make a fair comparison, the basic SA applied with geometric cooling schedule (Abramson et al.,1999) and compare it with the SA with the adopted cooling schema proposed by Lewis (2006) in Table 3. The SA with the adopted cooling schema performed better than the geometric cooling schedule almost in all instances, whereas geometric cooling schedule performed better in Comp 5 and Comp 10 but ties with the adopted cooling schema.
| Table 3: | Comparable results between SAs (adopted cooling schema and geometric cooling schema) average penalties costs over 30 indepe ndent runs |
| Table 4: | Comparison between different numbers of non-Improved iteration (average value of penalty costs over 25 runs) |
| Table 5: | Computational statistics results of the SAM algorithm over 30 independent runs under the ITC 2007 competition stop conditions |
Next, this study made preliminary experiments to find good number non improvement
consecutive iterations,
Results under ITC 2007 timeout condition: Table 5 illustrates the computational statistic of the proposed SAM algorithm based to the following performance indicators:- the best penalty cost (Best), the average penalty costs (Mean), median result (Median) and the standard deviation over 30 runs.
| Table 6: | Best results and comparison with the best known results under ITC 2007 timeout condition over 30 independent runs |
| Best results are bold | |
Results in Table 5 showed that SAM standard deviation is quite small and the mean penalty results is small as well.
Table 6 shows the comparison results of SAM with best known results under ITC 2007 timeout condition (http://tabu.diegm.uniud.it/ct/). The first column indicates the instances. Column 2-4 indicate the penalty of best, average results and average runs time in seconds over 30 runs on each instance for the SAM. Column 5-6 shows the penalty cost of the best known results and the approaches that obtained the best known results.
As shown in Table 6, SAM obtained competitive results with all best known approaches. For instance Comp 1, Comp 11, DDS2, DDS3, DDS5, DDS6, DDS7 and Toy, the optimal solutions are found (under the ITC 2007 timeout condition). Therefore, this study can conclude that the SAM algorithm is generally able to produce high quality solutions when compared to the best known results.
In the next experimentation, the experiments evaluate the performance of SAM with other algorithms in literature (Lu and Hao, 2010; Cesco et al., 2008; Muller, 2008; Lach and Lubbecke, 2008; Geiger, 2008; Clark et al., 2008), (M2 to M6) consecutively (Table 6). Best solutions cost is written in bold.
CONCLUSION
This study presented a new hybridization between simulated annealing with non-accepted solutions memory. The main idea of the hybrid SAM is to enhance the ability of escaping from local optimum. SA could be trapped in local optimum especially when the temperature is very low. When the search trapped in local optimum for a number of consecutive non-improvement solutions, SAM randomly select one solution from the memory which was generated and not-accepted in some recently visited iterations, to be the current solution . Thus, the search can jump to other promising region and escape from local optimum. Whilst, the memory and the proposed shaking procedure leads the search to avoid recycling and trapping in the same local optimum.
In this work, the SAM algorithm is evaluated on curriculum-based course timetabling problem track 3 of the Second International Timetabling Competition. The computational results showed that the SAM algorithm competes very well with reference algorithms and the best known results in the literature. Thus, the proposed SAM enhanced the SA performance by enhancing the ability of escaping from local optimum, which might lead to a good promising region.
In future works, the next study plan to use tabu list mechanism to save both not accepted and not visited solutions in order to avoid recycling and will test it on in real world course timetable dataset from Universiti Kebangsaan Malaysia (Faculty of Engineering case study).
ACKNOWLEDGMENT
The authors wish to thank Ministry of Higher Education for supporting this work under the FRGS Research Grant Scheme (FRGS/1/2012/SG05/UKM/02/11).