基于三维立体遗传编码设计的排课系统-论文.pdf

《基于三维立体遗传编码设计的排课系统-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第31卷第7期重庆工商大学学报(自然科学版)2014年7月V01．31N0．7JChongqingTechnolBusinessUniv．(NatSciEd)Ju1．2014文章编号：1672-058X(2014)07-0010-04基于三维立体遗传编码设计的排课系统张丽丽，许峰，胡娟(1．安徽理工大学理学院数学系，安徽淮南232001；2．淮南职业技术学院基础部，安徽淮南232001)摘要：选择合适的编码方法是遗传算法解决排课问题的关键，在分析排课具体问题的基础上提出了三维立体编码，即将教室，教师，班级

2、，上课时间段及课程均赋以十进制代号，使其数据化，然后将此5组因素重新分成3组，其中教师，班级和课程捆绑成1组，教室，上课时间段分别为另2组，用新三维数组表示排课信息；映射在三维空间里为一个立体方块。再利用立体方块无碰撞或者投影不重叠解决冲突问题；最后用仿真实验验证了此编码方法和冲突处理的可行性。关键词：排课问题；三维编码；遗传算法；投影法中图分类号：TP311文献标志码：A随着本科教育的大众化，高校的招生规模不断壮大，高校的教务管理问题变得困难化和复杂化，这其中一个显著问题便是排课问题。排课问题又称课程表

3、问题，也称时间表问题，其目的是合理解决排课中时间和空间的冲突问题。简单来说可归结为集教师，教室，班级，课程和时间的多因素最优化决策问题。当教师，教室，班级，课程和时间这几个因素数据量较大时，手工排课表已经难以实现，如何排一个较为合理的课程表成为一个亟待研究的问题。从20世纪50年代提出排课问题至今，经过几十年的研究，国内外专家提出了各种算法，如：关联规则FP-growth算法¨，基于资源匹配的算法_2J，分组优化决策的算法J，分支界定算法以及有限回溯法等。因为排课问题是一个NP完全问题_6，以上各种算法都

4、是找到了较为合理的满意解。遗传算法是(GeneticAlgorithm，简记GA)是1975年美国Michigan大学J．Holland教授首次提出的，基于自然界物竞天择思想，并逐渐发展成为一种迭代自适应启发式概率搜索算法。它将问题的潜在解编译成二进制编码，格雷码等形式，对编码形式的解进行选择，交叉，变异等遗传操作，得到新的解。这个过程其实是一次迭代，它在每一次迭代时都拥有一组解，这组解最初是随机生成的，在每次迭代时又会有一组由遗传操作产生的新的解。遗传算法不依赖于问题的具体领域，具有很强的鲁棒性，适合大

5、面积搜索。鉴于此，拟采用遗传算法来解决排课问题。1排课问题模型1．1问题描述排课问题是高校教务管理系统中非常重要又复杂的问题之一。近年来随着大学生数量的激增，教师、教室等资源显得紧张，如何高效、合理地排好课表，是件亟待解决的难题。大学课表具有数量多，规模大，涉及因素多，限制条件多等特点，为描述问题方便，现假设学校有t个教师，r间教室，c个班级，s门课程，P个上收稿日期：2014一O1—02；修回15t期：2014—02—01．作者简介：张丽丽(1979一)，女，安徽省凤台县人，硕士，讲师，从事群智能化算法

6、研究第7期张丽丽，等：基于三维立体遗传编码设计的排课系统课时间段。则问题涉及到几个集合：教师集合71={，i=(1，2，3，⋯，t)}，教室集合R={R，i：(1，2，3，⋯，r)}，班级集合C={C，i：(1，2，3，⋯，C)}，课程集合S={S，i=(1，2，3，⋯，s)}，时间集合P={P，ii--(1，2，3，⋯，P)}。假设一周上5天课，周六周日不上课，每天分为4个教学单元，每个单元2节课，上午2个，下午1个，晚上1个，则时间集包含20个时间段。1．2问题分析课程表问题对应到数学上即是将以上几个

7、集合的元素重新排列组合，混合组成一个大集合，且大集合里的元素表示的是某班某时间由某老师在某教室上某课的意思，每两个元素不能有重叠，这个重新的组合涉及到的最大难题就是冲突问题。一个合理的课程表应该满足如下约束条件：(1)硬约束条件(可行性约束)：一个教师在同一时间段不能上两门及以上课程；一个班级在同一时间段不能听两门及以上课程；一门课程给同一个班级不能安排两次及以上；一个教室在同一时间段不能安排两门及以上课程；教室容量满足待排课程要求。满足硬约束条件的解即为可行解。(2)软约束条件(优化条件)：尽可能使每门

8、课在每周的分布时间均匀；连续四节课的尽量安排在一栋教学楼内；愿意连续上四节课的老师时间安排集中点；重要的基础课专业课尽量安排在上午。满足软约束条件的解即为满意解。2基于三维遗传编码设计的排课系统2．1遗传算法遗传算法借鉴生物的进化思想，通过计算机模拟物种繁殖过程中父代遗传基因的重新组合与“优胜劣汰”自然选择机制的联合作用解决科学与工程中的复杂问题。用遗传算法解决问题时，首先要对问题的模型结构和参数进行编码，一般用字符串表示。这