排课算法分析

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

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

3、加演化 的时间。5作为解决方法，可采用一种惩罚方法，并将此惩罚体现在适应度值函数中，这样一个约束优 化问题就转化为一个附带考虑代价或惩罚的非约束问题。也就是说，如果适应度值函数的某 些变量需要满足约束条件，则需要在演化时对前面的适应度函数作修改，加入惩罚函数，形 成广义的目标函数，从而使遗传算法在惩罚函数的作用下找到问题的最优解。5 TOC o 1-5 h z HYPERLINK l bookmark10 o Current Document 广义目标函数可定义为F3) = f 3)+的3)5其中，。 0程为惩罚因子，它的大小表明了对解的可行性要求的严格程度；中(x)为惩罚函数。5对于约束极大

4、化问题，惩罚函数可取5平(x) = 0, x可行平(X) 0程为惩罚因子，它的大小表明了对解的可行性要求的严格程度；中(x)为惩罚函数。对于约束极大化问题，惩罚函数可取平(x) = 0, x可行平(x) 0,其它问题转化: 由于本论文是用遗传算法解决排课问题，因此首先要将排课问题转化为遗传算法问题，它们 之间的关系如下：基因(gene):由一个时间编号或教室编号构成，分别称为时间基因和教室基因：染色体(C):由一个时间基因和一个教室基因构成“时间一教室”基因对，每个“时间一 教室“基因与一门待排课程对应;再由这些基因对链接组成染色体，即一种排课方法；适应度评价函数(E ):使用惩罚函数；初始种

5、群(P o)：随机生成若干排课方法(染色体)组成：选择算子()：使用轮盘赌选择方法；交叉算子()：使用单点交叉算子；变异算子(平)：使用基于基因的变异；终止条件(T ):当最大适应度函数值为1时终止。将一门待排课程的时间编号、教室编号对应作为染色体的一个时间一教室基因对，实现 从表现型(时间教室对)到基因型(基因)的映射即编码工作。解码操作是指将染色体还原为一门一门的课程。它实际上贯穿了整个遗传操作过程，因 为每一次进行染色体的适应度计算时，都涉及到对各课程所占用的时间教室段进行冲突检 测，这时就需要将染色体解码为整型的时间、教室编号。算法模型：遗传算法类似于自然进化，通过作用于染色体上的基因

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

7、一个二进制串很难表示 出这两种信息，因此，需要一种新的编码方式来表示遗传基因。我们采用了一种叫做布尔矩 阵5的表示方法来对课表基因进行编码，这个布尔矩阵表示对课程的分配方式。矩阵横坐标 为时间，纵坐标为教学班级，其中0表示没有安排，1表示安排。遗传算法的基本操作：在遗传算法中，主要的遗传算子是选择，交叉，和变异。选择算子选择策略对算法性能起到举足轻重的作用，不同的选择策略将导致不同的选择压力。较大的 选择压力使最优个体具有较高的复制数目，从而使得算法的收敛速度较快，但容易出现过早 收敛现象。相对而言，较小的选择压力一般能使群体保持足够的多样性，从而增加了算法收 敛到全局最优的概率，但算法收敛速

8、度较慢，本论文采用轮盘赌式选择。设群体中个体数量为N，令丈f表示群体的适应度值之总和，f.表示群体中第i个染色体 i=1的适应度值，它产生后代的能力正好为其适应度值所占份额上fi=1将一个圆盘分成N份，第i个扇形的中心角为遗传算法中采用轮盘赌式选择的结果是某个个体或几个个体的适应度一旦超过其它个体适 应度的平均值，就会出现强者恒强，弱者恒弱的现象。轮盘赌式选择遵循了达尔文生物进化论中的物竞天择，汰弱留强的原则。交叉操作选择的效果提高了群体的平均适应值，但是损失群体的多样性，最好个体的适应值将无 法得到改进。因此，遗传算法效仿生物的自然进化，两个同源染色体通过交配而重组，产生 新的染色体的方法，形成交叉算法。交叉运算是产生新个体的主要方法，它决定了遗传算法 的全局搜索能力。代表个体的矩阵在行和列的方向上均有相应的约束，两个个体在某个随机选择的交叉点 实行交叉，生成的子个体很有可能不再满足约束条件。课表中，每个个体需要遵循的规则是 周课次数是固定的（指定值），无论是交叉还是变异都不能违背该规则。因此，我们设计的交 叉操作必须要考虑这个因素，我们用单点交叉的方法随机选择一个行的位置作为交叉点，交 叉后生成的个体满足行方向的约束，但是列方向的约束将打破，因此交叉以后，要判别约束。变异算子变异算子的基本功能是对群体中的个体串的某些基因值做变动。一般来说，变异算