（计算机科学与技术专业论文）基于遗传算法的高校排课系统设计与分析.pdf

摘要 排课是学校教学管理中十分重要且又相当复杂的管理工作之一，随着高校教 育事业的发展，学生人数的不断增加，在教室资源有限的前提下课程编排显得更 加繁重，同时课程的编排也更成为教学管理工作的关键，在一定程度和深度上影 响着学生培养与教学质量的提高。 由于本人在广东海洋大学教务处负责排课工作，在这几年的工作当中我深知 排课的复杂性，要想在短期内排出一张令所有教师和班级都满意的课表难度很 大，为了能最大的提高排课的效率本人对于排课算法提出了一些改进。排课问题 是一个有约束的、多目标的、难解的组合优化问题，采用具有智能性和并行性的 遗传算法，来对排课问题进行求解，是所有求解该问题方法中较明智的选择。本 文旨在相关遗传算法和多目标优化理论的基础之上。提出一个课表方案的随机生 成和优化算法，能够较大程度地反映实际排课情况和尽量达到多个目标最优。本 论文的主要工作有： 1 详细 兑明排课问题中的要素和常用的约束条件，分析排课问题的求解难点 和目标，提出本文求解排课问题方案的总体思路和技术路线。 2 以p o w e r b u i l d e r 语言为工具，制定排课系统的主要数据库结构和主要字段 ( 教师编码) 的数据编码结构，并采用优化编码结构组合的方法减少排课冲突， 降低算法的复杂度。 3 对排课问题的关键参数进行量化分析，针对排课问题的染色体编码完成各 个遗传算子的设计和开发任务，最后集成排课的整体优化算法，完成排课软件关 键模块的系统设计。 关键词：遗传算法；排课；教师编码；冲突 奎三些盔兰三耋堡圭兰堡丝三 a b s t r a c t a r r a n g i n gc o u r s es t r u c t u r ei se s s e n t i a li na c a d e m i ca d m i n i s t r a t i o no fu n i v e r s i t y , l i k e w i s ei ti sac o m p l i c a t e dm a n a g e m e n tt a s k i nr e c e n ty e a r s ，d u et ot h ed e v e l o p m e n t o ft h eh i g h e re d u c a t i o nc a r e e r , t h en u m b e r so ft h es t u d e n t si sg e t t i n gi n c r e a s i n g ，t h e a r r a n g e m e n tt a s ko fc o u r s es t r u c t u r e i s g e t t i n gh e a v i e ru n d e rt h el i m i t a t i o n o f c l a s s r o o mr e s o u r c e s ，m e a n w h i l e ，c o u r s ea r r a n g e m e n tb e c o m e st h ek e yo ft h et a s ko f t h ee d u c a t i o na d m i n i s t r a t i o n f u n c t i o n ，i n f l u e n c i n g s t u d e n tc u l t i v a t i o na n d e n h a n c e m e n to f e d u c a t i o nq u a l i t yo n ac e r t a i nl e v e la n ds t a t e b e c a u s eia mr e s p o n s i b l ef o ra r r a n g i n g c o u r s ew o r ki nt h eg u a n g d o n go c e a n u n i v e r s i t yd e a n so f f i c e ，i nt h e s ey e a r sw o r kif u l l y r e a l i z e da r r a n g i n g c o u r s et h e c o m p l e x i t y , w a n t st oa r r a n g eac l a s ss c h e d u l ew h i c ht h et e a c h e ra n dt h ec l a s s a n d g r a d ea l ls a t i s f i e si nt h es h o r t t e r mt oh ev e r yd i f f i c u l t ，i no r d e rt ot h ee n h a n c e m e n t a r r a n g i n g c o l n s ee f f i c i e n c y m a x i m u mm y s e l fp r o p o s es o m ei m p r o v e m e n t so n a r r a n g i n g - c o u r s ea l g o r i t h m s i n c e c o u r s e a r r a n g e m e n tp r o b l e m i sr e s t r i c t i n g m u l t i - o b j e c t i v ea n dd i f f i c u l t i nc o m b i n a t i o n a lo p t i m i z a t i o n , u s i n gi n t e l l e c t u a la n d p a r a l l e li n h e r i tc a l c u l a t i o n ，i no r d e rt or e s o l v ec o u r s ea r r a n g e m e n tp r o b l e m , i st h e w i s eo p t i o nf o ra c h i e v i n gs u c hp r o b l e ms o l u t i o n t h eo b j e c t i v eo ft h i st e x ti st o i n t r o d u c ear a n d o mg e n e r a t i o na n do p t i m i z i n gc a l c u l a t i o nf u rc o u r s ea r r a n g e m e n t b a s e do nt h ei n h e r i tc a l c u l a t i o na n dm u l t i - t a s k i n gc o n c e p t ，i no r d e rt or e f l e c tt h e a c t u a lc o u r s ea r r a n g e m e n tc o n d i t i o na n da c h i e v i n gt h eb e s to fm u l t i - t a s k i n g t h e f u n c t i o n so f t h i st h e s i sa r em a i n l yc o n s i s t i n g ： 1 d e t a i l e de x p l a i n i n ge s s e n t i a l so fc o u r s ea r r a n g e m e n ta n dc o m m o n l yu s e d r e s t r i c t i n gr e q u i r e m e n t ，a n a l y z e t h es o l v i n ga n dt a r g e to fc o u r s ea r r a n g e m e n t p r o b l e m s ，p r e s e n t i n gt h eo v e r a l lt h i n k i n ga n dt e c h n i c a lp a t h o fr e s o l v i n gc o u r s e a r r a n g e m e n tp l a n l 2 u s i n gp o w e r b u i l d e rl a n g u a g ea sat o o l ，e s t a b l i s h i n gt h em a i n d a t a b a s e s t r u c t u r ea n dw o r d s ( e d u c a t i o nc o d i n g ) f o rt h ec o u r s ea r r a n g e m e n ts y s t e m , a n du s i n g t h em e t h o d o l o g yo fo p t i m i z i n gc o d i n gs t r u c t u r ea n dc o m b i n a t i o nt od i m i n i s hc o n f l i c t o f c o u r s ea r r a n g e m e n t ，r e d u c i n gt h ec o m p l e x i t yo f c a l c u l a t i o n 3 c o n d u c t i n gq u a n t i t a t i v ea n a l y s i s o nt h ek e yp a r a m e t e ro ft h ec o u r s e a r r a n g e m e n t ，c o m p l e t i n gt h ed e s i g no fe a c hi n h e r i to p e r a t o r sa r i de x p l o i t i n gt a s ki n a c c o r d a n c ew i t hc h r o m o s o m ec o d i n go fc o u r s ea r r a n g e m e n t ，f i n a l l y i n t e g r a t i n g o v e r a l lo p t i m i z i n gc a l c u l a t i o no f c o u r s ea r r a n g e m e n t ，i no r d e rt of u l f i l ls y s t e md e s i g n o f t h ek e yc o u r s ea r r a n g e m e n tm o d u l e k e y w o r d s ：g e n e t i ca l g o r i t h m s ；c o u r s e a r r a n g e m e n t ；t e a c h e rc o d e ；c o n f l i c t 1 0 c a l i z a t i o n 1 1 1 独创性声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及所取得的研究成果。尽我所知，除了文中特别加 以标注和致谢的地方外，论文中不包含其他人已经发表或者撰写过的研究成果， 不包含本人或其他用途使用过的成果。与我一同工作过的同志对本研究所做的任 何贡献均已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期i 日j 在导师的指导下取得的。论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 指导老师签字： 论文作者签字：掰“厂 2 0 0 7 年岁月扣r 第一章绪论 第一章绪论 本章介绍了课题的背景、研究意义及方法，阐述了排课问题的现实需求及国 内外对排课问题的研究现状，介绍了本文的研究内容和主要特色，最后，介绍了 课题的主要工作和全文将要解决的主要问题。 1 1 课题背景 近年来，随着高校新生的扩招力度加大，专业设置、课程设置不断向深度和 广度发展，各高校都面l 临着教室资源紧张的问题，要在每个学期末的一个短时问 内拿出一份涉及到有关全校教室统调的课表来，对高校的教务处来说是一个很艰 巨的任务，手工排课己经越来越难于解决教室资源冲突或教师资源冲突的情况， 其不可避免的工作繁琐，工作量巨大，效率低下的缺点也就越来越突出了，同时 手工操作也不易于充分利用资源满足经常变化的需求。由于本人现在在广东海洋 大学教务处负责排课工作，本人深知排课的复杂性。随着校园网的普及和校园办 公自动化的一步步实现，很多的数据可以通过校园网传递，所以根据实际教务工 作的需求以及硬件设施的配套进一步完善，实现计算机的智能排课势在必行，本 文就是在此背景下完成的。 1 2 研究意义及方法 在学校的日常教学管理工作中，教学计划的实施是最重要也是最基本的环 节。而课表则是实施教学计划的具体表现方式，课表的制作是进行教学管理的开 始，它在执行教学计划这教学管理中心环节中起着极其重要的作用，通过它对 教学活动和教学秩序实施科学的组织和管理，因此，课程编排问题在一定程度和 深度上影响着学生培养与教学质量的提高。 课表的编制在学校整个教务管理中历来都是一项耗时巨大的、繁琐的系统工 程。其实质就是为学校所设置的课程安排时间、地点和授课教师，从而使整个教 学能够有计划有秩序地进行。 广东工业大学工学硕士学位论文 目前，国内大部分学校尤其是普通中小学校仍然采用手工排课的方法。对于 那些只拥有几百名学生，数十名教师的小规模中、小学校来说，手工排课虽然任 务不轻，但在有经验的教务人员的操作下还可以勉强完成。而稍大一些的学校要 安排出合理的课程表往往需要花费教务人员一、二个星期甚至更长的时帕j ，工作 量大、排出的课表也很难调整。 由于计算机具有运算速度快，处理能力强等特点，很自然地进入到教务“排 课”这一应用领域中。所谓计算机排课，就是把排课问题化为计算机应用领域的 有约束的时空组合优化问题进行求解。它对课表上的时| 日j 进行了分片和编号处 理，使分成的每个时间片和每个教室空间组合，构建了一个个大小不等的时空组 合块，并根据求解规则，对每个开课计划进行时空组合块分配，而且分配的组合 ( 安排方案) ，必须在目标空间中表现出良好的人为满意度。这些人为满意度往 往不仅多个，而且是模糊的。利用计算机来模拟手工排课工作，可以抽象问题中 的各个要素，数学表达各种约束条件，并根据课表的组织形式和普遍存在的规律， 缩减了问题空阳j 的搜索范围，以及有效组织了排课知识，使其在一定程度上呈现 智能化。但由于其问题本身的求解规模过于庞大，各要素之间的关联层出不穷， 以及人们对多个课表优劣评定的准则存在差异，使计算机在求解排课问题的过程 中，面对难以穷尽的组合和多个模糊目标的优化，也表现得无能为力。 因此，就其实质而言，排课问题是一个有约束的、非线性的、模糊多目标优 化的、难解的、时空组合的数学问题。即在满足各种己知的约束条件的情况下找 到一组较优的时空组合，同时在具体实践上它受到教学组织形式、客观物质条件 和求解目标等多种因素的相互影响，使这一问题在实际解决时呈现出受具体条件 制约的特点。这也是造成排课问题很难获得普遍性解决的主要原因。 总的晚来，国内由于各高校资源的不同、习惯( 约束) 的差异，排课软件难 于提高它的普遍适用性，使教务排课工作至今仍是：手工排课为主，计算机排课 为辅。所以，研究高效、灵活、自动化程度高的排课系统不但仍有意义而且是迫 切的需求。 1 3 国内外排课问题的研究现状 计算机排课问题是一个多目标、有限资源、带有模糊约束条件的组合规划问 2 第一章绪论 题，是计算机应用领域的一个具有一定代表性问题。2 0 世纪6 0 年代末， o t l i e b c c 教授就对课程表问题进行了形式化描述。随后，此类研究发展起来， 遍布各地。7 0 年代中期，s e v e n 等人就论证了课表问题是n p 完全类问题，将 该问题理论化，同时也说明了课表问题有其自身固有的数学模型，即课表问题存 在解，并且能找到解但是根据计算和难解性理论，目前还没有解决n p 完全类问 题的多项式算法。到1 9 7 9 年，s c h m i d t 和s t r o h e i n 在文献中就列出了3 0 0 多篇 这方面己发表的文献。近年来，研究这一问题的人员不断增多，国外的运筹学杂 志几乎每年都有相关内容的文章发表。此外，它还广泛出现在计算机、应用数学、 教育管理等杂志上。8 0 年代初，我国的很多大学也普遍开始研究排课系统软件。 大体上来说，这些排课系统可分成二大类：第一类是以所谓班一教员模型为主， 它是在g o t l i e b c c 工作的基础上发展起来的。主要讨论此类模型的定义扩充， 解的特性及分析，不断提出新的猜测和推论。基本模型变化不大，并且这类模型 较适合课程长度一致、无合班教室的情况，并不适合般院校的实际情况。第二 类是所谓的课程调度问题，多与图的结点的着色问题有关，模型一旦产生，它曲玲 变量往往太多，规模太大，此外根据具体的校情对模型提出的各式各样的要求对 模型的影响较大，有的甚至没有具体的模型可寻。通过对资料的查阅发现以往对 课表编排问题的研究多侧重于自动生成方面，难度较大，实现不易，往往是理论 研究上的工作多而实际应用方面的工作少。有一些实际的例子，也多是特定条件 下，对实际情况进行了简化后得到的，至今还未见有完全自动生成课表系统的软 件应用于实际的报道。我知道，对计算机而言，不像人工编排那样可以对各种约 束条件进行合理的取舍，因此完全不存在冲突的课表很难排出来。 在国内高校排课系统中，大连理工大学是从事此类软件系统开发较早的单 位，1 9 8 7 年该校开发了教学组织管理及课程调度系统1 0 0 版本”1 ，并于1 9 8 9 年通过了省级科技成果鉴定。这一系统是国内类似系统中出现比较早的、相对比 较成熟的作品。之后在教学组织管理及课程调度系统1 0 0 版本的基础上， 1 9 9 0 年，又推出教学组织管理及课程调度系统2 0 0 版本，1 9 9 2 年推出教 学组织管理及课程调度系统2 0 1 版本和安排考试补考的考试调度系统( 即 二合为一的教学调度系统) 。1 9 9 4 年推出了教学调度系统2 2 0 版本，1 9 9 8 年推出了在w i n d o w s 下运行的3 o o 版本。现在在各高校中使用比较多，反映较 好的除了大连理工大学开发的系统，还有清华大学开发的综合教务一排课系 广东工业大学工学硕士学位论文 统，以及北京大学_ 丌发的一套比较新的排课管理系统。 1 4 研究内容及主要特色 由于排课问题是一个有约束的、多目标的、难解的组合优化问题，采用纯数 学算法或者单一的算法是很难解决排课问题的。采用多种算法相结合，融合各种 算法的优点建立符合实际应用的排课模型来对排课问题进行求解，是所有求解该 问题方法中较明智的选择。该文以广东海洋大学教务排课系统为背景，研究排课 问题中的复杂因素和约束条件，旨在在研究已有算法和多目标优化理论的基础之 上，对己有算法进行改进并且建立能够较大程度地反映实际排课情况和尽量达到 多个目标最优的自动排课模型，提出一个课表自动编排算法，并且在系统中加以 实现和应用。 1 4 1 本文的研究内容 1 针对高校课表编排存在的普遍问题以及在本校排课过程中的遇到具体问 题，与相关人员反复探讨，并且对学校排课现状进行详细的需求调研，设计排课 系统的数据结构和各个需要的功能模块。在详细分析遗传算法的应用特点和关键 要素的基础上，对排课问题的难点和目标进行求解。综合考虑排课问题涉及到的 各种因素和约束条件，确定求解排课问题方案的总体思路，并设计出算法的设计 方案。 2 以p o w e r b u i l d e r 数据库语言为工具，制定排课系统的主要数据库结构和 主要字段( 教师编码) 的数据编码结构，并采用优化编码结构组合的方法减少排 课冲突，降低算法的复杂度。 3 研究如何解决排课问题中出现的资源冲突和课程重排问题，以提出解决 方法，最大限度减少和解决资源冲突问题。解决课表编排中的课程安排离散化和 平衡性问题，使得编排出的课表能够达到较好的教学效果。通过对课表问题中各 因素之间关系和排课算法的进一步研究，给出改进的排课程算法并且建立自动排 课算法模型；对排课问题的关键参数进行量化分析，针对排课问题的染色体编码 完成各个遗传算子的设计和开发任务，最后集成排课的整体优化算法，完成排课 4 第一章绪论 软件关键模块的系统设计。 4 给出排课系统的整体界面设计。根据对系统各个功能的需求分析，对系 统的主界面及其它各个功能界面进行设计。 1 4 2 本文主要特色 1 将遗传算法运用到自动排课中。 在详细分析遗传算法的应用特点和关键要素的基础上，对排课问题的难点和 目标进行求解。 2 解决连上两大节课无需跨教学楼上课的问题。 在以往的排课过程中经常会出现同一位教师或同一个班级在上午或下午连 上两大节课时跨教学楼上课的情况，而这对教师或学生来讲都是极不方便的。就 这个问题本文提出了通过设置教学区域之问的远近关系的方法来解决。 3 解决上课人数与教室容量相差甚远的问题。 在以往的排课中还会出现班级人数远远小于教室容量的问题，就这一问题本 文先通过给各教室设置一优先级，当系统自动排课寻找教室时就先在与班级人数 相近的教室中寻找，然后再在更大的教室中寻找，当出现班级人数小于教室容量 的某个比例时就提示，然后由排课人员手动进行调整。 1 5 本文组织 本文从广东海洋大学的实际情况出发，提出了排课系统的分析和设计方法， 结合遗传算法给出了系统详细的分析和设计方案，并在系统分析和设计的基础上 实现系统功能本文组织如下： 第一章：绪论，介绍了课题的背景、研究意义及方法，阐述了排课问题的现 实需求及国内外对排课问题的研究现状，介绍了本文的研究内容和主要特色，最 后，介绍了课题的主要工作和全文将要解决的主要问题。 第二章：遗传算法实现技术概述，介绍遗传算法的形成、应用特点、关键参 数与步骤、给出一般遗传算法的伪代码描述和执行框图，还有面向对象技术在系 统中的使用，介绍了e r d 、o o a 图。 第三章：基于遗传算法的排课系统需求分析，以排课算法的设计为目标，主 5 广东工业大学工学硕士学位论文 要完成以下五方面的工作：( 1 ) 业务需求分析；( 2 ) 数据需求分析：( 3 ) 数据 表分析( 4 ) 功能需求分析；( 5 ) 约束条件。 第四章：自动排课系统的设计，本章将以p o w e r b u i l d e r 语言为工具，对排课遗 传算法进行编程实现：建立主要数据库及其表结构：给出排课算法流程图；完成 关键遗传算子的模块设汁；详细阐述了数据库的设计。 第五章：排课系统的实现流程及界面，介绍了系统的主界面；排课课程调整模 块以及其它模块功能的具体实现情况 结束语：总结本文的工作，并讨论了系统设计与开发过程中的几点体会，指 出了系统丌发中的几个不足之处，并对系统的应用进行了展望。 6 第二章遗传算法实现技术概述 第二章遗传算法实现技术概述 本章分为5 个小节，对一般遗传算法的实现技术进行概要性描述。主要介绍 遗传算法的形成、应用特点、关键参数与步骤、给出一般遗传算法的伪代码描述 和执行框图，还有面向对象技术在系统中的使用，介绍了e r d 、o o a 图。 2 1 遗传算法的形成 遗传算法是美国m i c h i g a 大学的j o h n h h o l l a n d 教授及其学生们根据生物 进化的模型提出的一种优化算法嘲。自然选择学说是进化论的中心内容。根据进 化论，生物的发展进化主要有三个原因，即遗传、变异和选择。 遗传是指子代总是和亲代相似。遗传性是一切生物所共同的特性，它使得生 物能够把它的特性、性状传给后代。遗传是生物进化的基础。 变异是指子代和亲代有某些不相似的现象，即子代永远不会和亲代完全一 样。它是一切生物所具有的共同特征，是生物个体之问相互区别的基础。引起变 异的原因主要是生活环境的影响、器官的使用的不同及杂交。生物的变异性为生 物的进化和发展创造了条件。 选择是指具有精选的能力，它决定生物进化的方向。在进化过程中，有的要 保留，有的要被淘汰。自然选择是指生物在自然界的生存环境中适者生存，不适 者被淘汰的过程。通过不断的自然选择，有利于生存的变异就会遗传下去，积累 起来，使变异越来越大，逐步产生了新的物种。 生物就是在遗传、变异和选择三种因素的综合作用过程中，不断地向前发展 和进化。选择是通过遗传和变异起作用的，变异为选择提供资料，遗传巩固与积 累选择的资料，而选择则能控制变异与遗传的方向，使变异和遗传向着适应环境 方向发展。这样，生物就会从简单到复杂、从低级到高级不断地向前发展。 进化论的自然选择过程蕴涵着一种搜索和优化的先进思想。遗传算法正是吸 取了自然生物系统“适者生存，优胜劣汰”的进化原理，从而使它能够提供一个 在复杂空间中进行鲁棒搜索的方法，为解决许多传统的优化方法难以解决的优化 问题提供了新的途径。 广东工业大学工学硕士学位论文 遗传算法和传统的搜索算法不同，它从一组随机产生的初始解，称为“种群 ( p o p u l a t i o n ) ”开始搜索过程。种群中的每个个体是问题的一个解，称为“染 色体( c h r o m o s o m e ) ”。在遗传算法中最重要的概念是染色体，染色体通常是一 串数据( 或数组) ，用束作为优化问题的解的代码，其本身不一定是解。这些染 色体在后续的迭代过程中不断进化，称为遗传。在每一代种群中用“适应度值 ( f i t n e s s ) ”柬测量染色体的优劣程度，并根据其优劣度进行选择，由此生成 的下一代染色体称为后代( o f s p r i n g ) 后代是由前一代种群的染色体通过杂交 ( c r o s s o v e r ) 或者变异( m u t a t i o n ) 运算形成的。新一代形成中，根据适配值 的大小选择部分后代，淘汰部分后代，从而保持种群大小是常数。适配值高的染 色体被选中的概率较高。据此，经过若干代之后，算法收敛于最好的染色体，它 很可能就是问题的最优解或次优解。 2 2 遗传算法的应用 简单的讲，h o l l a n d 的遗传算法，通常称为简单遗传算法。操作的简单和作 用的强大是遗传算法的两个主要特点。它是基于自然选择和基因遗传学原理的搜 索算法，将“优胜劣汰，适者生存”的生物进化原理引入待优化参数形成的编码 群体中，按照一定的搜索技术，将种群代表一组问题解，通过对当前种群施加遗 传操作，从而产生新一代的种群，并逐步使种群进化到包含近似最优解的状态。 一般的遗传算法都包含三个基本操作： 1 选择操作( r e p r o d u c t i o np e r a t o r ) ： 2 交叉操作( c r o s s o v e rp e r a t o r ) ； 3 变异操作( m u t a t i o np e r a t o r ) ； 遗传算法在很多领域都得到了应用。从计算机排课研究的角度上考虑，应先 明确其算法特点和应用关键，才能对这种算法深入了解，灵活应用，以及进一步 研究开发。 2 2 1 应用特点 i 遗传算法是对参数的编码进行操作，而非对参数本身。遗传算法首先基 8 第二苹遗传算祛实现技术概述 _ _ e _ - _ | j _ e _ _ _ _ 自_ _ - _ i _ e _ _ - _ e e j _ e | _ i 于一个有限的字母表，把最优化问题的自然参数集编码为有限长度的字符串。优 化过程的第一步是把参数编码为有限长度的字符串，常用二进制字符串。随机生 成n 个字符串组成初始群体，对群体中的字符串进行遗传操作，直至满足一定的 终止条件；求得最终群体中适配值最大的字符串对应的参数即为所求解。遗传算 法是对一个参数编码群体进行操作，这样提供的参数信息量大，优化效果好。 2 遗传算法是从许多点丌始并行操作，而非局限于一点，因而可以有效地 防止搜索过程收敛于局部最优解。 3 遗传算法通过目标函数来计算适配值，而不需要其他推导和附加信息， 从而对问题的依赖性较小。 4 遗传算法的寻优规则是由概率决定的，而非确定性的。 5 遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜 索。 6 遗传算法对于待寻优的函数基本无限制，它既不要求函数连续，也不要 求函数可微，既可以是数学解析式所表达的显函数，又可是映射矩阵甚至是神经 网络等隐函数，因而应用范围较广。 7 遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算 速度。 8 遗传算法更适合大规模复杂问题的优化。 9 遗传算法计算简单，功能强。 2 2 2 应用关键 遗传算法在应用中的关键问题有如下5 个： 1 编码方式 本质问题是编码结构。基本遗传算法中，一般把问题的各种参数用二进制进 行编码，构成“子串”；然后把子串拼接构成“染色体”串。串长度及编码形式 对算法收敛影响极大。 但是，在求解连续参数优化问题时，采用二进制编码的遗传算法需要将连续 的空间离散化，若要提高解的精度，就必须增加个体长度，而且在进化过程中还 需要不停地进行编码和解码操作，计算时间比较长。 9 广东工业大学工学硕士学位论文 基于实数编码的遗传算法不存在编码和解码过程，能够大大提高解的精度和 运算速度，因此9 0 年代以来，基于实数编码的遗传算法得到了越来越多的重视 和发展。 2 适应度函数 适应度函数( f i t n e s s f u n c t i o n ) 也称对象函数( o b j e c t f u n c t i o n ) ，这是 问题求解品质的测量函数，需要根据求解对象进行构造。本算法的适应度函数通 过“期望值”的方式进行构造，该构造过程在论文4 3 3 小节中进行阐述。 3 自身参数 遗传算法自身参数有3 个，即群体大小z q s 、杂交概率p ，和变异概率p m 。 并不是所有被选择了的染色体都要进行交叉操作和变异操作，而是以一定的 概率进行，一般在程序设计中交叉发生的概率要比变异发生的概率要大若干个数 量级，一般遗传算法认为交叉概率取0 6 至0 9 5 之间的值，变异概率取0 0 0 1 至0 0 1 之间的值。 种群染色体( 或称为个体) 的总数目叫种群规模，它对算法的效率有明显的 影响，规模太小不得于进化，而规模太大将导致程序运行时问长。对不同的问题 可能有各自适合的种群规模，通常种群规模为3 0 至1 6 0 。 4 遗传算子 ( 1 ) 选择算子( r e p r o d u c t i o n ) ：选择算子从群体中按照某一概率选择个体， 某个体s i 被选择的概率p i 与其适应度值成证比。通常，用轮盘赌方法进行实现。 轮盘赔的实现方法为：设群体s ：s 1 ，s 2 s n ，每个个体的适应度值分别 为f ( s 1 ) ，f ( s 2 ) f ( s n ) ，令s u m = f ( s 1 ) + f ( s 2 ) + + f ( s n ) ，某 个体s i 被选择的概率p i = f ( s i ) s u m ( i = 1 ，2 ，n ) ，在0 与s u m 之间产生一个随机数a ，令b = o ，依概率p 1 ，p2 p n 在1 到n 之间随机产生 个个体编号m ，将f ( s m ) 累加进b 中，直到b a ，将此s m 作为被选个体。 ( 2 ) 杂交算子( c r o s s o v e r ) ：杂交算子将被选中的两个个体的基因链按概 率p c 进行杂交，即在某一确定段上，对等交换代码，生成两个新的个体，杂交 位置是随机的。本系统采取的是对两个个体交换特定行( 某班课表) 的方式实现 杂交操作。 ( 3 ) 变异算子( m u t a t i o n ) ：变异算子将新个体的基因链的各位按概率p m 1 0 第二章遗传算法实现技术概述 进行变异，对二进制基因链来说，就是对某些随机选取的位置取反。就本系统而 言，采取的是对随机选择的某个个体交换时间片中的教师编码的方法。即随机产 生两个时间片，将这两个时问片所在的教师编码进行交换。 5 遗传策略 在本系统中，由于涉及到多个约束条件，产生的新群体中难免会有不满足条 件的个体，因此在得到新群体后，首先用约束条件检验每个个体，对于不满足约 束条件的个体进行纠错，使之满足约束条件。然后计算其适应度值，对群体进行 演化计算产生下一代，从而加快了进化速度。 本文采取的遗传进化策略是：在计算得出群体中每个个体的适应度值后，按 照选择概率计算出每个个体的选择数，根据选择数复制若干个体进入待选群体 中，选择数为零的个体被淘汰；将群体中适应度值不等的个体依杂交概率数两两 随机搭配，组成父本进行杂交，把产生的子代个体放入待选群体中；依变异概率 数随机选择若干个体进行变异，把产生的子代也放入待选群体中；若待选群体中 的数目小于种群数，则继续下一轮的杂交和变异，直到待选群体中的数目大于静 群数。 接着，消除待选个体中的冲突，计算其适应度值，由此进入到下一轮的遗传 进化操作中。待选群体中包含了上一代有优良品性的父本，也包含了通过杂交与 变异产生的子代，通过适应度的排序进行父本与子代的重新竞争，将每一代中最 优个体进行保存，每次产生新群体后，判断新群体中是否有比现有最优个体的适 应度值更好的，若有，则将其加入到新群体中以取代相对较差的个体。通过父本 和子代的竞争，可以提高解的收敛速度。 6 停止进化准则 遗传算法是一种反复迭代的搜索算法，通过多次迭代进化逐渐逼近最优解而 不一定恰好等于最优解，因此需要终止条件。遗传算法可以采用多种方法来结束 算法的执行。在本系统中，采用以下两种方法相结合的方式来加以进化过程的停 止控制： ( 1 ) 设定最大遗传代数m ，当遗传进行到第m 代时，让其停止进化。该m 值由测试给出。 ( 2 ) 预先定义评价函数的一个指标数，当某一代最优个体的适应度值达到 或超过该指标数时，让其停止进化。 广东工业大学工学硕士学位论文 2 3 遗传算法设计的主要步骤 为了使用遗传算法来解决问题，准备工作分为以下四步： 1 确定表示方案： 2 确定适应值的度量； 3 确定控制该算法的参数和变量； 4 确定怎样指定结果及程序运行结束的标准。 在常规的遗传算法中，表示方案是把问题的搜索空间中的每个可能的点表示 为固定长度字符串。表示方案的确定需要选择串长l 和字母表规模k ，二进制位 串是遗传算法中常用的表示方法。适应值度量为群体中每个可能的确定长度的特 征串指定一个适应值，它经常是问题本身所具有的。控制遗传算法的主要参数有 群体规模n 和算法执行的最大代数m ，次要参数有复制概率p r 、杂交概率p c 、 变异概率p m 等参数。有关停止执行的标准要视具体问题而定。一旦这些准备步 骤完成后，就可以使用遗传算法。 遗传算法的基本流程： 1 随机产生一个由固定长度字符串组成的种群： 2 对于字符串种群，迭代地执行下述步骤，直到选种标准被满足为止： ( 1 ) 计算群体中的每个个体字符串的适应值： ( 2 ) 应用下述三种操作( 至少的两种) 来产生新的种群： 夺复制：把现有的个体字符串复制到新的种群中。 夺杂交：通过遗传重组随机选择两个现有的子字符串，产生新的字符 串。 夺变异：将现有字符串中某一位的字符随机变异。 3 把在后代中出现的最高适应值的个体字符串指定为遗传算法运行的结果。 这一结果可以是问题的解( 或近似解) 。 遗传算法流程图如图2 - 1 所示： 第二章遗传算法实现技术概述 图2 - 1 遗传算法的流程图 f i g2 - ig e n e t i cg l g o r i t h m sp r o g r e s sr e p o r t 2 4 面向对象技术在排课系统中的应用 在排课求解算法中采用面向对象技术，能够在排课模型的基础之上，更好地 模拟实际的排课情况，可以扩展形形色色的约束条件。实体关系图以及0 0 h 的使 用是面向对象技术中的常用的分析方法。 1 3 广东工业大学工学硕士学位论文 2 4 1 排课系统的实体关系图( e r d ) 在纯0 0 ( o b j e c t e d o r i e n t e d ) 数据库成熟之前，关系数据库仍然是建立大 型软件系统必不可少的。基础数据库设计的第一步是要建立数据库应用系统的概 念模型，传统的e r d ( 实体联系图) 是建立概念模型的首选工具。 e r 方法最早在7 0 年代被提出，作为一种概念模型的方法，到现在被广泛采 用。e r 模型由三个要素构成：实体集合、属性和关系。e r 模型是以“实体”的概 念为基础，实体及实体之问的联系被认为是e r 模型的元，这些元被e r 模型称为 用户视图，它用来解释、指定和处理数据库系统的需求并使之文档化。实体是客 观存在并可相互区分的事物：一个实体通常由若干个属性来刻画，属性是描述实 体的特征；具有相同属性的同类实体组成的集合被称为实体集，在许多场合，实 体集和实体互不加以区分。实体通过其一个或多个属性来标识。实体之问可以通 过联系相互关联。e r 模型包含联系和联系类，联系类是实体类之间的联系，而 联系是实体之自j 的联系。 e r 模型是以e r 图( e r d ) 描述的。在e r d 中，有三个基本符号，即长方形、 椭圆形和菱形，分别用束描述实体集合、属性和关系。基本符号通过线段互相连 接。其中： 1 如果属性a 是依附实体集合e 的，则在a ，e 问以直线连接。 2 如果实体集e 和巳之间存在关系r ，则在e 和r ，r 和之间画两条直线 将两者连接。 3 若有实体集e 和e ，e 。& ，则e 和b 之间存在一种特殊关系，称作i s a 关系，此时要以有向线段连接三者( e ，e 。，i s a ) 。 e r d 不仅具有较强的表达数据逻辑结构的能力，可以方便地转换为关系数据 模型，而且图形简洁，便于丌发者与管理人员交流。排课系统的e r d 不仅描述了 排课问题中可能涉及实体，而且标明了实体之l 日j 的关系，反映数据库系统中的数 据逻辑。特别是，由于e r d 实际上与o o a 模型在表达数据方面存在着某种内在联 系，e r d 中几乎每一个实体都对应o o a 模型中一个含有属性的类，因而e r d 有时 也作为o o a 的辅助工具。第二步将数据库概念模型转换为关系模型，即把e r d 中 每一个实体和联系都可转换为关系构成关系集合；最后一个重要步骤是利用关系 1 4 第二章遗传算法实现技术概述 规范化理论，将关系数据模型进行优化处理，使其具有较低的数据冗余和较高的 存取效率。 2 4 2 排课系统的o o a 面向对象的方法学认为： 1 - 客观世界是由各种对象组成，任何事物都是一个对象都有自己质的规定 性和运动变化的规律，每个对象都属于某个对象“类”，都是该对象的一个实 例化元素。不同对象的组合及其相互作用就构成了我们可研究、分析和构造的客 观系统。 2 通过分析和比较，可以发现对象间的相似性，即揭露出不同对象的共同 属性。这就是构成对象的依据。在按“类”、“子类”、“父类”等概念构成 对象类的层次关系时，如不加以特殊说明，则低层对象可以自然地继承高一层对 象的属性。对己经分成类的各个对象，可以通过定义一组“方法”来说明该对象 的功能，也就是允许作用于该对象上的各种操作。对象问的相互联系及作用是 通过传递消息来完成的，消息就是通知对象去完成允许作用于该对象上的操作。 面向对象开发方法包括三个基本成分：面向对象分析( o o a ) 、面向对象设计 ( d o d ) 和面向对象程序设计( o o p ) 。其中，o o a 是信息系统开发过程中的重要步骤。 o o a 是对问题空间的理解和分析，分析阶段进行通过类或对象的认定，确认类之 间( 或对象间) 关系，然后对它们的属性、所提供的方法和所需要的方法进行描述， 并按照它们之间的关系进行组织，得到类( 或对象) 结构。o o a 建立在信息模拟( e r d 和语义数据模型) 和面向对象程序设计语言的概念及基础上，如图2 3 所示。从 信息模拟吸取了属性、关系、结构以及对象作为问题域中某些事物的实例的表示 方法等概念，从面向对象程序设计语言中吸取了属性和方法的封装，属性和方法 作为一个不可分割的整体，以及各类结构和继承性等概念。 广东工业大学工学硕士学位论文 2 5 本章小结 图2 - 2o o a 的形成 f i g2 - 2t h ef o r m a t i o no f o o a 本章对一般遗传算法进行了必要的介绍。从算法的特点、关键步骤、遗传算 子、关键函数、进化过程、停止进化准则、算法流程、执行框图、e r d 、0 0 a 图 等方面展丌概述。为后续章节针对排课的遗传算法进行深入的研究与实现奠定了 理论基础。 第三章基于遗传算法的捧课系统需求分析 第三章基于遗传算法的排课系统需求分析 依据上一章介绍的遗传算法基本理论，以排课算法的设计为目标，主要完成 以下血方面的工作：( 1 ) 业务需求分析：( 2 ) 数据需求分析；( 3 ) 数据表分析( 4 ) 功能需求分析；( 5 ) 约束条件。 3 1 业务需求分析 排课工作是一项十分繁重而复杂的工作，就以广东海洋大学而言，它涉及到 5 4 个专业、八百余名教师、一力多名学生，同时要对三千多门课程进行合理的 组织安排，而所使用的教室资源却在学生规模每年都在增加的趋势下越发显得紧 张了。 排课的整个过程中充满了矛盾运动，其中包括上课班级、所丌课程、任课教 师、上课时间、上课地点这5 个方面在排列组合中发生的冲突和矛盾现象。课程 门类多、班级多、教师少、教室少是排课时发生冲突和矛盾的主要因素，而班级 多、教室少则是矛盾的重要方面。 课程表则是解决这些矛盾的舞台，是提高教学管理水平、组织师生进行有序 教学的规范之一，对有效地提高教育