论文网

银行招聘

校园招聘

教师资格证

公务员考试

我要自学网

教师招聘试题

CAD教程

医院招聘

教育局

兼职招聘

工作总结

招工信息

实习生招聘

卫生人才网

您当前的位置:首页 > 科技论文 > 数学论文
| 科技小论文 | 数学建模论文 | 数学论文 | 节能减排论文 | 数学小论文 | 低碳生活论文 | 物理论文 | 建筑工程论文 | 网站设计论文 | 农业论文 | 图书情报论文 | 环境保护论文 | 计算机论文 | 化学论文 | 机电一体化论文 | 生物论文 | 网络安全论文 | 机械论文 | 水利论文 | 地质论文 | 交通论文 |

遗传算法在多校区排课系统中的应用(图文)

来源网络

论文导读:多校区排课是一个典型的多因素的优化决策问题,是组合规划中的NP完全类问题,涉及信息较多且求解复杂性为课表规模的指数量级。遗传算法被证明解决该类问题是最合适的。采用截断选择法,染色体按适应度函数值从高到低排序,只有最优秀的个体才能被选作父个体。
关键词:遗传算法,多校区排课,适应度函数

  排课是教务管理工作的一个重点和难点。排课涉及教师、学生人数、教室容量、教室类型、教室间距等诸多因素。尤其是多校区同时运行的高校格局增加了更多的约束条件,问题的复杂度也增加了许多。多校区排课是一个典型的多因素的优化决策问题,是组合规划中的NP完全类问题,涉及信息较多且求解复杂性为课表规模的指数量级。遗传算法被证明解决该类问题是最合适的。
  一、排课问题描述
  编排课表的整个过程中充满了矛盾运动,其中包括上课班级、所开课程、任课教师、上课时间、上课地点等方面在排列组合中所发生的冲突和矛盾现象。课表的编排必须精心组织,准确无误,科学合理,充分发挥时间、空间、人力、物力,以保证教学过程的正常运转。课表要有利于教学设备的充分利用,要符合教学规律。将这个原则进行细化、清晰化,一般可以归纳为以下具体要求。
  课表中没有硬性冲突,在排课过程中必须遵守如下约束条件:
  1. 每位教师在同一时间段内只能安排一门课程
  2. 一个教室在某一时间只能安排一门课
  3. 教室的位置数量与每个自然班的人数应尽量匹配
  4. 必须根据核定的教学计划所规定的学时数排课,不得任意增减
  5. 一个教师两节课间路程不超过10分钟,半天的工作必须安排在同一个校区
  课表要求有较高质量,为了使排出的课表更优化、合理、排课还应考虑以下因素:
  1. 一门课程在每个班的每两天只能安排一次
  2. 专业必修课尽量安排在上午
  3. 同一门课的上课地点尽量安排在同一教室
  4. 体育课必须排在下午或者上午3-4节,体育课后避免安排讲授课
  5. 实验、操作、训练、演示等课应排在下午
  6. 满足个别教师的特殊上课时间要求
  7. 编排课表时,先排公共课,后排专业课;先排合班课,后排单班课;先排多头课(一个教师有多门课),后排独头课;先排多时课,后排少时课。
  二、排课问题的遗传算法设计
  根据高校现状,许多院系都有各自独立的教学楼,且实验、体育课等应有固定的教学场所,为此可以利用遗传算法固有的并行性将排课问题分为若干个子问题。
  首先,人工安排或计算机根据条件自动生成,集中安排实验、实习、社会实践等有固定
  时间和地点的课程。
  其次,剩余课程按照院系为单位分为若干个子块,用遗传算法对每个子块进行排课操作。
  2.1染色体编码
  遗传算法中首要考虑的是如何表现问题,即如何对其进行染色体编码,使之适用于GA操作。一条染色体中应包含课程、老师、教室、学生、时间和校区等相关信息。但由于某一门课程信息里面已经包含了老师、学生和校区信息,故染色体中仅需要对课程、教室和节次采用可拼接的二进制编码。若某院系一学期有40门课程,可编为X1=(a1,a2,a3,a4,a5,a6),ai∈{0,1}。每个院系一般有20个教室不等,可编为X2=(b1,b2,b3,b4,b5),bi∈{0,1}。每周上五天课,每天4次,共20次,可编为X3=(c1,c2,c3,c4,c5……,c19,c20),ci∈{0,1}。所有课程的DNA分子拼接形成一条染色体。
  2.2初始化群体
  群体初始化的规模数n应取适中。一般,n取值为染色体长度的两倍左右。根据上述的染色体编码,一个DNA分子长度为31,40门课程的一个染色体码长为1240,故n可取2480。
  每条染色体中的DNA分子之间由于教室、时间、学生、老师、校区等因素会产生冲突,比如一个老师不能在同一时间安排两门或两门以上的课程。产生初始群体时,在不产生冲突的情况下(满足上述5条硬约束条件),随机为基因块赋0或1,直到满足群体规模。
  2.3适应度函数设计
  遗传算法根据适应度群体中个体的优良程度,适应度较高的个体遗传到下一代的概率较大。因此,遗传算法是在适应度函数的引导下运行的,适应度函数选择的好坏直接影响算法的优劣。在适应度函数设计中,我们主要考虑以下冲突;
  P1:教师冲突,教师安排是否冲突,同一时间段是否安排两次课。
  P2:教室冲突,同一教室同一时间段不能安排两门课。
  P3:班级冲突,同一班级同一时间的段不能安排两门课。
  P4:交通冲突:对于多校区或单校区教学楼分散情况,教师或学生相邻时的教室间距不应超过10分钟;
  P5:教室大小与学生人数的冲突。
  以上约束条件Pi∈{0,1},0表示有冲突,1表示没有冲突
  首先对一条染色体中的每个DNA分子(一门课程)计算适应度,然后计算一条染色体所有DNA分子适应度之和,将该值作为个体适应度,数学表达式如下:
  fi=(P1×P2×P3×P4×P5×(f×Q1+j×Q2+h×Q3)
  
  f表示节次优先度,j表示课程类别优先度,h表示组合优先度。Q1、Q2,Q3代表相应权值,F个体适应度。
  2.4选择算子
  采用截断选择法,染色体按适应度函数值从高到低排序,只有最优秀的个体才能被选作父个体。其中,用于决定染色体被选作父个体的百分比的参数称为截断阀值,范围取90%~80%。在该阀值之外的个体不能产生子个体。
  2.5交叉算子
  

 
 

交叉只对复制产生的85%的个体进行,此时适当的选择交换概率p,p过大或过小都不易收敛到最优解,设p为0.95(保留的15%不参加交换)。采用一点交换方式,在排课问题中,每周某一课程上课节次是固定的,随机选择第n个DNA分子时间节次码中第m个基因位为1的基因。具体操作是:
  2.6变异算子
  排课系统中由于课表合法性问题,如果采用简单的随机变异,会出现大量的冲突,导致需要消耗大量精力去纠错。因此,我们在研究中采用有条件的基因变异。
    变异操作的作用是防止丢失有用的可能解,保证搜索到空间的重要点,使算法具有全局收敛性,变异的概率较小,在本文中取0.01。和交叉算子一样仅是时间节次码参与交换,教室和课程码保持不变。选择两个点进行变异,具体操作是:随机选择第n个DNA分子,再随机选DNA分子中的时间码第p、q个点进行变异。具体操作时:
  个体A ……01000101001000000000……
  
  新个体A ……01000001001010000000……
  2.7终止条件
  采用迭代次数来决定,取2500。
  三、结论
  本文提出的利用遗传算法解决多校区排课问题的方案,很好地解决了多约束下的排课问题。该方法具有很大的现实意义,对遗传算法求解组合优化问题也有一定的借鉴作用。

【参考文献】
[1]肖俊.遗传算法的工程应用[J].计算机科学,2005,11(32):247~250
[2]徐宗本,张讲社,郑亚林.计算智能中的仿生学—理论和算法[M].科学出版社,2003
[3]业宁,梁作鹏,董逸生.一种基于遗传算法的TTP问题求解算法.东南大学学报.2003(1):41-44
 


用Jordan标准型给出方阵的(图文)
一类随机微分方程的稳定性(图文)
来顶一下
返回首页
返回首页
 
相关文章
    无相关信息
栏目更新
栏目热门