An adaptive artificial bee colony and late-acceptance hill-climbing algorithm for examination timetabling

Abstract

The artificial bee colony (ABC) is a population-based metaheuristic that mimics the foraging behaviour of honeybees in order to produce high-quality solutions for optimisation problems. The ABC algorithm combines both exploration and exploitation processes. In the exploration process, the worker bees are responsible for selecting a random solution and applying it to a random neighbourhood structure, while the onlooker bees are responsible for choosing a food source based on a selection strategy. In this paper, a disruptive selection strategy is applied within the ABC algorithm in order to improve the diversity of the population and prevent premature convergence in the evolutionary process. A self-adaptive strategy for selecting neighbourhood structures is added to further enhance the local intensification capability (adaptively choosing the neighbourhood structure helps the algorithm to escape local optima). Finally, a modified ABC algorithm is hybridised with a local search algorithm, i.e. the late-acceptance hill-climbing algorithm, to quickly descend to a good-quality solution. The experiments show that the ABC algorithm with the disruptive selection strategy outperforms the original ABC algorithm. The hybridised ABC algorithm also outperforms the lone ABC algorithm when tested on examination timetabling problems.

1 Introduction

The examination timetabling problem (ETTP) is one of the most difficult combinatorial optimisation problems and is considered to be $NP$-hard (Cooper and Kingston 1995; Schaerf 1999), being prevalent in many academic institutions (Carter et al. 1996). The ETTP can be considered as the process of allocating a set of examinations to a limited number of time slots while satisfying a predetermined set of constraints (Burke et al. 1996; Qu et al. 2009). A large number of approaches have been described and discussed for solving such examination timetabling problems, which can be classified into two main types: local-search-based and population-based approaches (Qu et al. 2009). Interested readers can find more details about examination timetabling research in Abdullah et al. (2009), Burke and Newall (2004), Burke et al. (1996); Burke et al. (2010), Burke et al. (2004), Carter (1986), Lewis (2008) and Turabieh and Abdullah (2011a); Turabieh and Abdullah (2011b).

Observation of group behaviours in natural self-organised systems motivated researchers to develop population-based approaches, which are known as swarm intelligence. Examples of population-based approaches for examination timetabling problems include the following: ant colony (Dowsland and Thompson 2005), particle swarm optimisation (Chu et al. 2006), fish swarm optimisation algorithm (Turabieh and Abdullah 2011a, b) and honeybee mating optimisation (Sabar et al. 2009). Swarm intelligence aims to simulate the behaviour of such self-organised systems. In particular, the intelligent behaviour of honeybees motivated the development of metaheuristic algorithms that model such behaviour in order to find better solutions to optimisation problems. Such honeybee algorithms can be classified based on three different groups of behaviour (Baykasoglu et al. 2007), i.e. foraging, marriage and queen bee behaviours. Algorithms that are based on the foraging behaviour of honeybees are applied to solve optimisation problems, e.g. the artificial bee colony (ABC), bee algorithm (BA) and bee colony optimisation (BCO). These three algorithms have different behaviour models for the drone bees.

In this paper, we study the ABC algorithm that was first proposed by Karaboga (2005) for solving numerical optimisation problems. A further version of the ABC algorithm was later updated and proposed by Karaboga and Basturk (2007) for solving constrained optimisation problems. This algorithm has drawn great attention from researchers (Bao and Zeng 2009; Kang et al. 2009; Karaboga and Akay 2009; Pham et al. 2006; Singh 2009). The ABC algorithm works based on local communication between three groups of bees (i.e. scouts, workers and onlookers) and with their environment, contributing to the collective intelligence of the bee colony (Karaboga 2005).

This paper focusses on hybridising the ABC and the late-acceptance hill-climbing (LAHC) algorithm. The LAHC algorithm is a local search method that was introduced by Burke and Bykov (2008). The algorithm has the capability to quickly explore the search space and accept a worse solution based on adaptive criteria using fewer parameters, in contrast to the ABC algorithm, which only accepts an improved solution. This capability is believed to be able to prevent the algorithm from becoming stuck in local optima. Thus, better solutions can be obtained.

