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

《多种排课算法的探讨与分析文献综述》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、单位代码01学号040101172分类号密级文献综述多种排课算法的探讨与分析院（系）名称信息工程学院专业名称计算机科学与技术学生姓名指导教师2008年3月15日黄河科技学院毕业设计(文献综述)第I页多种排课算法的探讨与分析摘要课程表的编排是学校教学管理工作中不可或缺的一部分，是教学工作顺利进行的保证。由于学校教学工作的科目安排，不仅反映出学校的办学思想，也体现学校教育管理的水平，所以，科学、合理地编排各学科教师的授课时间，是不容忽视的。而如何实现课表编排的高效与快速性，是本文所要描述的内容。本文分别对PBIL算法，案例注入式遗传算法、混合型模拟退火算法、分支定界算法的背景、原理、实

2、现及存在优缺点做了分析与比较，其中PBIL算法是一种进化演绎算法，以学习为手段，用概率作指导，通过重复计算和目标函数的收敛性求得最优解；案例注入式遗传算法通过对案例库的相似搜索，然后通过学习、复制、交叉、变异实现新案例的生成；退火算法采用复杂度高者优先、循环首次适应算法、贪婪法、回溯法和松弛法等多种方法，由随机函数求得最优解；分支定界算法是一种在问题的解空间树上搜索问题的解的方法。这几种算法各有优缺点，而收敛速度和最优解是受关注的。关键词：课程表，遗传算法，分支定界算法，PBIL算法黄河科技学院毕业设计(文献综述)第I页目录1绪论12PBIL算法22.1PBIL算法描述22.2PB

3、IL算法的进化过程23案例注入式遗传算法33.1案例注入式遗传算法简介33.2案例注入式遗传算法组成结构33.3案例注入式遗传算法存在的问题44混合型模拟退火算法54.1混合型模拟退火算法简介54.2模拟退火的思想54.3混合型模拟退火算法的前景65分支定界算法75.1分支定界算法简介75.2分支定界法的思想7结论9参考文献10黄河科技学院毕业设计(文献综述)第9页1绪论随着学生人数的不断上升和社会的进步，学校的课程设置也向深度和广度发展，因此手工排课的实现相应增加了困难。然而随着科学技术的日益进步，计算机的应用越来越广泛。而且计算机具有运算快，处理能力强等特点，很自然地会应用到这

4、一领域。而且用计算机进行排课能够快速地得到满足约束条件的可行性结果，具有排课时间短、质量高和节约人力的优点，这能使教务人员从繁杂的排课任务中解脱出来，并对推动教学的发展起到非常重要的作用。所以如何用计算机实现高效的、快速的课程表编排工作，成为许多人研究的目标，而在这其中算法的分析与选择是相当重要的，是实现高效功能的关键。所以要对许多相关算法进行探讨与分析，以此找到一种高效、快速的排课算法来实现课程表的编排工作。课程表的编排，实际上就是各种方案的筛选过程[1]。而这个过程较为复杂，用人工来编排课程表，运算速度慢，筛选方案少，其结果合理程度也会大打折扣。因此可以利用计算机的优势来进行课

5、程表的编排工作。计算机编排课程表起点是用随机函数选定的，所以计算机每重复一次编排，其结果肯定不同，因此利用计算机运算速度快的优势让其在短时间内，进行多次重复，就可实现很多次的方案筛选。在具体程序设计时加入适当的检索，让计算机自动筛选出带有合理参数的方案，供决策者最后确定。也可以由计算机直接根据合理参数筛选出最后结果，如果不满意还可让计算机不停地进行筛选，直至最终得出较为满意的结果。这就是算法的应用与实现。黄河科技学院毕业设计(文献综述)第9页2PBIL算法2.1PBIL算法描述PBIL(Population-BasedIncrementalLearning)算法是一种进化演绎算法，

6、它将进化过程由原来的生物进化过程转变为一种学习过程，用学习概率来指导产生后代，完成目标功能的实现[2]。这种概率是整个进化过程信息的积累。在这样的进化过程中，在目标函数的指导下，可以得到目标函数值越来越小的解，并且用多次重复计算，可以得到多种不同的解，便于使用者从中挑选合适的解作为安排的方案。由此过程产生的结果也就更具有优化性，因此能在许多问题中获得更快的收敛速度和更好的结果。2.2PBIL算法的进化过程第1步：初始化学习概率p；第2步：由学习概率指导产生k个解；第3步：计算上一步产生的k个解的目标函数值，并从中找出一个最优解，设为B；第4步：用目标函数值中的最优解B修正学习概率P

7、；第5步：返回到第2步循环，直至满足一定的结束条件为止。由于实际问题中的每一个解，往往需要多位取值，此时若仍用二进制位表示，会造成许多不便，所以会经常使用其他类型的编码方法进行操作[3]。如任意整数编码，二维表。在课表的编排过程中会涉及多种约束条件，而求解过程就是排除约束条件间的冲突矛盾，同时要尽量合乎现实情况。这里会出现课表编排问题中的两个条件：硬约束条件和软约束条件。其中：硬约束条件是必须满足的条件，软约束条件是尽量满足的条件。课程表安排问题是组合规划中典型的优化