1、2023.7电脑编程技巧与维护1概述排课问题是中学教学管理中非常重要的一环。好的排课方案符合学生注意力和记忆规律，能够提高学生学习效率，有助于教师提高课堂效率、做好整体规划；反之，如果排课不恰当，则面临反复调课，从而造成教学管理秩序混乱、学生无所适从的严重后果。近年来，国内外学者将遗传算法应用于中学或大学的排课问题上，取得了较好的效果。文献4和7提出了一种交叉、变异概率随适应度自适应变化的改进遗传算法，种群中高适应度的个体（个体适应度大于平均值）随适应度升高，交叉、变异操作的概率降低，从而最大限度地保留优秀个体；文献5将混沌思想引入到遗传算法中，通过混沌的随机性、规律性、遍历性等特点，提高收敛
2、速度；文献6中对高中排课系统具体实现给出详细的描述，使用十进制字符编码进行数据存储，并指出在排课问题中直接进行两个个体之间随机交叉操作，将会导致大量的教师与课程冲突，他们采用在同一个体、同一班级、不同时段课程交叉互换的方式进行操作；文献8中提出了一种分布式遗传算法，在原始遗传算法基础上增加了组间突变，通过一定概率的组间染色体互换来避免过早收敛到局部最优解。当前研究很多聚焦于大学排课问题，而中学排课问题与大学排课问题存在明显差异，例如，教室固定、班级学生固定等情况，部分改进策略并不适用于中学排课问题。在此通过对遗传算法的交叉、变异操作进行改进，使之在更短的时间内形成相对更优的排课方案。2中学排课
3、问题中学排课方案往往受多种复杂因素影响，因此，要使得排课方案尽可能合理，应反复协调多种约束条件，得出一种符合绝大多数条件的方案。约束条件主要分为硬约束条件和软约束条件两种。硬约束条件是指必须满足的硬性条件，具体如下：（1）同一时间同一班级只能上一门课。（2）同一时间同一教师只能上一门课。（3）每门课每周的课时数应符合要求。（4）在各学科每周固定的进修、教研时间不能排课。软约束条件是指一定程度上需要满足的条件，可使得排课方案更加合理，具体如下：（1）在每天精力集中的时段尽量安排统考科目。（2）同一学科尽量避免在同一天内多次授课，在一周中均匀分布。（3）尽量在多门统考科目中间穿插非统考科目。排课系
4、统主要根据以上约束条件来评定一个排课方案的好坏，并进行优化迭代得到最优解的近似解。3适应度函数与遗传操作的设计3.1适应度函数适应度函数指判定当前种群满足约束条件程度的判定函数，是衡量当前组合方案好坏的重要标准。如何设定适应度函数，决定了算法最终结果是否足够逼近最优解。在此排课系统主要考虑学科节次优度与学科均匀程度两个方面。其中，学科节次优度决定了如何将每天精力集中的时段分给统考科目，故将其权值设定为0.7；学科均匀程度使得同一学科在一周内尽量均匀地分布，权值设定为0.3。适应度函数定义如公式（1）所示：f=0.7f1+0.3f2（1）其中，f1为排课方案的学科节次优度的评定值；f2为学科均匀
5、程度的评定值。学科节次优度4是根据学生每天注意力的集中程度及学科自身属性共同设定的，因此将公式设定为各节次作者简介：刘志华（1997），男，本科，中学二级教师，研究方向为中学信息技术教学。改进遗传算法在中学排课问题中的研究刘志华（北京市和平街第一中学，北京100013）摘要：中学排课问题受学科多、课时满、教师任教班级交叉等因素影响，存在难度大、复杂度高等问题，目前主要依靠软件生成与后期人工调整，仍存在耗时久、效果不明显的问题。为更好地解决这一问题，选用遗传算法进行研究，并针对这一问题对算法的交叉、变异操作进行改进，旨在通过迭代进化的方式得出较优的排课方案。对比实验结果显示，改进后的算法在同等条
6、件下更加接近最优解，执行效率有了较大提升，较好地解决了中学排课问题。关键词：遗传算法；中学排课系统；人工智能35DOI:10.16184/prg.2023.07.0032023.7电脑编程技巧与维护两者的乘积之和（中学每周节次固定，无需取均值），如公式（2）所示：（2）其中，ti为该节课的节次权值；si为节课的学科权值；n为每周授课总节次数。每天中学生注意力集中程度分布如下：上午的最后两节课（第4、5节）、下午的最后一节课（第8节）学生较为疲惫、注意力集中程度较差；下午的第一节课（第6节）学生较容易犯困、上课效率较低；其余节次（第1、2、3、7节）效果较好。因此将各节次权值设定为3、3、3、2
7、、1、1、2、1。学科权值主要根据是否为统考科目进行划分，统考科目一般学业要求较高，更适合安排在精力集中时段，因此将语数英3科的权值设定为5；将史地政理化生6科权值设定为3；其余非统考科目权值设定为1。学科均匀程度指同一学科两节课之间的间隔时间，间隔时间较短容易使学生难以消化、效率降低；间隔时间过长容易使学生忘记之前所学，不利于之后内容的讲解，尤其是学生目前处于基础教育阶段，不宜间隔过久。因此，将均匀程度权值设定为同一天为0、相邻两天为1，间隔一天为1.5、间隔2天及以上为0.5。将同一天权值设定为0可以最大限度地避免同一天同一学科多次授课，将间隔2天及以上设定为0.5可以最大限度地避免周课时
8、为1的非统考科目对学科均匀程度造成影响。学科均匀程度将公式设定为各节次学科自身权值与该学科总均匀程度值的乘积之和，如公式（3）所示：（3）其中，ki为该学科一周的课时数；uj为同一学科相邻两节课的均匀程度值，相邻两节课的均匀程度值可由两节课所在的天数相减得出。虽然历史、地理等学科与语文、数学等学科课时数相差较多，但相邻两节课的均匀程度值较大，因此二者总均匀程度类似，选取总均匀程度作为评定标准更为合理。3.2选择操作选择操作类似于生物繁殖过程，在当前种群中选出一部分优秀的个体繁殖出下一代，使优良基因在种群繁衍过程中得以保留。上文提到的适应度值正是判断个体是否优秀的判别标准，适应度值越高，被选择的
9、概率就越大。个体被选择的概率如公式（4）所示：（4）其中，N为种群规模；fi为单个个体的适应度。在此选用选择操作中常用的轮盘赌选择策略，先根据个体被选择概率计算累计概率，相邻两个个体的累计概率之间的区域即为后者的轮盘区域，再生成与种群规模N相等数量的随机数，根据随机数落入的轮盘区域选取要进入下一代的个体。该操作具有随机性，可能会导致优秀个体丢失，因此引入精英选择策略，每次选取最优的个体直接晋级，在一定程度上提升结果的优良性。3.3交叉操作交叉操作是将两个个体的一部分随机基因相互交换，产生一对新的个体。由于排课方案的特殊性，直接对应基因交叉会导致两个个体的各学科课时数异常。例如，一个个体某一节次
10、的语文课与另一个个体的对应节次的数学课交换，会导致前者的课表中数学课时增加、语文课时减少，而后者与之相反，违反了硬性约束条件中课时数的要求。为解决交叉操作在排课过程中遇到的这种问题，在此给出一种创新性的方法，即在两个个体基因交换的基础上，分别从自身课程表中进行一次对应交换。以图1为例（图1中数字表示该节课的授课教师编号），当交叉点的2和1交换后，分别从本体中随机选择一个1和2改为对应值，从而保证在基因交叉过程中两个个体自身的各学科课时数保持不变。在这一方法在实现过程中，应注意满足硬性约束条件。在交叉操作之前，应先判断该教师是否在同一时间的另一个班有另一节课。如果两个个体的交叉点上有任何一个不满
11、足交换条件，则该交叉点的课不能交换，需要重新随机选择另一个交叉点；如果交叉点都满足，则分别从本体中随机选择对应交换点进行替换。本体对应交换点同样面临该问题，如果不满足交换条件，则更换新的对应交换点即可。如果本体中对应交换点全部都不满足交换条件，则说明本体中无法通过自我协调满足该交叉操作，此时将对应交换点选取为交叉点的位置，在原地进行两轮交叉（即数值保持不变）。交叉流程如图2所示。图1交叉后本体对应交换示意图362023.7电脑编程技巧与维护受教师任教班级数量大、学科课时多等因素影响，并不是任意两个个体都可以完成交叉操作，存在两个个体中每个节点都无法完成交叉的情况。此时交叉操作可将交叉点与本体对
12、应交换点设置为同一位置，交叉操作退化为交叉点互换完后再次互换，从而保证在无法交叉情况下运算的正确性。3.4变异操作变异操作类似于生物的基因突变，某个或某些基因发生更改，产生新的特征。因为排课问题的特殊性，需要保证各学科课时数不变，所以在某处突变后，应调整对应区域，使其突变合理化。在此提出一种随机选取翻转点进行整体基因翻转的方案，变异前后翻转示意图如图3所示。由于该操作是将单个个体（排课方案）中全部班级课表分别进行翻转，该操作并不影响排课方案的正确性，不会产生任何冲突。4实现效果交叉概率与变异概率分别取0.7和0.1。采用Python语言对提出的改进遗传算法进行实现，并结合工作实际对某年级3个班
13、、13个学科、17名教师，以种群规模20、迭代轮数10 000进行了多次的实验。整体效果较好，多次实验的结果均逼近理论上最优值801.75，如图4所示。由于学科节次优度与学科均匀程度两项评定指标可能存在相互冲突的情况，且不存在两者同时达到最优的情况，因此实验最优值可能会略小于理论最优值。5结语通过改进遗传算法中的交叉、变异操作，较好地解决了中学排课难问题，能够在较短的时间内给出一个优化的排课方案。通过与前人研究对比，验证了算法的有效性，在结果优度小幅度提升的基础上，大大缩短了运行时间，使排课过程更加高效。参考文献1李德毅.人工智能导论M.北京:中国科学技术出版社,2018.2马永杰,云文霞.遗
14、传算法研究进展J.计算机应用研究,2012,29(4):1201-1206.3刘萍,俞焕.一种改进的自适应遗传算法J.舰船电子工程,2021,41(6):101-104.4马小姝,李芙蓉.基于改进遗传算法排课系统应用研究J.青岛大学学报（工程技术版）,2020,35(3):15-20.5SUN G M,LI Y H.Research and analysis of course ar-rangement based on genetic algorithm J.Journal ofPhysics:Conference Series,2020,1650(3).6康婷婷,牟莉.基于混沌遗传算法的排
15、课问题的研究J.电子设计工程,2021,29(18):30-34.7LI W T,LIU B T,XIAO H,et al.Research on appli-cation of genetic algorithm in high school course ar-rangement system J.World scientific research jour-nal,2021,7(5).8N G A P H SAPTARINI,SUASNAWA I W,P I CIP-TAYANI.Senior high school course scheduling usinggenetic algorithm J.Journal of Physics:ConferenceSeries,2018,953(1).图2交叉过程图3变异前后翻转示意图图4改进算法实验值与理论最优值的对比开始交叉操作随机选取交叉点否交叉点同时满足交叉条件？交叉点是否全部不满足条件？否是随机选取本体中对应交换点否否是对应交换点同时满足交叉条件？对应交换点是否全部不满足条件？是是完成交叉操作交叉点、对应交换点设定为同一位置适应度802800798796794792790次数02468实验值理论最优值37
