基于遗传算法的排课系统 |
您所在的位置：网站首页 › 排课流程图 › 基于遗传算法的排课系统 |
基于遗传算法的排课系统
|
整体思路
为所有课程班找到一个时空序列。课程班，（有别于课程的概念）即特定老师所上的具体的课程。时空序列是指，某一教室某一天的某一课时的开始时间。在时空序列不冲突的情况下，再去解决老师上课时间的冲突。 文件介绍 │ chromosomeSet.js │ chromosomeSet1.js 第一个学期课程表结果 │ chromosomeSet2.js 第一个学期课程表结果 │ classRooms.js 教室 │ common.js 工具函数 │ config.js 配置文件 │ courses.js 所有课程 │ ga-demo.html │ GA.js 遗传算法主要函数 │ lessonClasses_2020-2021-1.js 第一个学期课程 │ lessonClasses_2020-2021-2.js 第二个学期课程 │ teachers.js │ view.js 页面显示 ├─lib │ │ echarts.min.js │ │ vue.js │ │ │ └─element-ui │ │ index.css │ │ index.js │ │ │ └─fonts │ element-icons.woff 数据结构adaptability：二维数组保存各个课程班，在各个时空序列的适应程度，根据是否符合条件打分。 function initAdapt(){ adaptability = []; for (let i = 0; i < lessons.length; i++) { adaptability[i] = []; for (let d = 0; d < DAYS; d++) { for (let t = 0; t < TIMES; t++) { for (let r = 0; r < classRooms.length; r++) { // 判断不可用时段 if (unableDayTime[d] && unableDayTime[d].includes(t)){ adaptability[i][index] = 0; continue; } var index = indexUtil.getIndex(d,t,r); adaptability[i][index] = adapt(i,d,t,r); } } } } }chromosomeSet:一组基因，geneOrder：每组基因按照课程班顺序保存对应时空序列，badSelect：冲突数，adapt：适应度 this.getIndex = (day,time,roomIndex)=>{ return timeLength *roomIndex + times*day + time; } this.getPosition = (index)=>{ var room= Math.floor(index/timeLength); var daytime = index%timeLength; var day = Math.floor(daytime/ times); var time = daytime%times; return {day,time,room}; }其中: days:一周上课日 规定 0-6为周一-周日 times:每天上课总时间 timeLength= days*times 此三个参数： (day,time,roomIndex)第几天，第几节课，教室下标 由于此处仅仅记录了，课程的上课时间。所以要限制上课开始时间。联排两课时的可以选择第一节，第三节开始，第五节开始。联排三次课的可以选择第7节课，第10节课开始。 var unitUnableTime = { //此处时间为下标，从零开始 1: [], 2: [1,3,5,7,8,10,11], 3: [0,1,2,3,4,5,7,8,10,11], };这样同时也会带来一些问题，例如黎仁华老师下学期有20余门课且是三个学时的。三个学时最多能排2 * 5个时间段。这种情况明显是不够排的。是不是数据本身有问题？20门课，日均上四门课每次课三个学时！ 使用技术选择vue,es6,echarts原因： vue:选择Vue原因是实现组件化编程，实现可视化操作 es6 :模板字符串，箭头函数 echarts:前端画图工具 数据处理数据预处理 第一学期：2521 第二学期课程：2249 通过数据清洗得到以下四个数据： 1.教师数据 teachers.js { "id": "090099", "name": "宫志方" },教学计划表，从第二列数据中获取教师id，例如 (2020-2021-1)-015090-031142-2，其中031142为教师号。有一些是"000000",暂且跳过这些课程 2.教室数据 classRooms.js { "id": "1185", "roomType": "playgroud", "capacity": "1000", "roomNO": "体育馆二楼东侧平台" },体育馆二楼东侧平台,体育馆,1000 ,playgroud,1185。为了记录教室类型（roomType），容量（capacity） 3.课程数据 { "id": "034642", "name": "中国现代文学名著与作家人生", "totalHour": "16", "weekHour": 2.0, "roomType": "media", "onceHour": 2, },包含课程名，总学时，周学时，教室类型，每次学时 4.课程班数据 { "id": "5075", "course": "040397", "teacher": [ "031045" ], "studentNum": "60" },包含课程号，教师数组（一门课可能由多个老师上），学生人数 实现功能 同一时间，地点不多次排课 周二下午不排课 同一门课程一周上多次时，不安排在一天 一门课多个老师上也不冲突 课程班上课人数必须小于教室大小 具体实现 初始化课程同一课程的不同课时不能在同一时间 需要检查冲突，同样一个老师也不能在同一个时间上课 function initLessons(){ lessons = []; var teacherConflict = {}; lessonClasses.forEach(function(lesson, index) { let course = coursesMap[lesson.course]; let timesPerWeek = course.weekHour/course.onceHour; let conflictArr = []; // 同一课程的不同课时不能在同一时间 需要检查冲突 for (let i = 0; i < timesPerWeek; i++) { lessons.push(lesson); for(let t of lesson.teacher){ if (!teacherConflict[t]){ teacherConflict[t] = []; } teacherConflict[t].push(lessons.length-1); conflictArr.push(lessons.length-1); } } switch (timesPerWeek) { case 2: conflict.add(conflictArr,Conflict.Scope.skipDay,"同门课程"+lesson.id); break; case 3: case 4: conflict.add(conflictArr,Conflict.Scope.day,"同门课程"+lesson.id); break; default: conflict.add(conflictArr,Conflict.Scope.halfDay,"同门课程"+lesson.id); } }); for (const key in teacherConflict) { const conflictArr = teacherConflict[key]; conflict.add(conflictArr ,Conflict.Scope.time,"教师"+key); } 初始化适应度根据时间条件满足给时空序列打分 function (lesson, day, time, roomIndex, value) { var course = coursesMap[lesson.course]; var onceHour = course.onceHour; let val = 0; if (time >= 12 || (day == 1 && time >= 4) || (day == 4 && time >= 9)) { // 周五晚上/周二下午不排课 return CONFIG.unable; } if (day == 5){ // 周六尽量不排课 val += -10; } if (time < 4) { // 早上最优先 val += 6; } if (time>=4 && time < 6) { // 下午前两节优先 val += 3; } return val; },根据空间（教室）条件满足给时空序列打分 function(lesson,day,time,roomIndex,value){ var course = coursesMap[lesson.course]; var room = classRooms[roomIndex]; if(course.roomType != room.roomType){ logger.debug('不满足教室类型 lesson:',lesson.id,'roomtype',room.roomType); return CONFIG.unable; } var ratio = lesson.studentNum/room.capacity; if (ratio > 1) { logger.debug('教室容量不足 lesson:',lesson.id,'studentNum',lesson.studentNum,'capacity',room.capacity); return CONFIG.unable; } if (ratio > 0.8) { return 10; } if (ratio < 0.5) { return -5; } return 0; } 初始化基因从所有课程中随机取值 而不是从第一个开始 避免每次都是排在数组最开始位置的课程有最优先的选择 weights：某门课各个时空序列的适应程度 tolerance：对冲突的容忍程度，越小容忍程度越小，为零时，坚决不容忍。资源有限时或老师课程较多时，不宜设置为零。 skip：跳过已经被选择的时空序列 negativeFilter：消极过滤函数，接受参数 时空索引， 返回 ture则按照消极对待 会以极小的概率选择此值，可以认为只有没有其他任何选择时才会选中此值 function roll(weights,skip,negativeFilter) { var sum = 0; var length = weights.length; var tolerance =0.0000001 let badSet = new Set(); for (var i=0; i=0 && point!=i) { gene = motherGene[point]; set.add(point); related.push(point); point = fatherGene.indexOf(gene); } relatedGenes.push(related); } for (let i = 0; i < relatedGenes.length; i++) { let releted = relatedGenes[i]; let fromFather = Math.random()=0) { geneOrder[i] = result; } } } } 数据展示前端UI如下图 可以根据需要选择查询的学期调整 保存基因组结果,读取结果 每次将结果保存正在localStorage localStorage.setItem(CONFIG.chromosomeNum,JSON.stringify(chromosomeSet));读结果，以免页面刷新，不可再次查询 localStorage.getItem(CONFIG.chromosomeNum); chromosomeSet = localStorage.getItem(CONFIG.chromosomeNum); chromosomeSet = JSON.parse(chromosomeSet)迭代在20代是适应度开始收敛
按照教师查询 按照教室查询 如图所示
1.打开在浏览器打开main.html 2.选择学期数，按照教师（教师名或者id），课程id查询，教室号查询 按照教师查询
1.在config.js设置迭代次数，和基因数。 /** 染色体数量 */ chromosomeNum : 20, /** 迭代次数 */ iteratorNum : 100,2.打开在浏览器打开main.html 3.在浏览器控制台查看日志，根据设置的参数需要等待时间不一而同。染色体为5，迭代次数20时，大概需要15分钟 4.待运行结束，按照教师，课程id查询，教室号查询 |
【本文地址】
今日新闻 |
推荐新闻 |