《排课模型的算法分析与设计.doc》由会员分享，可在线阅读，更多相关《排课模型的算法分析与设计.doc（4页珍藏版）》请在三一文库上搜索。
1、排课模型的算法分析与设计王鹏飞 王 腾(浙江广厦建设职业技术学院，浙江 东阳 322100)摘 要：排课模型中的算法运用遗传算法和禁忌搜索算法，能提高遗传算法的局部搜索能力，根据遗传算法和禁忌搜索算法自身的特点，通过分析两者的优势和不足，给出一种将两者混合使用的排课算法。关键词：排课 JESS 遗传算法 禁忌搜索算法Analysis and Design of Algorithm of Course SchedulingWang Pengfei Wang Teng (Computer & electric engineering Institute, Guangsha College of A
2、pplied Construction Technology, Dongyang 322100, China)Abstract：Course scheduling algorithm is composed by genetic algorithm and tabu search algorithmGenetic algorithm and tabu search algorithm are powerful tools to solve the complicated large-scale optimization problemsThrough comprehensive contras
3、t and comparison between the above two algorithms，a hybrid optimization algorithm was proposed to improve the local search ability of genetic algorithmKey words：Course Scheduling; JESS; genetic algorithm; tabu search algorithm1 引 言计算机排课是把排课问题化为计算领域的有约束的时空组合优化问题进行求解的。它对课表上的时间进行了分片和编号处理，使分成的每个时间片和每个教室
4、空间组合，构建了一个个大小不等的时空组合块，并根据求解规则，对每个开课计划进行时空组合块分配，而且分配的组合必须在目标空间中表现出良好的人为满意度。2 遗传算法排课遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。由于其具有健壮性，特别适合于处理传统搜索算法解决不好的复杂的和非线性问题。以遗传算法为核心的进化算法已与模糊系统理论、人工神经网络等一起成为计算智能研究中的热点，受到许多学科的共同关注。基本遗传算法可定义为一个8元组：(，)式中：个体编码的方法；：个体适应度评价函数； ：初始群体； ：群体大小；：选择算子； ：交叉算子； ：变异算子； ：遗传运算终止
5、条件。根据遗传算法，设计出适应排课问题的排课算法。2.1 个体编码方法根据遗传算法和排课问题的特点，给出个体编码的方法如下：每个授课事件称为一个基因；每个授课事件用一个自然数表示；授课事件的全排列作为个体编码。2.2 遗传排课的设计输入：课程数据、教师数据、班级数据、教室数据、时段数据(数据来自事实库)。输出：课表(课表由授课事件组成)。具体如下：根据课程门数(假设为M)依次生成M个授课事件，并把课程ID依次放入授课事件相应的字段位；将与课程ID对应的教师ID和班级ID对应的放入授课事件相应的字段位；随机的将教室ID和时段ID放入授课事件相应的字段位；根据规则惩罚参数和规则奖励参数计算授课事件
6、(基因)的适应值；根据授课事件(基因)的适应值计算课表(个体)的适应值；重复上述五步，生成N个授课事件(个体),生成的初始群体规模为N；如果适应值达到指定的适应值，或达到指定的遗传次数，则跳转到最后一步；根据授课事件(基因)适应值大小计算选择概率Ps、交叉概率Pc和变异概率Pm；以选择概率Ps进行选择，以交叉概率Pc进行交叉，以变异概率Pm进行变异；重新计算出授课事件(基因)的适应值；根据适应值的大小选择出最优课表(个体)。3 禁忌搜索排课3.1 禁忌搜索算法的流程图1 禁忌搜索算法的流程 简单TS算法的基本思想是：给定一个当前解(初始解)和一种邻域，然后在当前解的邻域中确定若干候选解；若最佳
7、候选解对应的目标值优于“best so far”状态，则忽视其禁忌特性，用其替代当前解和“best so far”状态，并将相应的对象加入禁忌表，同时修改禁忌表中各对象的任期；若不存在上述候选解，则在候选解中选择非禁忌的最佳状态为新的当前解，而无视它与当前解的优劣，同时将相应的对象加入禁忌表，并修改禁忌表中各对象的任期；如此重复上述迭代搜索过程，直至满足停止准则。禁忌搜索算法的流程如图1所示。邻域函数、禁忌对象、禁忌表和藐视准则，构成了禁忌搜索算法的关键。其中，邻域函数沿用局部邻域搜索的思想，用于实现邻域搜索；禁忌表和禁忌对象的设置，体现了算法避免迂回搜索的特点；藐视准则，则是对优良状态的奖励
8、，它是对禁忌策略的一种放松。需要指出的是，上述算法仅是一种简单的禁忌搜索框架，对各关键环节复杂和多样化的设计则可构造出各种禁忌搜索算法。同时，算法流程中的禁忌对象，可以是搜索状态，也可以是特定搜索操作，甚至是搜索目标值等。同时，与传统的优化算法相比，TS算法的主要特点是：在搜索过程中可以接受劣解，因此具有较强的“爬山”能力；新解不是在当前解的邻域中随机产生，而或是优于“best so far”的解，或是非禁忌的最佳解，因此选取优良解的概率远远大于其他解。所以TS算法是一种局部搜索能力很强的全局迭代寻优算法。3.2 禁忌搜索排课的设计输入：课程数据、教师数据、班级数据、教室数据、时段数据(数据来
9、自事实库)；输出：课表(课表由授课事件组成)。具体步骤如下：设定算法参数，运用与遗传算法中生成个体的方法产生初始解集，随机选取初始解x，置禁忌表为空；判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继续以下步骤；利用当前解的邻域函数产生其若干邻域解，并从中确定若干候选解；对候选解判断藐视准则是否满足？若成立，则用满足藐视准则的最佳状态y替代x成为新的当前解，即x = y，并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用y替换“best so far”状态，然后转最后一步；否则，继续以下步骤；判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对应的最佳状态为新的
10、当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素；转上述第二步骤。4 混合算法排课GA和TS算法是两种十分有效的全局搜索算法，前者源于生物遗传学，模拟自然界生物的优胜劣汰、适者生存的过程，后者模拟一种智力过程。这两种算法都与问题无关，通用性与优化性较好，能处理复杂、大规模优化问题，但并不是对所有问题都适用。调用TS算法过于频繁，计算量大；而不调用TS算法又易早熟(群体中的个体过早地收敛到某点附近，不能使搜索转向解空间的其他区域)，产生局部最优解。4.1 遗传禁忌混合排课的策略禁忌搜索算法对于求解混合最优问题COP(Combinatorial Optimization Probl
11、ems)是非常有效的，它在邻域中重复地搜索准则，快速而高效地向好的方向移动。但它存在一个问题，即在算法中必须调整不同的参数，从这点看禁忌搜索没有很好的鲁棒性，因为参数的选取对最后得到的解有着直接的影响。由于遗传算法只需调整群体的几个参数而不是单个的解，因而遗传算法是禁忌搜索方法的一个补充。GATS算法中GA和TS的混合结构如图2所示：图2 GATS算法中GA和TS的混合结构此混合结构就是将遗传算法中的交叉和变异操作产生的新个体(多个)，看作是禁忌搜索法中当前解Xn的邻域V(Xn)，然后搜索V(Xn)中的每一个个体。文中GATS算法可以从邻域V(Xn)中选择多个解，只要选择出的这些解都能通过GA
12、TS算法的禁忌结构的筛选即可，这正体现了遗传算法是基于群体而不是个体进行演变的这一重要特征。图2中，若将TS模块去掉，则整个结构为典型的遗传算法结构。GA模块的作用相当于构造了禁忌搜索法的邻域结构，为其提供了较好的初始解。这种混合结构由于融入了禁忌搜索的思想，使得那些只有通过禁忌检验的个体才能真正地被作为新的个体所接收，一方面使得那些有效基因缺失、但适应值不高于其父代的个体被禁忌掉，另一方面也使得那些包含有有效基因、但适应值较低的个体有更多的机会参加交叉和变异，从而延缓或避免了早熟收敛的发生，也提高了遗传算法的爬山能力。4.2 评测实例和结果图3 遗传算法和混合算法排课结果比较 实例如下所示：
13、实例1：64门课程、12位教师、16个教室；实例2：100门课程、21位教师、25个教室；实例3：150门课程、26位教师、31个教室；实例4：200门课程、33位教师、37个教室。对于以上4个实例，分别进行时段数为20、15和12的测试；根据文献把交叉概率设为0.75，变异概率设为0.3，最大迭代次数T设为20000，初始群体N设为300。根据实例结果，比较见图3。5 结 语首先给出基于遗传算法的排课，接着给出基于禁忌搜索的排课算法，随后分析说明两种算法的优缺点，最后给出结合遗传算法和禁忌搜索算法混合的排课算法。实验结果表明，该算法在计算速度方面有显著提高。参考文献：1周建新，王科俊，王文武课表编排专家系统J计算机应用，2000，（5）.2胡小兵，鲁宏伟基于模糊专家系统的排课系统关键技术的研究J长沙电力学院学报，2001，16(4).3王凤鸣，许方大学课程表编排方法分析J南阳师范学院学报，2005，4(3).4谢凡荣求解排课表问题的一个启发式数值算法J运筹与管理，2005，14(5). 责任编辑：程 娟4