Heuristic Evolutionary Algorithms For Examination Timetabling Problems

The timetabling optimization is the hotspot in scheduling area, which has been widely used in real applications, from military affairs to times schedules of school or hospital. The study of timetable optimization would have great implications for the country, the society and individuals. This thesis analyzes main problems of solving examination timetabling problems. For example, the direct coding might have some weaknesses; some evolutionary operators and fitness functions are not suitable for optimizing hard and soft constraintssimultaneously; the traditional single-objective modeling is inefficient, and so on. We make great effort on designing several effective evolutionary algorithms by employing hyper-heuristic approaches, co-evolutionary strategies and multi-objective optimization theories. The major contributions are outlined as follows:Getting the inspiration from hyper-heuristics and evolutionary, a memetic algorithm based on hyper-heuristics (MAHH) was proposed for solving examination timetabling problems in chapter 2. The proposed memetic algorithm based on hyper-heuristics is a hybrid algorithm which combines hyper-heuristics and evolutionary algorithm. Instead of using the traditional way for directly individuals searching, we employ an indirectly searching method. Heuristic lists generated by traditional evolutionary strategies could find potential individuals. This indirectly searching method obtains a better search performance when compared with the traditional directly searching method. Moreover, MAHH designs a local search strategy that the mutation is applied on individuals directly. Experiment results indicate that the proposed algorithm outperforms other compared algorithms on 11 problems. Moreover, the proposed method performs better than seven traditional methods which were designed on the basic of hyper-heuristics on three problems.A memetic algorithm based on double evolutionary strategies (MADES) for examination timetabling problems is proposed in chapter 3. Using the same evolutionary operator and fitness function is not suitable for solving optimization problems in examination timetabling problems. To overcome this problem, different evolutionary operators and fitness functions are designed for two different evolutionary spaces. The lack of feasible individuals could be effectively improved by using clone operator. Experimental results show that these operators have a positive impact on the evolutionary search. Compared with several classical methods for examination timetabling problems, the proposed algorithm achieves comparable results on most test problems.In chapter 4, we propose an adaptive co-evolutionary memetic algorithm (ACMA) for solving examination timetabling problems. ACMA employs two evolutionary spaces. Evolution strategy based on both hyper-heuristics and traditional evolution strategy are used for optimizing soft and hard constraints, respectively. Besides, an adaptive operator is proposed to use computing resourceseffectively. The major contribution of the designed adaptive operator is that the population adaptively selects appropriate search space during the evolution, which makes the evolution search become more purposeful and directional. Therefore, the unnecessary computing resource existing in random search is avoided effectively. Experimental results demonstrate that evolutionary’ strategy based on hyper-heuristics is benefit for optimizing hard constraint. Besides, the traditional evolutionary strategy could well maintain the population diversity. With the introducing of adaptive operators, the computational efficiency and convergence rate have been increased. The proposed ACMA performs better than the compared methods in most cases.Get the inspiration form NNIA, EMIA is proposed in chapter 5 for solving examination timetabling problems efficiently. Firstly, we design a resource allocation model for allocating computing resources properly. The dynamic way which makes the solutions well-distributed is more reasonable. Besides, an individual with greater crowding-distance is reproduced more times and then less-crowded regions will have more chances to be searched, which improving the search ability of EMIA on less-crowding regions. Compared with several state-of-the-art multi-objective evolutionary algorithms, including NNIA、NSGA-II, MOEA/D on 10 well-known and frequently used multi-objective problems, the proposed algorithm achieves comparable results in terms of convergence, diversity metrics on most problems. The convergence of EMIA is even better than that of MOEA/D in some cases.On the basic of the designed EMIA, we propose an enhanced version for multi-objective examination timetabling problems. The single-objective model is extended to a multi-objectives model for examination timetabling problemsby adding another objective function. The proposed method employs a hybrid approach for initialization. Instead of using the traditional way for computing crowding distance, we design a new way to dynamically compute crowding distance for maintaining the population diversity. Moreover, a specific local search strategy is employed for further individual optimization. Experimental results indicate that the enhanced EMIA could obtain comparable results in terms of convergence and diversity metrics.