基于改进遗传算法的排课问题研究

范明杰 怀丽波

摘 要：针对遗传算法在解决排课问题中易陷入局部最优解的缺陷.提出一种改进的遗传算法。在传统遗传算法基础之上.融合模拟退火思想.使交叉得到的子代以一定概率进入下一代.并对传统的基于概率的计算方法进行改进.编排出优质的课表。实验结果表明改进算法不仅加快了前期进化速度.而且解决了遗传算法后期易陷入局部最优解的缺陷。

关键词：遗传算法;排课;模拟退火。

中图分类号：TP301.6

文献标志码：A

0 引言

排课问题是一个多目标、多约束的优化决策问题，是一个NP组合优化问题r。由于排课的这些特点，排课是教务管理工作中的一个难点。目前我国高校所使用的排课系统大部分只面向于课表编排、解决课程表编排过程中的资源冲突，而没有充分考虑资源分配的优化问题，完全用计算机实现排课的所有过程。

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的仿生算法[2]。是一种通过模拟自然进化过程搜索最优解的方法。其主要特点是群体搜索策略和种群中个体之间的信息交换，具有优越的全局搜索能力以及很强的健壮性。适合维数较高、环境复杂、问题结构不十分清楚的场合[3]。实践证明，遗传算法对于组合优化中NP完全问题非常有效[4]。但遗传算法也存在一些缺陷，如存在易收敛到局部最优解的早熟现象等。

1 相关问题简述

1.1 排课问题

在排课问题中，我们的主要任务是将班级、老师、课程、教室安排在一周内某一不发生冲突的时间。在排课过程中必须严格遵守以下硬约束条件：

（1）在某一时间段对某一教师，最多只能为其安排一门课程的教学任务;

（2）在某一时间段对某一班级，最多只能为其安排一门课程;

（3）在某一时间段对某一教室，最多只能安排一门课程;

此外，排课还有一些软约束条件，在2.2节会详细说明。

1.2 遗传算法

遺传算法由J.H.Holland教授的学生J.D.Bagley在1967年首先提出[5]，1975年Holland教授出版了第一本系统论述遗传算法的专著《自然界和人工系统的自适应性》（ Adaptation in Naturaland Artificial Systems）[6]，标志着遗传算法正式诞生。遗传算法是一种模拟生物进化机制的随机搜索算法。其基本思想为：以初始种群为起点，根据种群中每个个体对环境的适应度施加特定操作，实现优胜劣汰的进化过程。通过多代的进化，使其解逐步逼近最优解[7-8]。算法步骤[9]如下：

1）初始化第一代种群。

2）进入繁衍期，进行交叉和变异操作，评估已知染色体适应度，按照适应度进行染色体选择，形成下一代。

3）不断繁衍，直至进化终止条件成立。

遗传算法不需要计算目标函数的导数和梯度，也不要求目标函数具有连续性，并且算法具有内在的隐含并行性和全局寻优能力[10]。目前，遗传算法已被广泛应用于数值优化、组合优化、机器学习、图像识别、神经网络和模糊控制等众多领域。

2 改进遗传算法排课研究

2.1编码

本次研究中，用一个基因表示一个课元，即一个班级（可能是合班级）的一门课程的所有课次的教师、时间序列和教室安排。基因的构成为：课程号十班级序列十教师号十教室号十时间序列。其中课程号，班级序列（合班级则有多个班级号，否则仅有一个班级号），教师号在教学计划中已经给出，教室号和时间号由排课系统产生。染色体是由基因组成的串，一条染色体即为一种排课方案。

2.2 适应度函数

一个好的排课方案应该尽量满足一些人为制定的软约束条件。在本次研究中主要考虑如下软约束条件：

2.3 遗传操作

2.3.1 选择

