（化工过程机械专业论文）基于遗传算法的自动排课问题的研究.pdf

摘要 排课问题是一个有约束的、多目标的组合优化问题，并且已经被证明为一 个n p 完全问题。 遗传算法是一种借鉴于生物界自然选择和进化机制发展起来的高度并行、 自适应的随机搜索算法，是一种非常有效的解决n p 完全的组合问题的方法。本 文将遗传算法应用于排课问题的求解，进行了以下几个方面研究工作： 1 系统完整地讨论了排课问题中的影响因素、主要约束条件、求解目标和 难点，用数学模型完整地描述了排课问题，并提出了排课问题求解方法 的总体框架和技术路线。 2 给出了排课问题的e r d 和类图，设计了排课系统的数据结构，并以此 对课表安排过程的各个子算法进行了研究，提出了一个具有局部回溯和 启发能力的、易于快速生成可行方案的随机安排算法。 3 对多个模糊排课目标进行定量分析，建立了排课优化目标空间。 4 针对排课问题研究了染色体编码方式以及遗传操作算子的设计，并引入 多目标决策协调模型，提出了种基于多目标决策协调模型的适应度计 算方法，并改进了遗传算法一般结构，形成了套多目标协同优化的排 课算法。 5 。以v c + + 和d e l p h i 为基本开发工具，m ss q ls e r v e r 2 0 0 0 为后台数据 库，设计和实现了基于g a 算法的自动排课系统。经过对一个具有两个 校区、共2 2 9 5 个教师和9 9 6 个班级的1 9 7 3 个开课计划的实例，在由节 次优度、日分布均匀度、教师时间期望和教师课时分布四个因素组成的 目标空间上进行求解，所得结果令人满意，其过程的目标值跟踪显示， 算法稳健趋优。该系统已在浙江工业大学等多所高校的排课工作中展开 应用，大大提高了工作人员的排课效率。 关键词：排课问题，遗传算法，多目标优化，多目标决策协调，组合优化 来经作者、导肺同意 ，i 一 匆全文公布 a b s t r a c t t i m e t a b l i n gp r o b l e m ( t p ) i sam n l t i o b j e c t i v ec o m b i n a t i o no p t i m i z a t i o n p r o b l e mw i t hc o n s t r a i n t s ，a n da l s oh a sb e e n p r o v e dn p c o m p l e t e d g e n e t i ca l g o r i t h m ( g a ) i sah i g h e f f e c t i v er a n d o m l ys e a r c h i n ga l g o r i t h m ， b a s e do nt h en a t u r ee v o l u t i o n i ti sav e r ye f f e c t i v e a l g o r i t h m t or e 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 no p t i m i z a t i o np r o b l e m t h ep a p e ri sa i m e da t s o l v i n gt i m e t a b l i n gp r o b l e mu s i n gg a t h e m a i nc o n t e n ta r ea sf o l l o w i n g ： 1 w es y s t e m a t i c a l l ya n dc o m p l e t e l yd i s c u s sf 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 e a n dd i f f i c u l t ya t t a c h e dt ot p ，d e s c r i b e st p b y m a t h e m a t i cm o d e l ，a n db r i n g f o r w a r dt h ew h o l ef r a m ea n d t e c h n o l o g yr o u t eo f m e t h o d s 。 2 g i v i n g o u te n t i t y r e l a t i o nd r a w i n g ( e r d ) a n dc l a s si l l u s t r a t i o n ，d e s i g n i n g d a t as t r u c t u r e ，w es t u d y m a n ys u b - a l g o r i t h m si nc o u r s eo fs o l v i n gp r o b l e m ， p u t f o r w a r dar a n d o m a r r a n g e m e n ta l g o r i t h mh a v i n g l o c a lh e u r i s t i c b a c k d a t i n ga b i l i t yt of i n df e a s i b l es o l u t i o nq u i c k l ya n de a s i l y 3 g i v i n g o u tq u a n t i t a t i v ea n a l y s i so fs o m eo b j e c t i v eo f i n k l i n g ，w ee s t a b l i s h o 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 p 4 w e s t u d yc h r o m o s o m ec o d i n ga n dh e r e d i t yo p e r a t o rd e s i g n i n ga i m e da tt p ， t h e ni n t r o d u c et h em u t t i o b j e c t i v ed e c i s i o n - m a k i n gc o n c o r d a n c em o d e l ，p u t f o r w a r daf i t n e s sc o m p u t a t i o nm o d eb a s eo nm u l t i o b j e c t i v ec o n c o r d a n c e d e c i s i o n m a k i n gm o d e la n di m p r o v e t h eg e n e r a l i z e ds t r u c t u r eo f g a ，f o r m ac o o r d i n a t e dm u l t i o b j e c t i v eo p t i m i z a t i o na l g o r i t h mo ft p 5 w eu s ev c + + a n dd e l p h ia sb a s i c d e v e l o p m e n t t o o l s m s s q l s e r v e r 2 0 0 0a sd a t a b a s e ，d e s i g na n dr e a l i z ea u t o t i m e t a b l i n gs y s t e mb a s e d o ng a a f t e ra ne x a m p l e h a v i n gt w oc a m p u s e s ，2 2 9 5t e a c h e r s ，9 9 6c l a s s e s a n d1 9 7 3s c h e m a sh a sb e e ns o l v e di n o b j e c t i v es p a c ec o n s i s t e do ff o u r f a c t o r so fs 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 t y o n d a y ，t i m e p r e f e ro f t e a c h e ra n d h o u r - d e n s i t y o ft e a c h e r t h es o l u t i o ni s s a t i s f i e d t h e a 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 y s t e mh a sb e e na p p l i e di n i i s e v e r a ls c h o o l si n c l u d i n gz h e j i a n gu n i v e r s i t yo ft e c h n o l o g ya n di m p r o v e s t i m e t a b l i n ge f f i c i e n c yg r e a t l y k e yw o r d s ：t 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 o p t i m i z a t i o n ，c o m b i n a t i o no p t i m i z a t i o n 浙江工业大学硕士学位论文 第一章绪论 第一章绪论 随着高校招生规模逐年的扩大，以及计算机在教学工作中的普及应用，用计 算机代替劳动强度大、工作效率低的手工排课工作，越来越成为教学管理之中迫 切需要解决的研究课题之。然而排课问题本身的复杂性和难解性，直困扰着 众多计算机专家排课问题一直没有得到有效的解决。 本章概述了排课问题，评述了先人的研究工作，引出了本文的研究内容。 1 1 排课问题的概述 排课工作开始于教学计划的编制。即教务处必须在每学期前收集各个学院下 学期的开课信息，然而统计下学期全校可用的教学资源，与各学院协调交互，决 定各校区的时间组织形式和各门课程的开课与否，最后根据不同的专业背景，以 班级为单位编制下学期的开课任务书。开课任务书应该包括全校每个班级的开课 计划表，而开课计划表中的每个开课计划都应该包含校区、班级、教师、课程、 课程类型、开课学院、人数、需求教室资源类型、每周课时的情况、有特殊要求 时的上课方式以及教师期望时间等完备信息。 教学计划的实旅的关键是课表的编排。根据课程和课群的特性，或者出于特 殊情况的考虑，某些开课计划有着先于全校统安排的要求，则这些课程必须优 先安排预置，上报教务处备案。待特殊开课计划安排完毕，教务处还必须确定哪 些开课计划为难排计划，哪些开课计划为易排计划，根据“先难后易”的原则， 逐个对开课计划进行安排。在此过程中，还必须遵守多个排课原则： 1 在同一时间同学生不能上两门不同的课程； 2 在同一时间同一教师不能给两门不同课程上课； 3 在同一时间同一教室不能安排两门不同课程； 4 每门课程的教室都有自己特定的类型； 5 教室必须足够大，能够容纳上课的学生； 6 教师、学生在不同校区上课时要留一定的时间用于赶赴： 7 体育课需安排在特定时间，且同一时段内之后不能再安排课程： 浙江工业大学硕士学位论文 第一章绪论 8 实验课、实习课等课程有自身的安排方式。等等 而且一般还有以下多个目标： 1 一个班级时间安排在天上尽量分布均匀； 2 对于校区设置的课表的各个时间存在一定的偏好； 3 尽量满足教师上课时间的期望； 4 教师对时间安排在课表上的密度有一定的喜好； 5 教师和班级相邻两次上课地点尽量较近；等等 时下大多数院校的排课方法是手工编排方法，它主要通过人智能的判断和协 调来完成的。手工编排工作往往开始于一个学期数月前，各部门的协调交互频繁， 而且在实际安排过程中，涉及的校区有多个，教师数量成千，学生数目上万，教 师跨院上课和班级交叉上课众多，而且在计划安排完毕之后，往往由于频 繁的变动不得不及时调整。所有诸如此类因素，使得排课工作不堪重负，工作结 果也不尽人意。 计算机排课，它是把排课问题化为计算领域的有约束的时空组合优化问题进 行求解的。它对课表上的时间进行了分片和编号处理，使分成的每个时间片和每 个教室空间组合，构建了一个个大小不等的时空组合块，并根据求解规则，对每 个开课计划进行时空组合块分配，而且分配的组合( 安排方案) ，必须在目标空 间中表现出良好的人为满意度。这些人为满意度往往不仅多个，而且是模糊的。 虽然利用计算机来模拟手工排课工作，可以抽象问题中的各个要素，数学表达各 种约束条件，并根据课表的组织形式和普遍存在的规律，缩减了问题空间的搜索 范围，以及有效组织了排课知识，使其在一定程度上呈现智能化。但由于其问题 本身的求解规模过于庞大，各要素之间的关联层出不穷，以及人们对多个课表优 劣评定的准则存在差异，使计算机在求解排课问题的过程中，面对难以穷尽的组 合和多个模糊目标的优化，也表现得无能无力。 就其实质而言，排课问题是一个有约束的、非线性的、模糊多目标优化的、 难解的、时空组合的数学问题。即在满足各种已知的约束条件的情况下找到一组 较优的时空组合，同时在具体实践上它受到教学组织形式、客观物质条件和求解 目标等多种因素的相互影响，使这一问题在实际解决时呈现出受具体条件制约的 特点。 浙江工业大学硕士学位论文 第一章绪论 1 2 排课问题研究评述 排课问题是n p 完全问题，许多学者分别在理论、启发式搜索技术应用求解、 专家系统应用求解和遗传算法应用求解上作了很多研究。 1 2 1 排课问题的理论研究 国外从2 0 世纪5 0 年代末就对排课问题开展了研究。1 9 6 3 年g o t l i e b 在他的 文章【1 1 中提出了排课问题的数学模型，它标志着排课问题的研究正式跨入了庄严 的科学殿堂，但由于在实践中遇到的困难，使人们排课问题的题解是否存在产生 了疑问。1 9 7 6 年s e v e n 在论文【2 ( 译：关于时间表和多物流问题的复杂性) c o o p e r 等人在 3 】中，证明了排课问题是n p 完全的，这虽然回答了排课在实践中遇到困 难的原因，但同时等于宣布计算机解决排课问题无法实现，因为计算机难解性的 理论研究指出，现代计算机尚未找到解决n p 完全问题的多项式算法。此后这一 问题的研究大多离开理论研讨的轨道而转向经验方式，这使8 0 年代的许多排课 系统缺乏普适性。 se v e n 的论证正式确立了排课问题的学术地位，把人对课表编排复杂性的认 识提高到了理论的高度。 1 2 2 排课问题的求解方法 从1 9 6 3 年g o t l i e b 提出了个排课问题的数学模型 2 1 之后，人们又对排课问 题的算法作了许多探索，但由于排课问题是n p 完全问题，并且易受实际问边界 的影响，大多数求解结果都不理想。 f e r l a n d 等人 4 l 和吴金荣 5 1 把排课问题化成整数规划来解决，但计算量很大， 其仅仅适用于规模很小的课表编排，对于大规模复杂的排课情况，至今没有一个 切实可行的算法；还何永太【6 】年咕邸喷仁等人( ”试图用图论中的染色问题来求解排 课问题，可惜图的染色问题本身也是n p 完全问题。由于问题的复杂，许多文章 【1 1 【1 2 】【1 4 【1 5 【1 9 】 2 0 【2 i 【2 2 】【2 4 【2 5 铡用启发式函数来解决排课问题，大多数启发方法都是 模拟手工排课的过程来实现的。由于实际的排课问题存在各种各样的限制条件与 特殊要求，对这些因素处理的好坏就显得尤为重要。 进入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 s a f e r l a n d 以及c h a r l e sf l e u t e n t 等na r a b i n d a t r i p a t h y 的工作是针对以“人”为 单位进行课表编排的。他运用拉格朗日松弛法和分支定界技术求解，这种方法的 缺点是为了减少变量的个数，人为造成科目间的冲突。a t r i p a t h y 还研究了研究 生课表编排阀题，他采用多重课组的方法来处理冲突( 即根据学生选课的矛盾情 况，将人数多的课程在一星期内开多次) 。j a c q u e s a f e r l a n d 等人则把排课问题分 成两个子问题：时间表问题和分组问题。在时间表问题中，根据学生注册情况、 教师和教室的可利用情况形成一个主时间表。对于选课人数较多的大课，一个星 期要分成几个时间段来上，分组问题就是将学生分给各时问段。两个问题相关联， 通过惩罚因子来构造启发函数。它他们研制的s a p h i r 课程调度决策支持系统分 为数据处理、自动优化、交互优化等几个模块。该系统解决矛盾的主要方法也是 采用多重课组。这与西方的教学管理体制不可分的。 另外一批学者还将模拟退火法应用到排课问题的研究中 9 】【1 0 】 1 l 】【1 2 】。模拟退火 法( s i m u l a t e d a n n e a l i n g ) 是k i r l c p a t r i c k 等人于1 9 8 3 年首先提出的 1 3 ，它是人们 从自然界固体退火过程中得到启发并从中抽象出来的一种随机优化算法。模拟退 火法用于求解优化问题的出发点是基于物理中固体物质的退火过程与一般优化 问题间的相似性。在对固体物质进行退火处理时，常先将它加温使其粒子可自由 运动，以后随着温度的逐渐下降，粒子逐渐形成低能态晶格。若在凝结点附近的 温度下降速率足够慢，则固体物质定会形成最低能量的基态，优化问题也存在类 似过程。模拟退火法被用来解决许多实际应用中优化问题，取得了不错的效果， 但用其解决排课问题，现在还处在模型试验阶段，还有许多问题要解决。 国内对排课问题的研究开始于8 0 年代初期，所用方法从模拟手工排课到运用 人工智能构建专家系统或决策支持系统都有。 基于时间位图迭加匹配的算法 1 4 1 定义了教学过程中的时间位图、课时模式和 时间匹配等概念，将排课问题转化为基于时间位图迭加匹配的课时模式查找问 题，给出了相应的抽象具体排课过程，并对于排课过程中可能出现的冲突，探讨 了三种回溯消除冲突方式。 基于优先级自动排课算法【1 5 】利用了运筹学中分层规划的思想，把排课问题在 数学上看作为一个在时间、教师、学生和教室四维空间，以教学计划和各种特殊 要求为约束条件的组合规划问题，采用了化整为零的思想及提出了优先级的概 念，有效地抽象了实际排课情况，缩小了求解问题的空间。 4 浙江工业大学硬士学位论文 第一章绪论 基于专家系统的求解算法【1 6 】 1 7 1 8 】将专家系统知识引入排课问题的求解中，有 效组织排课过程中的知识，使各种排课逻辑从程序中解放出来，能够便于各种排 课经验的累计，使排课结果更加符合实际情况。 更多算法n9 1 2 。1 1 2 1 【2 2 3 1 2 3 】【2 4 c 2 5 3 已经提出，它们都是一定程度上启发搜索求解方 法，虽然对后继者有一定的借鉴意义，但它存在以下几点不足之处： 1 对于启发式搜索技术来说，搜索过程的启发信息依赖于实际情况，排课 问题的求解只能针对个别的实际问题，不能形成一种通用的有效排课方 法。 2 引入专家系统技术的排课方法，虽然可以对排课规则知识有效组织，但 由于排课过程中各要素关联规则的难以提取，并且实际求解效果也不理 想。 3 没有引入目标优化技术，课表的优劣判定的论述甚少，只能在问题的某 个方向进行搜索，不可能达到多个目标同时优化。 对于排课系统的研发，林漳希和林尧瑞1 9 8 4 年在p 7 l 上发表了该课题上的实验 性研究成果。成形的系统有大连理工大学1 9 9 8 年推出的的教学调度系统3 0 0 版 本【3 8 1 和由清华大学计算机与信息管理中心开发的综合教务管理系统 3 9 】。但是， 1 国内的排课软件很少，涉及到自动排课算法的系统更少，大部分局限于 辅助人工排课，并没有任何“智能”成分。 2 自动排课系统往往由于在随机求解过程中出现太多的未被安排课程而很 难在实际中使用。 随着人工智能的发展，特别是在计算智能领域的拓展，借鉴于生物界进化思 想和遗传机制的遗传算法，由于其超群的并行搜索能力，以及在解决优化问题中 表现出来的高度鲁棒性，它己经被广泛应用于各个领域。 作为一种随机的优化与搜索方法，遗传算法有着两个主要特性口6 】： 1 智能性。即遗传算法在确定了编码方案、适应值函数及遗传算予以后， 算法将利用演化过程中获褥的信息自行组织搜索。适应值大的个体具有 较高生存概率，它是具有“潜在学习能力”的自适应搜索技术。 2 并行性。由于遗传算法采用种群的方式组织搜索，从而可以同时搜索解 空间内的多个区域，并相互交流信息，这种搜索方式使得它虽每次只执 行与种群规模成比例的计算，而实质上，据g o l d b e r gd e 推算已进行了 大约o ( n 3 ) 次有效搜索。这使得遗传算法能以较少的计算获得较大的收 浙江工业大学硕士学位论文第一章绪论 益。 正是由于遗传算法的两个特性，使得遗传算法迅速被运用于求解组合优化的 排课问题。 c h upc 和b e a s l e y 对一般的安排问题中使用了遗传算法进行求解 2 ”，他们着 重于遗传算法的全局最优解的搜索能力，避免了问题的局部最优解。日本的s i g e r u 用具有控制约束的遗传算法来解决大学排课问题【28 1 ，提高了遗传算法的搜索效 率。姚新使用遗传算法优化了教师的合理利用，解决了在教室较少的情况下，如 何对教室的利用进行合理的分配【2 。针对高中课程的特点，意大利的c o l o r n i 等 人使用遗传算法解决了排课问题 3 ”。张春梅等人对大学课程进行分类，并对不同 的课程使用具有自适应能力的遗传算法进行了安排 3 1 】。p h i l i p p i n e s 的h os u n gc ， l e e 使用遗传算法对p h i l i p p i n e s 大学的数学学院排课问题进行了求解 3 2 】。杨宇对 分别使用遗传算法对局部排课问题和全局排课问题进行了求解t ”1 。 他们运用遗传算法针对自身所描述的排课问题进行求解，虽然在一定程度上 取得了喜人的成果，但综合考虑求解情况，有以下几点不足： 1 求解问题的边界定义。由于各自的研究背景不同，他们考虑的往往是排 课一般情况，有些甚至是理想状态的排课，对于排课中更多的约束条件 未予以考虑，而且问题的求解规模普遍偏小，使得实用程度较低，很难 在学校中展开使用。 2 问题的编码。一种较好的遗传算法的编码方式，不仅能够反映解空间完 备并无歧义的遗传信息，而且操作尽量简单，从而可以快速遗传操作和 适应度评定，继而影响算法整体的收敛时间。在以往的研究中，他们编 码虽然通俗易懂，但不能很好地反映针对更多实际情况的遗传信息，而 且操作很不方便。 3 求解的目标。以往的应用中，采用惩罚函数的居多，处理的都是单目标 问题，即使有多个目标，往往也线性聚合成一个目标进行处理。这在多 目标优化理论中，往往求解所得的是一个非劣解，而忽略了一组非劣解。 1 3 遗传算法的简述 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 是一种借鉴生物界自然选择和进化机制 发展起来的高度并行、随机、自适应的随机搜索算法。由于其具有健壮性，特别 浙江工业大学硕士学位论文第一牵绪论 适合于处理传统搜索算法解决不好的复杂的和非线形问题。简单的讲，它使用了 群体搜索技术，从而产生新一代的种群，并逐步使种群进化到包含近似最优解的 状态。 1 3 1 遗传算法的基本思想 遗传算法是从代表问题可能潜在解集的一个种群( p o p u l a t i o n ) 开始的，而一 个种群则由经过基因( g e n e ) 编码( c o d i n g ) 的一定数目的个体( i n d i v i d u a l ) 组 成。每个个体实际上是染色体( c h r o m o s o m e ) 带有特征的实体。染色体作为遗传 物质的主要载体，即多个基因的集合，其内部表现是某种基因组合决定的。初始 种群产生以后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近 似解。在每一代，根据问题域中个体的适应度( f i t n e s s ) 大小挑选个体，并借助 代表于自然遗传学的遗传算子( 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 ) ，可以作为问题的近似最优解。 遗传算法采纳了自然进化模型，如选择、交叉、变异、迁移、局域与邻域等。 与传统搜索算法不同，遗传算法是从一组随机产生的初始解开始搜索过程。 种群中的每个个体是问题的一个解，称为“染色体”，染色体是一串符号，比如 二进制0 1 串。这些染色体在后续迭代中不断进化，称为遗传。在每一代中用适 应度( f i t n e s s ) 来测量染色体的好坏。生成的下一代染色体称为后代( o f f s p r i n g ) 。 后代是由前代染色体通过交叉( c r o s s o v e r ) 或者变异( m u t a t i o n ) 运算形成的。 新一代形成中，根据适应度的大不选择部分后代，淘汰部分后代，从而保持种群 大小的稳定性。适应度高的染色体被选中的概率高，这样，经过若干代之后，算 法收敛于最好的染色体，它很可能就是问题的最优解或次优解。 1 3 2 遗传算法的一般结构 图1 1 表示了基本遗传算法的一般结构( 3 4 。由图1 1 中可以看出，最佳个体是 这样产生的：首先产生一个初始种群，然后对这个种群中的每一个个体进行适应 度计算，适应度即表示了个体对环境的适应程度。计算后的个体进行是否满足优 化准则判定，如果满足，那么算法找到丁这个个体并停止，如果不满足准则，那 么算法将对这个种群进行选择、复制、交叉、变异操作，遗传操作的目的是从初 浙江工业大学硕士学位论文第一章绪论 始种群中筛选出较优异的个体进行演变，这其中包括复制优秀个体重生、两个父 个体进行交叉和单个个体的变异这三种方式，对演变后的子代群体，重新进行优 化准则判定，如此循环下去，直到找到一个最优个体，或者达到其它循环条件为 止。 圈1 1 遗传算法的一般结构 对于遗传算法结构的更多研究可见” 。虽然出于对具体实际问题情况的考虑， 算法结构形形色色，各不相同，但是遗传算法的通用框架可以由图1 2 来表示， 群体z o ) 都是在遗传算子的作用下变为群体z ( f + 1 ) ，因此可将遗传算法看作如 下系统： 浙江工业大学硕士学位论文 第一章绪论 图1 2 遗传算法的通用框架 其中：f ( x ) 为适应度函数；q 为遗传算法的控制参数集合，如交叉概率、变异概 率等；n = l x i 为群体大小。从通用框架可以看出，遗传算法是一种高度非线性 的随机离散动态系统。各种结构遗传算法的性能的差别在于群体经系统e 作用后 个体基因的变化。 1 3 3 遗传算法的特点 遗传算法是基于自然选择和基因遗传学原理的搜索算法，它将“优胜劣汰， 适者生存”的生物进化原理引入待优化参数形成的编码串群体中，按照一定的适 配值函数及一系列遗传操作对各个体进行筛选，从而使适配值高的个体被保留下 来，组成新的群体，新群体包含上一代的大量信息，并且引入了新的优于上一代 的个体。这样周雨复始，群体中各个体适应度不断提高，直至满足一定的极限条 件。此时，群体中适配值最高的个体即为待优化参数的最优解。正是由于遗传算 法独特的工作原理，使它能够在复杂空间进行全局优化搜索，并且具有较强的鲁 棒性；另外，遗传算法对于搜索空间，基本上不需要什么限制性的假设( 如连续、 可微及单峰等) 。常规的优化算法，如解析法，只能得到局部最优化而非全局最 优，且要求目标函数连续光滑及可微信息；枚举法虽然克服了这些缺点，但计算 效率太低，对于一个实际问题常常由于搜索空间太大而不能将所有的情况都搜索 到，即使很著名的动态规划法，也遇到“指数爆炸”问题，它对于中等规模和适 度复杂性的问题，也常常无能为力；遗传算法通过对参数空间编码并用随机选择 作为工具来引导搜索过程朝着更高效的方向发展。同常规优化算法相比，遗传算 法有以下特尉”j ： 1 遗传算法是对参数的编码进行操作，而非对参数本身。遗传算法首先基 于一个有限的字母表，把最优化问题的自然参数集编码为有限长度的字 浙江工业大学硕士学位论文第一章绪论 符串。优化过程的第一步是把参数编码为有限长度的字符串，常用二进 制字符串。随机生成n 个字符串组成初始群体，对群体中的串进行遗传 操作，直至满足一定的终止条件；求得最终群体中适配值最大的字符串 对应的参数即为所求解。遗传算法是对一个参数编码群体进行操作，这 样提供的参数信息量大，优化效果好。 2 遗传算法是从许多点开始并行操作，而非局限于一点，因而可以有效地 防止搜索过程收敛于局部最优解。 3 遗传算法通过目标函数来计算适配值，而不需要其他推导和附加信息， 从而对问题的依赖性较小。 4 遗传算法的寻优规则是由概率决定的，而非确定性的。 5 遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜 索。 6 遗传算法对于待寻优的函数基本无限制，它既不要求函数连续，也不要 求函数可微，既可以是数学解析式所表达的显函数，以可是映射矩阵甚 至是神经网络等隐函数，因而应用范围较广。 7 遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算 速度。 8 遗传算法更适合大规模复杂问题的优化。 9 遗传算法计算简单，功能强。 1 3 4 遗传算法与其他搜索技术的比较 对于课程表的编排这类整体优化问题的搜索求解技术，主要包括基于微分的 搜索技术、随机搜索技术、启发式搜索技术和枚举技术。图1 3 对有关具体搜索 算法进行了大致分类。遗传算法属于进化算法，而进化算法及进化算法中的每一 个分支均属于启发式随机搜索方法。 浙江工业大学硕士学位论文第一章绪论 图1 3 搜索算法分类 目前，对于求解整体优化问题已经进行了大量理论研究，并提出了许多基于 导数的解析方法和其他非解析的数值集约化技术。但是，在实际领域中存在着各 种高度复杂的优化问题，其目标函数可能表现为非连续或非处处可微、非凸、多 峰和带噪声等各种形式，这类复杂优化问题不适合于采用解析方法，同时用传统 上的搜索技术求解也会遇到许多困难。因此，多年来人们一直在努力寻找能够处 理这类问题的新的、更稳健的优化技术。 借鉴于自然界的进化过程，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 就是一种典型的弱方法，与模拟退火算法、 爬山算法等相比，具有独特的算法形式和运行机理，在复杂优化问题求解中有着 比较显著的优势。 与传统的启发式优化搜索算法相比，遗传算法的主要本质特征在于群体搜索 策略和简单的遗传算子。群体搜索使遗传算法得以突破邻域搜索的限制，可以实 现整个解空间上的分布式信息探索采集和继承；遗传算子仅仅利用适应值度量作 为运算指标进行染色体的随机操作，降低了一般启发式算法在搜索过程中对人机 交互的依赖。这样就使得遗传算法获得了强大的全局最优解搜索能力、问题域的 独立性、信息处理的隐并行性、应用的鲁棒性、操作的简明性，是- - ；f e e 具有良好 普适性和可规模化的优化方法。 作为搜索技术的不同分支爬山法、模拟退火和遗传算法，有人用“袋鼠 登高”作了的形象比喻【3 6 】： “注意，在目前讨论的所有爬山法中，袋鼠最有希望到达靠近它出发点的的 山顶。但不能保证该山顶是珠穆朗玛峰，或者是个非常高的山峰。各种使用的 方法都试图找到实际全局最优值。 在模拟退火中，袋鼠喝醉了，而且随机地跳跃了很长时间。但是，它渐渐清 醒了并朝着峰顶跳去。 在遗传算法中，有很多袋鼠，它们降落到喜马拉雅山脉的任意地方( 如果飞 行员没有迷失方向) 。这些袋鼠并不知道它们被设想寻找珠穆朗玛峰。但每过几 年，你就在一些高度较低的地方射杀一些袋鼠，并希望存活下来的那些是多产的， 并在那里生儿育女。 从遗传算法的特点可以看出，利用遗传算法求解排课问题，与利用其它启发 搜索方法相比较，其搜索过程带有自组织的智能性和并行性，且操作简单，可以 更少地依赖于实际问题的情况，实现课表的优化。 浙扛工业大学硕士学位论文第一章绪论 1 4 本文研究内容 由于排课问题是一个有约束的、多目标的、难解的组合优化问题，采用具有 智能性和并行性的遗传算法，来对排课问题进行求解，是所有求解该问题方法中 较明智的选择。本文旨在在相关遗传算法和多目标优化理论的基础之上，提出一 个课表方案的随机生成和优化算法，能够较大程度地反映实际排课情况和尽量达 到多个目标最优。本论文的研究内容有： 1 详细说明排课问题中的要素和常用的约束条件，分析排课问题的求解难 点和目标，给出排课问题的完整数学描述，并提出本文求解排课问题方 案的总体思路和技术路线。 2 通过排课问题的e r d 和o o a 分析，描述排课系统的数据库结构和变量 的数据结构，并在数据结构的基础之上对课表安排过程的各个子算法展 开描述，提出了一个有局部回溯能力的随机安排算法，生成可行解，产 生初始种群，为后续的遗传算法优化课表的过程提供了遗传操作、迭代 进化的初始样本。 3 对多个排课问题的目标进行量化分析，建立遗传算法优化的目标空问。 针对排课问题进行染色体编码以及各个遗传算子设计，并对具有多个目 标的适应度的如何确定展开讨论，最后集成排课整体优化算法。 4 对一个实际问题的算例，利用上述的随机生成方案算法和基于遗传算法 的排课优化算法进行求解，并对一些中间值进行跟踪分析，从试验的角 度论述算法的可行性。 浙江工业大学硕士学位论文 第二章排课问题的建攘 第二章排课问题的建模 对排课求解目标进行分析，并建立相应的数学模型，可以确立排课问题算法 的总体方案。 2 1 排课目标分析 下文将就排课问题的要素、约束条件、组合爆炸和不确定性方面进行论述 归结排课问题的求解目标。 2 1 1 排课问题的要素 从手工排课的过程可以看出，排课问题需要考虑的因素，几乎是全校性的。 像能够单独完成某种任务的机器一样，学校是一个有机组合而成的整体，其内各 组成部分既各司其职，又密切协调合作，以保证日常正常教务工作的运转和教学 任务的完成。 从排课过程可能引起潜在冲突的角度，可以将排课问题涉及因素逐项考虑如 下： 时间：在排课问题中涉及关于时间的概念有学年、学期、周、天、时段、节。 上课时间一般是按周来计算的( 指周课表) ，从开学第一周至第n 周。每周的课 表一般来说是一样的，但也有可能存在不一样的周，如单双周或不是从第一周开 始的情况。每周分为m 天( m 7 ) 。每天可三个时间段( 上午、下午和晚上) 。 每个时间段分为p i 节，如上午为p 1 ，下午为p 2 ，晚上为p 3 。一节就是个课时， 是上课的最小单元，一般门课程的上课是按两节课( 两个课时) 来进行，但也 有某些课程是按时段、天或周的形式来组织的。在一周内开课多次的课程，应选 择隔天，如一周6 个课时的课程，可以在周一、周三和周五分别上两个课时，也 可以在周二和周四分别上三个课时。其中m 、n 、p i 以及同一课程的多次上课方 式视不同的校区而不同。 课程：每个课程都有自己的编号、名称以及开课学院。每个课程既可以有指 定的教师，又可以没有教师，临时外聘教师。每门课程可以有多个班级合并上课， 合班班级往往是同专业或相似专业，但有时候是跨院系的。每门课程都有指定的 浙江工业大学硕士学位论文 第二章排课问题的建模 教室类型。如普通教室、多媒体教室、语音室、实验室或机房等等。每门课程都 有授课计划，包括起始周和截止周以及周学时安排。某些课程由于上课班级较多 难以协调或照顾教师要求等诸如此类原因，应该预先给定时间或教室。 教学区域：一个大学每个校区可以有多个教学楼宇，每个楼宇可以是一个教 学区域。几个连接的非常近的楼宇也可以视做一个教学区域。引进这个概念的目 的是为了减少学生和教师的走动范围。每个教学区域都和其它的教学区域有个远 近关系，可以将它们考虑成为两两远近关系表。远近关系可以分为很远、较远、 远、近、较近、很近。 教室：每个教室都有编号、门牌号码和名称。每个教室都隶属于某个教学区 域。每个教室都隶属于某种教室类型。每个教室都有一个支配使用单位，如学校 同一调度或被某个学院使用。每个教室在同一时间内只能接纳一门课程的授课， 并且教室容量应该大于等于上课的人数。当上课的人数远远小于教室容量时，这 种情况也是不合适的。 校区：每个校区都有自己的编号和名称。当教师在各个校区共享时，教师从 一个校区赶赴另一校区需要一定的时间，这就决定了两两校区间的教师赶赴时 间。 院系：每个院系都有编号和名称。 班级：每个班级都有编号和名称。每个班级都隶属于某个学院。每个班级同 一时间只能上一门课程。 教师：每个教师都有编号和姓名。每个教师同一时间只能上- - f 课程。每个 教师都可以有自己期望的授课时间和不期望的授课时间。如某个教师由于家远， 不期望课程安排在上午的1 、2 两节。 2 1 2 排课过程的约束条件 排课是将教师与学生在时间和空间上根据不同的约束条件进行e l l e n 组合，以 使教学正常进行。这里约束条件主要为避免冲突，所谓冲突，它所包含的内容很 广泛，几乎发生在所有两个或多个排课涉及因素之间。而避免冲突也是排课问题 中要解决的核心问题。只有在满足全部约束条件和避免所有冲突的基础上，才能 保证整个教学计划合理正常进行。而对教师、教室、学生及时间等几部分资源进 行最优化组合配置，才能保证充分发挥各资源的优势和提高教学质量。 这儿，我们不妨把排课过程中的约束条件分为三类：基本硬约束、硬约束和 浙江工业大学硕士学位论文第二章排课问题的建模 软约束。其中基本硬约束是指教师、学生和教室在时空概念上发生了不可能发生 的事情，它是排课过程中最基本的约束条件，也是众多排课模型中都涉及的约束 条件；硬约束是由于学校的实际情况，排课时必须遵循的原则，否则将会导致排 课结果无意义；软约束是指排课过程中满足更佳但不满足又无妨的约束条件，它 们的违反与否往往是与排课实际情况相关。在三类约束条件之中，前两者是衡量 排课方案是否切实可行的标准，软约束是衡量排课方案优劣的标准，通常判别一 个排课方案的优劣标准有多个。 可以把排课过程常见的约束条件分类罗列如下( 表2 1 所示) ，这些约束条件 也比较符合排课过程的实际情况。( 分类编号，首字母表示英文类型大写字母) 基本硬约束( b a s e - h a r dc o n s t r a i n t s ) b 1 在同时间同学生不能上两门不同的课程 b 2 在同一时间同一教师不能给两门不同课程上课 b 3 在同一时间同一教室不能安排两门不同课程 硬约束( h a r dc o n s t r a i n t s ) h l 上课按最小单位一节的形式进行，周天上的课表可以进行定制 h 2 课程的学时在周和星期上分配有一定的规律 h 3 每门课程都有自己特定类型的教学资源 h 4 教室必须足够大，能够容纳上课的学生 h 5 某些课程可以先行手工排定时间和教室 h 6 某些教师、班级或教室在某个时间上可能不能够利用 h 7 教师、学生在不同校区上课时要留一定的时间用于赶赴 h 8 体育课安排在上午3 4 节或者下午，体育课之后不安排课程 h 9 实验课、实习课等课程有自身的安排方式。 软约束( s o f tc o n s 廿m n t s ) s 1 班级课程表在星期上尽量分布均匀 s 2 一周课表中的每个时间有一定优度 s 3 教师对上课时间存在一定的喜好 s 4 班级相邻上课地点尽可能距离较近 s 5 教师不推荐在时间上接连上课 表2 1 排课过程的常见约束条件 浙江工业大学硕士学位论文 第= 章排谋问题的建模 2 1 3 排课问题的组合爆炸和不确定性 经典的组合规划问题的求解，主要依靠约束