Hybrid particle swarm optimization transplanted into a hyper-heuristic structure for solving examination timetabling problem

摘要

Examination timetabling is a discrete, multi-objective and combinatorial optimization problem which tends to be solved with a cooperation of stochastic search approaches such as evolutionary algorithms (EAs) and heuristic methods such as sequential graph coloring heuristics. This research investigates the use of discrete particle swarm optimization (DPSO) for solving examination timetabling problem. A combination of mutation, specialist recombination operator and graph coloring heuristics are used to update position of particles in the DPSO. A new local search method, called two staged hill climbing, is proposed and is utilized to hybridize the DPSO algorithm. Three structures for the DPSO and three strategies to hybridize it are proposed. On one hand, since the proposed DPSO algorithms such as hyper-heuristics methods employ a strategy to manage a set of constructive low-level heuristics, they can be classified as hyper-heuristic systems and, on the other hand, the DPSO is a stochastic global optimization method from class of EAs. The proposed algorithms are tested on a set of Carter benchmark problems to set the parameters of algorithms and also to compare different methods. The obtained results demonstrate that the proposed hill climbing local search, in spite of its simplicity, has a better performance than original hill climbing method. Among different graph coloring heuristics, those of algorithms which employ the saturation degree heuristic lead to the better results. Also among different proposed algorithms, the first structure of DPSO and third strategy of hybridizing obtain a better performance than the other structures and strategies. In a later part of the comparative experiment, performance comparisons of the proposed algorithms with some other hyper-heuristic and EA methods are done. The obtained results confirm that the proposed hybrid algorithm has a better, or at least comparable, performance than other hyper-heuristic systems. Also it obtains the best results among hyper-heuristic systems on some problems. Also in comparison of other EAs, it has a completely comparable performance.