用混合进化法解决大学课程表问题

1、用混合进化法解决大学排课表问题123Salwani Abdullah, Edmund K. Burke, and Barry McCollum摘要进化法结合局部搜索为许多排课表问题提供了最优解。 本文描述的是一种大学课程表算法的延伸。这个问题与大学课程如何分配教室和时间有关。若要得出可行方案，就要满足大量的必要约束条件。而方案质量高低要由罚值来衡量，罚值代表了满足非必要约束条件的程度。混合进化算法通过建立数据集，对比文献资料中具有艺术性的运算技巧的方式进行测试。得到的结果证明：混合进化法可以用来制作课表方案，而且能够对文献中的基本问题给出一些最低罚值。因此，结论是混合进化算法是一种可以生成高质

2、量大学课表方案的极其有效的研究方法。I 引言（绪论）在制表过程中，大多关注的是如何自动生成时间表结构问题，期间应用了各种技术包括模拟退火算法（如【 1,2,3 】），禁忌搜索法（如【 4】），和遗传算法 ( 如【 5】 ) 。其中一个有限解决排课表问题的方法就是局部搜索的混合算法 （也称文化基因算法） 。本文结构如下： 第二部分论述排课表问题和解决排课问题的各种方法梗概。第三部分是联系其他算法概述进化法。下一章描述了我们的混合进化算法和排课问题中的实际应用。第五章是实验操作结果，最后对高水准解决方案间的比较做总结性的评论。II. 大学排课表问题这个问题是在一系列必要和非必要约束条件下，如何把课

3、程安排到适合的时间和教室里。必要条1件即完全要求， 满足此条件的方案为可行性方案。以下将以 【 8】必要约束条件来检测我们的混合进化法。任意学生不能同时上两节课教室容积需满足该课程要求上课的学生数量小于等于该教室容积特定时间内每个教室只能上一节课下面是【 8】必要约束条件：一个学生有一节课安排在某天最后一个时间内一个学生有两节以上连续的课一个学生一天只有一节课设定的基本问题是：1N一组课程记作 e=e e 45 个时间段R型教室一组F 型教室一组学生 M一组问题解决的目标是在满足必要约束条件下最小化不必要约束条件的扰乱性影响。尽管此模式缺乏现实生活的许多实例和限制条件【9】，但我们还是要在此基

4、础上和其他最高水准的算法作对比。近年来一些关于上述问题的论文已经出现在文献上202 年， Socha et al. 提出了解决以上11 个问题的蚁群法，这些问题最初在Paechter的大学课程表安排生产机制中提出，后来在国际启发式网络提出aullah et al.发明了一种多样化相邻搜索法，用固定的禁值删除特定相邻结构。2005年， Asmuni etAl. 又提出了这一问题解决方案的模糊概念法。在（14）中 Socha etAl. 建立蚁群算法并首次运用到本文讨论的数据中。Rossi-Doricaet al.引用同样的数据提出大量元启发式比较法。Burke et al.引进了禁止搜索启发式算

5、法并结合护士花名册编排方法运用到大学排课系统中。本论文旨在系统解决不同的问题而非特指时间表。Burke et al.也曾引用启发2式图表的禁止搜索算法，而且在大学考试和课程安排的基本点中都得到了运用，那么，这又对处理不同问题的一般性提出了更高要求。 Paechter 的生成结构也与以上数据有关， 但他解决问题的方法只是为了参加 2002 年举行的课程表竞赛。对这些数据的调查报告不在本论文论述范围之内，而且对那些仅适用以上数据合在其他地方不适用的方法论也不在本文之列。III 混合进化算法在此论述的混合法（即遗传算法和局部搜索结合）在各种文献中有其他的说法例如：基因算法，混合基因算法， ，基因搜索

6、算法【 8】在【 679】同样能找到大量解决大学时间表的方法案例。描述的方法是用基因算法解决大学排课系统，其中先用两个进化算符（一个轻罚值变量，另一个重罚值变量）然后用“爬山”算法计算，最后一组真实的考试数据上检测质量，可结果显示与单独使用进化算符方案要优于前一种。这采用了一种运用几种变量的基因算法解决排课问题，实验表明在方案中使用独立变量和相连变量能够极大地提高运算效率。在（19）里，作者引入了把分解法和进化法综合在一起的多层次进化算法。检验这一方法的实效性要使用真实数据。实验的结果是这个方法可以用来完善方案质量，并用来减少搜索最佳方案的时间。对此感兴趣的读者可以在（ 18,20 ）中找到更

