вся идея
Найдите пространственно-временную последовательность для всех занятий курса. Класс курса (в отличие от концепции курса) — это конкретный курс, пройденный конкретным учителем. Пространственно-временная последовательность относится к времени начала определенного периода урока в определенном классе в определенный день. В случае, если пространственно-временная последовательность не конфликтует, разрешите конфликт времени класса учителя.
Введение в файл
│ 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: количество конфликтов, адаптация: пригодность
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};
}
в:
дни: учебные дни в неделю, 0-6 понедельник-воскресенье
раз: общее время занятий в день
timeLength= days*times
Эти три параметра: (день, время, 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": "宫志方"
},
В таблице плана обучения получите идентификатор учителя из данных во втором столбце, например (2020-2021-1)-015090-031142-2, где 031142 — идентификатор учителя. Некоторые из них "000000", пока пропустите эти уроки.
2. Данные о классе
classRooms.js
{
"id": "1185",
"roomType": "playgroud",
"capacity": "1000",
"roomNO": "体育馆二楼东侧平台"
},
На восточной площадке второго этажа гимназия, гимназия 1000, детская площадка 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;
}
ген инициализации
Случайным образом выбирать значения из всех классов вместо того, чтобы начинать с первого, чтобы каждый раз не выбирать класс в начале массива.
веса: степень адаптации каждой пространственно-временной последовательности курса
Терпимость: терпимость к конфликту, чем меньше терпимость, тем меньше терпимость.Когда он равен нулю, он решительно нетерпим. Его не следует устанавливать равным нулю, когда ресурсы ограничены или когда существует много курсов для учителей.
пропустить: пропустить выбранную пространственно-временную последовательность
отрицательный фильтр: функция отрицательного фильтра, которая принимает пространственно-временной индекс параметра, возвращает значение и обрабатывает его как отрицательное. Это значение будет выбрано с очень малой вероятностью. Можно считать, что это значение будет выбрано только тогда, когда нет другого выбора. .
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<length; i++) {
let weight = weights[i];
// 当在skip数组当中 ，它的概率变为0
if(weight == 0 ||(skip && skip.includes(i))){
continue;
}
if (negativeFilter && negativeFilter(i)){
weight = weight * tolerance;
badSet.add(i);
if(tolerance==0){
continue;
}
}
sum += weight;
}
var rand = Math.random() * sum;
sum = 0;
for (var i = 0; i<length; i++) {
let weight = weights[i];
// 当在skip数组当中 ，它的概率变为0
if(weight == 0 ||(skip && skip.includes(i))){
continue;
}
if (negativeFilter && negativeFilter(i)){
weight = weight * tolerance;
if(tolerance==0){
continue;
}
}
sum += weight;
if (sum >= rand) {
return i;
}
}
return -1;
}
Обнаружение конфликтов генов
function checkBadSelect(gene){
let badSelect = 0;
for (let i = 0; i < gene.length; i++) {
let check= conflict.relatedDayTime(i,gene);
if(check.has(indexUtil.getDayTime(gene[i]))){
badSelect ++;
}
}
return badSelect;
}
Пересекать
function cross(fatherGene,motherGene){
var childGene = [];// 以父基因为基础添加母基因来实现交叉
var set = new Set(); // 用于保存已经关联的基因
var relatedGenes = []; //关联基因的索引
// 遍历寻找关联基因
for (let i = 0; i < fatherGene.length; i++) {
if(set.has(i))
continue;
let gene = motherGene[i];
let point = fatherGene.indexOf(gene);
let related = [i];
while (point >=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.5?true:false;
for (let j = 0; j < releted.length; j++) {
let index = releted[j];
childGene[index] = fromFather? fatherGene[index]: motherGene[index];
}
}
return childGene;
}
Мутации
function vary(geneOrder){
for (let i = 0; i < geneOrder.length; i++) {
if(Math.random()<CONFIG.varyRate){
let adapt = adaptability[i];
let conflictSet = conflict.relatedDayTime(i,geneOrder);
let result = roll(adapt,geneOrder,dayTimeRoom => conflictSet.has(indexUtil.getDayTime(dayTimeRoom)));
if (result>=0) {
geneOrder[i] = result;
}
}
}
}
Отображение данных
Внешний интерфейс выглядит следующим образом
Вы можете выбрать семестровую настройку запроса в соответствии с вашими потребностями
Сохраняйте результаты геномики, читайте результаты
Каждый раз результат сохраняется в localStorage
localStorage.setItem(CONFIG.chromosomeNum,JSON.stringify(chromosomeSet));
Прочитайте результаты, чтобы не обновлять страницу, и не запрашивайте повторно
localStorage.getItem(CONFIG.chromosomeNum);
chromosomeSet = localStorage.getItem(CONFIG.chromosomeNum);
chromosomeSet = JSON.parse(chromosomeSet)
Итерация в 20-м поколении — это когда пригодность начинает сходиться.
Поиск по учителю
Поиск по классу
function lessonToString(lessonIndex,geneOrder){
let lesson = lessons[lessonIndex];
let course = coursesMap[lessons[lessonIndex].course];
let roomId = classRooms[indexUtil.getRoom(geneOrder[lessonIndex])].id
let teacherNameList = []
for (t of lesson.teacher){
teacherNameList.push(teachersMap[t].name)
}
return `课程名:${course.name}
任课教师:${teacherNameList}
教室号:${roomId}
课程人数:${lesson.studentNum}
课程班ID:${lesson.id}
上课课时:${course.onceHour}
`
}
как показано на рисунке
инструкции
прямой запрос
1. Откройте open main.html в браузере
2. Выберите количество семестров и выполните запрос по учителю (имя или идентификатор учителя), идентификатору курса и номеру класса.
Поиск по учителю
Запрос после выполнения алгоритма
1. Задайте количество итераций и количество генов в config.js.
/** 染色体数量 */
chromosomeNum : 20,
/** 迭代次数 */
iteratorNum : 100,
2. Откройте open main.html в браузере
3. Просмотрите лог в консоли браузера Время ожидания зависит от заданных параметров. При числе хромосом 5 и количестве итераций 20 это занимает около 15 минут.
4. После завершения операции выполните запрос по учителю, идентификатору курса и номеру класса.