遗传算法在排课系统中的应用.doc

遗传算法在排课系统中的应用摘 要： 随着信息时代的到来， 将信息系统应用于学校日 常工作已势在必行。 学校教育信息管理的核心是资源的统筹利用， 它包括人力资源、 物力资源以及时间资源等。 本文给出了排课问题的数学模型，提出基于遗传算法解决方案。结果表明，该算法能比较有效的解决排课问题。该方法易于学习和应用，且不必依赖特殊的实现模式。关键词： 排课 遗传算法 优化算法1. 引言 随着现代信息技术在教育领域的普遍应用， 我国高校教学系统的管理模式已逐步进入了网络化和信息化时代。 近几年我国高等教育的快速发展及高校办学规模的不断扩大， 本科学分制、 选课、 试听制度以及双专业辅修学制的进一步推行， 使得高校排课的工作量成倍增长，工作难度进一步加大。 传统手工排课模式已不能适应这一挑战， 这就向教学排课管理子系统提出了新型化和多元化的要求。 教学管理现代化、 信息化是高校的必然选择。 2. 遗传算法简介 遗传算法是模拟自然界自然选择与进化机制求解极值问题的一类自适它以生物群体的观点看待优化问题。 所求问题解空间中的一点为一个个体结合起来构成一个群体， 群体中的每一个个体都代表了问题的一个可能解群体称为代。在遗传算法中，待优化参数通常用符号串来表示，这一过程由某一符号串求得其表示的具体参数值的过程称为解码。 符号串也称为染本组成单位称为基因。针对具体问题， 遗传算法通过定义一个适应度函数来而每个个体所对应的适应度函数值代表该个体对环境的适应程度， 适应度函个体适应环境的能力越强。 初始群体确定后， 在选择、 交叉、 变异等遗传照类似于自然选择的过程逐代进化， 最终获得问题的满意解。 1 3.排课问题基本描述 排课问题就是将课程、 任课教师以及学生在合适的时间段内分配到合适的教室中。 在高校中排课工作更加的复杂， 会涉及任课教师、 学生班级、 学生人数、 教室容量、 教室类型等硬性要求条件以及单双周、 课程均匀分布、 授课时间分布、 教室之间间距等其他软性要求条件。 排课问题的本质就是时间表问题 TTP(Time tabling Problem) 。 TTP 问题是一类多元受限的不确定性问题，它决定一个从项目到资源的最优分配， 使得总的代价最小且能满足 K 个条件。早在 1975 年， Shimon Even 等人就证明了 TTP 问题是 NP-Complete 问题。而遗传算法具有良好的并行性、 很强的通用性、 良好的全局优化和稳定性等优点。 对于传统优化方法无法或很难解决的非线性、 不可微分问题， 遗传算法都能很好地解决。 遗传算法的特点使其解决时间表问题成为可能。 此外， 排课所需的各种信息可以存储在计算机中的数据库内。 所以可以设计基于遗传算法的学校排课管理子系统。 4、排课问题的算法1.算法分析 排课的冲突异常复杂，对于这些冲突的复杂度我们进行分析。以下给出分析的过程。过程1：将模型中的五个集合降维为一个给定四维空间V(S，T，R，C)，称之为：课表。四维分别代表了：S（教师）：全校所有课程的任课教师；T（时间）：上课的时间段，每天分为1-2、3-4、5-6、7-8、9-10，总共五个时间段，每学期20周，每周五天，合计每学期有500个上课时间段；R（教室）：全校所有的可用教室，包括不同的教室属性，如：教室大小、是否为多媒体或语音教室等等；C（班级）Class：当前学期的所有教学班级，包括班级属性，如：班级人数、是否合班。过程2 ：在课表V中求解存在着子空间L，且L 过程3 ：在课表V中求解存在着四维向量l (Sr，Tm，R，C)，且lL，那么称l为：课。过程4 ：在课表编排过程中，对于P( liVljL，i，jN)，li (Tr，Tm，R，C)与lj (Tr，Tm，R，C)，没有冲突，认为V是：有效课表。 通过对四维向量li ( Sr，Tm，R，C)与lj (Sr，Tm，R，C)的简化。在排课过程中的所有关系情况TmR + Tm RC。那么：由过程1、过程2 可以推导出，在课表空间中，恒有f (Tr，Tm，R，C)，那么V就是有效的课表。最后为了简化，再给出过程5：过程5 ：在课表V中，对于li ( Sr，Tm，R，C)与lj (Sr，Tm，R，C)，i、jN，没有冲突，记为：lilj ；对于Li、Lj没有冲突，记为：LiLj。这样有对于P( liVljL)，li (Sr，Tm，R，C)与lj (Sr，Tm，R，C)，i、jN，没有冲突，就可以得到VL。235、结束语该求解方法已在实际中得到应用，取得了较好的效果。在使用遗传算法优化后排课算法的实际效率有极大的提高。因此用遗传算法实现类似排课问题的最优解也是一种比较简单实用的方法，收敛速度很快，时间段分配均匀。但是在实际应用中也可能没有终止条件，目的是可以依次提供不同的可行解以供使用者选择直到所有解给完或者使用者终止。如果只考虑最优解的问题，可以使用迭代的适应度几乎不变作为终止条件或者规定迭代次数。值得一提的是，有些实际问题的可行解可能是唯一的，比如教学场地或教师资源紧缺的情况，更严重的是如果约束条件太苛刻，甚至可能没有可行解，在此类情况下人工干预还是有必要的。6.参考文献1 郭嗣琮，陈刚信息科学中的软计算方法