基于遗传算法的高校排课系统.doc

基于遗传算法的高校排课系统 1?基于遗传算法排课系统的问题背景：? ??随着近几年各个高校的合并与扩招，我国的综合性大学和各个高校中在校的学生数量的大大增加，对于高校教务部门来说，排课工作是非常令人头痛的事，经常会出现课程排列冲突，比如：一个教师在同一时间上两门课，有两个教师同时去一个教室上不同的课程，一些公共课程需要几个班合上(如计算机基础课)，一些英语的基础课程必需安排在拥多媒体的语音室进行教学，有些教师在特定时间不可以上课等。如果没有很好地解决这些冲突，必将产生教学混乱等现象。可见，排课算法的正确性、高效性是非常关键的。? 2?遗传算法用生物学在计算机科学中的描述：? 在生物系统中，进化被认为是一种成功的自适应方法，具有很好的健壮性遗传算法有哪些信誉好的足球投注网站的假设空间中，可以如下描述遗传算法。? ??遗传算法（GA）是一种受生物进化启发的学习方法，它不再是从一般到特殊或从简单到复杂地有哪些信誉好的足球投注网站假设，而是通过变异和重组当前已知的最好假设来生成后续的假设,每一步，更新被称为当前群体的一组假设，方法是使用当前适应度最高的假设的后代替代群体的某个部分? ??这个过程形成了假设的生成测试的柱状有哪些信誉好的足球投注网站，其中若干个最佳当前假设的变体最有可能在下一步被考虑?? 3?遗传算法一般共同结构及流程：? 首先产生一个初始种群，然后对这个种群中的每一个个体进行适应度计算，适应度即表示了个体对环境的适应程度。计算后的个体进行是否满足优化准则判定，如果满足，那么算法找到了这个个体并停止，如果不满足准则，那么算法将对这个种群进行选择、复制、交叉、变异操作，遗传操作的目的是从初始种群中筛选出较优异的个体进行演变，这其中包括复制优秀个体重生、两个父个体进行交叉和单个个体的变异这三种方式，对演变后的子代群体，重新进行优化准则判定，如此循环下去，直到找到一个最优个体，或者达到其它循环条件为止。其基本结构如图? ?以下是遗传算法的伪代码。 ?Void?yichuan() ?{? Int?I=0 //循环参数? Initialize?P(i)??//先产生一个新的种群? Infitness(i)??//计算种群适应度? While?(?not?Terminate-Condition) ?{? Reprodureperator?C(I);?//?选择操作? Crossoverperator?C(I);//交叉操作? Mutationperator?C(I);?//变异操作? Infitness(i)//再次计算机种群适应度? I++??//?循环函数加一?? }? }??????选择操作(Reprodureperator)? 交叉操作(Crossoverperator)? 变异操作(Mutationperator)??L={l1，l2，…，lp，…，lP}；班级集合：C?=?{c1，c2，…，cm，…，cM}?；教室集合：R?=?{r1，r2，…，rn，…，rN}?；教师集合：S={s1，s2，…，sk，…，sK}?；时间集合：T={t1，t2，…，td，…，tD}；①?同一时间，一个教师不能同时有一门以上的课程，记为R1：R1≤1，其中：k=1，…，K；d=1，…，D0=1?教师sk?在时间td?和教室rn?上课程lp；0则否。? ②?同一时间，一个班级不能同时有一门以上的课程，记为R2：R2≤1，其中：m=1，…，M；d=1，…，D0=1班级cm?在时间td?上教师sk?的课程lp；0则否。? ③?同一时间，一个教室不能同时有一门以上的课，记为R3：R3≤1，其中：?n?=?1，…，N；d?=?1?，…，D0=1教室rn在时间td由教师sk上课程lp；0则否。?? ? ? 5?排课系统中的遗传基因及应用：? 排课过程：? 1、产生遗传因子：产生初始的因子序列。? 2、对因子序列进行杂交：将产生的两个因子序列充分杂交。?3、对杂交后的因子序列优化、筛选，产生最优课程解。?? 排课的过程中，首先产生一个以时间、教室、课程、班级为基数的课程因子，如用字符串0000?0000?0000?0000基因来表示一组初始因子，即第0号时间段，在0号教室，上0号课程，上课的班级为0号班级。用1111?1111?1111?1111基因来表示另一组初始因子，即第n号时间段，在n号教室，上n号课程，上课的班级为n号班级。? 利用这两个初始因子，开始进行杂交，然后产生一系列的课程因子。利用优化函数对课程因子进行筛选，再重新杂交，直到得到满意的结果为止。? 在此过程中，掌握好判定因子是否达到最佳状态是关键。我们可以利用一个判定函数来进行确定。? 首先，将产生的新因子与前面因子进行比对，如果因子已经存在，则舍弃。?其次，在比对的过程中，如果发现因子之间违背了数