In addition, the performance of the ABC algorithm can be enhanced by using a selection strategy and a self-adaptive mechanism as previously presented by Alzaqebah and Abdullah (2011a); Alzaqebah and Abdullah (2011b).

This paper is organised as follows: Sect. 2 presents the examination timetabling problem and its formulation, while the artificial bee colony algorithm is presented in Sect. 3. The proposed approach is discussed in Sect. 4. The experimental results are presented in Sect. 5, and conclusions are given in Sect. 6.

2 Problem description and formulation

In this paper, the problem description is divided into two distinct parts: the Toronto datasets and the International Timetabling Competition (ITC2007) datasets, as discussed below:

2.1 The Toronto datasets

These datasets were introduced by Carter et al. (1996), and were considered as uncapacitated examination timetabling problems, i.e. where room capacity requirements are not taken into account. The description of the problem is adapted from Burke and Newall (2004). In these datasets the problem consists of the following inputs:

• N is the number of examinations.

• $E_{i}$ is an examination, $i\in \{1,\ldots , N\}$.

• $T$ is the given number of available time slots.

• $M$ is the total number of students.

• $C = (c_{ij})_{N \times N}$ is the conflict matrix, where each element denoted by $c_{ij}$, $i, j \in \{1{,\ldots , N}\}$ is the number of students taking examination $i$ and $j$.

• $t_{k}$ ($1\le t_{k} \le T$) specifies the assigned time slot for examination $k$ ($k \in \{1,\ldots ,N\}$).

The minimisation of the fitness function in Eq. 1 is formulated to space out students’ examinations throughout the examination period:

$$\begin{aligned} \mathrm{Min} \frac{\sum \nolimits _{i=1}^{N-1} F_1 (i)}{M}, \end{aligned}$$

(1)

where

$$\begin{aligned} F_1 (i)=\sum \limits _\mathrm{j= i+1}^\mathrm{N} c_{ij} \cdot \mathrm{Proximity} (t_i, t_j) \end{aligned}$$

(2)

with