选择采用轮盘赌选择法，具体步骤为：首先根据种群中个体的适应度不同，将整个种群分布在轮盘上。然后对每个个体的概率进行累积，所有个体的概率和为100%，每个个体占其中的一个百分比段，个体的适应度越大，在轮盘上占的比例就越大。选择时系统随机产生一个O～1的百分数，该数落在哪个个体的百分比段，就选择哪个个体，这种选择法对适应度高的个体选种的机会相对就多，也就是实现了优胜劣汰，同时也存在着选择适应度小的个体的可能性，这样又保证了群体的多样性，使保留在较差个体中的优秀基因段有机会得以保存[11]。

2.3.2 交叉

交叉算法流程如下：

Stepl：根据种群各个个体适应度，运用轮盘赌选择法选出双亲Pl，P2。

Step2：依次更新子代child每一个课元的教室号。更新child某个课元教室号cr_no的策略为：从Pl，P2随机选取一个父代P，取出P的对应课元的教室号，赋给cr_no。

Step3：求出子代每一个课元的时间分配优先度。课元的时间号分配优先度一课元班级的周总学时十课元教师的周总教学课时十课元教室的周总课时。

Step4：更新子代未分配时间且时间分配优先度最高课元的时间序列ti_list。更新策略为：从Pl，P2随机选取一个父代P，取出P的对应课元的时间序列，赋给ti_list。

Step5：进行冲突检查，如果发生冲突，执行Step6，否则执行Step7。

Step6：进行冲突处理，处理成功执行Step7，否则执行Stepl。

Step7：判断子代是否存在未分配时间的课元。是则执行Step4，否则执行Step8。

Step8：求child的适应度，比较Pl，P2适应度，优先度最高的父亲记为P _best。求出两代个体的适应度差值△f=fitness（P__best）-fitness（ child）。

Step9：计算child进入种群下一代的概率Pc。

Stepl0：取随机数r=rand （0，1），如果r

冲突检查：传统遗传算法在有约束的组合优化算法中有一定缺点，比如变异新个体以及随机交叉产生的新个体很可能是无意义的个体[12]，表现在本研究中即为产生冲突课元，因此必须进行冲突检查。冲突检查分为时间冲突检查和教室冲突检查。时间冲突检查：更新某个课元时间片为T后，若该课元的班级或者教师在T时间已经安排课程，则发生时间冲突，否则不发生时间冲突。教室冲突检查：更新某个课元时间片为T后，若该课元的教室在T时间已经安排课程，则发生教室冲突，否则不发生教室冲突。

冲突处理分为时间冲突处理和教室冲突处理。

时间冲突处理算法如下：

Stepl：生成l-dch·wcd随机排列的乱序时间序列RTI，dch为一天能安排的最大学时，wcd为一周上课的天数。

Step2：取出RTI的第一个未使用的时间片，赋给冲突课元的冲突时间片T。

Step3：对更新的课元进行冲突检查。若新课元不发生冲突，输出时间冲突处理成功，算法结束。否则执行Step4。

Step4：检查RTI是否存在未取出的时间片。是则执行Step2，否则输出时间冲突处理失败。

教室冲突处理算法中需要计算某个教室的更换概率。计算方法如下

Pcr—update（cr）=cr_hour（cr）/WH

（8）

其中，cr_hour （cr）为求出教室cr的周安排课时。WH为一周能安排的最大课时。

教室冲突处理算法如下：

Stepl：判断冲突课元的教室cr是否为指定安排教室。是则执行Step7。否则执行Step2.

Step2：计算cr所有同类型教室的更换概率。根据这些教室的更换概率，建立教室选择轮盘。

Step3：计算cr的教室更换概率Pcr。取0～1随机数r，若r≤Pcr，则执行Step4.否则执行Step7。

Step4：检测轮盘是否为空。是则返回处理失败，算法结束。否则轮盘赌选择出新的教室new一cr，将new_cr从教师选择轮盘上去除，并把new一cr赋给cr。

Step5：对新课元进行冲突检查。发生冲突则执行Step6，否则输出处理成功，算法结束。

Step6：判断冲突类型。若为时间冲突，执行Step7，否则执行Step3。

Step7：进行时间冲突處理。返回时间冲突处理结果。

