猪八戒网

   摘要：大学课程表问题（University Timetable Problem-UTP）或者时间表问题（Time Table Problem-TTP）是一个一直困扰各个学校的令人头疼问题，它是运筹学典型的组合优化问题之一。教师，教室，时间，课程和班级是五个制约该问题解决的重要因素。1975年，经过对该问题进行证明，S.Even提出它是一个NP完全问题。这意味着普通的方法比如图着色，整数规划，对复杂的学校排课问题并不能进行良好的解决。现在提出了很多其他不同算法来解决该问题，而目前解决该问题最好的两种方法是遗传算法和模拟退火算法。本文想要介绍的就是一种改进的混合遗传算法。

    十九世纪，达尔文提出了生物学上的进化论，理论的核心就是“物竞天择，适者生存”。而遗传算法就是一种模拟自然界自然选择和自然遗传机制发展起来的，高度并行，使用群体搜索技术来寻找NP完全问题最优解的办法。经过实践证明，遗传算法是解决该类NP完全优化组合问题的最行之有效的方法之一。

    基于案例的推理(Case-Based Reasoning，CBR)技术，最先是由美国人Roger. Schank教授提出的，之后逐步推广到机械CAD、医疗卫生、企业管理、军事等领域，并得到了成功的应用。CBR是基于知识学习的方法，它的核心思想就是：相似的问题总是有较为相似的解决方案和同一类型的问题总是不断地重复出现。它试图通过对先前的知识和经验进行学习，然后加以改变用来解决当前相似的问题。本文就是希望使用CBR这种特性来对遗传算法进行改进优化，以达到期望中更好的效果。

笔者在文中讨论一下几个问题：1．   本文详细介绍了课程表问题中的影响因素，约束条件，并对其进行了数学化描述，其次用数学理论与方法建立课程表问题（University Timetable Problem-UTP）的模型并对其进行了较为详尽的分析。2．   通过对一般遗传算法结构的详细表述和对CBR的分析，指出其在两者解决课程表问题（University Timetable Problem-UTP）中笔者认为不甚理想的地方，然后利用二者的优点加以融合，重新设计出结合二者优点的改进的遗传算法。3．   对改进的遗传算法和一般的遗传算法进行比照分析，通过一些图表来说明性能的改进。

关键字：遗传算法 基于案例的推理 课程表问题 时间表问题多目标优化

    第一章  概述 

    1.1  文章的内容和结构

  本文是一篇研究遗传算法和基于案例推理的技术在解决大学课程表问题(University Time Table Problem)或者时间表问题(Time Table Problem )上的如何进行有效配合的文章。一开始先对大学课程表问题(University Time Table Problem)做了一个大致的介绍，指出它是一个NP完全问题，也是一个多目标优化问题，遗传算法比较适合解决该问题；然后开始讲述遗传算法的大致情况；再者介绍基于案例推理的技术，指出它和遗传算法在解决大学课程表问题的优势和劣势，说明二者融合的良好前景；再然后对该问题进行数学建模和数学化描述；最后给出两种技术融合后的改进的遗传算法和测试报告。本文大致结构可如下：

                            图1：论文结构图

     论文的第一章也就是本章是对全文做一个总的概括，第二章提出要就解决的问题和该问题的背景研究历史等，第三章和第四章开始做知识的铺垫为后面章节打基础，第五章和第六章应该是本文的核心着重讲述了问题的模型建立和主要算法，第七章收尾对算法的性能作一个说明比较。

   1.1   研究的任务和目标

本文的目标是提出一种改进的遗传算法，或者称为混合算法，提升排课系统的效率，优化排课方案，使其更合理，更符合实际问题的要求。

本文的主要任务有以下几项：

1.             对所用到的知识，包括遗传算法和基于案例推理的知识做一个较为详细而且系统的讲述，为后面的章节作铺垫。

2.             提出大学课程表问题的教师和教室课程安排情况的表示方法，使能够方便判断出上课情况，数学语言描述课程表问题的各种约束，为后来的算法约束判断打下基础。              

3.             提出各种完备的子算法。判断案例相似性算法，以方便在遗传算法初始化时候从案例库中找到最相似案例初始化；班级合并算法，初始化时将同一个位老师教授同一门课的班级变为合班；课程冲突检测算法，防止初始化时课程安排违反硬约束；提出课程安排算法，将在案例库中无法找到最相思案例的案例初始化。教室安排算法，为各门课程安排教室而又不发生冲突。

