一种基于遗传算法的TTP问题求解算法

被引：39

作者：

业宁

梁作鹏

董逸生

机构：

[1] 东南大学计算机科学与工程系

[2] 南京林业大学信息学院计算机系

来源：

东南大学学报(自然科学版) | 2003年 / 01期

关键词：

时间表; 排课; 遗传算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

提出并实现了一种高校自动排课算法 ,利用遗传算法建立数据模型 ,定义一个四维的染色体编码方式和包含学生人数、教室座位、特殊课程、教师、班级、一门课的时间间隔等因数的适应度函数 .通过切片算子 ,生成指定要求的基因型个体 ,用交叉算子和变异算子对基因型个体进行运算 ,再利用选择算子选择适应度函数值较高的染色体编码方案 ,最后对优化的染色体按指定方向切片 ,生成教师课表、学生课表和教室课表 .对某高校的真实数据进行实验 ,结果显示无一例教室、教师、班级冲突 ,在PⅢ866PC机上运行 ,耗时为 2 3 2 3 .5 73s.该算法可以推广到车辆调度、会议安排、超大规模电路板设计等应用领域

引用

页码：41 / 44

页数：4

共 10 条

[1]

Search strategy for constraint-based class-teacher timetabling. Legierski W. In: PATAT 2000 . 2000

[2]

Trick: a schedule-then-break approach to sports timetabling. Michael A. In: PATAT 2000 . 2000

[3]

University course timetabling with soft constraints. Rudov H,Murray K. In:PATAT 2000 . 2000

[4]

Adaptation in nature and artificial systems. Holland J H. . 1992

[5]

CS-R9567 A survey of automated timetabling. Andrea Schaerf. . 1995

[6]

FIMU-RS-99-09 timetabling with annotations. Hana Rudova,Ludek Matyska. Brno, Czech Republic: Faculty of Informatics, Masaryk University . 1999

[7]

Age neticalgorithmtosolvethetimetableproblem. ColorniA,DorigoM,ManiezzoV. http: citeseer.nj.nec.com context638417182445 . 1992

[8]

Universitytimetablingus ingconstraintlogicprogramming. HansJoachimGoltz,DirkMatzke. PACLP’’99 . 1999

[9]

Alleles, loci, and the traveling salesman problem. Goldberg D E,Lingle R. In: Proc of the 1 st Int Conf on Genetic Algorithms ICGA-85 . 1985

[10]

Carter: a comprehensive course timetabling and student scheduling system at the University of Waterloo. Michael W. In: PATAT 2000 . 2000

← 1 →