多约束条件下的大学考试移除

多约束条件下的大学考试移除

1硬约束条件的约束大学考试时间自然响应问题是一个多才多艺的优化问题。以往的方法包括遗传统计法和模拟退火法。这些方法通常存在两个问题:首先求解时间表问题最优解的时间复杂性是时间表规模的指数级,优化过程计算量很大;再者,不同学校、不同制度下对考试安排的约束要求都不一样,不同对象对时间表优劣评价也不同,花费了巨大代价的全局寻优得到的权衡解并不一定理想,仅仅靠一个把所有约束综合起来的适应值函数经常不能明确反映出孰优孰劣。甚至在寻优操作过程中有时会破坏了硬约束条件而得到了不可行解。考试时间表的约束条件通常分为必须要满足的硬约束条件和尽量要满足的软约束条件。该文中的硬约束是同一学生选读的课程不能在同一时间考试、同一个教师任教的课程必须在同一时间考试。软约束条件是每个学生的几门课程的考试时间间隔大一些平均一些,利于学生复习。在此校方希望整个考试周天数尽量缩短,而学生希望考试课程时间间隔大一些,便于复习。该文从实际出发,对基于图着色模型得到的满足硬约束并且考试周长度尽可能短的初始解,用非常适合的分组遗传算法在不破坏硬约束条件的基础上进行优化。在不延长考试周的基础上扩大了学生的复习时间,协调了校方和学生要求之间的矛盾关系。2考试总总控制公式(1)的数学模型中c表示整个考试安排的代价,它趋向最大也就是使学生总的复习时间最大。T代表总的考试时间段,该文中一天只有一个时间段考试,那么T就代表考试周的天数;M代表总的考试课程数;npq表示同时参加考试p和q的学生人数;dst表示时间段s和t的距离,即学生的复习时间;yps表示p考试安排到s时间段;yqt表示q考试安排到t时间段。公式(2)表示一门考试q只安排在一个时间段t:公式(3)表示安排在时间段t中的所有考试总数小于校方规定的一个固定的最大值:公式(4)中如果s=t那就代表同一学生参加考试的两门课程安排在一个时间段,违反了硬约束条件,是不可行解,这时dst就取一个很大的负值。只有当s≠t时才是可行解。3根据组ga的计算时间，优化算法3.1熔喷非织造布的编码遗传算法常用的编码方法有二进制编码和实数编码。采用实数编码,即将其真实值作为变量的编码。将一个变量的编码按一定顺序连接在一起,形成个体编码串。解码时只需将染色体各个基因座上的基因值按序赋给相应的变量即可。在这里每个满足硬约束条件的初始解即为一个染色体,对于染色体的编码有传统的直接编码和改进分组编码两种方法。传统的染色体直接编码是:基因是考试课程,基因的值是时间,见表1。因为是基于图着色算法得出的初始解所以以颜色代表考试时间段,该文中一天只有一场考试,考试周天数和考试时间段数是一致的。A、B等字母代表考试课程名称。这样的编码方式有以下几个缺点:(1)染色体长度长,如果以某高校实际情况为例,大约有80多门不同课程考试,那么染色体的基因位数就是课程的门数有80多位。(2)带来冗余。表2的染色体跟表1染色体比较虽然基因C和D(见表2中黑体所示)的位置交换了,变成另外的一条染色体,但其实和表1所示的染色体是一样的。如果以学校实际情况为例,大约有80多门不同课程考试,安排在12天,这样的编码带来的冗余将会是惊人的。(3)根据优生的观点,父母亲代的染色体差异大容易产生优秀的后代,若用两个实际上是冗余一致的染色体交叉很可能产生很差的后代。(4)变异操作容易破坏解的硬约束条件如表2所示,如果G、K两门课是同一个任课教师,要安排在同一天考,那当课程H和课程G变异互换时破坏了硬约束条件,使这个染色体成为一个非法染色体。因此采用的是改进后的编码,即分组着色编码:分组着色问题是分组问题大家庭中一员,Falkenauer定义分组问题为将一系列实体按照硬约束条件分成互相独立无关联的子集组。装箱问题、任务分配、媒体循环等都可以认为是分组问题。图着色问题中有边连接的点分成不同组。每一组中的点都是无边连接的。分组编码有两个优点:(1)组的数量少。分组编码对应的染色体中每个组(色)是一个基因,值是考试课程,这样实际的编码长度即为考试周的天数,大约十几天。染色体基因的位数就是十几位,比传统编码少很多。(2)交叉、变易操作是不会破坏硬约束条件。3.2夯实班级考试时间的间隔不同班级的学生考试课程的门数不一样,所以人均理论复习时间X=考试周总天数/人均考试课程。例如:某个学生正考课程是4门,考试周总天数是12天,则他每门课的理论复习时间是X=考试总天数/人均考试课程=12天/4门=3天/门。若一个学生4门考试课程分别安排在第1、3、4、6天,则实际的复习时间也就是时间间隔距离分别为:3-1=2天、4-3=1天、6-4=2天(第一门课的复习时间默认很充足,不计算在内)。这个班级考试时间总的间隔个数为n=3。实际的复习时间与理论复习时间的标准方差为:则适配值函数f即为所有班级标准方差的平均值:公式(5)中的f趋向最小就意味着实际复习时间更接近理论复习时间;m代表班级数;n代表每个班级考试时间总的间隔个数;Di代表第i个间隔数,即复习时间;X代表人均理论复习时间。3.3子代染色体交叉操作寻找邻居的结论有两种移动“考试移动”和“时间段移动”对应于传统染色体编码的考试移动会打乱颜色的分组,破坏硬约束条件,放弃。应于改进后分组编码的染色体的时间段移动可以分以下几种:随机两个时间段交换、选一个序列(例如起点2,长度4)移动、选中一个序列颠倒、序列重排、循环移动。先采用循环移动产生若干种群,每个种群内再采用随机交换产生新解。以表3染色体为实例,考试安排在6天,则循环产生初始种群中有6个个体:以表3的实例为初始解,班级编号与考试课程对应关系如表4所示。考试如安排6天则循环移动产生包括6个个体的初始种群,个体1见表5。见表3的实例,红色代表第1天,黄色代表第2天,绿色代表第3天,蓝色代表第4天,紫色代表第5天,褐色代表第6天。理论复习时间为6天/3门=2天/门。用公式(5)计算得出适配值函数f=1.034。循环移动得到个体2,见表6:其中黄色代表第1天,绿色代表第2天,蓝色代表第3天,紫色代表第4天,褐色代表第5天,红色代表第6天。对应的每个班级复习时间如表7所示,用公式(5)同样可以计算出适配值函数。以此类推得到个体3、4、5、6。复制操作该文采用的是直接计算每个染色体的适配值,按适配值大小采用末位淘汰复制,直接淘汰f最大的个体,若f相同则随机淘汰其中之一。交叉操作该文采用的是实值重组,首先随机选取两个交叉点,并把这两个交叉点之间的区域定义为匹配区域,将交叉部分分别接在染色体后面,再删除前面重复的颜色,使两个子代染色体合法化。变异操作设计较简单,随机选2个基因位交换,因为采取分组编码方案,不会产生非法染色体。3.4多系统优化转变步骤1基于图着色模型得出初始可行解;步骤2循换产生初始种群,个体数目与考试周总天数一致(即如果考试周总天数是12天,则初始种群中有12个个体);步骤3计算每个个体的适应度,并判断是否符合优化准则,若符合,输出最佳个体及其代表的最优解,并结束计算,否则转向步骤4;步骤4依据适配值选择再生个体,淘汰适配值高的个体;步骤5交叉生成新的个体;步骤6变异生成新的个体;步骤7由交叉和变异产生新一代的种群,返回到步骤3。4夯实班级学生初始安排优化实验是在vf6.0中编译的程序,共有34个班级(人数忽略)参与实验,每个班级最少的考2门,最多的考6门,共计115门课程,安排在12天考试。图1和图2中分别用黄、红、蓝等颜色表示一个班级几门课程考试的安排时间,它们的间隔距离也就代表了学生的复习时间,图1是初始安排的时间表,很明显可以看出复习时间非常不平均,例如班级编号为1的班级三门课程考试时间安排分别为第2、11、12天。图2是优化后的时间表明显比图1中的初始安排平均分布,班级编号为1的班级三门课程考试时间安排分别为第3、8、11天,比初始安排明显均匀,其他班级考试安排的点间隔也明显比图1均匀。图3和图4是每个班级实际平均复习时间(图中用红色点表示)与理论复习时间(图中用蓝色点表示)的比较,图3初始安排中代表实际复习时间的红点大都在理论复习时间蓝点的下方,说明总的来说实际平均复习时间少于理论复习时间的居多。优化后实际平均复习时间大于初始安排中的实际复习时间,见图4中,实际平均复习时间比优化前更接近理论复习时间,红色的点平均分布于理论值的上下方,尤其是在考试门数大于等于4门的班级(图4中,班级编号大于25的几个班级)与理论值基本重合。初始安排时间表中实际复习时间与理论复习时间的标准方差即目标函数f为3.57,优化后减小至2.43,在寻优的过程中出现的最大f为3.9。5分组遗传算法寻优思想符合临床应用需求分组遗传算法非常适合某高校考试安排的实际应用,在不增加考试周总天数的条件下平均且扩大了学生的复习时间