WSEAS Transactions on Computers
Print ISSN: 1109-2750, E-ISSN: 2224-2872
Volume 12, 2013
Hybridizing Genetic Algorithms and Particle Swarm Optimization Transplanted into a Hyper-Heuristic System for Solving University Course Timetabling Problem
Authors: ,
Abstract: In this paper, we use genetic algorithms (GAs), particle swarm optimization (PSO) and hybrid versions of them to solve university course timetabling problem (UCTP). A new crossover method called 2-staged n-point crossover by combining classic n-point crossover method and graph colouring heuristics is introduced which aims to generate free-conflict offspring. The hybrid algorithms are generated by adding a local search (LS), based on hill climbing (HC) method, on three global search algorithms i.e. the GA, the PSO and a combination of them called GAPSO. The proposed algorithms such as hyper-heuristic systems, manage a set of graph colouring heuristics as low-level heuristics in a hyper-heuristic strategy. The proposed algorithms are examined by 11 well-known benchmark problems. Experimental results demonstrate that the GA outperforms the PSO and the GAPSO algorithms, but the hybrid GAPSO algorithm has a better performance than the hybrid GA and hybrid PSO. Also all hybrid algorithms obtain a better performance than their non-hybrid competitors. However the GA has been widely applied to UCTP, to the best our knowledge the obtained results of GA in this paper are the first reported results on these databases which are competitive than results of other approaches. In a later part of the comparative experiments, a comparison of our proposed algorithms and 14 other approaches reported in the literature confirms that by considering the hybrid GAPSO as a hybrid hyper-heuristic, it is one of the best strategies for the hyper-heuristic systems on the UCTP proposed so far. Also results of the hybrid GAPSO in comparison of other hybrid algorithms proposed in the literature are completely comparable.
Search Articles
Keywords: Crossover, Genetic algorithm, Hybrid algorithm, Particle swarm optimization, University course timetabling, Hyper-Heuristic