Abstract: Usually, meta-heuristic approaches that use several neighbourhood structures can perform better than single neighbourhood structure. However, choosing a suitable neighbourhood structure to be applied during the search process is also a crucial decision. Therefore, this study proposes an adaptive neighbourhoods structure selection (AD-NS) mechanism that adaptively memorised the improvement strengths for each neighbourhood structure. The neighbourhood structure with the best improvement history will be employed to generate neighbour(s) for the current iteration. The hypothesis is, “if the improvement history of neighbourhood structure can affect the performance of neighbourhood structures selection mechanism and subsequently, the performance the applied meta-heuristic, then the meta-heuristic (i.e., Simulated Annealing (SA) in this case) with AD-NS will outperform the meta-heuristic (i.e., SA) with other neighbourhood structure selection mechanisms”. To prove this, the experiment is conducted by applying SA with AD-NS, SA with Token ring and SA with Union neighbourhood structure selection mechanisms; tested on Curriculum-Based Course Timetabling problem for the ITC-2007 track3 benchmark datasets. Results based on the average ranked, shows that SA with AD-NS approach obtained the fourth rank compared with other approaches reported in the literature. Statistical analysis on SA with AD-NS against SA with other neighbourhood structure selection mechanisms proved that the performance of SA with AD-NS is significantly better than SA with other neighbourhood structures selection mechanisms tested in this work. This indicates that the improvement history of neighbourhood structure can affect the performance of neighbourhood structures selection mechanism and subsequently, the performance the applied meta-heuristic.
INTRODUCTION
The definition of the neighbourhood structure plays a crucial decision in local search algorithm (Lu and Hao, 2010). For example, a good neighbourhood structure can positively influence the performance of Simulated Annealing (SA) (Moscato, 1993). Choosing a suitable neighbourhood structure or the size of neighbourhood are critical decisions, in improving the performance of SA (Eglese, 1990; Fleischer and Jacobson, 1999). Some researchers reported that SA with small neighbourhood size had performed better than large neighbourhood size (Cheh et al., 1991). Whilst, others proved that SA with large neighbourhood size had performed better than the smaller neighbourhood size (Ogbu and Smith, 1990). In addition, combining two or more different neighbourhoods is a powerful mechanism to increase the performance of searching algorithm (Xinchao, 2011). Thus, employing several neighbourhood structures may produce better results compared to single neighbourhood structure. However, the computational time might be increased due to the number of neighbours that need to be visited and perhaps disconnected neighbourhoods. Indeed, the question is, “how to select a suitable neighbourhood structure to be applied at each iteration?” There are many ways to select the neighbourhood structure, such as union neighbourhood structures (Di Gaspero and Schaerf, 2006) and token-ring search (Glover, 1989) selection mechanisms. Many works have investigated on the effect of neighbourhood selection mechanism to the performance of meta-heuristic search. For example Lu and Hao (2010) compared between union and token ring combinations (operators/selections) within tabu search meta-heuristic. They found that token ring selection mechanism outperformed union combination for all instances. Avanthay et al. (2003) have combined six neighbourhood structures to enhance their proposed Variable Neighbourhood Search (VNS). They switched from one neighbourhood structure to another one, when the current neighbourhood structure cannot improve the solution in several consecutive non improvement iterations. The neighbourhood structure was selected according to the solution quality, which was produced by the VNS algorithm for each neighbourhood structure. Abdullah et al. (2010) had applied a Round Robin (RR) algorithm in SA to control the selection of neighbourhood structures called dual-sequence SA (DSA) to solve post enrolment course timetabling problems. They showed that the performance of DSA is comparable with the state-of-the-art techniques. Triki et al. (2005) had presented an empirical study on the effect of neighbourhood structure selection to the performance of SA algorithm. Results showed that choosing a suitable neighbourhood is important to the performance of SA. In other work, Zhang et al. (2010) have applied SA with a new neighbourhood structure for high school timetabling problems. In order to search for the best neighbour, they performed a sequence of swaps between pairs of time slots. Recently, Kalender et al. (2012) have hybridised SA with an improvement oriented heuristic selection mechanism to solve a curriculum based course timetabling problem at Yeditepe University.
This shows that the decision to choose a suitable neighbourhood structure to be applied can affect the performance of applied meta-heuristic. Therefore, this work proposes an adaptive neighbourhood structure selection mechanism in SA algorithm (SA with AD-NS). SA with AD-NS will adaptively switches among the neighbourhood structures, guided by the improvement history of each neighbourhood structure. The applied neighbourhood structure will be rewarded if it can improve the quality of the current solution. Otherwise, it will be penalised to give better chance to the other neighbourhood structures to be selected. The hypothesis for this work is, “if the improvement history of neighbourhood structure can affect the performance of neighbourhood structures selection mechanism and subsequently, the performance of the applied meta-heuristic, then the meta-heuristic (e.g., SA in this case) with AD-NS will outperform the meta-heuristic (i.e., SA) with other neighbourhood structure selection mechanisms”.
PROBLEM DESCRIPTION
This work use the curriculum based course timetabling problem (CB-CTT) that is a variant of an educational timetabling problem, presented in track 3 of the Second International Timetabling Competition-ITC2007 track3 (Di Gaspero et al., 2007), (http://www.cs.qub.ac.uk/itc2007/). CB-CTT consisted of scheduling all lectures into weekly timetable, where each course lecture must be assigned to a period and a room in accordance to a given set of constraints, by satisfying the hard constraints and minimising the violation of the soft constraints. Hard constraint is mandatory in order to have a feasible timetable. Whilst, violation of soft constraints should be minimised in order to have good quality timetable.
The Constraints for CB-CTT ITC2007 track3 datasets: This problem has four hard constraints (H1-H4) and four soft constraints (S1-S4) presented by Di Gaspero et al. (2007) as follows:
| • | 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 into the same room at the same period |
| H3: | Conflicts. Lectures of courses in the same curriculum or taught by the same teacher cannot be schedule into the same period |
| H4: | Availability. If the teacher of a course is not available at a given period, then the lectures of the course cannot 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 |
Objective function: To evaluate the quality of the timetable, an objective function as proposed in Lu and Hao ( 2010) Eq. 1 is used to calculate the violations of soft constrains. Since, this is the minimisation problem, smaller objective value (penalty cost) is better:
min (f(X)) = F1+F2+F3+F4 |
(1) |
where, F1 to F4 are the penalties cost for violating the soft constrains (S1-S4). F1 is calculated by subtracting the capacity of the room from the number of students attending the lecture (if the student enrolment for the lecture is greater than the room capacity, i.e., violation of S1). F2 is the violation of the minimum working day for the lectures of a course (i.e., violation of S2). If the lectures of a course are not adequately spread, then the penalty value is calculated. This is done by subtracting the day gap between two lectures of the same course from the minimum numbers of day gap. F3 is the violation of room stability (i.e., violation of S3). If a lecture is assigned to more than one room, the violation is counted by subtracting one from the number of rooms that the lecture is assigned. F4 is the violation of curriculum compactness (i.e., violation of S4). A violation is counted if the lecture is not adjacent to any other lecture belonging to the same curriculum within the same day.
PROPOSED ALGORITHM
This work uses a standard SA but the aim is to enhance the performance of SA by employing several neighbourhood structures and proposes an adaptive neighbourhood structures selection mechanism.
Basic simulated annealing: Simulated Annealing (SA) is one of the oldest meta-heuristic algorithms that have strategy to avoid local minima, by allowing the bad quality solution to be accepted (with some probability). SA always accepts good quality neighbour solution; and probably accepts worse quality solutions using probability acceptance criteria, P(Si) = e-Δf/Ti. This probability function control the acceptance of neighbour solution s* based on the quality of s*, f(s*), with regard to the quality of the current solutions, f(s) and the current temperature Ti, where Δf = f(s*)-f(s). The current temperature Ti is reduced using a cooling schedule with a given cooling rate α for each iteration or level, until the temperature reaches final minimum temperature, Tmin (that is closed to zero). SA stops when Tmin is reached.
Adaptive neighbourhoods structure selection: This study proposed new neighbourhood selection mechanism (AD-NS) by adaptively switch among the neighbourhood structures during the search process. The objective of the proposed neighbourhood structure selector is to improve the performance of the search algorithm (i.e., SA in this work), by applying a suitable neighbourhood structure at a given time. Using the AD-NS, the suitable neighbourhood structure with the best improvement history will be employed. To test the idea, this study used two neighbourhoods structures denoted as NS1 and NS2.
| NS2: | Move one lecture from the current period to another clash free position period |
| NS2: | Randomly swaps two different lectures (without violating the hard constraints) |
The improvement strength (fitness) (after the nth iteration) of the employed and unemployed neighbourhood structure (at the nth iteration) are calculated using Eq. 2 and 3, respectively:
| (2) |
where, n is the number of the employed iterations; i is the ith neighbourhood structure that is employed at the nth iteration; f(Sol) is the quality of the incumbent solution; and Δ is the differences between the quality of the current solution f(Sol) and the trial solution f(Sol΄), Δ = f(Sol΄)-f(Sol).
In order to update the fitness of the unemployed neighbourhood structures and give them fair chance to be selected later, this work proposes Eq. 3 that subtracts Δ from it. In the minimization problem, the value of Δ is negative when the quality of trial solution is better than the quality of the current solution. Therefore, the fitness of the applied neighbourhood structure (Ni) will be stronger (lower value of F(Ni)n) if it managed to generate good quality neighbour (note: The lowest fitness value indicates better fitness), whilst the fitness of the unemployed neighbourhood become weaker. However, the fitness of the unemployed neighbourhood will become stronger if the applied neighbourhood structure failed to generate a good quality neighbour. Therefore, the unemployed neighbourhoods will have better chances to be applied at the next iterations, when the current employed neighbourhood failed to improve the quality of the current solution:
| (3) |
| Fig. 1: | The pseudo code of the SA with AD-NS selection mechanism |
where, i≠j and j is the unemployed neighbourhood structure at the nth iteration and ρ is a random number between 0 and 1.
When Δ is equal to zero, the unemployed neighbourhood structure improvement history will be updated by subtracting a random number between 0 and 1 from it fitness value, in order to give the unemployed neighbourhood structure higher chance to be selected at the next iteration. Whilst, the fitness of the employed neighbourhood structure (that was not performed well), is not changed. AD-NS applies one neighbourhood per iteration. Thus, the neighbourhood structure with the best fitness (i.e., the best improvement history/smallest fitness value) will be applied at the current iteration.
Simulated annealing with adaptive neighbourhood structures selection: Figure 1 shows the pseudo-code for SA that implemented with AD-NS selection mechanism. In this study, the initial temperature is initialized dynamically using a dynamic initial temperature by applying several iterations (at the early stage) and calculate the deviation average to determine a suitable initial temperature for each instance. For the cooling schedule, the amount of reducing the temperature value is adaptively adjusted according to the total number of iterations and the initial temperature in order to decide the decrement amount during the search process as in Tarawneh et al. (2013).
SA starts once the initial solution Sol is generated (randomly or using constructive technique). For the first iteration, both NS1 and NS2 neighbourhood structures are employed to equally generate k neighbour solutions of Sol. Then the best quality neighbours of each neighbourhood are selected to update the improvement strength (fitness) of each neighbourhood structure, respectively, using Eq. 1. After the first iteration, the neighbourhood structure with the best (minimum) fitness (calculated using Eq. 1 and 2) is selected to generate k neighbour solutions of Sol. The best neighbour, Sol’ that is generated by the selected neighbourhood structure is then selected for calculating the Δ (where Δ = f(Sol΄)-f(Sol)). The Δ is used to calculate the fitness of all the neighbourhood structures and acceptance criterion of the SA. The fitness of all neighbourhood structures (employed and non-employed) are updated using Eq. 1 and 2, accordingly. From line 11 until 24 in Fig. 1, the SA with AD-NS works similar as standard SA algorithm.
Statistical method: Since SA is a stochastic algorithm, the quality of the generated solutions are not normally distributed. This was tested using Kolmogorov-Smirnov. Therefore, the Wilcoxon Signed-Rank Test (i.e., a non-parametric test) with a 95% confidence level, is used for a statistical analysis on the results obtained by the tested approaches. This is performed to validate the Alternative Hypothesis, which is:
“If the improvement history of neighbourhood structure can affect the performance of neighbourhood structures selection mechanism and subsequently, the performance the applied meta-heuristic, then the meta-heuristic (i.e., SA in this case) with AD-NS will outperform the meta-heuristic (i.e., SA) with other neighbourhood structure selection mechanisms.”
EXPERIMENTAL SETUP AND RESULTS
Table 1 shows the parameters setting for the SA algorithms tested in this work. These parameter values were determined based on preliminary test. The experiments have been carried out (with 31 independent runs) to investigate the search capability for AD-NS in SA algorithm.
| Table 1: | Parameters values used for SA algorithms |
| The neighbours size is determined based on the primarily experiments | |
For comparison, this study used the standard SA as in Abramson (1991) with dynamic initial temperature and adaptive cooling schedule.
Table 2 shows a comparison results among SA with AD-NS (Δ = f(Sol΄)-f(Sol)), SA with token-ring (NS1→NS2) and SA with union (NS1 U NS2) neighbourhood structures selections under the ITC2007 track3 timeout condition (460 sec in this machine). It shows that AD-NS with SA outperformed the other neighbourhood structures selections across in all instances, (for all best, worst, mean and the standard deviation). A statistical analysis on the results (Table 3) is performed using Wilcoxon Signed-Rank Test in order to support the Alternative Hypothesis, which is:
“If the improvement history of neighbourhood structure can affect the performance of neighbourhood structures selection mechanism and subsequently, the performance the applied meta-heuristic, then the meta-heuristic (i.e., SA in this case) with AD-NS will outperform the meta-heuristic (i.e., SA) with other neighbourhood structure selection mechanisms.”
Table 3 showed that (in general) the performance of SA with AD-NS is statistically significant better than the performance of SA with other two neighbourhood selection mechanisms (token-ring and union). SA with AD-NS obtained better quality of solutions almost in all instances (except comp01 and comp11). The significance level in this test is 0.05, i.e., if p value is less than 0.05 then, the performance of SA with AD-NS is statistically significant better compared to token ring and union neighbourhood structures selection mechanisms.
| Table 2: | Experimental results of AD-NS, token ring and union neighbourhood structures combinations in SA over 31 independent runs on ITC2007 track3 datasets |
| Best results in bold, All the figures in column “Best”, “Worst” and “Mean” representing the quality of solutions for best, worst and mean for 31 runs | |
Results supported the hypothesis that AD-NS can enhance the performance of SA compared to token ring and union neighbourhood structures selections mechanisms (i.e., the alternative hypothesis is accepted).
| Table 3: | Statistical analysis (Wilcoxon Signed-Rank Test) for AD-NS against token ring and union neighbourhood structures selections in SA tested on ITC 2007 track3 datasets |
Finally, the performance of SA with AD-NS is compared against other approaches from the literature (Table 4) and the best know results under ITC2007 Track3 timeout condition. Table 4 showed that the SA with AD-NS can produce good quality solution compared with other approaches in the ITC 2007 Track3, under the time out condition which is equal to 460 seconds in this work. For example, SA with AD-NS managed to obtain the best known results in the comp1 and comp11 (small instances). For comp17 and 21, SA with AD-NS obtained the best results in comparison with other approaches compared in Table 4. Furthermore, it outperformed (Geiger, 2012; Clark et al., 2008) approaches for all instances.
According to the average results (Avg) in Table 4, the approaches in Table 4 is ranked. The smaller average ranked is better. For example, Muller (2009) is ranked first for 15 instances out of 21, (Lu and Hao, 2010) ranked second and SA with AD-NS approach obtained the fourth rank compared with others. According to the average ranked in Table 4, the SA with AD-NS approach demonstrated that AD-NS selection mechanism can enhance the performance of SA.
| Table 4: | Average and best results of the SA with AD-NS in comparison with the top five competitors and best know results from ITC 2007 Track3 |
| Best known results in bold; while the best results among approaches in italic, Hybrid approach (Muller, 2009), TS (Lu and Hao, 2010), M1: Third place winner for the ITC2007 track3 (Note: There is no publication for this work except in the ITC2007 track3 web site) (http://www.cs.qub.ac.uk/itc2007/index_files/finalists.htm), Threshold accepting local search (Geiger, 2012), Repair-based Local Search (Clark etal., 2008), Avg: Average, Best : Best, Best*: Best Known results under ITC2007 track3 timeout condition | |
CONCLUSION
This work proposed a new adaptive neighbourhood structures selection (AD-NS) mechanism to enhance the SA performance by adaptively select the suitable neighbourhood structure during the search process according to each neighbourhood structure improvement history. The performance of AD-NS in SA was evaluated by testing the approach on curriculum based course timetabling problem that was presented in track 3 of the Second International Timetabling Competition (ITC2007 track3). Results demonstrated that AD-NS can enhance the performance of SA compared to token ring and union neighbourhood structures selections mechanisms. This indicates that the improvement history of neighbourhood structure can affect the performance of neighbourhood structures selection mechanism and subsequently, the performance of the applied meta-heuristic. For the future work, AD-NS will be applied using more neighbourhood structures in other local search algorithms such as variable neighbourhood structure algorithm.
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).
\