【基于蚁群遗传算法的实验教学排课优化策略】遗传算法 精英策略
[摘要] 随着高等教育事业的发展，实验教学体系的完善，如何利用现有的各种技术实现实验教学课表编排的自动化、科学化和合理化，提高资源利用率以及教师和学生对课表的满意度是目前高校教学管理工作函待解决的问题之一。
[关键词] 蚁群算法 遗传算法 蚁群遗传算法 排课问题
一、引言
目前，使用蚁群算法或者遗传算法解决实验教学排课问题已经成为众多学者和高校的研究热点。由于实验教学的特殊性，利用单一智能算法在求解速度和求精解效率上往往很难同时兼顾，所以排出的课表时有冲突。
二、实验教学排课问题描述
1.涉及元素
从概念模型上讲，实验教学排课是一个五维空间上的组合优化求解问题。五维分别指教师、班级、课程、时间和实验室，约束条件为教学计划和各个实验室的特殊要求，如图1所示。
2.排课问题优化目标分析
实验教学课程表问题主要考虑的是对给定的课程安排适当的教学资源，使学校课程整体达到一个较为合理的状态。而使课程安排目标达到最优效果的排课结果，主要体现在课程的时间均匀、实验室利用率高等上，实现此结果关键在于如何解决排课过程中众多约束和有效目标函数的建立。
3.约束条件
实验室排课过程中的约束条件分为四类：基本约束、硬约束、软约束、特殊约束。在四类约束条件之中，前两者是衡量排课方案是否切实可行的标准，软约束是衡量排课方案优劣的标准，通常反映一个排课方案的优劣标准有多种情况。
基本约束：同一时间内，同一位教师不得在两个不同的实验室上课；同一时间内，同一个学生不得上两门不同的课程；同一时间内，同一间实验室不得上两门不同的课程；
硬约束：实验室能够容纳上实验课班级的所有学生；特定课程对应特定类型实验室；实验课程所需软硬件必须与实验室所配备的软硬件环境相对应；实验课程安排在上午和下午四个时间段，每个课程占用一个时间段；某些教师、班级、实验室在特定时间不能排课；
软约束：同一班级连续两个时间更换实验室地点的距离不宜过远；教师不宜连续上课；教师对上课时间、实验室有特殊要求，应尽量满足；尽量选择设备好的实验室上课：各课程表课时尽量均匀分布。
4.排课问题的数学模型
实验教学课表编排过程中涉及的实体集合有：课程、班级、教师、实验室、时间，设定如下集合。
课程集合：L= ，Li表示第i门课程。
班级集合：C= ，Ci表示第i个班级。
教师集合：T= ，Ti表示第i位教师。
时间集合：Q= ，Qi表示第i个时间段。
实验室集合：R= ，Ri表示第i个实验室。
实际上每个排课结果就是（L、C、T、Q、R）的集合，时间与实验室的笛卡尔积为：
其中课程是关键实体，其他实体都与其有关。课程包括如下属性：
其中h�i为周学时，c�i表示该课程的上课班级，可以为多个班级。t�i为该课程的任课教师，可以为多个教师。q�i为该课程的上课时间，如果一周安排多次则为多个时间。r�i为该课程的上课实验室，每个时间唯一对应一个上课实验室。在以上的5个元组中，前3个为已知元组，后2个为待求元组。
三、蚁群与遗传算法融合优化策略
1.蚁群算法
自然界中蚁群能通过相互协作找到从巢穴到食物的最短路径，并且能随环境变化而变化，如突然出现障碍物时，还是能很快地重新找到最短路径。根据仿生学家长期研究发现：蚂蚁在寻找食物的行进过程中会沿途留下一种挥发性物质――信息素，其他蚂蚁能根据这种物质浓度的大小选择路径前进，并且沿途又留下这种信息素，使得这条路径上的信息素浓度不断增加，从而会吸引更多的蚂蚁沿此路前进。在一段时间后，较短路径上信息素由于挥发的少，同时访问的蚂蚁多，使其浓度远远超过较长路径上的信息素，此过程持续进行直到所有蚂蚁都选择最短路径。
2.遗传算法
与传统搜索算法不同，遗传算法是从一组随机产生的初始解开始搜索整个过程的。种群中的每个个体是问题的一个解，称为“染色体”。这些染色体在后续迭代中不断进化，称为遗传。在每一代中用适应度来衡量染色体的好坏。生成的下一代染色体称为后代，后代是由前一代染色体通过交叉或者变异运算形成的。新一代形成中，根据适应度的大小选择、淘汰部分后代，从而保持种群大小的稳定性。适应度高的染色体被选中的概率高，这样，经过若干代之后，算法收敛于最好的染色体，它很可能就成为问题的最优解或次优解。
3.蚁群遗传融合算法
在求解各种问题的特殊性和复杂性上，蚁群算法、遗传算法都有各自的优点和缺陷。
蚁群算法的优缺点：其是一种正反馈机制、是一个增强型学习系统，融入了人类的智能，易于与其他优化算法融合。但蚁群算法在解决大型优化问题时，在搜索空间和时间性能上容易产生矛盾，易于出现过早收敛于非全局最优解以及求解速度较慢。
遗传算法的优缺点：具有全局搜索能力，与问题领域无关；具有潜在的并行性，可进行多值比较，鲁棒性强；计算过程简单，能很好地解决开发最优解和探寻搜索空间的矛盾，具有可扩展性，易与其它算法结合。但遗传算法对于系统中的反馈信息利用不够，当求解到一定范围时往往会做大量的无效迭代，求精确解效率低。
基于蚁群算法和遗传算法的融合，其基本思想是采用蚁群算法寻找最佳空间，采用遗传算法寻找空间中最好方案。同时汲取两种算法的优点，克服各自的缺陷，优势互补。从而在优化排课问题时，在时间效率上优于蚁群算法，在求精解效率上优于遗传算法。
（1）编码
采用Holland的二进制编码方法，以矩阵A来表示一个染色体，每个染色体就是一个排课方案。行值代表时间P，列值代表所有授课任务D。
（2）适应度函数
适应度值按照实验教学排课的约束条件分为三类：基本适应度（用Fitness_B表示）主适应度（用Fitness_M表示）和副适应度（用Fitness_S表示）。基本适应度用来记录基本约束，主适应度用来记录硬性冲突，冲突越大，该值越大；因此，当此值为0时，不存在硬性冲突，该染色体可作为一个待选排课方案；副适应度用来记录软性约束。
（3）选择操作
选择操作的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙，这是借用了达尔文适者生存的进化原则。
选择操作的方法较多，本文采用适应度排序法复制最优染色体，用轮盘赌的方法去选择染色体。与基本遗传算法选择步骤中的排序法有所不同，在该方法中，个体的选择概率与其轮盘值成比例。得到选择概率公式为：
其中：p�i为选择概率；i为染色体序号；w�i为个体i的转盘值wheel；N为染色体群体数。
（4）交叉操作
交叉，是遗传算法中最主要的一种操作。复制操作虽然能够从旧种群中选择出优秀者，但不能创造新的染色体，因此，遗传算法的开创者提出了交换操作，它模拟生物进化过程中的繁殖现象，通过两个染色体的交换组合，来产生新的优良品种。
普通的遗传算法直接从上一代中选取两个染色体进行交叉，这样可能因为局部收敛而得不到较优解。要推动染色体不断进化，其交叉操作必然要符合一定的规则。若将两个染色体随机按列交换，必然破坏授课任务的合理性。
本文采用行值交叉的方式，以避免任何数据的破坏。先随机选择要交叉的某行，然后依次比较两个父个体此行对应的每个元素。如果两个父个体相对应元素都不为0，则在各自父个体中交换对应的课程对象的位置；如果两父个体相对应元素有为0的情况，则保持位置不变。交叉算子的主要作用是调整选课学生人数和实验室座位数之间的冲突。
（5）变异操作
变异，虽然以很小的概率发生，但它用来模拟生物在自然遗传环境中由于各种偶然因素引起的基因突变。通过变异操作，可确保种群中遗传基因类型的多样性，使搜索能在尽可能大的空间中进行，避免丢失搜索中有用的遗传信息而陷入局部次优解，从而有效抑制遗传算法早熟现象发生。这里，先对选中的个体，随机选择某两行，然后在选中的各行中再随机选择某一元素进行交换，这样就把某一门课程的某一次课调换到不同的时间――实验室中，从概率上讲，能达到变异目的。
四、效果评价
为验证蚁群遗传融合算法在实际排课策略优化中的效果，分别利用基本遗传算法和蚁群遗传算法进行模拟实验。
假设种群数量为250、遗传迭代数为250，交叉概率为0.9，变异概率为0.01。当授课任务数为57、80、135时，二种算法各测20组数据取平均值，得到的平均运行时间实验结果如表1所示：
五、结束语
采用蚁群算法寻找最佳空间，遗传算法寻找空间中最好方案的办法，来克服遗传算法过早收敛于某一区间，而无法找到最优解的弊端的思想。利用理论联系实际的方法，提出了把蚁群算法融入到遗传算法中的蚁群遗传混合智能算法。通过建立蚁群遗传算法优化的目标空间，利用遗传算法的快速性、随机性、全局收敛性，产生有关问题的初始信息素分布。然后，在有一定初始信息素分布的情况下，对排课问题进行染色体编码以及选择、交叉、变异等遗传算子的设计。在交叉环节，利用蚁群算法的并行性、正反馈机制以及求解效率高等特性，来判断区间内遗留的信息素的强弱，从信息素强的区间内，以最大概率选择最优染色体。最后通过变异染色体，使适应度值达到指定要求，从而以最快速度得到排课结果的最优解。利用此算法产生的实验教学排课方案各门课程时间段分布均匀，基本满足学校实际应用需求。
参考文献：
[1]李明杰.课表编排系统的算法分析与设计[J].计算机工程与设计，2004.
[2]段海滨.蚁群算法原理及其应用[M].北京：科学出版社，2005.
[3]王凌.群智能优化算法及其应用[M].北京：清华大学出版社，2001.
[4]黄敏.基于遗传算法的排课系统研究[D].重庆大学工程硕士学位论文，2008.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文