论文研究 故障诊断 .pdf

大学考试时间表是一个多约束条件下的优化问题。传统遗传算法寻优的计算量是指数级的规模，而寻优的操作有可能会破坏时间表的硬约束条件，从而最终得到的解并不一定理想甚至不可行。该文从某高校的实际应用出发，对用图着色模型得到的已经满足了硬约束条件的初始考试时间表，用改进的分组遗传算法在既不破坏硬约束条件也不延长考试周的条件下扩大并平均分配了学生的复习时间，并且还大大减少了寻优的计算量。2382009,45(23)Computer Engineering and Applications计算机工程与应用表5初始种群的个体1染色体34分组遗传算法的步骤班级考试课程考试时间(对应第几天)复习时间步骤1基于图着色模型得出初始可行解;红、黄、绿(1、2、3)步骤2循换产生初始种群,个体数目与考试周总天数一致黄、蓝、紫(2、4、5)(即如果考试周总天数是12天,则初始种群中有12个个体);红、黄、绿(1、2、3)34567步骤3计算每个个体的适应度,并判断是否符合优化准K蓝、紫、褐(4、5、6)红、绿、紫(1、3、5)2、2则,若符合,输出最佳个体及其代表的最优解,并结束计算,否AHI红、绿、蓝(1、3、4)2、1则转向步骤4;AHG红、绿、褐(1、3、6)2、3步骤4依据适配值选择再生个体,淘汰适配值高的个体;表6初始种群的个体2染色体步骤5交叉生成新的个体步骤6变异生成新的个体;值A DC HF BI EJ GK基因黄绿蓝紫褐红步骤7由交叉和变异产生新一代的种群,返回到步骤3。对应的每个班级复习时间如表7所示,用公式(5)同样可4实验以计算出适配值函数。优化实验是在v6.0中编译的程序,共有34个班级(人数表7个体2染色体复习时间情况忽略)参与实验,每个班级最少的考2门,最多的考6门,共计班级所选课程考试时间(对应第几天)复习时间115门课程,安排在12天考试。AFC黄、绿、蓝(1、2、3)1、1图1和图2中分别用黄、红、蓝等颜色表示一个班级几门DBE绿、紫、褐(24,5)课程考试的安排时间,它们的间隔距离也就代表了学生的复习234567黄、绿、蓝(1、2、3)时间,图1是初始安排的时间表,很明显可以看出复习时间非紫、褐、红(4、5、6)AHJ黄、蓝、褐(1、3、5)2、2常不平均,例如班级编号为1的班级三门课程考试时间安排分AHI黄、蓝、紫(1、3、4)别为第2、11、12天。图2是优化后的时间表明显比图1中的初AHG黄、蓝、红(1、3、6)2、3始安排平均分布,班级编号为1的班级三门课程考试时间安排以此类推得到个体3、4、5、6分别为第3、8、11天,比初始安排明显均匀,其他班级考试安排复制操作该文采用的是直接计算每个染色体的适配值,按的点间隔也明显比图1均匀。适配值大小采用末位淘汰复制,直接淘汰∫最大的个体,若f相图3和图4是每个班级实际平均复习时间(图中用红色点同则随机淘汰其中之表示)与理论复习时间(图中用蓝色点表示)的比较,图3初始交叉操作该文采用的是实值重组,首先随机选取两个交叉安排中代表实际复习时间的红点大都在理论复习时间蓝点,并把这两个交又点之间的区域定义为匹配区域将交又部下方,说明总的来说实际平均复习时间少于理论复习时间的居分分别接在染色体后面,再删除前而重复的颜色,使两个子代多。优化后实际平均复习时间大于初始安排中的实际复习时染色体合法化。间,见图4中,实际平均复习时间比优化前更接近理论复习时变异操作设计较简单,随机选2个基因位交换,因为采取间,红色的点平均分布于理论值的上下方,尤其是在考试门数分组编码方案,不会产生非法染色体大于等于4门的班级(图4中,班级编号大于25的几个班级)14某水●246810121416182022242628303234246810121416182022242628303234班级编号班级编号→课程1课程2一课程3一一课程4米课程5课程6一课程!课程2一课鞋3一课强4课程5课程6图1初始安排中每个班级考试安排情况图2优化后每个班级考试安排情况回246810121416182022242628303234246810121416182022242628303234班级编号班级编号理论复习时间一平均复习时间→→理论复习时间一平均复习时间图3初始安排中理论复习时间和实际平均复习时间比较图4优化后毎个班级理论复习时间和实际平均复习时间比较(下转241页)