| 基于遗传算法的排课算法思路 | 您所在的位置：网站首页 › 自动门的设计思路 › 基于遗传算法的排课算法思路 |
基于遗传算法的排课算法思路
|
摘自毕业论文《基于微服务的智能教学质量管理平台的设计与实现》 （1）问题描述 课程编排（排课）是平台的核心功能。排课问题被国外专家证明为属于NP完全问题，本质是求出满足一定软硬约束下的教学任务、教室、时间三者的笛卡尔积。其涉及到的因素比较繁杂，属于多目标的调度问题，在运筹学中也被称之为“时间表问题”。 在课程编排中需要满足一些的硬条件约束。一个班级在同一时间段内只能安排一门课程、一个教室在同一时间段内只能安排一门课程等。除了硬性约束，还有一些为了使课程安排更加合理、人性化的软约束应该得到满足。尽量不将课程安排至晚上、尽量将一门课分散在一周中，避免出现课程安排过于集中的情况。这些需求都会由于实际情况不同而与排课目标出现差距，因此即使课程编排算法无法满足这些软约束，也可由人工进行课程调节。 （2）思路分析 排课问题作为NP完全问题，时间复杂度较高，在对课程编排的算法研究中，众多研究者提出了一些优化算法来解决排课问题，如模拟退火，约束满意，列表寻优搜索，遗传算法等。本文使用暴力算法和遗传算法两种方式实现了排课，比对后发现遗传算法可更快的找到最优解。 本平台设计时已经将教师、学生、课程进行了合并，也就是将其视为一个教学任务，因此只需要保证教学任务安排至教室而不发生时间冲突即可。 暴力法是枚举出所有排课选择的方法。假设每周可编排课程的时间段有n个，且有m个教学任务在等待编排，那么在不使用其他优化的方式下进行课程编排可得时间复杂度为O(n^m)。为降低时间复杂度，枚举前引入随机的课程编排，暴力算法的课程编排步骤如下： Step1：查询出指定学年、学期下需要排课的教学任务列表TaskList。 Step2：查询出指定学年、学期下可以使用的教室列表ClassRoomList。 Step3：针对每一个TaskList教学任务task，随机一个工作日和排课节次以及一个可用的教室。检查是否在指定学年、学期下已有教学任务已编排进此教室。如是，说明发生了排课碰撞，则循环执行Step3，在允许碰撞次数m次内发生排课碰撞都可认为是正常的（默认m 为20）。如在允许碰撞次数内未排课成功，进入Step4。如允许碰撞次数内未发生排课碰撞，则可安排此课程。 Step4：在指定学年、学期下，遍历ClassRoomList中的教室和工作日的课程编排节次，如存在空闲排课计划，则可安排此课程。继续遍历下一个TaskList，针对下一个task执行Step1直至TaskList遍历结束。如经过遍历仍未将task进行安排，则进入Step5。 Step5：返回课程编排失败的信息，提示用户可用资源不足。 图4-1展示的是遗传算法的流程，其类似于基因演化的循环过程，根据待解决问题设计种群，让种群中的染色体不断进行交叉和变异，将生成的优质后代组成新的种群，并不断迭代。根据实际约束计算种群的适应度，以寻找问题最优解。
图4-1 遗传算法流程图 基于遗传算法设计实现的排课算法流程如下： Step1：针对待排课问题，生成一组随机解，称为“种群”，种群中的个体成为“染色体”，即一种排课方案。 Step2：对染色体的适应度进行评估，判断此染色体是否符合约束，即判断排课方案是否出现教室、时间、教学任务的冲突。若没有出现冲突，则可将此染色体作为最优解返回。否则进入Step3。 Step3：根据种群中各染色体的适应度由低到高排序，筛选出优质染色体作为精英种群，遗传的后代便是通过精英种群的变异、交叉得到的。 Step4：按照一定的概率对精英种群做交叉、变异处理，以生成新的优质染色体。交叉操作是在精英种群中随机挑选两条染色体，交换课程安排信息。变异操作是随机在精英种群中挑出一条染色体，随机变更课程安排信息。将新的优质染色体加入精英种群。 Step5：将种群替换为精英种群，迭代进入Step2。 遗传算法通过模拟自然界优胜劣汰的进化现象，通过优质染色体的交叉和变异，加大获得最优解的概率，对比于其他算法，遗传算法的求解效率更高。 （2）核心实现代码 package com.edusystem.util.ga; import lombok.AllArgsConstructor; import lombok.Data; import java.util.List; import java.util.Random; /** * 染色体 * @author 花菜 * @date 2021/5/22 0:33 */ @Data @AllArgsConstructor public class Schedule { /** * GA中首要考虑的是如何表现其问题，即如何对染色体编码，使之适用于GA操作。 * 在经典的遗传算法中，常采用浮点数或二进制的编码方法， * 目前，每条染色体代表每一节课的安排 * 至于排课结果的优劣，则由适应度函数评估染色体的适应值来决定。 */ private String teachtaskid; //哪一个教学任务==》包含了courseid teacherid classid //下面三个字段是经过ga给的 private String classroomid; //在哪一个教室 private Integer weekday; //周几上课（1-7） private Integer slot; //第几节课（12 34 56 78 910 11）==》（1-6） public Schedule() {} public Schedule(String teachtaskid) { this.teachtaskid = teachtaskid; } void random_init(List roomRange){ //这里随机初始值的时候 还是使用一周五天 一天4节课的正常 课程安排条件 Random random = new Random() ; this.classroomid = roomRange.get(random.nextInt(roomRange.size())); this.weekday = (int)( 1 + Math.random() * (5 - 1 + 1)); this.slot = (int)( 1 + Math.random() * (4 - 1 + 1)); } @Override public String toString() { return "Schedule{" + "teachtaskid='" + teachtaskid + '\'' + ", classroomid='" + classroomid + '\'' + ", weekday=" + weekday + ", slot=" + slot + '}'; } } package com.edusystem.util.ga; import com.edusystem.entity.Classroom; import jdk.internal.org.objectweb.asm.ClassReader; import lombok.AllArgsConstructor; import lombok.Data; import org.apache.commons.collections4.map.LinkedMap; import java.util.*; /** * 遗传算法排课 * @author 花菜 * @date 2021/5/22 0:31 */ @Data @AllArgsConstructor public class MyGa { //种群的规模（0-100） private Integer popsize = 32; //种群的变异概率 private Double mutprob = 0.3; //精英种群的个数 private Integer elite = 15; //进化代数（100-500） private Integer maxiter = 500; //所有的种群 每一个种群中存放需要编排的课程列表 private List population; public MyGa() { } /** * ga主体 * 参数：教学任务信息列表 、所有可以使用的教师的id列表 、需要排到第几节课 * @param schedules * @param roomRange * @return */ public List evolution(List schedules, List roomRange){ //冲突最小的染色体的冲突得分，若为0则说明已获得最优的解，可返回 int bestScore = 0; //最优的课程编排结果 List bestSchedule = new ArrayList(); init_population(schedules, roomRange); for(int i = 0 ; i < this.maxiter ; i++){ List newPopulation = new ArrayList(); //获取冲突结果 LinkedMap cost_map = schedule_cost(this.population, this.elite); for(List key : cost_map.keySet()){ //若发现冲突结果为0 则说明可将其当做最优排课结果返回 bestScore = cost_map.get(key); if(bestScore == 0) { bestSchedule = key; return bestSchedule; } } //精英种群集合 for(List key : cost_map.keySet()){ newPopulation.add(key); } while (newPopulation.size() < this.popsize){ List tmp = new ArrayList(); if(Math.random() < this.mutprob){ //落在变异概率内 变异 tmp = mutate(newPopulation, roomRange); }else{ //交叉 tmp = crossover(newPopulation); } newPopulation.add(tmp); } this.population = newPopulation; } return bestSchedule; } /** * 变异 根据精英种群集合 在将其中随机一个染色体变异后 返回变异后的染色体 * @param eiltePopulation * @param roomRange * @return */ List mutate(List eiltePopulation , List roomRange ){ Random random = new Random(); //选择变异哪一个精英种群中的染色体 int getIndex = random.nextInt(eiltePopulation.size()); List ep = eiltePopulation.get(getIndex); for(Schedule s : ep){ int pos = random.nextInt(3); if(pos == 0){ s.setClassroomid( roomRange.get(random.nextInt(roomRange.size())) ); }else if(pos == 1){ s.setWeekday((int)( 1 + Math.random() * (5 - 1 + 1))); }else if(pos == 2){ s.setSlot((int)( 1 + Math.random() * (4 - 1 + 1))); } } return ep; } /** * 交叉 根据精英种群集合 在将其中两个染色体交叉后 返回一个新的染色体 * @param eiltePopulation * @return */ List crossover(List eiltePopulation){ Random random = new Random(); //选择变异哪两个精英种群 int getIndex1 = random.nextInt(eiltePopulation.size()); int getIndex2 = random.nextInt(eiltePopulation.size()); List e1 = eiltePopulation.get(getIndex1); List e2 = eiltePopulation.get(getIndex2); int pos = random.nextInt(3); for(int i = 0 ; i < e1.size() ; i++ ){ if(pos == 0){ e1.get(i).setClassroomid( e2.get(i).getClassroomid()); }else if(pos == 1){ e1.get(i).setWeekday( e2.get(i).getWeekday()); }else if(pos == 2){ e1.get(i).setSlot( e2.get(i).getSlot()); } } return e1; } /** * 随机初始化不同的种群 * @param schedules * @param roomRange */ void init_population( List schedules , List roomRange ){ this.population = new ArrayList(); for(int i = 0 ; i < this.popsize ; i++){ List entity = new ArrayList(); for(int j = 0; j < schedules.size() ; j++ ){ Schedule tmp = schedules.get(j); tmp.random_init(roomRange); entity.add(new Schedule( tmp.getTeachtaskid(), tmp.getClassroomid(), tmp.getWeekday(), tmp.getSlot() )); } this.population.add(entity); } } /** * 计算课表种群的冲突。 * 返回：精英种群--精英种群中排名第一的染色体若冲突值为0则说明是可以作为最优解返回 * 当被测试课表冲突为0的时候，这个课表就是个符合规定的课表。 * 冲突检测遵循下面几条规则： * 同一个教室在同一个时间只能有一门课。 * 同一个班级在同一个时间只能有一门课。 * 同一个教师在同一个时间只能有一门课。 * 但是对于目前系统中已经将班级、教师、课程拼成了一条教学任务 * 故只需要满足 同一个教室在同一个时间 只能有一各教学任务 * @param population * @param elite * @return */ LinkedMap schedule_cost(List population , Integer elite){ LinkedMap utilMap = new LinkedMap(); LinkedMap resMap = new LinkedMap(); List conflicts = new ArrayList(); //一个染色体有多长==》有多少课程需要安排 int n = population.get(0).size(); for(List p : population){ //对种群遍历，求种群中染色体的适应度 int conflict = 0; for(int i = 0 ;i < n-1 ;i++){ for(int j = i+1 ;j < n ; j++){ //check course in same time and same room //检查冲突 需保证 在同一天 同一节课 下的 同一个教室中没有两个课程 if(p.get(i).getClassroomid().equals(p.get(j).getClassroomid()) && p.get(i).getWeekday() == p.get(j).getWeekday() && p.get(i).getSlot() == p.get(j).getSlot() ){ conflict += 1; } } } utilMap.put( p , conflict); } //根据冲突值排序 List entryList = new ArrayList(utilMap.entrySet()); Collections.sort(entryList,new Comparator >() { @Override public int compare(Map.Entry me1, Map.Entry me2){ //按照从小到大的顺序排列 return me1.getValue().compareTo(me2.getValue()); } }); Iterator iter = entryList.iterator(); Map.Entry tmpEntry = null; int flag = 0; while (iter.hasNext()) { tmpEntry = iter.next(); resMap.put(tmpEntry.getKey(), tmpEntry.getValue()); flag++; if(flag == elite) break; } //说明一下：此处的resMap的大小会变化 因为排序后可能会出现相同的种群情况 因为把value值更新了 return resMap; } }
|
【本文地址】