4.             描述遗传算法优化课程案例的详细实现过程。给出一个完整的改进的遗传算法的实现方案。

5.             测试改进遗传算法的性能，与一般算法进行比较，给出详细的测试方案和详尽的结果。

    第二章   排课问题研究的概述

    2.1  大学课程表问题的描述

     2.1.1 时间表问题概述

 时间表问题（Time Table Problem）既是一个理论方面的问题也是一个来源于实践的问题，它是实际生活中人们可以遇到的问题，甚至对于我们来说很常见。比如说交通时间表问题^[11][12]（transportation Timetabling)，这个问题是如何设计城市中公交车或者有轨电车的时间表问题,使其能够良好的运行，减缓城市交通的压力；比赛时间表问题^[13] (employee timetabling)是如何设计一项大型赛事的时间表，来保证大型赛事能够良好的进行；还有雇员工作时间表问题(employee timetabling)，研究得是如何来安排雇员的工作，使其工作能够达到最高的效率；当然还有我们要研究的大学课程表问题，这个问题研究的主要目的是提出一种优秀的算法最大程度上使安排大学课程人性化，合理化。

 时间表问题是一类具有多约束的将有限时间资源分配给多个事件组合优化问题。通常，一个时间表问题会有一系列事件(event)和一组有限的时间单元(timeslot)和一组具体地点，并且还要受到一系列约束的限制，这些约束又分为硬约束和软约束。硬约束就是一系列的限制我们在进行时间表安排的情况下必须无条件满足，不能有任何违反，而软约束也是一系列的限制，但是我们不一定要全部满足，但是这些软约束的满足情况却决定了我们时间表安排的合理情况。在后面章节中我们将详细讲述我们所主要研究的大学课程表问题的软硬约束。

    2.1.2 大学课程表问题概述

本文主要研究的是时间表问题中的大学课程表问题。这个问题是来源于大学日常生活，和大学生的日常生活息息相关。随着大学扩招的进行，学生的数量急剧增加，学校的教育资源显得越来越有限，这个问题就显得越发突出。所以对这个问题的研究具有现实意义，但是它又不缺乏理论性，1975年，S.Even对该问题进行了研究，并指出大学课程表问题是一个NP完全问题，这就说明了该问题没有真正意义上的最优解，人们的求解只有可能是相似最优解，也就是说求解获得的答案只可能不断接近最优解，但是不可能是最优解。于是人们就尝试用各种方法去解决这个问题如图着色，分支定界，整数规划等，经过实践证明，遗传算法和模拟退火算法是两种解决该问题比较理想的方法。本文在后面主要着重介绍遗传算法。

那什么是大学课程表问题？虽然已经从感性上已经了解了这个问题，但是下面将给出一个较为严格的定义方便深入理性的理解这个问题。Carter和Laporte这样定义：“大学课程表问题是一个多元分配问题，它研究的就是如何把学生和老师分配给课程，课程单元或者班级，如何把事件（上课事件）分配给教室和时间。”下面为原文：

“a multi-dimensional assignment problem in which students,teachers (or faculty members) are assigned to courses,course section or classes; events (individual meetings between students and teachers) are assigned to classrooms and times”^[14]

简单一些的说大学课程表问题研究的就是如何把一系列的课程分给有限的教室和一周内有限的上课时间单元，如何把学生和老师分配给课程。当然实际研究的时候并没有理论上说得这么简单，它会受到多种约束的影响，有硬约束也有软约束，这我们在前几段已经提到了，在后面第五章中我们将详细讲述大学课程表的软硬约束。

 2.2  大学课程表问题的研究情况

     2.2.1 大学课程表问题的理论研究

 大学课程表问题在20世纪50年代末就已经开始被人们所重视，将它作为一个科学问题来研究，但是一直到1963年才由Gotlieb提出了该问题的数学模型和形式化描述，这标志着排课问题正式被作为科学问题来被人们所研究，到了1975年S. Even在他的论文中提出并证明大学课程表问题是一个NP完全问题，把该问题理论化，同时也说明该问题有解，并能够找到解。但是根据计算和难解性理论，目前还没有解决NP完全问题的多项式算法。到1979年，Schmidt和Stroheim在文献中就列出了300多篇有关大学课程表问题的已发表文献。现在每年外国的关于运筹学的杂志上依然总会出现一些关于该问题的论文。

    2.2.2 大学课程表问题解决方法

