发布时间 : 星期日 文章计算机自动排课系统设计与实现更新完毕开始阅读461ae55acaaedd3383c4d3d0
题的所有解：其次构造状态空间树，这棵树的每条完整路径都代表了一种解的可能：再次是构造约束函数，通过描述合法解的一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分：然后通过深度优先搜索完成回溯。
①设置初始化的方案(给变量赋初值，读入已知数据等)； ②变换方式去试探。若全部试完则转⑦ ；
③ 判断此法是否成功(通过约束函数)，不成功则转② ； ④ 试探成功则前进一步再试探； ⑤正确方案还未找到则转② ； ⑥ 已找到一种方案则记录并打印； ⑦退回一步(回溯)，若未退到根则转② ； ⑧ 已退到根节点则排课结束或打印无排课结果。
回溯法适用于解的组合数相当大但仍然有限的那一类问题。它的一个有重要的特性是在搜索执行的同时产生解空问。在搜索期间的任何时刻．仅保留从开始节点到当前节点的路径。因此．回溯算法的空间需求为一个常数，即从开始节点起最长路径的长度。这个特性非常重要．因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话。再多的空间也不够用。其缺点是时间复杂度较大．因此在采用时还需要谨慎。最好是和其它的算法结合使用。
1.3.3遗传算法
遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是有美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Hilland教授所提出的GA通常为简单遗传算法（SGA）。
遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产
生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小挑选（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。
遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点：
1、 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子。
2、 遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。 3、 遗传算法使用多个点的搜索信息，具有隐含并行性。 4、 遗传算法使用概率搜索技术，而非确定性规则。
根据其算法特点，遗传算法非常适合于应用到排课处理中。具体应用方式将在后面设计部分详细说明。
1.4遗传算法国内外现状
进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。
随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。
三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（Evolution Programming,EP）以及进化策略（Evolution Strategy,ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的智能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。
1991年D.Whitey在他的论文中提出了基于领域交叉的交叉算子（Adjacency based crossover），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了TSP问题中，通过实验对其进行了验证。
D.H.Ackley等提出了随即迭代遗传爬山法（Stochastic Iterated Genetic Hill-climbing，SIGH）采用了一种复杂的概率选举机制，此机制中由m个“投票者”来共同决定新个体的值（m表示群体的大小）。实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力。
H.Bersini和G.Seront将遗传算法与单一方法（simplex method）结合起来，形成了一种叫单一操作的多亲交叉算子（simplex crossover），该算子在根据两个母体以及一个额外的个体产生新个体，事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。同时，文献还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三者交叉算子比其余两个有更好的性能。
国内也有不少的专家和学者对遗传算法的交叉算子进行改进。2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题。
2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法（Building-block Coded Parallel GA，BCPGA）。该方法以粗粒度并行遗传算法为基本框架，在染色体群体中识别出可能的基因块，然后用基因块作为新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编码的染色体群体作为下一轮以相同方式演化
的初始群体。
2005年，江雷等针对并行遗传算法求解TSP问题,探讨了使用弹性策略来维持群体的多样性,使得算法跨过局部收敛的障碍,向全局最优解方向进化。
1.5研究目标及内容 1.5.1研究目标
对遗传算法进行研究，进而将其应用到排课系统中，利用计算机来模拟手工排课工作，可以抽象问题中的各个要素，数学表达各种约束条件，并根据课表的组织形式和普遍存在的规律，缩减了问题空间的搜索范围，有效组织了排课知识，使其在一定程度上呈现智能化。
1.5.2研究内容
学校排课问题本质上是时间表问题的一类典型应用实例，是为了解决课程安排对时间和空间资源的有效利用并避免相互冲突。在排课过程中需要考虑课程教学效果、满足教师特殊要求等多项优化指标，将各门课程安排到相应的时间和教室。
1）排课问题具体研究的内容如下： （1）遗传算法的理论 （2）排课问题的建模
（3）遗传算法在自动排课中的应用方法 （4）排课算法的实现
2）排课问题具体研究的重点和难点如下： （1）深入理解遗传算法理论。
（2）排课问题的建模，包括排课问题的要素以及排课过程的约束条件等。 （3）遗传算法在排课问题中的应用方法，包括基因编码、初始种群的产
生、适应度函数、控制参数的设定等。
（4）排课问题本身的求解规模过于庞大，各要素之间的关联层出不穷，
以及人们对多个课表优劣评定的准则存在差异，在求解排课问题的过程中，会面对难以穷尽的组合和多个模糊目标的优化问题，实际解决时会受到一些制约。
3）排课问题具体研究方法如下：
采用循序渐进的方法进行研究，首先必须要学习遗传算法，在学习