文档介绍：应用混合遗传算法求解高校排课问题摘要:单纯利用直接启发式算法和遗传算法求解排课问题存在着不能获取全局最(近)优解和收敛速度慢等缺点。为了解决问题,将直接启发式算法和基本遗传算法相结合形成了混合遗传算法,并提出了简单直观的二维时空数组编码和块交叉算子,使得交叉和变异只产生少量课元冲突,而且形成的冲突容易消解。实验表明,该算法能快速得到全局近优解。关键词:排课;混合遗传算法;直接启发式算法;时空片;课元中图分类号:TP18排课问题是一个多目标优化问题,S·Even等人证明了排课是一个NP完全问题。求解排课问题的方法目前主要有两类:模拟手工排课的直接启发式算法和各种改进的遗传算法。直接启发式算法的特点是简单、直接、快速,往往根据具体问题获得启发性知识,算法通用性通常较差,但能快速得到较好的解。然而,不能保证直接启发式算法求出的解是最优解。遗传算法提供了一种求解复杂优化系统的通用框架,具有很强的鲁棒性。使用遗传算法求解排课问题可可以获得全局最优解,但存在收敛速度慢的问题。实验证明,采用直接启发式算法与改进的遗传算法相结合的混合遗传算法以较快获得全局最优解。1排课问题描述目前高校排课问题具有以下特征:每学期一个班级要上多门课程,每个班级上课的教室不固定,一门课程由一个或多个教师教授,一个教师可以上一门或多门课程。每门课程根据学时总数决定每周授课的次数和每次授课的节数。为了描述方便,将每次授课涉及的元素(课程,班级列表,教师,周学时)称作课元,将一周内可供授课的时间划分为时间片,最小的时间片为一节课,将(时间片,教室)组成的有序对称为时空片。对同一个教室的时空片,若其时间片连续,则将这组时空片称为时空片簇。所以排课的任务就是要为所有的课元安排合理的时空片簇。求解排课问题就是要在满足全部硬约束条件的情况下,为所有课元按照每门课程课时总数的要求,为其分配互不相交的时空片簇,从而获得问题的可行解,即一张满意的课表。一个解如果满足所有约束条件,则此解为最优解,但实际上并不是所有的约束都能得到满足,因此为了表示解的满意程度,引入以下两个函数。将所有约束条件依次编号为1,2,…,z,并根据这些条件的重要程度为其赋予相应的权重wi≥0(1≤i≤s)。设解为t,定义函数f(i,t)=w1x1+w2x2+…+wsxs表示课元i在可行解t中的满意度。其中xj(1≤j≤s)表示在解t中对课元i的安排是否违反了第j个约束条件,若违反xj=0,否则xj=1。设课元集合为C,定义函数O(t)=∑i?Cf(i,t)为可行解t的满意度。对于多个可行解,如果某个解的满意度最高,则这个解就是要求解的最优解。所以取maxO(t)作为目标函数。使用启发式算法求解,就是求取尽可能使O(t)达到较大值的可行解t。(icAlgorithm,GA)是模拟自然选择和遗传的一种随机搜索算法。该算法的最初目的是研究自然系统的自适应行为,由密执安大学的JohnHolland提出。遗传算法是一种迭代算法,它模拟自然的遗传和进化,最初随机生成一组解,然后在这组解的基础上进行多次迭代,每次迭代时通过遗传和进化操作产生一组新的解,使用目标函数对生成的每个解进行评价。这一过程不断重复,直至达到某种形式上的收敛。新的一组解不但可以有选择地保留一些目标函数值高的旧解,而且可以包括