7、多有关混合进化算法的更多扩展内容。对于用来解决时间表问题的基因算法概论可以再（ 21）中找到。IV. 混合进化算法在大学排课系统中的运用我们在进化算法中使用的主要技巧是：先用一个轻变量，再用随机性反复式算法。其中不包括交叉算符。A. 方案描述如下直观描述：每个基因包含某一课程的时间和地点信息，表1 是基因集合： C1是第一节课， CN是课程最大值，记作i （ 1， N）例如课程C1安排在第5 时段的 2 号教室；3B. 第一代运算结构算法用来生成大量随机可行方案。先由空白表格创立，这类似于随机标图法（见22），然后通过增减适合必要条件下的课程来创建可行性方案，并用类似轮盘循环的方法为下一代集合

8、群选择算符，由于刚开始测试，循环代定位100.C. 进化算符：变异对 20%的课程我们将从选出的 20%的下一代算符中随机运算轻变量， 选择的百分比数建立在初试基础上，然后在任意点上随机选课并分配到下一组最早排课的时间段内，表2 中是变量运算的虚拟算符。D. 随机性反复式发展运算（ 12）讨论的方法用到了本地搜索算符中，在变量运算结束后使用。方案越优化，运算会变得越容易，但不排除特殊情况下产生的不理想方案。在这里要注意制表过程中，必要条件是不易受干扰的，以下要论述的是如何进行本地化搜索。假设有 K 组相邻单元可放入方案，记作 TempSol（ i ）可以连续表示为I（ 1， k）， TempS

9、ol（ i ）中最好的方案Sol * 跟现在正在使用中的方4案 记作 Sol （ best ）对比，如果方案质量得到了完善，那么就采用新的方案Sol *但是要用蒙特指数？接受度标准，如果随机生成的数量介于（0,1 ）之间，小于e- ， 是新方案和老方案之间的差异度（如 =f （Sol *）-f （ Sol ） ），运算一直到生成最终的标准终止（这里终止标准定于 200000，见 12）随机性反复式运算虚拟编码详见于图3E运算图表 4 和图表 5 展示了原理图和虚拟编码。注意进化法中不使用交叉算符，这种算符会给方案生成增加难度（如会修复新一代算符）包含在这里面的数据可以用到我们的方法中，运算开始

10、，先建立一个大小为100 的集合，接着连续生成几代运算，在这过程中会从前一集合中选出20%的算符，然后，从以上算符中随机选出20%的课程作变量，最后运用本地搜索法，这样可以保留运算得出的最佳方案，把这些准方案保存在集合群里，也可能会被选取到下一代并用轮盘旋转的方法得出新一轮的运算符，直到运算进行到原定的循环代数量（在实验中此数值定为30）或时间表罚值为零，这时运算终止。注意这里的参数由最初的实验设定。5VI. 实验第 IV 部分描述的方法用的是微软MicrosoftVisualC+第 6 版本， Athlon处理器 1.2GHz256MB RAM ，运行 5 此之后可以得到最佳方案，20000

11、0 次运算最多用10 小时来运算每个数据组，注意制作课表通常会困扰制表人好几个月，在现实的例子中花费10 小时制作出解决方案已经相当完美了。这是一个课表安排问题，花费的时间并非重点。表1 中是测试此运算的大量标准示例。6表 2 是混合进化法与其他文献资料中可行性方法比较，如本地搜索法对比蚁群算法（8），禁止搜索下的大启发式算法，图表启发，模糊算法，禁止条件下的大量相邻搜索用的是反式相邻结构随机反复运算（26），表 2 中 术语“ x% Inf.”表示不包含可行性方案的运算百分比；“ Ave. ”表示不运算的平均结果； “ Best ”代表运算最佳结果，见表中用粗体；7说明：M1：我们的混合进化

12、算法M2：随机反复运算法结合相邻算法（作者Abdullah et al.， 2005【 12】）M3:多种相邻搜索（作者Abdullah et al.， 2005 【26】）M4：本地搜索法（作者Socha et al.，2002 【 8】）M5：蚁群算法（作者Socha et al.， 2002【 8】）M6：禁止搜索式大启发运算（作者Burke et al.， 2003【 4】）M7：大启发式图表标注法（作者Burke et al.， 2006【 16】）M8：模糊算法（作者Asmuni et al.， 2005【 13】）VII.结论混合进化法优于10 个限制条件下的局部搜索法；优于 7

13、 个限制条件下的蚁群算法（它的每一个问题都只能绑定运算5 个数据库），而且比 (4) 和（ 16）或其他有大量数据库的方法获得的优质方案更多，和（ 26）相比：对处理大型数据库和全部中型数库都有更好的优势，并能包含所有的小型数据库，最有趣的是把本文的运算结果和（12）中的作比较发现，混合进化算法更好的处理了大型和全部中型数据还有包括小型数据，这表明遗传算符和局部搜索结合后会产生一个比只用它们各自运算的方法功能强大的多的结果，混合进化算法除了三个数据在其他所有数据库操作上是全部文献方法中产生的方案最好的，在此注意 （14,15 ）描述的方法所用数据虽然相同，但并没有给出运算的大量结果，所以我们无法进行直接对比