$$\begin{aligned} \mathrm{Proximity}(t_i, t_j)= \left\{ \begin{array}{ll} 2^{5}/2^{|t_i -t_j|} &{} \quad \mathrm{if}\; 1\le |t_i -t_j |\le 5 \\ 0 &{} \quad \mathrm{otherwise} \\ \end{array} \right. \end{aligned}$$

(3)

subjected to

$$\begin{aligned} \sum \limits _{i=1}^{N-1} \sum \limits _{j=i+1}^N c_{ij} \cdot \gamma (t_i, t_j)=0, \end{aligned}$$

where

$$\begin{aligned} \gamma ( t_i, t_j)=\left\{ \begin{array}{ll} 1 &{} \quad \mathrm{if} \; t_i =t_j \\ 0 &{} \quad \mathrm{otherwise} \\ \end{array}\right. \end{aligned}$$

(4)

Equation 2 represents the penalty for examination $i$, which is given by the proximity value multiplied by the number of students in conflict. Equation 3 represents a proximity value between two examinations (Carter et al. 1996). Equation 4 represents a clash-free requirement so that no student is allocated to sit more than one examination at the same time. The clash-free requirement is considered to be a hard constraint.

Table 1 presents the details of the Toronto datasets (Qu et al. 2009).

Table 1 Toronto datasets

2.2 The International Timetabling Competition (ITC2007) datasets

ITC2007 introduced three tracks of problems: examination timetabling, curriculum-based course timetabling and post-enrolment course timetabling problems. In this paper, the focus is on the first track, i.e. the examination timetabling problems, which include a number of real-world constraints. The details of the datasets are given in Table 2 followed by a set of hard and soft constraints, listed in Tables 3 and 4, respectively (McCollum et al. 2010).

Table 2 ITC2007 examination datasets

Table 3 Hard constraints

Table 4 Soft constraints

A feasible timetable is one where each exam is assigned to a period and room, and there is no violation of hard constraints. The objective is to minimise the violation of soft constraints as given in Eq. 5 (McCollum et al. 2010).

$$\begin{aligned}&\min \sum \limits _{s\in S} \left( W^{2\mathrm{R}} C_\mathrm{S}^{2\mathrm{R}} +W^{2\mathrm{D}} C_\mathrm{S}^{2\mathrm{D}} +W^\mathrm{PS} C_\mathrm{S}^\mathrm{PS} \right) \nonumber \\&\quad +\left( W^\mathrm{NMD} C_\mathrm{S}^{2\mathrm{NMD}} +{W}^\mathrm{FL} {C}^\mathrm{FL}+{W}^\mathrm{P} {C}^\mathrm{P}+ {W}^\mathrm{R}{C}^\mathrm{R}\right) .\qquad \end{aligned}$$

(5)

Each dataset has its own set of weights as presented in Table 5 (McCollum et al. 2010).

Table 5 Associate weights of the ITC2007 collection of examination datasets

3 Artificial bee colony (ABC) algorithm

3.1 Basic artificial bee colony (ABC) algorithm

The ABC algorithm was originally developed based on the foraging behaviour of real honeybees in finding and sharing information on food sources in their hives (Kang et al. 2009; Karaboga and Basturk 2007, 2008; Karaboga 2009; Pham et al. 2006; Bao and Zeng 2009).

The ABC system consists of three groups of agents (scout, worker and onlooker bees). In the ABC algorithm, the position of a food source represents a possible solution, and the quality of nectar in the food source corresponds to the quality (fitness value) of this solution. The number of worker bees is equal to the number of solutions in the population. Table 6 illustrates the analogy between the natural and artificial bee colonies.

Table 6 Analogy between natural and artificial bee colonies

The algorithm begins with a population of randomly generated solutions (or food sources); then, steps 1–4 (in Fig. 1) are repeated until a termination criterion is met (Karaboga 2005, 2009).

Fig. 1

Original ABC search algorithm

The search process of the original ABC algorithm starts with initialisation of the population (food sources). After the initialisation, the worker bees adjust the food source position in their memories and start to discover the position of nearby food sources (step 1). If the quality of nectar in the new food source is higher than the previous food source, the bees memorise the position of the new source and forget the old one. After all the worker bees have completed the search process, they share the information on the sources with the onlooker bees by doing a wiggle dance. Each onlooker bee watches the dance, chooses one food source, and searches locally in the neighbourhood of the selected food source (step 2). In step 3, the scout bees find the abandoned sources and replace them by randomly produced new food sources. Finally, the algorithm memorises the best food source found so far (step 4).

3.2 The selection process

In the original ABC algorithm, the onlooker bees applied a stochastic selection strategy based on roulette-wheel selection to select a food source based on the information gathered from the worker bees, which can be summarised as follows:

• (i) Calculate the value of $\mathrm{fit}_i$ as follows:

  $$\begin{aligned}&\mathrm{fit}_i =\frac{1}{1+f_i }, \end{aligned}$$

  (6)

  where $f_{i}$ is the fitness value of the $i$th food source. ($f$ is calculated using Eq. 1 or 5 for the Toronto or ITC2007 datasets, respectively.)

• (ii) Calculate the probability $P_i$ as follows:

  $$\begin{aligned}&P_i =\frac{\mathrm{fit}_i }{\sum \nolimits _{i=1}^\mathrm{SN} \mathrm{fit}_i}, \end{aligned}$$

  (7)

  where SN is the number of food sources and $P_i$ is the probability of the $i$th food source.

• (iii) Finally, from all the solutions (food sources), select a candidate solution with probability $P_i$ using roulette-wheel selection as discussed in Holland (1975).

There are two problems when using the basic ABC selection strategy as stated in Bao and Zeng (2009): (i) The super-individual is selected too often, which makes the whole population tend to converge towards its position. This will cause loss of diversity because the same solutions are selected too often; (ii) When all the solutions converge to the same area (because of the loss in diversity), the new generated solution will be from the same area as these solutions, so it is not guaranteed that the generated solution will be better than the existing one. Furthermore, this generated solution cannot be added to the current population. Consequently, the algorithm becomes stuck in a local optimum, thus preventing a better solution from being found. To alleviate these problems, a disruptive selection strategy, as introduced by Kuo and Huang (1997) and explained in Sect. 3.2, is therefore applied.

The findings from our previous work in Alzaqebah and Abdullah (2011a) showed that the ABC algorithm with the disruptive selection strategy is able to explore the search space better than either the original ABC algorithm or the ABC algorithm with tournament and rank selection strategies. The tournament selection strategy randomly selects a number of solutions and compares them based on a probability. The solution with the highest fitness value is chosen. In the rank selection strategy, the solutions are ranked based on the fitness values, so it is biased towards solutions with higher rank (i.e., better fitness). Meanwhile, the disruptive selection strategy gives preference to both low- and high-quality solutions, and tries to retain population diversity by improving the worse-fitness solutions concurrently with the high-fitness solutions. This motivated us to use the disruptive selection strategy within the ABC algorithm in this work.

Disruptive selection provides more chances for higher and lower individuals to be selected by changing the definition of the fitness function as shown in Eq. 8 (Kuo and Huang 1997).

$$\begin{aligned} \mathrm{fit}_i =|f_i - \overline{f_i} |P_i =\frac{\mathrm{fit}_i}{\sum \nolimits _{i=1}^\mathrm{SN} \mathrm{fit}_i}, \end{aligned}$$

(8)

where $\overline{f_i}$ is the average value of the fitness function $f_i$ of the individuals in the population.

4 The proposed algorithm

4.1 Neighbourhood search operations

In this paper, the following neighbourhood operations are employed to enhance the search algorithm performance (adapted from Abdullah and Burke 2006; Abdullah et al. 2007a, b):

• Nbs1 Select two examinations at random and swap their time slots (including rooms if rooms are available) feasibly.

• Nbs2 Select a single examination at random and move to a new feasible time slot (including a new room if a room is available).

• Nbs3 Select four examinations randomly and swap the time slots (including rooms if rooms are available) between them feasibly.

• Nbs4 Select two examinations at random and move to new random feasible time slots (including random feasible new rooms if rooms are available).

The neighbourhood is selected by using a self-adaptive method as discussed in Sect. 4.2. Note that, for the ITC2007 datasets, the room is considered to be included in the above neighbourhood operators.

4.2 Self-adaptive method for neighbourhood search

During the search processes performed by the worker and onlooker bees, a self-adaptive strategy is applied in finding the neighbouring food sources, which is explained as follows (Pan et al. 2011):

• (i) The self-adaptive method starts by filling a neighbour list (NL) with the four neighbourhood operations (as in Sect. 4.1) that are randomly selected. Note that the list NL with a specified length is generated previously.

• (ii) During the search process, one neighbourhood operation is taken from NL and is used to generate a new food source for a worker or onlooker bee. If the new food source is better than the current one, this approach inserts the neighbourhood operation into a new list known as the winning neighbouring list (WNL). The process is repeated until NL becomes empty.

• (iii) When NL becomes empty, 75 % of NL is refilled from the WNL list, the remaining 25 % is refilled randomly from the four neighbourhood search operations, and WNL is reset to zero. If WNL is empty, then the most recent NL is used again (Pan et al. 2011).

By using the self-adaptive method, suitable neighbourhood operations are learned and the winning ones are reused later. The chance of using the winning neighbourhood operations is higher than for others due to the fact that the NL list is 75 % filled from WNL. This method also has some randomness, i.e. 25 % of the NL. In this paper, the length of NL is set to 200 as stated in Pan et al. (2011). The details of the self-adaptive method can be found in Alzaqebah and Abdullah (2011b).

4.3 Late-acceptance hill climbing (LAHC)

The simple local search method LAHC is embedded into the basic ABC algorithm in order to quickly explore the search space in the ABC algorithm and prevent it from becoming stuck in local optima. This is due to the use of a greedy acceptance criterion in the basic ABC that only accepts an improved solution and eliminates the worst.

LAHC seems to be as fast as simple hill climbing but more powerful. This is due to the fact that LAHC is able to accept a worse solution based on intelligent use of an adaptive memory to keep information from previous iterations and reuse it later (Burke and Bykov 2012).

The main idea behind the LAHC method is based on a memory $\hat{C}$ (LAHC list) of size $L$ that is used to memorise the fitness values of the previous solutions. During the search process, the acceptance decision is made according to a comparison between the candidate solution and the previous solution obtained at the $L$th step, as follows: the candidate solution is accepted if its fitness value is better than or equal to the fitness value in the list $\hat{C}$ with index $v$ (the virtual beginning of the list). The virtual beginning ($v$) is calculated dynamically as the remainder of the integer division of the current iteration number $I$ by the length ($L$) (see Eq. 9).

$$\begin{aligned} v = I\mod L. \end{aligned}$$

(9)

Figure 2 (lines 27–49) shows the pseudo-code for the LAHC algorithm (Burke and Bykov 2012). The stopping condition used in this algorithm is described in Sect. 5.

Fig. 2

Pseudo-code for ABC with the LAHC algorithm

4.4 Adaptive artificial bee colony with LAHC algorithm

Figure 2 illustrates the pseudo-code that represents the approach embedding the LAHC algorithm, as used in this paper.

As shown in Fig. 2, the algorithm starts with a feasible initial solution, as described in Sect. 4.5. The population is initialised as follows: (i) select a number of examinations at random and swap their time slots and/or rooms; (ii) select a number of examinations at random and move them to feasible time slots and/or rooms. There are three processes in each iteration. In the first process, the worker bees work on random solutions and apply neighbourhood operators based on the self-adaptive method (as explained in Sect. 4.2) to all solutions in the population in order to find more profitable ones.

In the second process, the solutions are arranged based on the profitability. The onlooker bees select a solution based on one of the three selection strategies (as explained in Sect. 4), and then a local search (LAHC) is utilised (as explained in Sect. 4.3). Finally, in the last process, the scout bees determine the abandoned food source (i.e. the food source that has been visited by all other bees without improvement) and replace it with a new food source (which is generated as the food source when the population is initialised).

4.5 Initial solution construction

The explanation of the application of two constructive heuristic algorithms in constructing the feasible initial solutions for the Toronto and ITC2007 datasets is given below:

• Toronto datasets: A largest degree graph colouring heuristic (Carter et al. 1996) is used to generate initial solutions.

• ITC2007 datasets: The examination with the largest number of hard constraints is scheduled first (step 1). Then, the largest degree heuristic (Carter et al. 1996) is applied by randomly selecting a time slot and a room that satisfy the hard constraints (step 2). If the examination cannot be scheduled to a specific room, then it is allocated to any randomly selected room. In some cases, a feasible timetable can be obtained after employing these two steps. However, if a feasible initial solution is not obtained, certain exams are moved (into different time slots and/or rooms) or swapped until feasibility is achieved (step 3).

5 Simulation results and comparison

In all our experiments, three different modifications of the ABC algorithm were investigated: (i) the ABC algorithm based on disruptive selection (denoted DABC), which emphasised the selection strategy chosen based on the experimental results presented in Sect. 5.1; (ii) the DABC algorithm with the self-adaptive method for neighbourhood search (denoted SA-DABC); and (iii) SA-DABC with a local search (LAHC) (denoted LAHC-SA-DABC).

The performance of these modifications was compared with the basic ABC algorithm to show the effects of employing the different modifications. Table 7 presents the final setting of the parameters, which were experimentally chosen from a total of ten runs to obtain average results (note that the experiments were carried out on $\hbox {Intel}^{\circledR }\,\hbox {Core}^{\textsc {TM}}$ i3 processors).

Table 7 Parameters: final setting

Note that the length of the LAHC list of 500 is adopted from Burke and Bykov (2008). The stopping condition for LAHC is 500 iterations, or until there is no more improvement after a number of non-improved moves (set to 50 in this work).

5.1 Toronto dataset experimental results

This section presents a comparison of the performance among the basic ABC, DABC, SA-DABC and LAHC-SA-DABC algorithms when tested on the Toronto datasets, as presented in Table 8. Note that all the algorithms in Table 8 use the same computational resources. The best results are highlighted in bold. Note that these results were obtained from 11 independent runs and the central processing unit (CPU) times are between 300 and 9,600 s based on $\hbox {Intel}^{\circledR }\,\hbox {Core}^{\textsc {TM}}$ i3 processors.

Table 8 Results of comparisons between the algorithms on the Toronto datasets

The comparison in Table 8 shows that the three modified versions of the basic ABC algorithm perform better than the lone basic ABC algorithm. From Table 8, it can also be deduced that the disruptive selection strategy (DABC) outperforms the lone basic ABC algorithm. Use of the self-adaptive method to select the neighbourhood search operations further enhances the quality of the solutions. Applying the local search (LAHC algorithm) within the SA-DABC aids the algorithm to produce better solutions.

Figure 3 shows the resulting convergence graphs when applying the basic ABC, DABC and LAHC-SA-DABC algorithms on the Toronto datasets.

Fig. 3

Convergence graphs for the Toronto datasets

The lines in the graphs represent the trends between the number of iterations and the solution quality (penalty). These graphs show that the quality of the solution obtained by the basic ABC algorithm was greatly improved by the modifications, whereas the convergence of the lines in these graphs shows how the ABC, DABC and LAHC-SA-DABC algorithms explore the search space.

The behaviour of the algorithms is similar at the beginning of the search, where improvement of the solutions can be easily obtained. However, later, when the search becomes steady, it becomes harder to improve a solution. Regarding the effect of the LAHC algorithm, it can be easily seen that it is more flexible in accepting worse solutions, which later provides a better chance of finding a better solution compared with the ABC and DABC algorithms. It can be concluded that employing the local search (LAHC in this case) within DABC helps to descend quickly to high-quality solutions. In addition, the self-adaptive method for selecting neighbourhood search operations also helps the algorithm to determine the best neighbourhood structure, unlike selecting a neighbourhood structure at random as applied in ABC and DABC. This is indicated by the greater improvement in the fitness value with the self-adaptive mechanism.

5.2 International Timetabling Competition (ITC2007) dataset experimental results

The performance of the basic ABC, DABC, SA-DABC and LAHC-SA-DABC algorithms was also tested on the International Timetabling Competition (ITC2007) datasets. Table 9 presents a comparison of the results produced by these algorithms. The best results are highlighted in bold. Note that these results were obtained from 11 independent runs with a stopping condition of 460 s (as a result of using the competition computation tools to determine the “time limit” based on $\hbox {Intel}^{\circledR }\,\hbox {Core}^{\textsc {TM}}$ i3 processors).

Table 9 Results of the comparisons between the algorithms on the ITC2007 datasets

Table 9 shows that, once again, there is a significant improvement as ABC progresses to DABC, then to SA-DABC and finally to LAHC-SA-DABC.

The graphs in Fig. 4 show the status of the improvement of the population for the ABC, DABC and LAHC-SA-DABC algorithms. The diamond symbol in the graphs indicates how the initial population was spaced throughout the search process, and the triangle symbol represents the improved solutions in the population after 460 s. From this figure, it can be concluded that the DABC and LAHC-SA-DABC algorithms improved the solutions of the population. This can be observed in the spacing of the triangle symbols for the DABC and LAHC-SA-DABC algorithms, which are located much closer to each other. This indicates the closeness of the quality of the solutions in the population, unlike the spacing found in the lone basic ABC, which appears to be more scattered.

Fig. 4

Convergence graphs for three datasets (Exam_2, Exam_4 and Exam_5)

Figure 5 shows the behaviour of the proposed algorithms during the search process when tested on the ITC2007 datasets. Again from this figure, it can be easily seen that the use of the stochastic selection strategy in the basic ABC algorithm can lead to premature convergence of the algorithm and limits the search scope by repeatedly choosing only high-quality individuals. This can be noted by the curve representing DABC, which shows a downward slope that is steeper than for the basic ABC algorithm. Later, when both the local search and self-adaptive method are added to the algorithm, it is obvious from the presented figures that the embedded local search proves to be the dominant factor in obtaining better solutions in the ABC algorithm, where the local search helps to intensify the selected solution obtained by the onlooker bees during the exploitation process (as shown in Fig. 2).

Fig. 5

Convergence graphs for the ITC2007 datasets

Based on the graphs presented in Fig. 5, it can be seen that the ABC and DABC algorithms reach the stopping condition at about 300–320 iterations, but the LAHC-SA-DABC algorithm reaches the stopping condition at about 200–300 iterations (given the same stopping condition). This shows that, even with a smaller number of iterations (representing a smaller number of candidate solutions), the LAHC-SA-DABC algorithm is still able to obtain better results. It is believed that this is due to the ability of the adaptive mechanism in selecting the correct neighbourhood search operations (based on the quality of the current solution in hand rather than a random selection of neighbourhood search operations), and the embedded local search can further improve the performance of the algorithm in finding better solutions. Thus, these results clearly show the effectiveness (in terms of the quality of the solution obtained in a smaller number of iterations) of the modified algorithm compared with the basic ABC approach.

It is also observed that the ABC algorithm with the disruptive selection strategy is able to better explore the search space and transport all the solutions to converge together. The introduction of the self-adaptive strategy (compared with the stochastic selection strategy) in selecting neighbourhood structures manages to help the algorithm to escape from local optima. The results from Table 9 also show that the LAHC-SA-DABC algorithm is able to obtain better solutions compared with the other proposed approaches on all the tested datasets.

5.3 Results analysis and comparison with the best known results for the Toronto datasets

A comparison between the best results obtained from the tests run in this paper, i.e. using LAHC-SA-DABC, with the best known results (the three best approaches from the survey by Qu et al. (2009), i.e. Caramia et al. (2009), Yang and Petrovic (2005) and Burke and Bykov (2008)) for the Toronto datasets is presented in Table 10. The best results are highlighted in bold. In addition, statistical analysis of the LAHC-SA-DABC and the best literature approaches was conducted to identify any significant differences between them. These are presented in Tables 11 and 12.

Table 10 Toronto datasets: experimental comparisons with the best approaches

Table 11 Average (Friedman) ranking of the algorithms on the Toronto datasets

Table 12 Adjusted (Friedman) $p$ values on the Toronto datasets

For the statistical analysis, the Friedman test was first employed, followed by the Holm and Hochberg tests as post hoc methods (if a significant difference was detected) to obtain the adjusted $p$ value for each comparison between a control algorithm (the best performing one) and the rest (Garcia et al. 2010, 2009). Table 11 summarises the ranking obtained by the Friedman test, where the lowest rank reflects the best algorithm. Note that Caramia et al. (2009) were not included in the statistical analysis because their average values are not available.

The $p$ value computed by the Friedman test was $0.0018$, which is below the critical level ($\alpha =0.05$). This value shows that there is a significant difference in the observed results. The post hoc methods (Holm and Hochberg tests) were also applied for the LAHC-SA-DABC algorithm. Table 12 presents the adjusted (Friedman) $p$ value, where the Friedman test considers the Burke and Bykov algorithm as a control algorithm.

The Holm and Hockberg procedures show a significant difference when using the Burke and Bykov algorithm as the control. The LAHC-SA-DABC algorithm is better than the Yang and Petrovic algorithm and comparable to the Burke and Bykov algorithm, with $\alpha = 0.05$ and $\alpha = 0.01$ (1/3 algorithms).

This comparison with the best known results shows that, even though these tests were unable to beat any of the best known results in the literature, they were still able to produce “good enough” solutions.

5.4 Results analysis and comparison with the best known results on the International Timetabling Competition (ITC2007) datasets

Table 13 compares the proposed algorithm with the four best approaches in the literature. Note that these approaches and the approach employed here use 11 runs for each dataset and the same CPU time (as set in the ITC2007 computation rule). The best results are highlighted in bold.

Table 13 ITC2007 datasets: experimental comparison with the best approaches

The LAHC-SA-DABC algorithm is able to obtain solutions that are better than some of those obtained with the compared approaches, such as those of Atsuta et al. and Pillay, on all the tested datasets. It is highlighted here that the difference between these results and the best known results in the literature is in the range of 5.2–26.4 %.

The results were also analysed and compared against five winners of the International Timetabling Competition 2007 that can be found at http://www.cs.qub.ac.uk/itc2007/ as listed below:

• First place: Tomas Müller

• Second place: Christos Gogos

• Third place: Mitsunori Atsuta, Koji Nonobe and Toshihide Ibaraki

• Fourth place: Geoffrey De Smet

• Fifth place: Nelishia Pillay

Friedman’s test was applied to the ITC2007 datasets, yielding a $p$ value of 9.425E-6, which is below the significance level of $\alpha = 0.05$, showing that there is a significant difference in the observed results.

Table 14 presents the average algorithm rankings found by the Friedman test, where a lower value indicates a better rank.

Table 14 Average (Friedman) rankings of the algorithms on ITC2007

Table 15 presents the adjusted (Friedman) $p$ value and the further results of the post hoc methods (Holm and Hochberg tests).

Table 15 Adjusted (Friedman) $p$ values on the ITCC2007 datasets

5.5 Box and whisker plots for the Toronto and ITC2007 datasets

Figures 6 and 7 show box and whisker plots for the Toronto and ITC2007 datasets, respectively, comparing the distribution percentiles for the LAHC-SA-DABC algorithm. Each box has lines at the lower quartile, the median and the upper quartile for the set of 11 runs.

Fig. 6

Box and whisker plots obtained for LAHC-SA-DABC on the Toronto datasets

Fig. 7

Box and whisker plots obtained for the LAHC-SA-DABC algorithm on the ITC2007 datasets

The figures show less dispersion of the solution points, particularly for the upper and lower quartiles, in Figs. 6 (car91, car92, hec92I and uta92I datasets) and 7 (Exam_2, Exam_5 and Exam_6). The LAHC-SA-DABC algorithm generally finds good-quality solutions for both problems. In all the Toronto datasets (Fig. 6), the median lies between the best and worst runs, and their qualities are closer than for ITC2007, because of the complexity of the problem.

6 Conclusions and future work

The primary aim of this paper is to enhance the performance of the basic ABC algorithm by use of a disruptive selection strategy (DABC), a self-adaptive strategy for selecting neighbourhood structures and local search algorithms (late-acceptance hill climbing, in this case). The experimental results demonstrate that the LAHC-SA-DABC algorithm outperforms other modifications of the ABC algorithm and is comparable to state-of-the-art approaches when tested on examination timetabling problems. The experimental results also show that, with the disruptive selection strategy, the solutions in the population tend to converge together. In future research work, it is suggested to investigate the effect of these modifications on other categories of honeybee algorithms and to test their performance on a broader range of timetabling problems.