（计算机软件与理论专业论文）基于三维编码的自适应遗传算法在排课系统上的应用.pdf

ab s t r a c t abstract t i m e t a b l i n g p r o b l e m ( t p ) i s a mu l t i o b j e c t i v e c o m b i n a t i o n o p t im i z a t i o n p r o b l e m w i t h c o n s t r a i n t s , a n d a l s o h a s b e e n p r o v e d n p - c o m p l e t e d . g e n e t i c a l g o r i t h m ( g a ) i s a h i g h - e ff e c t i v e r a n d o m l y s e a r c h i n g a l g o r i t h m , b as e d o n t h e n a t u r e e v o l u t i o n . i t i s a v e ry e ff e c t i v e a l g o r i t h m t o s o l v e n p - c o m p l e t e d c o m b i n a t i o n o p t i m i z a t i o n p r o b l e m . g e n e t i c a l g o r it h m i s a d o p t e d t o s o l v e t p i n t h i s p a p e r . t h e m a i n c o n t e n t s a r e as f o l l o w i n g : ( 1 ) t h i s p a p e r s y s t e m a t i c a l l y a n d c o m p l e t e l y d i s c u s s e s f a c t o r s , r e s t r ic t i o n s a n d o b j e c t i v e s a t t a c h e d t o t p , a n d d e s c r i b e s t p b y m a t h e m a t i c m o d e l . ( 2 ) t h i s p a p e r i m p r o v e s t h e g e n e r a l i z e d c o d i n g m e t h o d o f g a , s y n t h e t i c a l l y a d o p t s t h r e e - d i m e n s i o n c o d i n g a n d s e l f - a d a p t i v e d e s i g n i n g m e t h o d o f c r o s s o v e r a n d m u t a t i o n p r o b a b i l i ty , a n d b r i n g s f o r w a r d a s e l f - a d a p t i v e g a b as e d o n t h r e e - d i m e n s i o n c o d i n g . ( 3 ) a c o ur s e s c h e d u l i n g s y s t e m b a s e d o n a b o v e - m e n t i o n e d i m p r o v e d g a h as b e e n d e s i g n e d a n d r e a l i z e d b y u s i n g d e l p h i 7 .0 as d e v e l o p i n g t o o l a n d ms s q l s e r v e r 2 0 0 0 as d a t a b ase . a n d a t p e x a m p l e w i t h 1 1 0 c l ass r o o m s , 3 8 9 s c h o o l t e a c h i n g e v e n t s h a s b e e n t e s t e d i n o b j e c t i v e s p a c e c o n s i s t s o f t h r e e f a c t o r s o f s l o t - s u p e r i o r , d i s t r i b u t i n g - u n i f o r m i ty - o n - d a y , a n d g y m l e s s o n s t i m e . t h e r e s u l t i s s a t i s f u n g . t h e s y s t e m h as b e e n a p p l i e d t o o n e c o l l e g e i n m y p r o v i n c e a n d i m p r o v e s c u r r i c u l u m s c h e d u l i n g e ff i c i e n c y g r e a t l y . k e y w o r d s : c u r r i c u l u m s c h e d u l i n g ; g e n e t i c a l g o r it h m ; t h r e e - d i m e n s i o n c o d i n g ; s e l f - a d a p t i n g ; t i m e t a b l e 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已 经发表或撰写过的 研究成果， 也不包含为获得 南昌大嵘 或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学 位 论 文 作 者 签 “ (手 写 反 证签 字 日 期 : - 7 年 。 ” “ / 日 学位论文版权使用授权书 本学位论文作者完全了 解南昌大学有关 保留、 使用学 位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅 和借阅。 本人 授权南昌大学可以 将学 位论文的全部或部分内 容编入有关数据库 进行检索， 可以 采用影印、 缩印 或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 作l .阵u晰飞. 学 位 论 文 作 者 签 “ (手 写 ，:座泣 导师签名 ( 手写) : 签 字 日 期 :)-o 4/ 年 ， 月 习 日 签字日期: 6 月 年 |/1 0话编 电邮 学位论文作者毕业后去向: 工作单位: 通 讯地址 : 第 i 章 引言 第 1 章 引言 1 . 1问题的提出及课题来源 1 . 1 . 1问题的提出 时间表( t i m e t a b l e ) 问 题是一类多元受限的资源调度组合优化问题， 应用领域 非常广泛，包括列车时刻表、航班时刻表、城市公路运营表、医院病房调度表 等， 学校课程表的编排也是时间表问题的一个应用。 课程表编排问题 ( 排课问题)是指在有限的时间段和教室数量里调度课程 的多因素受限问题。 手工编排课程表通常要耗费大量的工作日。另外，手工编排出的课程表往 往存在着时间、地点等冲突。 计算机课程表编排问题是人们关注而一直未能满意解决的计算机应用领域 中一个具有代表性的问题。1 9 7 5年 s . 艾温 ( e v e n . s )证明了课程表编排问题是 n p 一 完全的，宣布了这一时空组合问题的学术地位和难度。n p问题有很多类， 按解的不确定性分为完全的和不完全的。其中按数学求解的难易程度，完全的 n p问题是最难解的。因此，对课程表编排问题的研究在理论上具有相当典型的 代表性，这个问题的解决对解决其他的n p - h a r d , n p 一 完全问题，具有非常重要 的指导意义。 为了让计算机自 动完成课程表编排任务， 许多软件厂商作了很大努力， 开发 出了相应的自 动排课系统。但从实际使用情况来看， 这些系统在实用性及通用性 上仍不尽如人意。这一方面归咎于排课问题是一个很复杂的系统工程， 要想面面 俱到是一 件很困难的事， 另一方面每个学校由 于其各自 的 特殊性， 自 动排课软件 很难普遍适用， 完全满足所有要求。特别是在手工微调过程中一个很小的变动， 都会引起全部排课情况的大调整， 这在实际应用中也是很难于解决的事情。因而 有些学校仍然喜欢手工排课， 但对排课中的错误却又不能及时发现， 等上课时再 发生冲突就会影响教学计划。因此，开发新的实用性更强的计算机智能排课软 件势在必行。 第 1 章 引言 1 . 1 . 2课题来源 本课题是我省教育厅课题 基于回溯和相关元算法的智能排课系统的后 继研究课题，所开发的排课系统已成功应用于我省某高校的排课工作中。 1 . 2研究现状与发展趋势 1 . 2 . 1国内外的研究现状 ( 一) 国外的研究现状 自1 9 6 3 年以 来，国外对学校课程表的自 动生成技术给予了 极大的关注，发 表了 大量研究此类问 题的学术论文，一些相关的应用也取得了 成功 u 国外大多数早期研究运用的是建立在模拟人工解决这类问题基础之上的启 发式方法。也就是将课程逐门加入到课程表中，直到所有的课程都编排好。 近年来，国外研究者们开始应用综合性的技术探讨课程表类问题，例如网 络模型、整数规划等。另外，也有学者试图将这类问题抽象成图着色问题来加 以研究。最近，开始有人试图用人工智能技术研究课程表问题，例如专家系统、 模拟退火思想、 t a b u 搜索以及遗传算法等。 第 1 章 引言 表1 . 1 国外研究现状简表 时间研究者使用的方法发表的论文 2 0 0 5 s h a w c h i n g c h a n g a e t cg e n e t i c a l g o r i t h m 参考文献 幻 2 0 0 2a. s . as r a t i a n e t c g e n e r a l i z e d c l a s s - t e a c h e r m o d e l参考文献 3 2 0 0 2r a mo n al v a r e z v a l d e s e t ct a b u s e a r c h 参考文献 4 2 0 0 2 s h a n g y a o y a n e t co p t i m i z a t i o n b a s e d a p p r o a c h参考文献【 5 2 0 0 1u. ai t u r k i e t ct a b u s e a r c h 参考文献【 6 2 0 0 1mi c h a e l w e t ct a b u s e a r c h 参考文献【 7 2 0 0 1 mi k e wr i g h t s u b c o s t - gu i d e d s e a r c h 参考文献【 8 2 0 0 1 ki m l i n c h e w e t c o p t i m i z a t i o n b a s e d a p p r o a c h 参考文献【 9 2 0 0 0l . r. f o u l d s d e c i s i o n s u p p o r t s y s t e m参考文献【 1 0 2 0 0 0r a mo n al v a r e z v a l d e s e t ct a b u s e a r c h 参考文献【 川 2 0 0 0 p e r ry f i z z a n o e t co p t i m i z a t i o n b a s e d a p p r o a c h参考文献【 1 2 2 0 0 0b r u n o de b a c k e r e t c c o n s t r a i n t b a s e d a p p r o a c h a n d me t a h e u r i s t i c s 参考文献【 1 3 1 9 9 9s a f a a i d e r i s e t c c o n s t r a i n t b a s e d a p p r o a c h a n d g e n e t i c a l g o r i t h m 参考文献【 1 4 1 1 9 9 8 al b e r t o c o l o mi e t cme t a h e u r i s t i c参考文献 1 5 1 1 9 9 8mi c h a e l e t c g e n e t i c a l g o r i t h m a n d t a b u s e a r c h 参考文献【 1 6 ( 二) 国内的研究现状 国内对课程表问题的研究开始于 2 0世纪 8 0年代初期。研究的早期主要以 临界资源分配算法为主，随后出现了以人工智能理论为基础的算法，如知识推 理、 专家系 统等。自1 9 7 5 年美国m i c h i g a n 大学h o l l a n d 教 授提出了遗传算法并 将其成功地应用到机器学习当中，遗传算法在解决组合优化问题上给予了人们 新的启示，应用遗传算法解决课程表问题于是成为国内新的研究方向。在非数 值计算方法中，除了上述遗传算法外，还出现了其他模拟自 然界的方法，如进 化算法、模拟退火算法等等。 第 1 章 引言 表1 . 2 国内 研究现状简表 时间研究者使用的方法发表的论文 2 0 0 5 陈炼，刘昌 平模拟多处理机调度的方法参考文献 1 7 2 0 0 4朱冠字，王乘，席大春遗传算法 参考文献【 1 8 2 0 0 4 孙建平， 曾经梁专家系统参考文献 1 9 1 2 0 0 3 业宁， 梁作鹏，董逸生遗传算法参考文献 2 0 1 2 0 0 3 李增智， 王云岚， 陈靖混合型模拟退火算法参考文献【 2 1 2 0 0 2 唐勇， 唐雪飞， 王玲遗传算法参考文献 2 2 2 0 0 2 孙建平， 梅晓勇， 肖 政宏， 史忠植关联规则参考文献【 2 3 2 0 0 2 胡顺仁， 邓毅， 王铮图论法参考文献 2 4 2 0 0 2 陈谊 ， 杨怡， 张国 龙， 王尚忠基于 优先级的方法参考文献 2 5 2 0 0 1熊伟清， 魏平， 赵杰f 1遗传算法 参考文献仁 2 6 1 2 0 0 1 胡小兵， 鲁宏伟模糊专家系统参考文献 2 7 2 0 0 1孙吴 基于时间位图迭加匹配的 方法 参考文献 2 8 2 0 0 1 赵辉， 秦维佳基于资源分配的方法参考文献 2 9 1 2 0 0 0 汪红星， 康立山等演化算法参考文献【 3 0 2 0 0 0 周建新， 王科俊， 王文武， 张建波专家系统参考文献仁 3 1 2 0 0 0 黄干平， 姚自 珍， 张轶静模拟退火算法参考文献【 3 2 2 0 0 0 龙一飞， 郭文宏知识推理参考文献【 3 3 2 0 0 0 金炳尧， 蔚承建， 何振亚进化算法参考文献【 3 4 2 0 0 0陈幼明， 陈光喜基于资源分配的方法 参考文献【 3 5 1 1 9 9 9陈淑珍， 孙晓安回溯算法 参考文献 3 6 1 1 9 9 8 董艳云， 钱晓群， 张宇舒基于课元相关运算的方法参考文献 3 7 1 9 9 8 王枯民， 赵致格定额匹配算法参考文献【 3 8 1 . 2 . 2当前的发展趋势 ( 1 ) 深入研究现有理论、 技术与方法u 对各种搜索优化技术在解决课程表问题上展开更深入的研究。继续探讨目 第 1 章 引言 前各种解决组合优化问题的理论、技术与方法，拓宽这些理论、技术与方法在 课程表问题上的应用范围; ( 2 ) 课程表问 题标准化u 7 不同的学校有它与众不同的排课规则与要求，存在很多大相径庭的制约排 课的因素，高校尤其为甚。这就使得为一所学校编制的排课程序很难适用于其 他学校。尽管如此，用高度抽象的数学语言建立一个满足所有学校排课要求的 超集，从而使课程表问题标准化，对解决课程表问题是非常有益的: ( 3 ) 比较并综合各种不同的理论、 技术与方法17 比较各种解决课程表问题的方法，可以对特定方法的性能及适用范围有更 深入的理解。比较同样也能说明在各种不同的情况下哪种方法能取得较好的效 果。将各种适应情况不同的方法综合起来，取长补短，就可能可以在原有的基 础上生成更优的解决方案。例如为了克服t a b u 搜索的局部寻优及遗传算法的早 熟现象， m i c h a e l 等人采用了 两者相结合的方法探索时间表问 题的解 16 ( 4 ) 研究课程表问 题的最优解u 目 前解决课程表问题算法的质量都只能通过和其他算法的比较来说明，而 不能通过和最优解的比较来证明。相反，其他问题 ( 如图着色和工厂作业调度) 的理论研究都提供了大量的近似最优解。因此，研究课程表问题的近似最优解 是非常有意义的; ( 5 ) 研究、运用新的理论、技术与方法: 研究表明，解决大规模课程表编排问题单纯依靠现有方法是行不通的，必 须研究、运用其他的理论、技术与方法。如利用运筹学中分层规划的思想将课 程表问题分解，是一个有希望得到成功的方法2 s 7 1 . 3排课问题解决方法综述及遗传算法解法的优势 1 . 3 . 1排课问题解决方法综述 从1 9 6 3 年第一个排课问题的数学模型提出 之后， 人们又对排课问题的算法 作了许多探索。但由于排课问题是n p 完全的问题，并且易受实际问题具体情况 的影响，大多数求解结果都不理想。对于计算机自 动排课，己经研究出了许多 种解决方法，下面是一些常见解法及其简介侧: 第 i 章 引言 ( 1 ) 遗传算 法( g e n e t i c a l g o r i t h m ， 简称g a ) 遗传算法借鉴生物界自 然选择和自 然遗传机制，使用群体搜索技术，适用 于处理传统搜索方法难以解决的复杂和非线性问题。经过近4 0 年的发展，遗传 算法在理论研究与实际应用两方面都取得了巨大的成功。许多人通过对遗传算 法进行改进和优化，较好地解决了课程表编排问题。 ( 2 ) 模拟退火算法( s i m u l a t e d a n n e a l i n g ， 简称s a ) 一批学者还将模拟退火算法应用到课程表问题的研究中。模拟退火算法是 k i r k p a t r i c k 等人于1 9 8 3 年首先 提出 的， 它是人们从自 然界固 体退火过程中 得到启 发并从中抽象出来的一种随机优化算法。模拟退火法用于求解优化问题的出发 点是基于物理中固体物质的退火过程与一般优化问题之间的相似性。在对固体 物质进行退火处理时，常先将它加温使其粒子可自由运动，之后随着温度的逐 渐下降，粒子逐渐形成低能态晶格。若在凝结点附近温度下降的速率足够慢， 则固体物质一定会形成最低能量的基态。优化问题也存在类似过程。模拟退火 法被用来解决许多实际应用中的优化问题，取得了不错的效果，用其解决排课 问题，也有了一些成功的应用。 ( 3 ) 模拟退火遗传算法 在任学惠、顿毅杰、管会生的 4 0 中提出了利用模拟退火遗传算法解决课 程表安排优化问题的算法。这种方法结合了遗传算法和模拟退火算法的优点， 使得两种算法的搜索能力得到相互补充，克服了遗传算法中参数选择不当易陷 入 “ 早熟”和模拟退火算法对 “ 退温”过程的限制条件苛刻的缺点， 可以避免搜 索过程陷入局部最优。 ( 4 ) 蚁群算法 在张林的 4 1 中，采用了蚁群算法来解决课程表问题。蚁群算法是通过模 拟蚁群在觅食过程中寻找最短路径的方法来求解优化问题，目前在旅行商问题 等组合优化问 题中有成功的 应用。蚁群算法目 前有a s . a c s . m m a s 等三种常 用的模型， 但是在排课问题上这三种蚁群算法都有易于陷入局部最优解的缺陷， 从而使得排课问题的求解过程过早地停止。 ( 5 ) 增强学习算法 在郭方铭的【 4 2 1 中，给出了 基于增强学习算法的课表编排模型的实现思路。 增强学习算法是一种机器学习的框架，其智能体通过一系列的活动影响其外部 环境，并收到活动的回报。智能体通过状态映射到动作来选择能获得最大回报 第 i 章 引言 的动作。增强学习算法的优点:a . 在应用增强学习算法编排课表时，不需要对 排课问题做过多的分析，也就是说，增强学习算法避开了课表编排问题本身的 复杂性;b . 排课智能体能在一定程度上自 主学习并决策，大大降低了人工排课 的劳动强度，而且在安排课表的同时也在进一步学习人工决策的结果，系统的 性能得以逐步提高。但是由于排课问题的复杂性，该算法的运用中还存在一些 问题有待进一步的改进:a . 排课任务的顺序是该算法中的一个关键问题，不同 的顺序对应不同的学习效果。因而，如何针对不同的教学情况提供尽可能合适 的排序原则是一个有待改进的问题;b . 系统的排课是在学年学分制体系下，按 专业教学计划进行安排的，没有考虑学分制选课模式下的排课。如何在学分制 选课模式下根据选课情况对教室资源的需求量进行估算以提高教室利用率也是 有待深入研究的问题。 ( 6 ) 专家系统算法 在胡小兵、鲁宏伟的【 2 7 1 中，所用专家系统算法的特色是实现了知识与程 序的分离。该算法把知识集中在知识库中，事实数据集中在综合数据库中，程 序则构成推理机。排课的数据、原则与程序分别对应专家系统的综合数据库、 知识库和推理机。排课数据、排课原则从推理程序中分离出来，便于进行修订 和补充。排课算法重点解决逻辑推理，使得程序结构简练清晰，便于维护。但 逻辑推理过程比较繁琐。 ( 7 ) 图论算法 在胡顺仁、邓毅、王铮的 2 4 1 中，针对高校排课问题的现状，将教师、班 级、教室之间的关系转化为集合关系，提出了图论的观点，并据此将排课问题 进行数学建模，把教师、班级、教室、每节课等元素转换成图形元素之间的匹 配关系， 提出了较为可行的排课算法。 然而，图的染色问 题本身是n p - h a r d 完全 问题，因此算法的实现比较繁琐。 ( 8 ) 资源匹配算法 在赵辉、秦维佳的【 2 9 1 中提出了大学排课问题的一个资源匹配模型解决方 案，但该方案未能考虑教师对上课时段问题的特殊要求。 ( 9 ) 分支限界算法 在吴金荣的 4 7 中，采用了 枚举法进行搜索。在对一棵庞大的树进行搜索 时，大胆地将无可行路线的大量分支去掉，即采用 “ 分支限界法”来剪枝。这 棵树的根就是排课的起点。限界采用一种判别原则，即在编排课程表时，定义 第 1 章 引言 一种抽象的界，使得在排到某门课时，判断它是否超过了这个界，如果超过了 这个界，就把它剪掉。这是一种非完全的穷举法，有可能过早地产生可行解而 进入局部最优的陷阱。而且计算量很大，仅适用于规模较小的课表编排情况。 ( 1 0 ) 贪婪算法 在聂小东的【 4 3 中提出了基于贪婪算法的排课系统。该系统对于贪婪准则 的确定还是建立在人工排课考虑的因素上，没有充分考虑提高课表质量的其它 人文因素。并且目 前实现的排课系统只是满足用户现在的排课要求，还没有实 现真正的智能排课，有待进一步的研究。 ( 1 1 ) 关联规则算法 在孙建平、梅晓勇、肖 政宏、史忠植的 2 3 中，使用关联规则的思想来处 理排课问题。在课表编排过程中，考虑了教师冲突、班级冲突和教室冲突。同 时也考虑了满足一些特殊要求，如特殊课程( 体育课) 的处理要求和教师的特殊 要求。但对于以下几个方面的问题却未解决:a . 对于机房、语音室等特定资源 的使用上，可能会出现多个班级同时使用的冲突，即 “ 特定资源”冲突问题; b . 自习课问题;c . 多学时课程的均匀分布问题;d . 对好的教学日和教学时间点 合理分配的问题。 ( 1 2 ) 课元算法 在董艳云、钱晓群、张宇舒的【 3 7 中，提出了以“ 课元相关运算”和 “ 课 元的时间片计算”为核心的智能排课算法。虽然考虑了编排课程表中的各种冲 突和一般的经验常识，但在课程表的编排中只是以课程为中心，无法兼顾到授 课教师的特殊要求。 ( 1 3 ) 分组逐次算法 在王枯民、赵致格的【 3 8 中，计算机模仿了人工编排课程表的过程。按照 先难后易的原则，分组逐次排课。由于利用这种算法在编排课程表时是对全部 的课程的一个部分进行编排，这样最终形成的课程表就可能是局部的最优解， 而不是全局的最优解。 ( 1 4 ) 多阶段自动排课算法( ma c a 算法) 在钱德凤的 4 4 中提出了多阶段自 动排课算法( m a c a 算法) 。 ma c a 算法 通过使用多阶段决策理论和动态规划技术，把整个排课过程根据排课要素分为 几个阶段， 每个阶段采用不同的算法进行处理。 ( 1 5 ) 并行机任务调度算法 第 1 章 引言 在陈炼、刘昌 平的【 1 7 中，以课程表求解算法模拟并行处理任务调度过程 中的分派程序( d i s p a t c h e r ) ，以 授课事件模拟并行处理中的进程，建立了 课程表 求解过程与并行处理中进程执行过程间的内 在联系，借鉴并行处理中进程的调 度方式，设计了计算授课事件优先级的方法，并总结出基于优先级调度授课事 件的可剥夺及不可剥夺方式。 ( 1 6 ) 其它算法 还有许多学者，从矩阵编码方案、智能回溯、边着色、分层结构模型等不 同的角度给出了其它许多求解排课问题的算法。许多方案具有一定的独创性， 给研究同类问题提供了借鉴作用。但这些方案中大部分都是只针对特定的办学 单位和特定的教学资源，有很大的局限性。 1 . 3 . 2选传算法解法的优势 通过分析比 较上述各算法，我认为:用遗传算法解决排课问题是一种较好 的选择，主要原因有如下五点: ( 1 ) 遗传算法具有智能性。遗传算法在确定了编码方案、适应度函数及遗传 算子以后，算法将利用演化过程中获得的信息自 行组织搜索，适应度大的个体 具有较高的生存概率，适应度小的个体则具有较低的生存概率。遗传算法是具 有 “ 潜在学习能力”的自 适应搜索技术; ( 2 ) 遗传算法具有并行性。由于遗传算法采用种群的方式进行搜索，从而可 以同时搜索解空间内 的多个区域，并相互交流信息。这种搜索方式使得它虽然 每次只执行与 种群规 模成比 例的 计算， 而实际 上， 据g o l d b e r g d e 的 推算 进行了 大 约 。 (n ) 次 的 有 效 搜 索。 这 使 得 遗 传 算 法能以 较 少的 计 算 获 得 较 大的 收 益: ( 3 ) 遗传算法解法能够得到基本满足各方要求的课表( 全局近似最优解) ; ( 4 ) 遗传算法解法能够较好地解决各级各类学校对课表编排的特殊要求， 使 复杂的排课约束条件能够通过 “ 适应度函数值”的方式得以量化，这有利于解 决类似于排课这种模糊的不确定问题; ( 5 ) 遗传算法易于 使用 d e l p h i , v i s u a l b a s i c , v i s u a l f o x p r o 和 p o w e r b u i l d e r 等常用m i s 开发工具实现，而掌握了 这些开发工具的计算机( 或电子信息技术) 教师遍布各级各类学校。 第 1 章 引言 1 . 4现有遗传算法解决方案及其不足之处 1 . 4 . 1现有遗传算法解决方案 目 前，已 经有很多使用遗传算法求解课程表编排问 题的应用4 5 1 ( 1 ) c h u p c 和b e a s l e y j e 对课程表的一 般安 排问 题使用了 遗传算 法来进行 解决，着重于遗传算法的全局最优解搜索，避免了问题的局部最优解: ( 2 ) 日 本的 s i g e r u 在遗传算法 解决课表安排问 题中 加 入了 控制约束的 方法， 提高了遗传算法的搜索效率; ( 3 ) 针对高中课程的特点， 意大利的c o l o rn i 等人使用遗传算法解决了高中课 表的安排问题; ( 4 ) h o s u n g c .l e e 使 用遗传算 法对p h i l i p p i n e s 大学 数学学院的 课程表问 题 进 行了求解; ( 5 ) 兰慧4 6 1 使用基本遗传算法 ( s g a ) 设计了一个基于组件结构的排课系统 c a s 。 系统设计成组件结构， 每个组件完成一个较独立的逻辑功能， 增加了系统 的灵活性和可维护性; ( 6 ) 胡献华45 1 针对排课问 题引入多目 标决策协调模型， 提出了一种基于多目 标决策协调模型的适应度计算方法，并改进了遗传算法一般结构，形成了一个 多目标协同优化的排课算法; ( 7 ) 姚新使用遗传算法优化教室的合理利用，解决了在教室较少的情况下， 对教室的使用进行合理分配的问题; ( 8 ) 杨宇使用遗传算法分别对局部排课问题和全局排课问题进行了求解。 这些使用遗传算法对课程表进行编排的应用也同时说明了课程表编排问题 的解决完全可以采用遗传算法，并且使用遗传算法来解决课程表的编排问题能 够获得很好的效果。 1 . 4 . 2现有遗传算法解决方案不足之处 以上应用针对自身所描述的排课问题进行求解，虽然在一定程度都上取得 了 较好的 成果， 但综合考虑求解情况， 仍有以 下几点 不 足4 51 ( 1 ) 约束条件。由于各自的研究背景不同，他们往往考虑的只是排课问题的 第 i 章 引言 一般情况，有些甚至是理想状态的排课，对于排课中更多的约束条件未予以考 虑; ( 2 ) 求解规模。问题的求解规模普遍偏小，使得实用程度较低，很难在学校 中展开实际应用; ( 3 ) 编码方式。一种较好的遗传算法编码方式，不仅能够反映解空间完备并 无歧义的遗传信息，而且操作应当尽量简单，从而可以快速地进行遗传操作和 适应度评定，继而缩短算法的整体收敛时间。然而在现有的应用中，采用的编 码不能很好地反映更多的实际情况，而且操作不很方便: ( 4 ) 交叉及变异概率。现有的系统通常不能随着实际排课数据的变化自 适应 地调整交叉及变异概率; ( 5 ) 求解目 标。 在现有的应用中， 处理的都是单目 标问题， 即使有多个目 标， 也往往线性地聚合成单个目 标进行处理。这样求得的往往是一个非劣解，而忽 略了一组非劣解。 1 . 5论文的研究内容及创新点 1 . 5 . 1论文的研究内容 本课题的目 标是运用基于三维编码的自适应遗传算法解决普通高校的课程 表编排问题。 遗传算法是一种可以用于复杂系统优化的鲁棒性搜索算法。实践证明，遗 传算法对于组合优化中的n p 完全问 题非常有效。 已 有人尝试利用遗传算法求解 课程表编排问题，但都存在一些缺陷。 本课题在比 较目 前国内 外相关排课算法的基础上，结合我省某高校的实际 情况研制适合我国大专院校具体排课问题的解决方法，并为解决其他类似的时 间表问题提供科学依据。 要实现上述目 标，达到预期效果， 本文进行了以下几个方面的研究工作: ( 1 ) 系统、 完整地讨论了排课问题中的影响因素、 主要约束条件和求解目 标， 用数学模型描述了排课问题: ( 2 ) 改进了遗传算法的一般编码方法，综合采用三维编码和自 适应的交叉、 变异概率设计方法，提出了一套基于三维编码的自 适应遗传算法; 第 1 章 引言 ( 3 ) 以d e l p h i 7 . 0 为前台开 发t - 具， s q l s e r v e r 2 0 0 0 为 后台 数 据库， 设 计并实现了基于上述改进型遗传算法的自动排课系统。 ( 4 ) 最后以我省某高校的排课数据测试了本论文的基于三维编码的自适应 遗传算法在实际排课问题中的应用，并定量、定性地分析了测试结果。 1 . 5 . 2论文的创新点 本论文改进了遗传算法的一般编码方法，综合采用三维编码和自 适应的交 叉、变异概率设计方法，提出了一套基于三维编码的自 适应遗传算法。 ( 1 ) 采用三维染色体编码方式表达排课问题 遗传算法最常用的编码方式是二进制编码，其他的编码主要有浮点数编码、 格雷码、符号编码、多参数编码等。结合本系统的实际应用需求，均衡考虑制 约学校排课系统的各因素，本论文采用了一种新颖的三维编码方式。它具有以 下优点:可方便地利用三维数组保存排课相关信息，编码和解码直观，进行交 叉和变异运算时方便进行冲突检测和适应度计算以 及程序实现复杂度低等: ( 2 ) 采用自 适应的交叉和变异概率设计方法 通常在优化时， 交叉概率p c 和变异概率p m 依经验取固定值: p c e 0 . 2 0 , 0 . 9 5 , p me 0 . 0 0 0 1 , 0 . 1 1 ，但是这种方法具有一定的盲目性。s r i n i v a s 等人提 出了 p c , p m 随 种群整体适应度自 适应( s e l f - a d a p t i v e ly ) 改 变的方 法， 主 要思想是 根据种群的进化情况来动态地调整p c 和p m，以达到克服过早收敛和加快搜索速 度的目的。根据其原理，本论文中对交叉和变异概率的选取分别建立了如下两 个表达式: k 1 * s i n ( 7 r / 2 * ( fi n a x - f c ) / ( fi n a x - f a v g ) ) k 2 f c r - f a v g f c f a v g f k 3 * s i n ( - / 2 * ( fi n a x - fi n ) / ( fi n a x - f a v g ) ) 厂m = 5 k 4 fi n r - f a v g fi n f a v g 其中: 0 k l , k 2 , 0, k 4 , 1 :5 c mx n , l , r j , r , e 凡r e 民r ; * r 且在课程表映射函数中存在如下映射: e ; - 1 - - + r ; e j - - l -* r 上 述映 射表明同 一 个 班级c l a s s , 在同 一时 间t v 不同 的 教 室c c x 上 课， 将 这 类冲突称为班级冲突 ( 由于 “ 校区”现象，同一个班级在同一个半天内相邻时 间于不同校区上课的情况也可视为班级冲突) 。 ( 2 ) 避免冲突的方法 为保证课程表解切实可行，必须克服上述课程表冲突。克服课程表冲突的 出发点是建立合适的课程表映射函数，依据此映射函数为授课事件分配资源时 能使得所得到的映射集合中不存在导致上述冲突的映射，从而避免冲突的出现。 针对不同种类的课程表冲突，在课程表映射函数中应采取相应的制约措施17 3 a . 避免资源冲突 导致资源冲突的根本原因在于在映射过程中，资源被多次分配。因此避免 资源冲突的途径便是把资源元素视为消耗性对象。将已被分配过的资源标记为 已消耗的资源，在下一轮授课事件安排时，将这些己消耗的资源淘汰出去，从 而避免资源冲突的出现。 b .避免教师及班级冲突 教师冲突与班级冲突的共同特点是事件参与者在时间上具有不可分性，不 能在同一时间出现在两个不同的地点。因此避免这类冲突的出发点便是在排课 过程中记录事件参与者在时间上的占用情况。 ( 二) 约束 在课程表映射函数中仅仅增加避免冲突的制约规则，并不能得到科学和切 实可行的课程表解。不同的实际应用环境对课程表解还有着不同的具体要求。 为使所得的课程表解符合实际的应用环境，在映射函数中还需要增加合适的约 束来体现实际应用环境对于课程表的具体要求。以下是一些常见的课程表约束: . 尽量满足教师对于上课时间的期望; . 体育课尽量安排在下午进行: 第2 章 问题的描述 . 教师或班级接连两次上课的地点应尽量较近; . 教室容量应当大于或等于上课人数; . 较高的教室利用率 ( 上课人数/ 教室可容纳人数); . 一个班级的上课时间在一周内应尽量均匀分布: . 同一门课程授课时间均匀分布:依据教育心理学原理，在一周之内 如果 某门课程需要多次授课，则相应的授课时间在一周内的分布应当均匀， 不能出现在某一天或者连续若干天之内。例如大学英语每周授课两次， 则两次授课时间之间至少应当间隔一天