交叉结果的确定：交叉获得的子代进入种群下一代的概率计算方法是本文算法改进的核心。设交叉的得到的子代child进入种群下一代的概率为Pc，并规定双亲中最优个体P_best进入下一代的概率Pp =1- Pc。求出两代适应度差值△，一fitness （P__best）-fitness（ child）.

在传统的遗传算法中，Pc=1;

其中g为当前进化代数，gturn为（0，1）的一个设定常数。gmax为最大进化代数。

改进算法不仅在进化前期能够明显加快进化速度，而且在进化后期提高了全局搜索能力，能够较好地解决遗传算法易陷入局部最优解的缺点。

2.3.3 变异

变异操作能够改善算法的局部搜索能力和维持种群多样性，分为教室变异和时间变异。

具体流程如下：

3 实验结果及分析

为了验证算法的有效性，以延边大学5栋教学楼、工学院的5个班级、28个教师、55门课程、20个教室进行仿真实验。种群规模取20，模拟退火温度T = Tmax* 0.96generation，Tmax为最高退火温度，取Tmax =1000，generation，为迭代代数。令gturn=0.3，gmax =400。实验结果如下：

表一给出了三种算法在不同进化次数下适应度的比较，图3给出了三种算法适应度曲线的比较图。

图3中的曲线给出了三种算法种群中最优适应度随进化代数的增加的变化趋势。可见，在前120代，原混合算法和改进混合算法最优适应度增长速度明显快于传统遗传算法。120代左右，传统遗传算法和原混合算法均陷入局部最优解，改进混合算法最优适应度仍呈现良好的增长趋势。

4 结论及展望

通过实验结果，可以看出改进算法不仅加快了遗传算法前期进化速度，而且解决了遗传算法后期易陷入局部最优解的缺陷。但公式（10）尚存在进一步的改进空间，包括gturn合适值的自适应选取，以及△f≥0 and g≥gturn*g情况下表达式的进一步优化，从而使改进算法性能达到更优。

参考文献

[1]宗薇，高校智能排课系统算法的研究与实现[J]，计算机仿真，2011，（12）：389-392.

[2]刘勇，康立山，陈毓屏，非数值并行算法[M].北京：科学出版社，1998：150-161.

[3] 吕聪颖，智能优化方法的研究与应用[M].北京：中国水力水电出版社，2014.：28-29.

[4]肖俊，遗传算法的工程应用[J]，计算机科学，2005， （11） ：247 - 248.

[5]BAGLEY J D.The behavior of adaptive systems whichemploy genetic and correlation algorithms [D].University ofMichigan， 1967.

[6]HOLLAND J H. Adaptation in natural and artificial systems[M].MIT press， 1975.

[7] JONG K A D.An analysis of the behavior of a class ofgenetic adaptive systems [Dl. University of Michigan， 1975.

[8] GOLDBERG，D E.Genetic algorithms in search， optimiza-tion， and machine learning [M].Addison-Wesley Publishing.Co.Inc.1989.

[9]高史义，罗小华，卢宇峰，等.基于遗传算法的功能覆盖率收敛技术[J].浙江大学学报：工学版，2015，（8）：1509-1515.

[10]贺毅朝，王熙照，李文斌，等，基于遗传算法求解折扣{O-l）背包问题的研究[J].计算机学报，2016，39（ 12）：2614 -2630.

[11]陈行平，陈江，陈启华.基于遗传算法的高校排课系统设计[J].绍兴文理学院学报，2004，24（10）：25-28.

[12]刘华森，程文明，张铭奎，等，基于改进遗传算法的旅客列车席位分配组合优化[J].中国铁道科学，2016，37 （6）：113 -120.

[13]曹恒智，余先川，单亲遗传模拟退火及在组合优化问题中的应用[J].北京邮电大学学报，2008，31（3）：38- 41.

[14]刘怀春，刘怀亮，李秀焕，等.改进的混合遗传模拟退火算法及其在组合优化中的应用研究[J].现代计算机：专业版，2004，（1）：14-16，41.

[15]李敬花.余峰，樊付见，等，基于遗传模拟退火融合算法的船舶分段装配序列优化[J].计算机集成制造系统，2013，19（1）：39-45.