The overall train of thought
Find a space-time sequence for all classes. A course, as distinct from a course, is a specific course given by a particular teacher. The space-time sequence is the beginning time of a particular class in a particular classroom on a particular day. In the case that the space-time sequence does not conflict, then to solve the conflict of the teacher’s class time.
The file is introduced
There are three classes on the ground: folders, folders, folders, folders, folders, folders, folders, folders, folders, folders, folders, folders, folders, folders, and folders Config.js configuration file │ courses.js all courses │ ga-demo.html │ ga.js Genetic algorithm main function │ Lessonclasses_2020-2021-1.js First semester course │ │ ├─lib │ ├─ echarts.min.js │ ├─ vue. Js │ ├─ element-u │ │ ├ ─fonts │ ├ ─fonts │ ├ ─fonts │ ├ ─fonts │ ├ ─fontsCopy the codeThe data structure
Adaptability: two-dimensional array to save the program, in all the adaptation degree sequence of time and space, according to the score is in line with the conditions.
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++) {
// Determine the unavailability period
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);
}
}
}
}
}
Copy the codeChromosomeSet: a set of genes, geneOrder: each gene in class order, badSelect: conflict number, adapt: fitness
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};
}
Copy the codeAmong them:
Days: School days in a week are Monday to Sunday from 0 to 6
Times: Total time of class per day
timeLength= days*times
This three parameters: (day,time,roomIndex) day, lesson, classroom subscript
Because this is just the time of the class. So limit the start time. For two classes, you can choose the first section, the third section and the fifth section. If you have three classes in a row, you can choose the 7th class, and the 10th class starts.
Var unitUnableTime = {/ / the time as the subscript, from 1: [], 2:,3,5,7,8,10,11 [1], 3:,1,2,3,4,5,7,8,10,11 [0],};Copy the codeThis will also bring some problems. For example, Teacher Li Renhua will have more than 20 courses in three hours next semester. Three credit hours can be arranged in 2 * 5 time periods at most. This is obviously not enough. Is there something wrong with the data? 20 courses, four courses a day, three class hours each!
The use of the technical
Select vue, ES6,echarts because:
Vue: The reason for choosing VUE is to realize componentized programming and visual operation
Es6: Template strings, arrow functions
Echarts: Front end drawing tool
The data processing
Data Preprocessing Course 1:2521 Course 2:2249
The following four data are obtained through data cleaning:
1. Teacher data
teachers.js
{"id": "090099", "name": "gongzhifang"},Copy the codeTeaching schedule, get the teacher ID from the second column data, for example (2020-2021-1)-015090-031142-2, where 031142 is the teacher number. Some of them are “000000”, so I’ll skip that for a moment
2. Classroom data
classRooms.js
{" id ":" 1185 ", "roomType" : "playgroud", "capacity" : "1000", "roomNO" : "on the second floor of the stadium on the east side platform"},Copy the codeEast platform, 2nd floor, Gymnasium,1000, Playgroud,1185. To record the roomType, capacity
3. Course data
{" id ":" 034642 ", "name" : "the Chinese modern literature and writers life", "totalHour" : "16" and "weekHour" : 2.0, "roomType" : "media", "onceHour" : 2,},Copy the codeIncludes course name, total class hours, week class hours, type of classroom, each class hour
4. Class data
{
"id": "5075",
"course": "040397",
"teacher": [
"031045"
],
"studentNum": "60"
},
Copy the codeContains course number, array of teachers (a course may have more than one teacher), number of students
Realize the function
- The same time, the place does not arrange classes more than once
- There are no classes scheduled on Tuesday afternoon
- When the same course is taken several times a week, it is not scheduled on one day
- There is no conflict between having more than one teacher in one course
- Class size must be smaller than the classroom size
The specific implementation
Initialization course
Different classes of the same course should not be checked for conflicts at the same time, and the same teacher should not be taught at the same time
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; 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. The add (conflictArr, conflict. The Scope. SkipDay, "biconditional gate course" + lesson #. Id); break; Case 3: case 4: conflict. The add (conflictArr, conflict. The Scope. Day, "biconditional gate course" + lesson #. Id); break; Default: conflict. The add (conflictArr, conflict. The Scope. HalfDay, "biconditional gate course" + lesson #. Id); }}); for (const key in teacherConflict) { const conflictArr = teacherConflict[key]; Conflict. Add (conflictArr, conflic.scope. Time," teacher "+key); }Copy the codeInitialize fitness
The space-time sequence is scored according to the time condition satisfied
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)) { // There are no classes scheduled on Friday evening/Tuesday afternoon
return CONFIG.unable;
}
if (day == 5) {// Try not to schedule classes on Saturdays
val += -10;
}
if (time < 4) { // Morning is the first priority
val += 6;
}
if (time>=4 && time < 6) { // The first two sections in the afternoon will take precedence
val += 3;
}
return val;
},
Copy the codeThe spatio-temporal sequence is scored according to the spatial (classroom) condition satisfied
function(lesson,day,time,roomIndex,value){
var course = coursesMap[lesson.course];
var room = classRooms[roomIndex];
if(course.roomType ! = room.roomType){ logger.debug('Not satisfying classroom type lesson:',lesson.id,'roomtype',room.roomType);
return CONFIG.unable;
}
var ratio = lesson.studentNum/room.capacity;
if (ratio > 1) {
logger.debug('Classroom capacity is insufficient',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;
}
Copy the codeInitializing gene
Take random values from all the classes instead of starting at the first so that the classes that are at the beginning of the array every time are chosen first
Weights: the fitness degree of each spatio-temporal sequence of a course
Tolerance = tolerance = tolerance It is not appropriate to set it to zero when resources are limited or the teacher has a large number of courses.
Skip: Skip the selected space-time sequence
NegativeFilter: a negativeFilter function that accepts the parameter space-time index. If true is returned, this value will be selected with minimal probability according to the negative treatment. It can be considered that this value will be selected only when there is no other option
function roll(weights,skip,negativeFilter) {
var sum = 0;
var length = weights.length;
var tolerance =0.0000001
let badSet = new Set(a);for (var i=0; i<length; i++) {
let weight = weights[i];
// When in the Skip array, its probability becomes 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];
// When in the Skip array, its probability becomes 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) {
returni; }}return -1;
}
Copy the codeDetect the number of conflicts in genes
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;
}
Copy the codecross
function cross(fatherGene,motherGene){ var childGene = []; Var set = new set (); Var relatedGenes = []; For (let I = 0; 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. The 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; }Copy the codevariation
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; }}}}Copy the codeThe data show
The front end UI is shown below
You can select the semester adjustment of the query as needed
Save the genome results, read the results
Save the result in localStorage each time
localStorage.setItem(CONFIG.chromosomeNum,JSON.stringify(chromosomeSet));
Copy the codeRead the result, lest the page refresh, cannot be queried again
localStorage.getItem(CONFIG.chromosomeNum);
chromosomeSet = localStorage.getItem(CONFIG.chromosomeNum);
chromosomeSet = JSON.parse(chromosomeSet)
Copy the codeIteration at generation 20 is when fitness begins to converge
According to teacher inquiry
Query by classroom
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:${course.name}Teacher:${teacherNameList}The classroom no. :${roomId}Number of courses:${lesson.studentNum}Class ID:${lesson.id}Class time:${course.onceHour}
`
}
Copy the codeAs is shown in
Instructions for
Direct query
1. Open Open main.html in your browser
2. Select the number of terms and query by teacher (teacher name or ID), course ID and classroom number
According to teacher inquiry
Perform the query after the algorithm is executed
1. Set the number of iterations and the number of genes in config.js.
/** Number of chromosomes */ chromosomeNum: 20, /** Number of iterators */ iteratorNum: 100,Copy the code2. Open Open main. HTML in your browser
3. View logs on the browser console. The waiting time varies according to the parameter Settings. With 5 chromosomes and 20 iterations, it takes about 15 minutes
4. After the operation is completed, query according to teacher, course ID and classroom number