多种排课算法的探讨与分析文献综述.doc

单位代码 01 学 号 040101172 分 类 号 密 级 文献综述 多种排课算法的探讨与分析 院（系）名称信息工程学院 专业名称计算机科学与技术 学生姓名 指导教师2008 年 3 月 15 日 黄河科技学院毕业设计(文献综述) 第I页 多种排课算法的探讨与分析摘 要课程表的编排是学校教学管理工作中不可或缺的一部分，是教学工作顺利进行的保证。由于学校教学工作的科目安排，不仅反映出学校的办学思想，也体现学校教育管理的水平，所以，科学、合理地编排各学科教师的授课时间，是不容忽视的。而如何实现课表编排的高效与快速性，是本文所要描述的内容。本文分别对PBIL算法，案例注入式遗传算法、混合型模拟退火算法、分支定界算法的背景、原理、实现及存在优缺点做了分析与比较，其中PBIL算法是一种进化演绎算法，以学习为手段，用概率作指导，通过重复计算和目标函数的收敛性求得最优解；案例注入式遗传算法通过对案例库的相似搜索，然后通过学习、复制、交叉、变异实现新案例的生成；退火算法采用复杂度高者优先、循环首次适应算法、贪婪法、回溯法和松弛法等多种方法，由随机函数求得最优解；分支定界算法是一种在问题的解空间树上搜索问题的解的方法。这几种算法各有优缺点，而收敛速度和最优解是受关注的。关键词：课程表，遗传算法，分支定界算法，PBIL算法目 录1 绪论12 PBIL算法22.1 PBIL算法描述22.2 PBIL算法的进化过程23 案例注入式遗传算法33.1 案例注入式遗传算法简介33.2 案例注入式遗传算法组成结构33.3 案例注入式遗传算法存在的问题44 混合型模拟退火算法54.1 混合型模拟退火算法简介54.2 模拟退火的思想54.3混合型模拟退火算法的前景65 分支定界算法75.1 分支定界算法简介75.2 分支定界法的思想7结 论9参考文献10 黄河科技学院毕业设计(文献综述) 第9页 1 绪论随着学生人数的不断上升和社会的进步，学校的课程设置也向深度和广度发展，因此手工排课的实现相应增加了困难。然而随着科学技术的日益进步，计算机的应用越来越广泛。而且计算机具有运算快，处理能力强等特点，很自然地会应用到这一领域。而且用计算机进行排课能够快速地得到满足约束条件的可行性结果，具有排课时间短、质量高和节约人力的优点，这能使教务人员从繁杂的排课任务中解脱出来，并对推动教学的发展起到非常重要的作用。所以如何用计算机实现高效的、快速的课程表编排工作，成为许多人研究的目标，而在这其中算法的分析与选择是相当重要的，是实现高效功能的关键。所以要对许多相关算法进行探讨与分析，以此找到一种高效、快速的排课算法来实现课程表的编排工作。课程表的编排，实际上就是各种方案的筛选过程1。而这个过程较为复杂，用人工来编排课程表，运算速度慢，筛选方案少，其结果合理程度也会大打折扣。因此可以利用计算机的优势来进行课程表的编排工作。计算机编排课程表起点是用随机函数选定的，所以计算机每重复一次编排，其结果肯定不同，因此利用计算机运算速度快的优势让其在短时间内，进行多次重复，就可实现很多次的方案筛选。在具体程序设计时加入适当的检索，让计算机自动筛选出带有合理参数的方案，供决策者最后确定。也可以由计算机直接根据合理参数筛选出最后结果，如果不满意还可让计算机不停地进行筛选，直至最终得出较为满意的结果。这就是算法的应用与实现。2 PBIL算法2.1 PBIL算法描述PBIL(Population-Based Incremental Learning)算法是一种进化演绎算法，它将进化过程由原来的生物进化过程转变为一种学习过程，用学习概率来指导产生后代，完成目标功能的实现2。这种概率是整个进化过程信息的积累。在这样的进化过程中，在目标函数的指导下，可以得到目标函数值越来越小的解，并且用多次重复计算，可以得到多种不同的解，便于使用者从中挑选合适的解作为安排的方案。由此过程产生的结果也就更具有优化性，因此能在许多问题中获得更快的收敛速度和更好的结果。2.2 PBIL算法的进化过程第1步：初始化学习概率p；第2步：由学习概率指导产生k个解；第3步：计算上一步产生的k个解的目标函数值，并从中找出一个最优解，设为B；第4步：用目标函数值中的最优解B修正学习概率P；第5步：返回到第2步循环，直至满足一定的结束条件为止。由于实际问题中的每一个解，往往需要多位取值，此时若仍用二进制位表示，会造成许多不便，所以会经常使用其他类型的编码方法进行操作3。如任意整数编码，二维表。在课表的编排过程中会涉及多种约束条件，而求解过程就是排除约束条件间的冲突矛盾，同时要尽量合乎现实情况。这里会出现课表编排问题中的两个条件：硬约束条件和软约束条件。其中：硬约束条件是必须满足的条件，软约束条件是尽量满足的条件。课程表安排问题是组合规划中典型的优化决策问题，已被证明是NP难题，至今为止，人们没有找到求解此问题的精确方法4。在PBIL算法的求解中需要首先确定样本集，这关系到算法实现的复杂度和问题实现的可行性。而样本集的确定是一个复杂而重要的问题，这也给算法实现带来了不便，因此解决这个问题很是关键。3 案例注入式遗传算法3.1 案例注入式遗传算法简介基于案例的推理(Case-Based Reasoning，CBR)技术最先是由美国耶鲁大学Roger Schank教授在他的论著Dynamic Memory中提出的，之后被逐步推广到机械CAD、医疗卫生、企业管理、军事等领域并得到了成功的应用5。CBR是一种基于知识学习的技术，通过对先前案例的查找，在案例库中找到一个与当前案例最为相似的案例，然后对这个最相似的案例进行学习，通过对该案例的解决方案进行修改来获取当前问题的解决方案。而解决的新案例会根据需要最终决定是否被存入到案例库中。对基于案例的推理技术来说，它可以通过对先前案例的学习来解决当前问题，以此加快解决问题的速度，另外由于其自身具备学习的能力，随着解决问题数目的不断增加，案例库中的案例也在不断地增加，因此从库中检索到能够解决当前问题的方法的概率也随之增大，从而可以进一步提高解决问题的速度。因此，考虑利用基于案例的推理来改进遗传算法的初始化操作，并在进化自然选择阶段使用基于案例的推理替换适应度较差的个体，以此来加快遗传算法的收敛速度，以便更快、更好地解决问题6。3.2 案例注入式遗传算法组成结构案例注入式遗传算法是一种混合式遗传法，它分为2个主要模块：案例模块与遗传算模块，它的基本结构如图3.1所示。案例存储案例注入案例管理模块案例库模块删除及管理案例搜索遗传算法模块图3.1 案例注入式遗传算法结构该模块完成以下几个功能：案例相似性的比较分析、案例的查找、案例的存储删除。遗传算法模块的主体与一般遗传算法结构基本一致，整个过程遵循自然选择策略，包括：复制、变异和交叉操作；适应度的评估；评估后再进行复制、变异和交叉操作7。如此反复直到适应度最终满足使用者的要求。在此基础上，结合基于案例的推理对算法进行调整：首先，对遗传算法的初始化部分采用了案例注入式的方法，从而加快了遗传算法的收敛速度。其次，在遗传算法进行中，经过复制、交叉和变异操作后可以选择一代中最好的案例存人案例库以丰富案例库。3.3 案例注入式遗传算法存在的问题对于遗传算法而言，种群初始化过程非常重要，它需要尽可能地囊括所有的优秀个体，但与此同时种群又不能过大，因为种群过大会增加算法的运算量和复杂度8,9。因此，大多数的遗传算法往往采用随机方式来初始化种群，这样做的目的是为了获得更多的优秀解决方案，产生无偏向搜索空间。然而对于解决类似课程表问题的系统来说，在系统频繁遇到的都是相似、相关问题的情况下，如果每次初始化都需要从头开始的话，势必造成运算量变大和复杂度增加等情况，从而影响算法的性能。浪费大量的系统时间，这也是影响遗传算法性能的主要原因。4 混合型模拟退火算法4.1 混合型模拟退火算法简介基于概率型启发式算法(HA)的混合型模拟退火算法采用了复杂度高者优先、循环首次适应算法、贪婪法、回溯法和松弛法等多种方法，该算法所排出的课程表可作为模拟退火算法的初始解10。模拟退火可对概率型启发式算法的排课结果做进一步优化，克服了启发式算法不具有全局收敛性的缺点。所以，混合型模拟退火算法具有启发式算法充分利用领域知识、计算量小、优化快速和模拟退火的全局收敛性，数值实验也证明了它的有效性和可行性。中小学课表问题有它的特点和难点，第一阶段采用基于概率论的启发式算法，该阶段又分两步：第一步：用基于概率论的启发式方法排出每个班每门课每天上几节，可得到多种排法；第二步：采用启发式方法，排出每个班每天每一节上什么课，可得到多个不同的课表。第二阶段运用模拟退火方法，对概率型启发式算法所排出的课表做进一步优化，使其尽可能满足所有约束条件。在第一阶段中所采用的启发式规则包括：复杂度高者优先、循环首次适应算法、贪婪法、回溯法和松弛法，这些启发式规则可增强搜索的目的性，提高算法的效率。4.2 模拟退火的思想 模拟退火算法是基于Monte Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理退火过程与一般组合优化问题之间的相似性11。模拟退火算法是在某一初温下，伴随着温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的最优解，即在局部最优解能概率性地跳出，并最终趋于全局最优。标准模拟退火算法如下：(1) 给定初始温度t=t0，随机产生初始状态S=S0，令k=0；(2) repeat；(3) repeat；(4) 产生新状态s=Genete(s)；(5) f=f(s )f(s)；(6) if min1，expftkrandom0，1；(7) s=s；(8) 直到抽样稳定准则成立；(9) 退温 tk+1=update(tk)，并令k=k+1；(10) 直到算法终止准则成立；(11) 输出算法搜索结果。4.3混合型模拟退火算法的前景基于知识的概率型启发式算法(HA)和模拟退火(SA)相结合的混合型算法，该算法能充分利用领域知识，计算小、优化快速，并具有模拟退火的全局收敛性。数值实验进一步表明该算法的有效性和可行性。今后可继续研究模拟退火的不同退温策略，如增加升温或重升温过程，以及采用两种退温速率策略对算法效率和性能的影响。5 分支定界算法5.1 分支定界算法简介分支定界(Branch And Bound)算法是一种在问题的解空间树上搜索问题的解的方法12。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。利用分支定界算法对问题的解空间树进行搜索，它的搜索策略是：(1) 产生当前扩展结点的所有孩子结点；(2) 在产生的孩子结点中，抛弃那些不可能产生可行解(或最优解)的结点；(3) 将其余的孩子结点加入活结点表；(4) 从活结点表中选择下一个活结点作为新的扩展结点。如此循环，直到找到问题的可行解(最优解)或活结点表为空为止。从活结点表中选择下一个活结点作为新的扩展结点，根据选择方式的不同，分支定界算法通常可以分为两种形式：1、FIFO(First In First Out) 分支定界算法按照先进先出原则选择下一个活结点作为扩展结点，即从活结点表中取出结点的顺序与加入结点的顺序相同。2、最小耗费或最大收益分支定界算法在这种情况下，每个结点都有一个耗费或收益。如果要查找一个具有最小耗费的解，那么要选择的下一个扩展结点就是活结点表中具有最小耗费的活结点；如果要查找一个具有最大收益的解，那么要选择的下一个扩展结点就是活结点表中具有最大收益的活结点。5.2 分支定界法的思想分支定界算法又称分支定界搜索法。该算法是将原始问题分解，产生一组子问题。分支是将一组解分为几组子解，定界是建立这些子组解的目标函数的边界。如果某一子组的解在这些边界之外，就将这一子组舍弃。分支定界法原为运筹学中求解整数规划(或混合整数规划)问题的一种方法。用该算法寻求整数最优解的效率很高。将该算法原理用于过程系统综合可大大减少需要计算的方案数目。对于分支定界算法，首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。上界是已求得的可行解的目标函数值中的最小者，分为初始上界和在探测过程中产生的动态上界。分支定界法在求最优解的迭代过程中，若某结点估计的下界不小于已知的上界，则不必从该节点往下继续搜索。因此若能产生一个较好的上界，可以消除许多不必要的列举计算。课表编排实际上是组合优化中一个典型的判定问题。即在给定的约束条件下，判定该问题实例是否有解。它的难度在于，在有解的情况下要找出一个解，但是不能用近似算法求解。利用分支定界法可有效地解决此问题。结 论随着科学技术的日益进步，计算机的应用与推广也有着日新月异的变化，而其在课程编排领域的应用也达到了一定的深度，由于计算机具有运算快，处理能力强的特点，课程的编排问题也有了更好的解决方案计算机编排。于是排课算法得以研究与延伸，一种好的算法能够快速、高效地得到满足约束条件的可行性结果。从而使教务人员从繁杂的排课任务中解脱出来，并对推动教学的发展有非常重要的作用。在本文中介绍了PBIL算法，案例注入式遗传算法、混合型模拟退火算法、分支定界算法的原理和实现方法，并对存在的优缺点做了分析与比较，其中PBIL算法是一种进化算法，以学习为手段，用概率作指导，通过多次计算比较并参考目标函数的收敛性求得最优解；案例注入式遗传算法通过对原有案例库的相似性搜索，然后通过复制、交叉、变异等方法实现新案例的生成；退火算法采用复杂度高者优先、循环首次适应算法、贪婪法、回溯法和松弛法等多种方法，由随机函数求得最优解；分支定界算法是一种在问题的解空间树上搜索问题的解的算法，确定上下界进行逐渐缩小搜索实现最优解。参考文献1 张春梅，行 飞用自适应的遗传算法求解大学课程表安排问题J内蒙古大学学报(自然科学版)，2002，33(4)：459-4642 Baluja SGenetic Algorithms and Ex