禁忌搜索与遗传算法在求解时间表问题中的对比研究

GENETIC ALGORITHM VS. TABU SEARCH IN TIMETABLE SCHEDULING

时间表问题属于NP完全问题,一般来说,只能找出用于实际工作的"亚优解"(sub optimalsolution).对遗传算法和禁忌搜索算法用于求解时间表问题进行了对比研究,结果表明,禁忌搜索算法能找出比遗传算法更好的时间表,而且禁忌搜索算法所花费的搜索时间也比遗传算法少.但是,遗传算法能同时产生几个不同的逼近最优解的解.

Timetable problems are NP-completeness problems,which usually lead to satisfactory but sub-optimal solutions.This paper investigates and compares Genetic Algorithms and Tabu Search approaches to solve these kinds of problem.The experiment shows that TS approach can produce better timetables than those of GA approach can.Further,the search time spent in TS is less than that of GA.However,GA can produce several different near optimal solutions simultaneously.