首页 | 本学科首页   官方微博 | 高级检索  
     检索      

一种基于遗传算法的TTP问题求解算法
引用本文:业宁,梁作鹏,董逸生.一种基于遗传算法的TTP问题求解算法[J].东南大学学报(自然科学版),2003,33(1):41-44.
作者姓名:业宁  梁作鹏  董逸生
作者单位:1. 东南大学计算机科学与工程系,南京,210096;南京林业大学信息学院计算机系,南京,210037
2. 东南大学计算机科学与工程系,南京,210096
基金项目:江苏省“九五”重点攻关课题资助项目 (BJ980 17 1),江苏省“十五”高科技资助项目 (BJ2 0 0 10 13),南京林业大学科研基金重点课题资助项目 (X0 2 0 70 1(Z) ) .
摘    要:提出并实现了一种高校自动排课算法,利用遗传算法建立数据模型,定义一个四维的染色体编码方式和包含学生人数,教室座位、特殊课程、教师、班级、一门课的时间间隔等因数的适应度函数,通过切片算子,生成指数要求的基因型个体,用交叉算子和变异算子对基因型个体进行运算,再利用选择算子选择适应度函数值较高的染色体编码方案,最后对优化的染色体按指定方向切片,生成教师课表,学生课表和教室课表,对某高校的真实数据进行实验,结果显示无一例教室,教师,班级冲突,在PⅢ866PC机上运行,耗时为2323.573s,该算法可以推广到车辆调度,会议安排、超大规模电路板设计等应用领域。

关 键 词:TTP问题  求解算法  时间表  遗传算法  高校  自动排课算法  数据模型
文章编号:1001-0505(2003)01-0041-04

TTP algorithm based on genetic algorithm
Ye Ning , Liang Zuopeng Dong Yisheng.TTP algorithm based on genetic algorithm[J].Journal of Southeast University(Natural Science Edition),2003,33(1):41-44.
Authors:Ye Ning  Liang Zuopeng Dong Yisheng
Institution:Ye Ning 1,2 Liang Zuopeng 1 Dong Yisheng 1
Abstract:A time table problem (TTP) algorithm is proposed to conduct the arrangement of curriculum schedule in universities. First, a data model is set up using genetic algorithms (GA) and then a 4 dimension chromosome representation and a fitness function are defined, the former including time, day, classroom and course, and the latter including student number, seats, special courses, teachers, classes and intervals of courses. Genotype individuals are generated through slice operators and then crossover operators and mutation operators are used to operate these individuals. The best scheme of chromosome representation in which fitness function value is higher is selected by section operators. Finally the teacher curriculum schedule, student curriculum schedule and classroom curriculum schedule can be achieved by the optimum chromosome in some dimensions. This method was tested with real world data sets and the result is satisfactory. This algorithm is also applicable in vehicle dispatch, conference arrangement, VLSI (very large scale integration) and other fields.
Keywords:timetabling  arranging of curriculum schedule  genetic algorithm  
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号