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

GENETIC ALGORITHM VS. TABU SEARCH IN TIMETABLE SCHEDULING

作　　者：李红 成新文[2] 

机构地区：[1]重庆市北碚区教育信息中心 [2]四川省自贡教育学院计算中心,四川自贡643000

出　　处：《内蒙古师范大学学报（自然科学汉文版）》2003年第4期370-373,共4页Journal of Inner Mongolia Normal University(Natural Science Edition)

摘　　要：时间表问题属于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.

关 键 词：禁忌搜索 遗传算法 时间表问题 NP完全问题 算法 调度问题 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]