A Hybrid Evolutionary Algorithm For Combinatorial Optimization Problems

Abstract

This thesis studies the open research area of combinatorial optimization and focuses on solving timetabling combinatorial optimization problems. This research study introduces ADRRHH, an Adaptive Diversifying Ruin-Recreate Hyper-Heuristic framework, used within an iterated local search approach aiming to solve and find a near optimal solution to this class of problems. The work conducted here specifically focuses on the popular curriculum-based university timetabling problem. The proposed hybrid evolutionary hyper-heuristic algorithm iterates between applying a move operator using add-delete lists of variables on the solution and applying hill climbing on the perturbed solution. The algorithm maintains a history of the best recently used add-delete variables lists for use in later iterations, and induces an appropriate mixture of random and previously improving lists of variables during the iterated search move operator to achieve an appropriate balance between intensification and diversification. Moreover the algorithm applies a diversifying operator whenever the search is found to stall in a certain region in the partial search space in order to escape local optima and transition to other unexplored areas in the search space. Experimental results in this thesis study and summarize the performance of our approach with respect to a very recent add-delete hyper-heuristic approach. Computational results show that our approach achieved better results in multiple arbitrarily selected instances of the benchmark datasets used by an average factor of 1.16, which verifies its promising impact in the field of timetabling combinatorial optimization problems.