（计算机应用技术专业论文）基于遗传算法的大学排课问题的研究.pdf

延边大学工学硕士学位论文 摘要 排课问题是一个有约束的、多目标的组合优化问题，并且已经被证明是一 个n p 完全问题。 遗传算法借鉴生物界自然选择和自然遗传机制，使用群体搜索技术，尤 其是用于处理传统搜索方法难以解决的复杂的和非线性的问题。经过近4 0 年 的发展，遗传算法在理论研究和实际应用中取得了巨大的成功，本文将遗传 算法用于排课问题的求解，首先讨论了排课问题中的影响因素、主要约束条 件、求解目标和难点，并用数学模型完整地描述了排课问题。其次对多个模 糊排课目标进行了定量分析，建立了排课优化目标空间。针对排课问题研究 了染色体编码方式以及遗传算子的设计，提出了适应度函数的计算方法。最 后对排课问题进行了实验。实验结果表明，其过程的目标值跟踪显示，算法 稳健趋优，所得结果令人满意。 关键词课表问题；遗传算法：多目标优化 延边大学工学硕士学位论文 a bs t r a c t t i m e t a b l ep r o b l e mw h i c hi sp r o v e dn p - c o m p l e t e di sam u l t i 。o b j e c t i v e c o m b i n a t i o no p t i m i z a t i o np r o b l e mw i t hc o n s t r a i n t s g e n e t i ca l g o r i t h mb a s e do nt h eb i o l o g i c a lm e c h a n i s mo fn a t u r a ls e l e c t i o n a n dh e r e d i t ya n d l e v e r a g i n gc o l o n ys e a r c h i n gt e c h n o l o g y ，i sp a r t i c u l a r l y a p p l i c a b l ef o rt h er e s o l u t i o no fc o m p l i c a t e dn o n l i n e a rp r o b l e m si n t r a c t a b l ew i t h t r a d i t i o n a ls e a r c h i n gm e t h o d s f o rn e a r l y4 0y e a r s d e v e l o p m e n t ，g e n e t i c a l g o r i t h mh a sm a d eg r e a ta c h i e v e m e n t si nb o t ht h e o r yr e s e a r c ha n dp r a c t i c a l a p p l i c a t i o n s t h i st h e s i si sa i m e da ts o l v i n gt i m e t a b l ep r o b l e mu s i n gg a f i r s t l y ， f a c t o r s ，r e s t r i c t i o n s ，o b j e c t i v ea n dd i f f i c u l t ya t t a c h e dt ot i m e t a b l ep r o b l e ma r e d i s c u s s e da n dt i m e t a b l ep r o b l e mb ym a t h e m a t i cm o d e l s e c o n d l y ，t h eq u a n t i t a t i v e a n a l y s i so nf u z z yo b j e c t i v ei sg i v e no u ta n dt h eo b j e c t i v eo p t i m i z a t i o ns p a c eo f t i m e t a b l ep r o b l e mi se s t a b l i s h e d f u r t h e r m o r e ，c h r o m o s o m ec o d i n ga n dh e r e d i t y o p e r a t o rd e s i g n i n ga r es t u d i e da i m e da tt i m e t a b l ep r o b l e m ，a n daf i t n e s sf u n c t i o n c o m p u t i n gm e t h o di sp r o p o s e db a s eo nm u l t io b j e c t i v ec o n c o r d a n c e f i n a l l y ，e x p e r i m e n ti sc a r r i e do u tf o rt i m e t a b l ep r o b l e m ，a n dt h er e s u l t ss h o w t h a tt h ea l g o r i t h mi ss t e a d ya n do p t i m i z e w a r d ，t h es o l u t i o ni ss a t i s f i e d k e y w o r d st i m e t a b l i n gp r o b l e m ；g e n e t i ca l g o r i t h m ；m u l t i o b j e c t i v e i i 延边大学工学硕士学位论文 1 1 引言 第1 章绪论 课程表是一个学校日常教学工作和其他各项活动的指挥调度表。它不仅 是学生和教师上课的依据，而且对学校其他工作的统一安排也有直接影响。 利用计算机辅助手段编排课表，是教学管理实现科学化、现代化的重要研究 课题之一。 随着招生规模逐年的扩大，以及计算机在教学工作中的普及应用，用计 算机代替劳动强度大、工作效率低的手工排课工作，越来越成为教学管理中 迫切需要解决的研究课题之一。然而排课问题作为高校教学工作过程中必须 面对的问题，也是运筹学中研究的一个问题一一时间表问题( t i m e t a b l e p r o b l e m s ，简记t t p s ) ，它已经被深入细致地研究并被公认是n p 难解问题。 由于排课问题本身的复杂性和难解性，使其一直没有得到有效的解决。 本文便是在上述的背景下展开工作的，在研究和实践的过程中，结合实 际排课问题中的一些常见约束条件和优化目标，摒弃了传统的编码方式，提 出了针对排课问题的一种特殊的编码方式，把遗传算法应用于排课问题中， 用来优化排课方案。 1 2 研究目的及意义 现在大多数院校的排课方法是手工编排方法，它主要通过人智能的判断 和协调来完成的。手工编排工作往往开始于一个学期数月前，各部门的协调 交互频繁，而且在实际安排过程中，涉及的校区有多个，教师数量成千，学 生数目上万，教师跨院上课和班级交叉上课众多，而且在计划安排完毕之后， 往往由于频繁的变动不得不及时调整。所有诸如此类因素，使得排课工作不 堪重负，工作结果也不尽人意。随着办学规模的扩大，学科种类、专业数、 学生人数也都逐年增加，而教学资源相对紧张，采用人工的编排方法已经难 以完成高校课表编排的工作要求。 计算机排课是把排课问题化为计算机领域的有约束的时空组合优化问题 进行求解的。它对课表上的时间进行了分片处理，使分成的每个时间片和每 延边大学工学硕士学位论文 个教室空间组合，构建了一个个大小不等的时空组合块，并根据求解规则， 对每个开课计划进行时空组合块分配，而且分配的组合( 排课方案) ，必须在 目标空间中表现出良好的满意度。这些满意度往往不仅多个，而且是模糊的。 虽然利用计算机来模拟手工排课工作，可以抽象问题中的各个要素，数学表 达各种约束条件，并根据课表的组织形式和普遍存在的规律，缩减了问题空 间的搜索范围，以及有效组织了排课，使其在一定程度上呈现智能化。但由 于其问题本身的求解规模过于庞大，各要素之间的关联层出不穷，以及人们 对多个课表优劣评定的准则存在一定差异，使计算机在求解排课问题的过程 中，面对难以穷尽的组合和多个模糊目标的优化，也表现得无能无力。就其 实质而言，排课问题是一个有约束的、非线性的、模糊多目标优化的、难解 的、时空组合的数学问题，即在满足各种己知的约束条件的情况下找到一组 较优的时空组合，同时在具体实践上受到教学组织形式、客观物质条件和求 解目标等多种因素的相互影响，使这一问题在实际解决时呈现出受具体条件 制约的特点。 计算机排课系统的研究是当前各大高校数字化教学教务改革中面临的一 个比较突出的问题。排课是各个大学的教务部门的常务性工作，每个学期的 排课都是教务人员管理中艰巨的工作之一，采用人工排课已经难以完成高校 课表的编排i l ，2 l 。所以，利用计算机排课已经受到越来越广泛的关注，并且成 为迫切需要解决的实际问题。 1 3 排课问题研究评述 国外从2 0 世纪5 0 年代末就对排课问题开展了研究。1 9 6 3 年g o t l i e b 在 他的文章中就对课程表问题做了形式化的描述【3 】，提出了排课问题的数学模 型，它标志着排课问题的研究正式跨入了庄严的科学殿堂，但由于在实践中 遇到的困难，使人们对排课问题的解是否存在产生了疑问。1 9 7 6 年se v e n 和c o o p e r 等人证明了排课问题是n p 完全的【4 ，5 】，这虽然回答了排课在实践 中遇到困难的原因，但同时等于宣布计算机解决排课问题无法实现，因为计 算机难解性的理论研究指出，现代计算机尚未找到解决n p 完全问题的多项 式算法。此后这一问题的研究大多离开理论研讨的轨道而转向经验方式，这 使8 0 年代的许多排课系统缺乏普适性。se v e n 的论证正式确立了排课问题 的学术地位，把人对课表编排复杂性的认识提高到了理论的高度。 从1 9 6 3 年g o t l i e b 提出了一个排课问题的数学模型之后【4 j ，人们又对排课问 延边大学工学硕士学位论文 题的算法作了许多探索，但由于排课问题是n p 完全问题，并且易受实际问题 边界的影响，大多数求解结果都不理想。f e r l a n d 等人和吴金荣把排课问题化 成整数规划来解决m 。j ，但计算量很大，而且仅仅适用于规模很小的课表编排， 对于大规模复杂的排课情况，至今没有一个切实可行的算法。还有何永太和 胡顺仁等人试图用图论中的染色问题来求解排课问题 8 。9 】，可惜图的染色问题 本身也是n p 完全问题。由于问题的复杂性，许多方法是利用启发式函数来解 决排课问题 t o 1 9 】，大多数启发式方法都是模拟手工排课的过程来实现的。由 于实际的排课问题存在各种各样的限制条件与特殊要求，对这些因素处理的 好坏就显得尤为重要。进入2 0 世纪9 0 年代，国外对排课问题的研究仍然非常 活跃。如印度v a s t a p u r 大学管理学院的a r a b i n d at r i p a t h y 、加拿大m o n t r e a l 大学 的j e a na u b i n 和j a c q u e sa f e r l a n d 以及c h a r l e sf l e u t e n t 等】。m a b i n d at r i p a t h y 的工作是以“人”为单位进行课表编排的。他运用拉格朗日松弛法和分支定 界技术求解，这种方法的缺点是为了减少变量的个数，人为造成了科目间的 冲突。a t r i p a t h y 还研究了研究生课表编排问题，采用多重课组的方法来处理 冲突，即根据学生选课的矛盾情况，将人数多的课程在一星期内开多次。 j a c q u e sa f e r l a n d 等人则把排课问题分成两个子问题，时间表问题和分组问 题。在时间表问题中，根据学生注册情况、教师和教室的可利用情况形成一 个主时间表。对于选课人数较多的大课，一个星期要分成几个时间段来上， 分组问题就是将学生分给各时间段。两个问题相互关联，通过惩罚因子来构 造启发式函数。他们研制的s a p h i r 课程调度决策支持系统分为数据处理、自 动优化、交互优化等几个模块。该系统解决矛盾的主要方法也是采用多重课 组。这与西方的教学管理体制是不可分的。另外一批学者还将模拟退火法应 用到排课问题的研究中【1 0 ， 1 1 】，【2 l 】，1 2 2 1 。模拟退火法( s i m u l a t e d a n n e a l i n g ) 是 k i r k p a t r i c k 等人于1 9 8 3 年首先提出的【2 3 】，它是人们从自然界固体退火过程中得 到启发并从中抽象出来的一种随机优化算法。模拟退火法用于求解优化问题 的出发点是基于物理中固体物质的退火过程与一般优化问题间的相似性。在 对固体物质进行退火处理时，常先将它加温使其粒子可自由运动，以后随着 温度的逐渐下降，粒子逐渐形成低能态晶格。若在凝结点附近的温度下降速 率足够慢，则固体物质一定会形成最低能量的基态。优化问题也存在类似过 程。模拟退火法被用来解决许多实际应用中的优化问题，取得了不错的效果， 但用其解决排课问题，现在还处在模型实验阶段，还有许多问题要解决。 国内对排课问题的研究开始于8 0 年代初期，所用方法从模拟手工排课到 运用人工智能构建专家系统或决策支持系统。基于时间位图迭加匹配的算法【l 2 】 延边大学工学硕士学位论文 定义了教学过程中的时间位图、课时模式和时间匹配等概念，将排课问题转 化为基于时间位图迭加匹配的课时模式查找问题，给出了相应的抽象具体排 课过程，并对于排课过程中可能出现的冲突，探讨了三种回溯消除冲突方式。 基于优先级自动排课算法【1 3 】利用了运筹学中分层规划的思想，把排课问题在 数学上看作为一个在时间、教师、学生和教室四维空间，以教学计划和各种 特殊要求为约束条件的组合规划问题，采用了化整为零的思想并且提出了优 先级的概念，有效地抽象了实际排课问题，缩小了求解问题的空间。基于专 家系统的求解算法 2 4 。2 6 】将专家系统知识引入排课问题的求解中，有效组织排 课过程中的知识，使各种排课逻辑从程序中解放出来，能够便于各种排课经 验的累计，使排课结果更加符合实际情况。 更多算法己经提出，它们都是一定程度上启发搜索求解方法，虽然有一 定的借鉴意义，但它存在以下几点不足之处： ( 1 ) 对于启发式搜索技术来说，搜索过程的启发信息依赖于实际情况，排 课问题的求解只能针对个别的实际问题，不能形成一种通用的有效排课方法。 ( 2 ) 引入专家系统技术的排课方法，虽然可以有效地组织排课规则和知 识，但由于排课过程中各要素关联规则难以提取，并且实际求解效果也不理 想。 ( 3 ) 没有引入目标优化技术，课表的优劣判定的论述很少，只能在问题的 某个方向进行搜索，不可能达到多个目标同时优化。 对于排课系统的研发，林漳希和林尧瑞1 9 8 4 年发表了该课题上的实验性 研究成果1 2 “。成形的系统有大连理工大学1 9 9 8 年推出的的教学调度系统3 o o 版本和由清华大学计算机与信息管理中心开发的综合教务管理系统t i s e r p b 。这些应用界面很友好的排课软件已经可以帮助排课人员大大提高工作 效率。但遗憾的是，这些系统只能在排课过程中辅助工作人员进行排课，并 没有一套完善有效的自动排课算法。这些系统都模拟他们各自的手工排课， 当人工输入的条件达到一定的限制程度时，软件运行就有可能出现死锁现象， 不能得出结果或者不能得到需要的结果。一旦出现了这种现象，就要把所有 的数据作废或者打乱重排，之前做的工作都付诸东流。高校的课程、教室、 教师等因素都十分复杂，排课所需数据量也十分庞大，所以造成的时间、人 力损失也非常巨大。使得系统的实际应用非常困难，后期人工调整的工作量 并不比重新排课的工作量小很多。同时，国内的排课软件很少，涉及到自动 排课算法的系统更少，大部分局限于辅助人工排课，并没有任何“智能”处 理。 延边大学工学硕士学位论文 随着人工智能的发展，特别是在计算智能领域的拓展，借鉴于生物界进 化思想和遗传机制的遗传算法，由于其超群的并行搜索能力，以及在解决优 化问题中表现出来的高度鲁棒性，己经被广泛应用于各个领域。 作为一种随机的优化与搜索方法，遗传算法有两个主要特性【3 0 】： ( 1 ) 智能性。遗传算法在确定了编码方案、适应值函数及遗传算子以后， 算法将利用演化过程中获得的信息自行组织搜索。适应值大的个体具有较高 生存概率，它是具有“潜在学习能力”的自适应搜索技术。 ( 2 ) 并行性。由于遗传算法采用种群的方式组织搜索，从而可以同时搜索 解空间内的多个区域，并相互交流信息，这种搜索方式使得它虽每次只执行 与种群规模成比例的计算，而实质上，据g o l d b e r gd e 推算已进行了大约o 3 1 次有效搜索。这使得遗传算法能以较少的计算获得较大的收益。 正是由于遗传算法的这两个特性，使得遗传算法迅速被应用于求解组合 优化的排课问题。c h upc 和b e a s l e y 对一般的排课问题使用了遗传算法进行求 解i j ”，他们着重于遗传算法的全局最优解的搜索能力，避免了问题的局部最 优解。日本的s i g e r u 用具有控制约束的遗传算法来解决大学排课问题【3 2 ，提高 了遗传算法的搜索效率。姚新使用遗传算法优化了教师的合理利用，解决了 在教室较少的情况下，如何对教室的利用进行合理的分配【3 3 】。针对高中课程 的特点，意大利的c o l o r n i 等人使用遗传算法解决了排课问题【圳。张春梅等人 对大学课程进行分类，并对不同的课程使用具有自适应能力的遗传算法进行 了安排”。他们针对自身所描述的排课问题进行求解，虽然在一定程度上取 得了喜人的成果，但综合考虑其求解情况，仍有以下几点不足： ( 1 ) 求解问题的边界定义。由于各自的研究背景不同，他们考虑的往往是 排课一般情况，有些甚至是理想状态的排课，对于排课中更多的约束条件未 予以考虑，而且问题的求解规模普遍偏小，使得实用程度较低，很难在学校 中展开使用。 ( 2 ) 问题的编码。一种较好的遗传算法的编码方式，不仅能够反映解空间 完备并无歧义的遗传信息，而且操作尽量简单，从而可以快速进行遗传操作 和适应值的评定，继而影响算法整体的收敛时间。在以往的研究中，他们编 码虽然通俗易懂，。但不能很好地反映针对更多实际情况的遗传信息，而且操 作很不方便。 ( 3 ) 求解的目标。以往的应用中，采用惩罚函数居多，处理的都是单目标 问题，即使有多个目标，。往往也线性聚合成一个目标进行处理。这在多目标 优化理论中，往往求解所得的是一个非劣解，而忽略了一组非劣解。 延边大学工学硕士学位论文 1 4 遗传算法简述 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是一种借鉴生物界自然选择和进化机 制发展起来的高度并行、随机、自适应的随机搜索算法。由于其具有健壮性， 特别适合于处理传统搜索算法解决不好的复杂的和非线形问题。简单的讲， 它使用了群体搜索技术，从而产生新一代的种群，并逐步使种群进化到近似 最优解的状态。 1 4 1 遗传算法的发展 遗传算法研究的历史比较短，它出现在2 0 世纪6 0 年代初期，主要是由美 国m i c h i g a n 大学的j o h nh o l l a n d 与其同事、学生们研究形成的一个比较完整的 理论和方法，从试图解释自然系统中适者生存的过程入手，模拟生物进化的 机制来构造人工系统的模型。经过2 0 余年的发展，计算智能已经成为人工智 能研究的一个重要方向，以及后来人工生命研究的兴起，使遗传算法受到广 泛的关注。从1 9 8 5 年在美国卡耐基梅隆大学召开的第一届国际遗传会议 ( i n t e r n a t i o n a lc o n f e r e n c eo ng e n e t i ca l g o r i t h m s ：i c g a ，8 5 ) ，到19 9 7 年5 月 i e e e 的t r a n s a c t i o no ne v o l u t i o n a l r yc o m p u t a t i o n 仓l j ：f i j ，遗传算法作为具有系统 优化、自适应和学习的高性能计算和建模方法的研究渐趋成熟。 1 4 2 遗传算法的基本思想 遗传算法是从代表问题可能潜在解集的一个种群( p o p u l a t i o n ) 开始的， 而一个种群由经过基因( g e n e ) 编码( c o d i n g ) 的一定数目的个体组成。每 个个体实际上是染色体( c h r o m o s o m e ) 带有特征的实体。染色体作为遗传物 质的主要载体，即多个基因的集合，其内部表现是某种基因组合决定的。初 始种群产生以后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越 好的近似解。在每一代，根据问题域中个体的适应度大小挑选个体，并借助 代表自然遗传学的遗传算子( g e n e t i co p e r a t o r s ) 进行组合交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) ，产生出代表新的解集的种群。这个过程导致种群象自然 进化一样，后代种群比前代更加适应于环境，末代种群中最优个体经过解码 ( d e c o d i n g ) ，可以作为问题的近似最优解。 遗传算法采纳了自然进化模型，如选择、交叉、变异、迁移、局域与邻 域等。与传统搜索算法不同，遗传算法是从一组随机产生的初始解开始搜索 延边大学工学硕士学位论文 过程。种群中的每个个体是问题的一个解，称为“染色体”。染色体是一串 符号，比如二进制串。这些染色体在后续迭代中不断进化，称为遗传。在每 一代中用适应度来测量染色体的好坏。生成的下一代染色体称为后代 ( o f f s p r i n g ) 。后代是由前一代染色体通过交叉或者变异运算形成的。新一代 形成中，根据适应度的大小选择部分后代，淘汰部分后代，从而保持种群大 小的稳定性。适应度高的染色体被选中的概率高，这样，经过若干代之后， 算法收敛于最好的染色体，它很可能就是问题的最优解或次优解。 1 4 _ 3 遗传算法的一般结构和遗传操作 图卜l 表示了遗传算法的一般结构。由图可以看出，最佳个体是这样产生 的：首先产生一个个体进行适应度计算，适应度表示了个体对环境的适应程 度。计算后的个体进行是否满足优化准则的判定，如果满足，那么算法找到 了这个个体并停止。如果不满足准则，那么算法将对这个种群进行选择、交 叉、变异操作。遗传操作的目的是从初始种群中筛选出较优异的个体进行演 化，这其中就包括复制优秀个体重生、两个父个体进行交叉和单个体的变异 这三种方式。对演化后的子代群体，重新进行优化准则判定，如此循环下去， 直到找到一个最优个体，或者达到其循环条件为止。 延边大学工学硕士学位论文 图卜1 遗传算法的一般结构 f i g 1 - 1t h es t r u c t u r eo f g e n e t i ca l g o r i t h m 延边大学工学硕士学位论文 下面我们介绍遗传算法中的基本操作 遗传算法包括三个基本操作：选择、交叉和变异。这些基本操作又有许多 不同的方法。 1 4 3 1 选择( s e l e c t i o n ) 选择是用来确定重组或交叉个体，以及被选个体 将产生多少子代个体。首先计算适应度，适应度计算之后是实际的选择，按 照适应度进行父代个体的选择。可以挑选以下的算法： 轮盘赌选择( r o u l e t t ew h e e ls e l e c t i o n ) 随机遍历抽样( s t o c h a s t i cu n i v e r s a ls a m p l i n g ) 局部选择( l o c a ls e l e c t i o n ) 截断选择( t r u n c a t i o ns e l e c t i o n ) 锦标赛选择( t o u r n a m e n ts e l e c t i o n ) 1 4 3 2 交叉或重组基因( c r o s s o v e r r e c o m b i n a t i o n ) 基因重组是结合来自父 代交配种群中的信息产生新的个体依据个体编码表示方法的不同，可以有以 下的算法： 实值重组( r e a lv a l u e dr e c o m b i n a t i o n ) 离散重组( d i s c r e t er e c o m b i n a t i o n ) 中间重组( i n t e r m e d i a t er e c o m b i n a t i o n ) 线形重组( l i n e rr e c o m b i n a t i o n ) 扩展线性重组( e x t e n d e dl i n e rr e c o m b i n a t i o n ) 二进制交叉( b i n a r yv a l u e dc r o s s o v e r ) 单点交叉( s i n g l e p o i n tc r o s s o v e r ) 多点交叉( m u l t i p l e - p o i n tc r o s s o v e r ) 均匀交叉( u n i f o r mc r o s s o v e r ) 洗牌交叉( s h u f f l ec r o s s o v e r ) 缩小代理交叉( c r o s s o v e r 谢mr e d u c e ds u r r o g a t e ) 1 4 3 3 变异( m u t a t i o n ) 交叉之后子代经历的变异，实际上是子代基因按 小概率扰动产生的变化。依据个体编码表示方法的不同，可以有以下的算法： 实值变异 二进制变异 9 延边大学工学硕士学位论文 1 4 4 遗传算法的特点 遗传算法是基于自然选择和基因遗传学原理的搜索算法，它将“优胜劣 汰，适者生存”的生物进化原理引入待优化参数形成的编码群体中，按照一 定的适应值函数及一系列遗传操作对各个体进行筛选，从而使适应值高的个 体被保留下来，组成新的群体，新群体包含上一代的大量信息，并且引入了 新的优于上一代的个体。这样周而复始，群体中各个体适应度不断提高，直 至满足一定的极限条件。此时，群体中适应值最高的个体即为待优化参数的 最优解。正是由于遗传算法独特的工作原理，使它能够在复杂空间进行全局 优化搜索，并且具有较强的鲁棒性，另外，遗传算法对于搜索空间，基本上 不需要什么限制性的假设( 如连续、可微等) 。常规的优化算法，如解析法， 只能得到局部最优化而非全局最优，且要求目标函数连续光滑及可微。枚举 法虽然克服了这些缺点，但计算效率太低，对于个实际问题常常由于搜索 空间太大而不能将所有的情况都搜索到，即使很著名的动态规划法，也遇到 “指数爆炸”问题，它对于中等规模和适度复杂性的问题，也常常无能为力。 遗传算法通过对参数空间编码并用随机选择作为工具来引导搜索过程朝 着更高效的方向发展。同常规优化算法相比，遗传算法有以下特点【3 6 j ： ( 1 ) 遗传算法是对参数的编码进行操作，而非对参数本身。遗传算法首先 基于一个有限的字母表，把最优化问题的自然参数集编码为有限长度的字符 串。优化过程的第一步是把参数编码为有限长度的字符串，常用二进制字符 串。随机生成n 个字符串组成初始群体，对群体中的串进行遗传操作，直至满 足一定的终止条件，求得的最终群体中适应值最大的字符串对应的参数即为 所求解。遗传算法是对一个参数编码群体进行操作，这样提供的参数信息量 大，优化效果好。 ( 2 ) 遗传算法是从许多点开始并行操作，而非局限于一点，因而可以有效 地防止搜索过程收敛于局部最优解。 ( 3 ) 遗传算法通过目标函数来计算适应值，而不需要其他推导和附加信 息，从而对问题的依赖性较小。 ( 4 ) 遗传算法的寻优规则是由概率决定的，而非确定性的。 ( 5 ) 遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机 搜索。 ( 6 ) 遗传算法对于待寻优的函数基本无限制，它既不要求函数连续，也不 要求函数可微。既可以是数学解析式所表达的显函数，也可以是映射矩阵甚 延边大学工学硕士学位论文 至是神经网络等隐函数，因而应用范围较广。 ( 7 ) 遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计 算速度。 ( 8 ) 遗传算法更适合大规模复杂问题的优化。 ( 9 ) 遗传算法计算简单，功能强。 1 4 5 遗传算法与其他搜索技术的比较 对于课程表的编排这类整体优化问题的搜索求解技术，主要包括基于微 分的搜索技术、随机搜索技术、启发式搜索技术和枚举技术。遗传算法属于 进化算法，而进化算法及进化算法中的每一个分支均属于启发式随机搜索方 法。 目前，对于求解整体优化问题已经进行了大量理论研究，并提出了许多 基于导数的解析方法和其他非解析的数值集约化技术。但是，在实际领域中 存在着各种高度复杂的优化问题，其目标函数可能表现为非连续或非处处可 微、非凸、多峰和带噪声等各种形式，这类复杂优化问题不适合于采用解析 方法，同时用传统上的搜索技术求解也会遇到许多困难。因此，多年来人们 一直在努力寻找能够处理这类问题的新的、更稳健的优化技术。借鉴于自然 界的进化过程，h o l l a n d 首先将g a 用于计划的优化和选择，使得g a 逐渐成为 一种典型的启发式随机搜索算法，。为求解优化问题提供了一个有效的新工具。 采用g a 以及e s ( e v o l u t i o n a r ys t r a t e g i e s ，进化策略) 、e p ( e v o l u t i o n a r y p r o g r a m m i n g ，进化规划) 等一类进化算法来求解整体优化问题是目前进化计 算研究和应用的重点，统称为“进化优化”，而用来求解整体优化问题的遗 传算法也被称为“遗传优化器”。 传统的基于微分的方法，包括直接法( 如爬山法) 和间接法( 如求导数 方法) ，对问题性质有较高的要求，或者是针对特定问题形式而设计的，一 般统称为强方法。枚举方法是一种解空间的搜索方法，包括动态规划法、隐 枚举法和完全枚举法等，其特点是可以发现问题的全局最优解，但是计算效 率太低，不适用于大型优化问题求解。随机搜索方法是在问题空间中随机选 择一定数量的点，然后从中选优，带有一定盲目性，对于问题不能保证解的 质量，而且其计算效率与枚举方法基本等价。 启发式随机搜索方法是目前关于复杂优化问题求解的一类有效方法，不 需要或需要很少的关于问题的先验信息。其次，该类算法具有很强的鲁棒性， 延边大学工学硕士学位论文 即能适应不同领域的优化问题求解，并在大多数情况下都能得到比较满意的 解。启发式随机搜索方法一般统称为弱方法。g a 就是一种典型的弱方法，与 模拟退火算法、爬山算法等相比，具有独特的算法形式和运行机理，在复杂 优化问题求解中有着比较显著的优势。 与传统的启发式优化搜索算法相比，遗传算法的主要本质特征在于群体 搜索策略和简单的遗传算子。群体搜索使遗传算法得以突破邻域搜索的限制， 可以实现整个解空间上的分布式信息探索、采集和继承。遗传算子仅仅利用 适应值作为运算指标进行染色体的随机操作，降低了一般启发式算法在搜索 过程中对人机交互的依赖。这样就使得遗传算法获得了强大的全局最优解搜 索能力、问题域的独立性、信息处理的隐并行性、应用的鲁棒性、操作的简 明性，是- - j ；o o 具有良好普适性和可规模化的优化方法。从遗传算法的特点可 以看出，利用遗传算法求解排课问题，与利用其它启发搜索方法相比较，其 搜索过程带有自组织的智能性和并行性，且操作简单，可以更少地依赖于实 际问题的情况，实现课表的优化。 1 5 本文的研究内容 由于排课问题是一个有约束的、多目标的、难解的组合优化问题，采用 具有智能型和并行性的遗传算法，来对排课问题进行求解，是所有求解该问 题方法中比较明智的选择。本文旨在基于遗传算法的基础之上，提出一个课 表方案的优化算法，能够较大程度地反映实际排课情况和尽量达到多个目标 最优化。本文研究的主要内容有： ( 1 ) 详细说明排课问题的各要素及一般的常用约束条件，分析排课问题的 求解难点和目标，提出排课问题的完整数学描述。 ( 2 ) 对多个排课问题的目标进行量化分析，建立遗传算法优化的目标空 间。针对排课问题进行染色体编码以及各个遗传算子设计，对多目标的适应 度的确立展开讨论，最后提出排课整体优化算法。 ( 3 ) 对一个实际算例，利用上述的遗传算法的排课优化算法进行求解。并 对一些中间参数进行跟踪分析，从实验的角度论证算法的可行性。 延边大学工学硕士学位论文 第2 章课程表的编排问题 2 1 排课问题概述 排课工作开始于教学计划的编制。即教务处必须在每学期前收集各个学 院下学期的开课信息，然后统计下学期全校可用的教学资源，与各学院协调 交互，决定各校区的时间组织形式和各门课程的开课与否，最后根据不同的 专业，以班级为单位编制下学期的开课任务书。开课任务书应包括全校每个 班级的开课计划表，而开课计划表中的每个开课计划都应该包含班级、教师、 课程、课程类型、开课学院、校区、人数、需求教室资源类型、每周课时的 情况、有特殊要求的上课方式等信息。教学计划实施的关键是课表的编排。 根据课程和课程的特性，或者出于特殊情况的考虑，某些开课计划有着先于 全校统一安排的要求，则这些课程必须优先安排预置，上报教务处备案。等 特殊开课计划安排完毕，教务处逐个对开课计划进行安排。在此过程中，还 必须遵守多个排课原则： ( 1 ) 在同一时间同一学生不能上两门不同的课程； ( 2 ) 在同一时间同一教师不能上两门不同的课程； ( 3 ) 在同一时间同一教室不能安排两门不同课程； ( 4 ) 教室必须足够大，能够容纳上课的学生。 而且般还有以下多个目标： ( 1 ) 一个班级的课程时间安排在天上应尽量分布均匀： ( 2 ) 对于校区设置的课表的各个时间存在一定的偏好； ( 3 ) 尽量满足教师上课时间的期望； ( 4 ) 教师对时间安排在课表上的密度有一定的喜好； ( 5 ) 教师和班级相邻两次上课地点应尽量较近； ( 6 ) 教师、学生在不同校区上课时要留一定的时间用于赶赴，等等。 2 2 排课的目标分析 2 2 1 排课因素 排课问题需要考虑的因素几乎是全校性的，像能单独完成某种任务的机 延边大学工学硕士学位论文 器一样。学校是一个有机组合而成的整体，其内部各组成部分既各司其职， 又密切协调合作，以保证日常正常教务工作的运转和教学任务的完成。 从排课过程可能引起潜在冲突的角度，可以将排课问题涉及因素逐项考 虑如下： ( 1 ) 时间因素：在排课问题中涉及关于时间的概念一般为学年、学期、周、 天、时段、节次。上课时间一般是按照周来计算的( 即一个周课表) ，从开 学第一周到第n 周。每周分为m 天( m 7 ) 。每天分为5 个时间段( 上午2 个时 间段、中午1 个时间段、下午2 个时间段) 。一个时间段一般为两节课( 两个 课时) 。 ( 2 ) 课程要素：每个课程都有自己的课程代码、课程名称以及开课班级。 每个课程可以有指定的教师，也可以没有指定的教师。每门课程都有自己的 教室类型，如一般教室、多媒体教室、语音室、实验室、机房、运动场等等。 每门课程都有授课计划，包括学时数以及周学时数的安排。 ( 3 ) 教室因素：每个教室都有教室编号和名称。每个教室都隶属于某个教 学区域。每个教室都有自己的教室类型。一个教室在同一时间只能接纳一门 课程的授课，并且教室容量应该大于或者等于上课的人数。 ( 4 ) 班级因素：每个班级都有班级代码及名称。每个班级隶属于某个学院。 一个班级同一时间只能上一门课程。 ( 5 ) 教师因素：每个教师都有自己的教师代码及名称。每个教师在同一时 间只能上一门课程。 2 2 2 排课的约束条件 排课是将教师与学生在时间和空间上根据不同的约束条件进行排课组 合，以使教学工作正常进行。这里的约束条件主要是避免冲突。避免冲突也 是排课问题中要解决的核心问题。只有在满足全部约束条件和避免所有冲突 的基础上，才能保证整个教学计划合理正常进行。对教师、班级、课程、时 间、教室等几部分资源进行最优化配置，才能保证排课的顺利完成以及充分 发挥各个资源的优势以达到提高教学质量的目的。 这里的约束条件我们可以分为硬约束和软约束。硬约束是指教师、班级、 教室在时空概念上发生了不可能发生的事情，也就是发生了冲突。它是排课 过程中需要满足的最基本的约束条件，是排课时必须遵循的原则，否则将会 导致排课结果无意义。软约束则是指排课过程中若满足则更佳，不满足也无 延边大学工学硕士学位论文 所谓的约束条件。硬约束是衡量排课方案是否切实可行的标准，软约束则是 衡量排课方案优劣的标准。通常衡量排课方案的标准有多个，以下是根据延 边大学校情制定的约束条件。 硬约束条件：( 1 ) 在同一时间同一班级不能上两门不同的课程。 ( 2 ) 在同一时间同一教师不能教授两门不同的课程。 ( 3 ) 在同一时间同一教室不能安排两门不同的课程。 ( 4 ) 教室容量必须大于或等于实际上课人数。 软约束条件：( 1 ) 班级课程表在星期上尽量分布均匀。 ( 2 ) 一周的课表中每个上课时间都有一定的优度。 ( 3 ) 对于一门课程一周上多次情况，考虑上课时间尽量分 隔。 ( 4 ) 相邻上课地点尽可能距离较近，等等。 2 2 3 排课问题的组合爆炸和不确定性 经典的组合规划问题的求解，主要依靠约束条件来实现。只要约束条件 充分，那么最优的组合方案就能被唯一确定。因此，从理论的角度来说，组 合规划作为描述课表问题的数学模型没有什么不妥，但在实际工作中，随着 论域范围的膨胀，组合方案的增加，规划问题也就变得十分复杂。 表2 1 是s 、d 、t 类课程随课表空格n 的变化而产生的组合方案数的变化， 我们在这里只考虑一周5 天，一天3 个时段的情况。 s 类课程是一周上一次课，d 类课程是一周上两次课，t 类课程是一周上三 次课。 设表的空格数为n ，一个课程计划课次数为m ，则此门课程的组合方案数 为c ：，当n 和m 变化时，课程编排方案数变化如表所示。 表2 1 课表组合方案数 t a b 2 1c o m b i n a t i o n so f t h et i m e r a b l e 12 34567891 01 11 21 31 41 5 s l234 567891 01 11 21 31 41 5 d ol361 01 1 52 l 2 83 64 55 56 67 89 11 0 5 t oo141 02 03 55 68 41 2 0 1 6 5 2 2 0 2 8 63 6 44 5 5 延边大学工学硕士学位论文 幽2 1 课表组合方案数变化 f i g 2 - 1t h ec h a n g eo f t h et i m e t a l b e sc o m b i n a t i o n 从上述2 一l 表和2 1 图可以看出： ( 1 ) 若课表空格数相同，则课类越高，相应的编排方案越多； ( 2 ) 若课类相同，则课表空格越多，相应的编排方案也就越多； ( 3 ) 若课类越高，随课表空格的增加，编排方案数也就增加的越快。 显然编排方案越多，从中选择“最优”方案时需要的约束条件就越多，组 合规划求解也就越困难。 如果还要考虑各门课的先后安排次序以及一学期单双周上的变化，那么 方案的可排数目随问题规模的缓慢增长将急速上升。这种空间向量稍有增加， 就引起课表编排方案数量急剧增加的现象，称为“组合爆炸”。对于此类问 题的求解，在理论上是可行的，但即使放在当今世界最先进的计算机上，也 要运行上百年，因此类求解方法对实际情况来说毫无意义。因此，如何从实 际情况出发，采取适当的措施，抑制“组合爆炸”，缩小搜索空间，成为排 课问题中的一个关键问题。显然，按照经典的组合规划理论，编排方案越多， 从中选择“最优”方案时需要的约束条件就越多，组合规划求解就越困难。 而要想在排课问题中寻找足够的约束条件根本就是不可能，况且，很多约束 条件都是出于人的主观动机，这类约束条件是很难用明确的数学公式表达的。 对于经典的组合规划来讲，如果约束条件不充分，那么这个解就不可能是唯 一的，而是一个集合。在这个集合中，各个方案之间的差异将被忽略，这种 忽略我们称为方案优劣差异的融合，这种融合正是课表问题的不确定性的根 源。 渤瑚湖瑚挪黼m m 弱o 延边大学工学硕士学位论文 一张空的课程表是最容易安排的，因为我们可以立即按照最理想的方案 将待排课程填入。然而，如果按照规划模型来处理此类事情将非常复杂，模 糊数学的创始人l a 扎德曾经说过，“系统分析和计算机模拟的一般技术( 这 些技术立足于数值的精确计算的基础上) ，在本质上无法把握人类思维过程 的高度复杂性【3 ”。这就是说，要想对人文系统的行为作出有意义的论断，可 能必须抛弃高标准的严格性和精确性。对已构成的机器系统的数学分析再也 不能过高要求，对于本质上近似的方法也应该更加宽容。可能只有这样做， 计算机模拟才能分析对于一般定量技术来说太复杂或太不完善的系统的有效 工具”。的确，我们应该抛弃寻求“单个最优”方案的企图，除了满足所有 “硬性”约束条件以外，可以把人工排课中的“合理、使用、特色”的要求 ( 常被处理为软约束) ，作为排课的目标进行优化处理。当然，这种用语言 变量表达的要求是模糊的，本学位论文将通过一些方式将这些模糊的要求进 行精确处理，以便在算法中可以识别判断。 2 2 4 排课的求解目标 排课问题实质上是一个多目标的组合规划问题，对组合规划问题如果想 找到最优解，必须有相应的约束条件来实现。可是，对于部分属于人文范畴 的排课问题，不可能找到充足的约束条件，而且由于课表方案优劣差异的融 合，能够找到的解将不可避免的是一个解集合，这个集合中所有解都是可