课程表问题的一种模拟退火超启发式算法

课程表问题是经典的组合优化问题,属于NP-hard问题.长期以来人们一直都在寻求快速高效的近似算法,以便在合理的计算时间内准确解决大规模课程安排问题,并提出许多有效且实用的启发式和元启发式算法.在此基础上提出了一种基于多个图染色启发式规则的模拟退火超启发式算法.在超启发式算法的框架中,用模拟退火算法作为高层搜索算法,多个图染色启发式规则为底层的构造算法.与现有的方法相比,该算法具有很好的通用性,可以很容易推广到考试时间表、会议安排.旅行商问题、背包问题等应用领域.实验表明,该算法是可行有效的,且无一例时间、空间冲突.

Simulated annealing hyper-heuristic algorithm for TTP

The timetabling problem(TTP) is one of the most classical problems in the combinatorial optimization.Many heuristics and meta-heuristics have been developed for the TTP.An investigation of hyper-heuristic approach upon a set of widely used constructive heuristics(graph coloring heuristics) in timetabling is presented.Within the hyper-heuristic framework,a simulated annealing algorithm is employed on the high level and graph coloring heuristics which are used for constructing timetables are work on the low level.The ob-jective of the algorithm is to develop an approach which is more widely applicable fundamentally and general with a wider range of the combinatorial optimization problems.This algorithm is tested with real-word data and the result is satisfactory.