禁忌搜索与遗传算法在求解时间表问题中的对比研究 |
| |
引用本文: | 李红,成新文.禁忌搜索与遗传算法在求解时间表问题中的对比研究[J].内蒙古师范大学学报(自然科学版),2003,32(4):370-373. |
| |
作者姓名: | 李红 成新文 |
| |
作者单位: | [1]重庆市北碚区教育信息中心,重庆400700 [2]四川省自贡教育学院计算中心,四川自贡643000 |
| |
摘 要: | 时间表问题属于NP完全问题,一般来说,只能找出用于实际工作的“亚优解”(sub-optimal solution),对遗传算法和禁忌搜索算法用于求解时间表问题进行了对比研究,结果表明,禁忌搜索算法能找出比遗传算法更好的时间表,而且禁忌搜索算法所花费的搜索时间也比遗传算法少。但是,遗传算法能同时产生几个不同的逼近最优解的解。
|
关 键 词: | 禁忌搜索 遗传算法 时间表问题 NP完全问题 算法 调度问题 |
文章编号: | 1001-8735(2003)04-0370-04 |
修稿时间: | 2003年5月13日 |
GENETIC ALGORITHM VS. TABU SEARCH IN TIMETABLE SCHEDULING |
| |
Abstract: | 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. |
| |
Keywords: | timetable problem genetic algorithm tabu search |
本文献已被 CNKI 维普 等数据库收录! |