至今已经有很多算法被拿来研究用于尝试解决该问题。起初，图论是研究大学课程表问题的一个主要武器，图着色技术被广泛的用来尝试解决该问题。举个例子，1994年，Burke, Elliman 和Weare^[16]就研究出一种启发式的图着色方法，该方法把考试进程分成若干组，然后把它们放在一起安排，以求找到一种能够解决考试时间表问题的方法。但是图着色技术本身就是一个NP完全问题，所以对解决该问题帮助不大。后来CARTER, M.W. 和 LAPORTE^[15]尝试采用按序分派的方法解决该问题，这种方法需要按启发顺序把事件分出先后顺序，然后再尝试寻找一个可行的解决方案。Ferland 等人^[18]和吴金荣^[17]把排课问题转化成整数规划问题来解决，但计算量很大，只适合一些理论中的简单情况对于解决复杂问题是不可行的。许多文章^{[19][20[21][22]}试图利用启发式函数来解决排课问题，但是大多数启发方法都是模拟手工排课的过程来实现的。但是由于实际的排课问题存在各种各样的限制条件与特殊要求，处理不好这些限制和要求就无法找到理想的排课方案。

最近，后启发式算法被引入大学课程表问题，而且在一定程度上获得成功，在解决大学课程表问题上取得了不错的成绩。后启发式算法主要包括三种：禁忌搜索(Tabu Search)，模拟退火算法(Simulated Annealing)和进化算法(Evolutionary Algorithms)（遗传算法）。

    1.禁忌搜索( Tabu Search)

禁忌搜索是一种主要研究研究具有各种特殊的要求的真实世界时间表问题的算法。它由Glover在1986年提出，进而慢慢形成一种独特而又完整的算法。经过研究表明这种算法如果能够正确恰当选择参数（禁忌列表，初始化解决方案和目标函数）那么它在解决大学课程表问题上将有很出色的表现。1998年，Nonobe 和Ibaraki^[23]开发出一种基于禁忌搜索的处理一般问题解决系统，这种系统对于满足约束问题特别是高中课程表问题有着出人意料的良好效果。后来在2002年，Alvarez.Valdes, Crespo和Tamarit ^[24]研制出了一种基于禁忌搜索的具有友好界面的系统，这个系统经过一系列实验也取得不错成绩。现在关于这项技术的研究还在继续，我们这里就不再赘述了。

    2. 模拟退火算法(Simulated Annealing)

    模拟退火算法是一种被广泛研究的算法，它也经常被用来解决时间表问题和大学课程表问题。它是一种模拟固体退火过程的算法。它由Kirkpatrick等人于1982年提出，后来就专门用来解决大规模组合优化问题，它是一种解决NP完全组合优化问题的有效的近似算法。现在一些研究表明，模拟退火算法在课程表问题^[25]和考试时间表^[26]问题上的实现是高度依赖于各种设定与参数（解决方案空间，降温时间表，邻居产生和评估函数）。因此使用这种算法的时候需要谨慎的选择参数。

    3.进化算法(Evolutionary Algorithms)

    进化算法和遗传算法现在已经被广泛用来研究时间表问题和大学课程表问题。遗传算法最早是由Colorni^[27]等人在90年代初期引入用来解决课程表问题的，一开始他们引进了矩阵表示方案和交叉，变异算子。后来Colorni^[28]又把遗传算法成功应用到米兰一所较大的学校的课程排布问题中。Paechter^[29]等人对TTP问题进行了研究，提出了时域置换法和放置一查找法，并针对较大规模的实际TTP问题比较了这二种算法的性能.Burke^[30]对将进化算法分阶段的用于UTP问题做了初步的研究，得到一些颇有价值的成果。遗传算法是本文研究的重点，后面第四章我们将更加详细的讲解遗传算法。

    另外基于知识学习的技术也渐渐的参与到对于时间表问题和课程表问题的求解上来。基于知识学习的技术是一种模仿人类思维过程的技术，人类在解决问题的时候总是先在大脑中寻找一个相似的问题，然后对这个相似问题进行分析学习，然后对这个相似问题进行改进以求获得当前新问题的解决方案。这种技术有一个很至关的重要问题，就是如何能清晰地表示经验和知识，并将其存入知识库以便后来之用。这种技术主要包括两种：一种是基于规则的专家系统，另一种是基于案例推理的系统(Case-Based Reasoning-CBR)。现在大多数用来解决时间表问题的基于知识学习的系统都是基于规则的，很少有基于案例推理的系统。但是用基于案例推理的技术来解决时间表问题有自己很大的优势。Rong Qu, BSc在2002年8月提出了用基于案例推理的技术来解决时间表问题，并在其论文中详细讲述了该技术的优点。本文主要讲述时后一种基于案例推理的系统。我们将在第五章作较为深入的讲述说明。

   2.3  排课的各种算法的比较

至今为止有很多的方法技术和算法都已经被用来尝试解决时间表问题或者大学课程表问题，他们效果各异，有的完成很出色，有的则只在某些特定情况下才能有不错的效果。传统的算法比如说图论和整数规划在应付简单时间表问题和课程表问题时可以较容易的编码，通常情况下可以圆满地完成任务。但是他们通常对于大型的复杂约束时间表或者课程表问题显得束手无策。人工智能领域的全局搜索技术包括（遗传算法，禁忌搜索，还有模拟退火算法）在各个问题领域都取得了很不错的效果。他们都能够处理各个级别的问题，既可以是简单的问题，也可以是复杂的大型问题。但是他们也有自己的问题需要注意，在使用他们的时候不同场合参数的初始化往往不同，这是一个既重要而又难以处理的问题。研究表明基于后启发方式的混合算法，在处理问题时候往往会比单独一种算法有更好的更出色的效果。所以本文就是在尝试于基于案例的推理技术来初始化遗传算法。

     可以看出后启发式算法是解决时间表问题和大学课程表问题各种算法中的翘楚。但是当他们之间作比较的时候，一些研究表明，当算法使用的环境不同，表示的方法不同和选择的算子不同的时候他们往往会有完全不同的表现。1995年，Ross 和 Corne在解决一个时间表问题时，对遗传算法，模拟退火算法和随机爬山算法进行比较，得出结论随机爬山算法在解决问题的质量上略胜一筹[31]。Colorni, Dorigo 和 Maniezzo在1998年，对遗传算法，模拟退火算法，禁忌搜索和辅以局部搜索的遗传算法进行比较，得出结论禁忌搜索的效果更佳，但是辅以局部搜索的遗传算法给出了一系列的高质量解决方案，给用户更多的灵活性，以满足各种不同的要求。虽然在不同的环境下，各种后启发算法会有不同的表现。但是大家都一致认为遗传算法在解决现实生活中问题的时候具有足够的灵活性，可以给出一系列的较优解以满足人们各种方面不同的需要。本文将着重研究的就是遗传算法，一种改进的混合算法，希望能够对解决时间表问题有较好的作用。

大学课程表问题作为一个典型时间安排问题已经成为了一个具有丰富知识和经验的应用领域。这些积累的经验就可以使基于案例的推理技术大展身手。现在几乎所有的用来解决时间表问题的基于知识学习系统都是基于规则的。因为实际问题的各种约束的复杂性，使其不能很好的将经验转化为规则，因此大多数使用规则的基于知识学习系统都将知识和经验定位于辅助作用而不是重用已有的丰富经验和知识。本文试图讲述一个使用基于案例推理技术进行初始化，并用该技术用来指导算法进行的改进的遗传算法。 

    第三章  遗传算法简介 

    3.1  遗传算法的来源和研究发展 

    3.1.1         从生物进化到进化计算

19世纪达尔文通过艰辛的考察多年的研究，最终提出了一个具有划时代意义的理论－进化论。按照进化论，地球上的每一物种从诞生开始就开始了漫长的进化。生物种群总是从低级，简单的类型逐步发展到高级，复杂的类型，从简单单细胞生物逐步发展成为高级多细胞生物。每种生物为了生存需要不停的斗争，包括同一种群内部的斗争，不同种群之间的斗争，和自然无机环境进行斗争。有些生物生存了下来，并繁衍壮大，因为它具有与众不同但是能够适应环境适合生存的特点；有的生物消亡了，不再存在于地球，留给我们只是化石和无边的猜测，这是因为它不能够适应环境，不能在生物竞争中取胜。达尔文通过研究考察发现了这一过程，并将它称为“物竞天择，适者生存”。

生物学家通过研究发现有的生物之所以繁衍壮大，有的生物之所以消亡，就是因为他们具有了一些别的种群没有的特点，而这些特点又是遗传基因决定的，遗传基因上有大量的遗传信息，这些遗传信息就是决定生物身上各种性征，而这些性征有一部分又能够决定生物在自然界的竞争中胜败，而竞争的胜败直接决定了某一种生物的生存和发展。但是一种生物的壮大就需要生物能够把自己的性征传给下一代，而这一过程是通过遗传基因来做到的。