最新【精品】范文参考文献专业论文基于遗传算法的智能排课系统的设计和实现基于遗传算法的智能排课系统的设计和实现摘要：本文针对遗传算法后期收敛速度慢，易陷入局部最优的困境，提出了改进方案，有效解决了智能排课问题。关键词：遗传算法；排课问题；组合优化中图分类号：N945.23文献标识码：A文章编号：排课是一个比较复杂的过程，对于特殊课程的排课采取的是手动方式，而一般课程则采用自动方式。在自动排课前需要对一些参数进行初始化，课表生成后可以进行人工调整。1排课的约束条件在排课的过程中，有些硬性约束条件必须遵循：如教师、教室、课程、时间和地点均不可存在冲突；也有一些软性约束因素值得考虑，这样能使课表更加的合理和人性化，如专业课尽量安排在效率较高的时间段；尽量满足某些教师的特殊上课时间要求；同时排课也不能太零散，要尽量减少教师来校的次数；应尽量避免学生一天课程很满而另一天却整天没课的情况，学生的上课时间不能安排得太过集中；在某个时间段不做任何教学任务的安排，以便教师和学生能利用这个时间开展一些课余活动。2排课的遗传算法设计2.1遗传算法流程设计遗传算法的核心内容包括：参数编码、初始群体的设定、适应度函数的设计、遗传操作设计及控制参数设定[1]。（1）基因编码：对课程和授课教师进行组合编码，可以采用教师编号（5位）+班级编号（5位）+教室编号（4位）+课程编号（6位）+周学时（2位）+特殊要求（6位）的编码方式。（2）产生初始种群：首先把固定教学时间段的教师编码填入对应的时间段中，然后产生一个1～20的随机数，根据产生的随机数在相应的位置填入该班的其他教师编码。若填入的位置已有数据，则重新产生随机数，直到所有的教师编码无重复地填入数组。如此循环直至产生满足种群规模数量的个体，组成初始种群。可以看出，上述方式产生的。（3）冲突检测：初始种群个体含有大量的冲突[4]，由于我们在编码已经考虑到时间、班级、教室避免同时上一门以上课程的冲突，因此，只需对同一时间，同一个教师同时上一门以上课程的冲突进行检测和消除。（4）冲突消除[5]：读取第一个课程表二维数组KCB(BJS，20)中第一个数据（教师编号）。将读取的数据与KCB数组中该列下一行的数据进行比较，若一致，则选择该行随机列的数据，若可以调整，则互换这两个数据；若不可调整则再次对该行随机列的数据进行选取，直到数据互不相同。取该列第三行数据，重复操作至该列所有数据互不相同为止。读取KCB（1，2），重复以上过程，直至每列数据互不相同，则冲突消除。该算法的对提高遗传算法处理效率有明显效果。（5）构造适应度函数：构造函数f(1)：考察多个教学时间段课程尽量分散度；函数f(2)：教师每天授课任务均衡度；函数f(3)：学生课时分布均衡度；函数f(4)：课程安排时间适宜性。得到适应度函数为：其中，k(i)为权值。（6）遗传算子选择算子：模拟生物界中的优胜劣汰的自然选择过程，采用赌盘法（如图2所示），将适应度高的个体放在轮盘较大区域，适应度低的放在轮盘的较小区域，则选择适应度高个体的几率会明显增大，从而筛选出适应度较高的个体[6]。图1赌盘选择法交叉算子：选择父本个体后随机选出两个个体，随机确定一个数作为交叉位置进行互换操作，如两父本个体F1、F2，位置为左起第6位，则：父本：F1=123456789F2=987654321产生子代：P1=123454789P2=987656321变异算子：在染色体上随机选择两点，将对应数据进行反转，如：325321257变异为325123257（7）参数设置种群规模，不宜过大也不宜过小。过小减弱群体多样性，可能不存在最优解；过大则会增加计算量，降低算法的运算速度。交叉率，交叉概率取值过大时，会近亲繁殖，失去活力；过小对系统不利。一般认为取值在0.6～0.9之间，本系统取0.7。变异率，变异概率较大时，会使遗传算法变成随机搜索；当变异概率较小时，新个体的产生会少。进化迭代数，为了使最终结果既收敛又能达到最优，那么遗传代数的取值应该足够大，本文遗传代数取值为1000。3实例测试及分析本系统利用Matlab7.6进行了模拟测试，用到的数据如表1所示：表1实验数据（1）种群规模选取三个对照组进行实验：表2种群规模对排课效率的影响(单位：秒)由表2可以看出，种群的规模越小，时间越短，效率也就越高。(2)交叉概率表3交叉概率对排课效率的影响(单位：秒)从表3中观察到，交叉概率的取值较大时，它对系统效率的影响则较小。经过反复分析，本系统Pc取值为0.7。（3）变异概率表4变异概率对排课效率的影响从表4看出，过大会使算法的稳定性低，过小又会使得全局搜索难以进行，并且很难有较好的模式产生。基于