排课算法分析

《排课算法分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、排课算法分析:由丁•本论文的排课是针对中学课程，学牛的上课教室不变，并且一个教室只有一个班级使用，因此学牛班级教室可以看成是一个变量。约束条件5排课要遵循很多约束条件，可以分为两大类，硬约束和软约束。其中，硬约束为必须满5足的条件，而软约束是为了让排出的课表更合理、更人性化，只要尽量满足。5硬约束包括•：5教师授课时间冲突，即一个老师在一个时间段只能授一门课程5班级上课时间冲突，一个班级在一个时间段只能上一门课程5由于其他条件产生的约束条件，某些课程必须排在早上；某些课只能排在上午的3,4节或者下午，如体育课等等；这些硬性

2、规定的约束条件。5以上条件必须全部遵守，才能排出一个止确的课表。5软约束包括：5一门课程如果一周上多次课，不要在一天内安排多次，并且希望能隔开上满足教师教案的周期性，使其富有人性化5某些教师对上课时间有某些特定喜好。5适应度函数：5遗传算法靠适应度來评估和引导搜索，我们可以采用一种十分口然的的方法來考虑约朿条件，即在进化过程小，迭代一次就设法检测一下新的个体是否违背了约束条件。如果不满足约束条件，则将其作为无效个体出去。但是不满足约束条件的个体中，可能包含有前面几代的演化过程中保存下来的有效信息，如果出去，重新开始，可能造

3、成资源的浪费，增加演化的时间。5作为解决方法，对采用一种惩罚方法，并将此惩罚体现在适应度值函数中，这样一个约束优化问题就转化为一个附带考虑代价或惩罚的非约束问题。也就是说，如果适应度值苗数的某些变彊需要满足约束条件，则需要在演化时对前面的适应度函数作修改，加入惩罚函数，形成广义的目标函数，从而使遗传算法在惩罚函数的作用下找到问题的最优解。5广义目标函数可定义为尸⑴=/(*)+跑(兀)5其中，0〉0程为惩罚因子，它的大小表明了对解的可行性要求的严格程度；©(x)为惩罚函数。5对于约朿极大化问题，惩罚函数可取5(p(x)=0,

4、兀可彳亍气(p(x)<0,其它问题转化：5rh于本论文是用遗传算法解决排课问题，因此首先要将排课问题转化为遗传算法问题，它们Z间的关系如下：6基因(gene):由一个时间编号或教室编号构成，分别称为时间基因和教室基因:6染色体(C):山一个时间基因和一个教室基因构成“时间一教室”基因对，每个“时间一6教室“基因与一门待排课程对应;再由这些基因对链接组成染色体，即一种排课方法；…..…6适应度评价函数（E）:使用惩罚函数；6初始种群（P0）:随机生成若干排课方法（染色体）组成：6选择算子（①）:使用轮盘赌选择方法;6交叉算子

5、（「）:使用单点交叉算子；6变异算子（屮）：使用基于基1大I的变异；6终止条件（T）:当最大适应度函数值为1时终止。6将一门待排课程的吋间编号、教室编号对应作为染色体的一个吋间一•教室基因对，实现….6从表现型（吋I'可教室对）到基因型（基凶）的映射即编码工作。6解码操作是指将染色体还原为一门一门的课程。它实际上贯穿了整个遗传操作过程，因....6为每一次进行染色体的适应度计算时，都涉及到对各课程所占用的时间教室段进行冲突检6测，这时就需要将染色体解码为整型的时间、教室编号。6算法模型：6遗传算法类似于自然进化，通过作用于

6、染色体上的基因寻找好的染色体来求解问题。与..亠自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染6色体进行评价，并基于适应值來选择染色体，使适应性好的染色体有更多的繁殖机会。在遗6传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始群体；通6过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗6传操作，经过遗传操作后的个体集合形成下一代新的种群。对这个新种群进行下一轮进化。67遗传算法流程图7编码方法：7编码方式必须能够包含遗传信息。由于课表问

7、题的独特性，采川传统遗传算法屮的二进....7制编码并不是很适合，因为课表空间是二维的，包含星期和节次，用一个二进制串很难表示出这两种信息，因此，需要一种新的编码方式来表示遗传基因。我们采川了一种叫做布尔矩阵［5］的表示方法来对课表基因进行编码，这个布尔矩阵表示对课程的分配方式。矩阵横坐标8为时间，纵坐标为教学班级，其中0表示没有安排，1表示安排。8遗传算法的基本操作：8在遗传算法中，主要的遗传算子是选择，交叉，和变异。81.选择算子8选择策略对•算法性能起到举足轻重的作用，不同的选择策略将导致不同的选择压力。较人的选择压

8、力使最优个体具有较高的复制数目，从而使得算法的收敛速度较快，但容易出现过早收敛现彖。相对而言，较小的选择压力一般能使群体保持足够的多样性，从而增加了算法收敛到全局最优的概率，但算法收敛速度较慢，木论文采用轮盘赌式选择。8N设群体中个体数量为N,令工九农示群体的适应度值之总和，/表示群体中第i个染色体i=