# Genetic algorithm to fill timetable for school

I wrote a program to fill a timetable for a school. There are some simple rules:

• Each subject has a preset number of blocks (blocks are 2 hour periods).
• Professor provide a valid hours they have to teach.
• There cannot be a subject at block and day x if there isn't any professor of that subject that can teach it at that time.

The program takes input from 2 txt files. The valid time is 5 days and 7 blocks. The amount of blocks used for teaching the subjects is less than the valide time. Every block has a code that starts with the 2 initial letters of the day (in Spanish) and the block starting from a to g (1 to 7). martes second period would be MAB (MA stands for martes and b stands for second period).

Main class:

package timetable;

import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

import com.jaysi.timetable.Profesor;
import com.jaysi.timetable.Subject;

public class Main {
public static final int popSize = 50;

public static final int attemptLimit = 500;
public static final int days = 5;
public static final int blocks = 7;
public static final int mutationChance =5;// 5/100
public static List<Class>classes = new ArrayList <Class>();
public static List<Candidate> population = new ArrayList <Candidate>();
public static boolean notFound = true;
public static int perfectFittnes = 1000;
public static Candidate timetable = null;
public static void main(String[] args) throws Exception {
population = generatePopulation(popSize);
int attempt = 0;
do{
for (int i = 0; i<population.size();i++){
if(population.get(i).getFitnnes()==perfectFittnes){
notFound = false;
timetable = population.get(i);
break;
}
}
Collections.sort(population, new fitnnesComparator());
evolvePop(population);
Collections.sort(population, new fitnnesComparator());
System.out.println("evolving pop!");
for (int i = 0; i<population.size();i++){
if(population.get(i).getFitnnes() == perfectFittnes){
notFound = false;
timetable = population.get(i);
break;
}
}
System.out.println("This its the general attempt number : " + attempt);
attempt++;
System.out.println("THIS ITS THE CURRENT POP FITTNES LEVEL:");

for(int h = 0; h<population.size();h++){
System.out.println("Candidate "+ h + ": "+ (population.get(h).getFitnnes()));
}
}while(notFound && attempt < attemptLimit);

}
private static void evolvePop(List<Candidate> population) {
Candidate parent1 = null;
Candidate parent2 = null;
Candidate child1 = null;
Candidate child2 = null;
for(int i = (popSize/2)-1; i< population.size(); i++){
population.remove(i);
}
for(int o = 0; o < ((popSize/2)/2); o++){
int i = ((popSize/2) -1);
parent1 = population.get(0);
parent2 = population.get(o+1);
child1 = crossOver(parent1, parent2);
child2 = crossOver(parent2, parent1);
mutate(child1);
mutate(child2);
mutate(parent1);
mutate(parent2);
o++;

}

}
private static void mutate(Candidate cand) {
Random rand = new Random();
int x = rand.nextInt(days);
int y = rand.nextInt(blocks);
int p = rand.nextInt(classes.size());
int chance = rand.nextInt(99);
if(chance<(mutationChance+3)){
cand.set(x, y, classes.get(p));
}

}

private static Candidate crossOver(Candidate parent1, Candidate parent2) {
Class[][] Timetable = new Class[days][blocks];
Class[][] p1Timetable = parent1.getTimetable();
Class[][] p2Timetable = parent2.getTimetable();
Timetable[0] = p1Timetable[0];
Timetable[1] = p1Timetable[1];
Timetable[2] = p2Timetable[2];
Timetable[3] = p2Timetable[3];
Timetable[4] = p2Timetable[4];
Candidate child = new Candidate(Timetable);
return child;

}

private static ArrayList<Candidate> generatePopulation(int size) {
ArrayList<Candidate> population = new ArrayList<Candidate>();
int attempt = 0;
while(attempt<size){
System.out.println("Generating candidate : " + attempt);
attempt++;
}
return population;

}
private static Candidate generateCandidate() {
Candidate candidate = null;
Class[][] candidateTimetable = new Class[days][blocks];
boolean[]filled = new boolean[classes.size()];
for (int t = 0; t<classes.size(); t++){
filled [t] = false;
}
boolean notFilled = true;
boolean allFilled = true;
Integer [] space = {11,12,13,14,15,16,17,
21,22,23,24,25,26,27,
31,32,33,34,35,36,37,
41,42,43,44,45,46,47,
51,52,53,54,55,56,57};
int[] counter = new int [classes.size()];
for (int s = 0; s<classes.size(); s++){
counter [s] = 0;
}

List<Integer> spaces = new ArrayList<>(Arrays.asList(space));
int xy = 0;
while(notFilled){

int x, y , u = spaces.size();
if(u <= 0){
notFilled = false;
break;
}
for(int i = 0; i< filled.length; i++){
if(counter[i]== classes.get(i).getBlocks()){
filled[i] = true;
}
}
for(boolean f : filled){
if(f == false){
allFilled = false;

}
}
if(allFilled){
notFilled = false;
break;
}
Random random = new Random();
int size1 = spaces.size();
int select1 = random.nextInt(size1);
xy = spaces.get(select1);
spaces.remove(select1);
x = xy/10;
y= xy%10;
int select2 = random.nextInt(classes.size());
if(filled[select2] != true){
candidateTimetable[x - 1][y - 1] = classes.get(select2);
counter[select2] ++;
}
}

candidate = new Candidate(candidateTimetable);
return candidate;
}
private static void readFiles(String pathProfesors, String pathSubjects) throws Exception{
ArrayList <Profesor>profesors = new ArrayList<Profesor>();
ArrayList <Subject> subjects = new ArrayList<Subject>();

//Fills Professors

String lineP;
String[] lineSplitP;
ArrayList<String> avalideHoursP = new ArrayList<String>();
while(lineP !=null){
lineSplitP = lineP.split("\\s+");
//fills avalide hours
//starts at 1 because 0 its name
for(int i = 1; i<lineSplitP.length; i++){
}
}

//Fills Subjects

String lineS;
String[] lineSplitS;
ArrayList<String> profesorsName = new ArrayList<String>();
ArrayList<Profesor> profesorsThatCanTeachThis = new ArrayList<Profesor>();
while(lineS != null){
lineSplitS = lineS.split("\\s+");
//fills profesorsName
//Starts at 2 because 0 its name 1 its blocks
for(int i = 2; i<lineSplitS.length; i++){
}
//fills profesorsThatCanTeachThis
for(int i = 0; i<profesorsName.size(); i++){
for(int x = 0; x< profesors.size(); x++){
if(profesors.get(0).getName().equals(profesorsName.get(i))){
}
}
}
}

//Fills classes
for(int i = 0; i<subjects.size(); i++){
}
}
}


Professor class:

package timetable;

import java.util.ArrayList;

public class Profesor {
private String name;
private ArrayList<String>avalideHours = new ArrayList<String>();
public Profesor(String name, ArrayList<String>avalideHours){
this.name = name;
this.avalideHours = avalideHours;
}
public String getName(){
return name;
}
public String[] getHours() {
String profposhours[]=new String[avalideHours.size()];
avalideHours.toArray(profposhours);
return profposhours;
}

}


Subject class:

package com.timetable;

import java.util.ArrayList;

import timetable.Profesor;

public class Subject {
private String name;
private int blocks;
private ArrayList<Profesor>profesorsThatCanTeachThis = new ArrayList<Profesor>();
public Subject(String name, int blocks, ArrayList<Profesor>profesorsThatCanTeachThis){
this.name = name;
this.blocks = blocks;
this.profesorsThatCanTeachThis = profesorsThatCanTeachThis;

}
public String getName() {
return name;
}
public int getBlocks() {
return blocks;
}
public ArrayList<Profesor> getProfessors() {
return profesorsThatCanTeachThis;
}

}


Class class:

package timetable;

import java.util.ArrayList;

import timetable.Profesor;
import timetable.Subject;

public class Class {
private String name;
private Subject subject;
private int blocks;
private ArrayList<Profesor> profesorsThatCanTeachThis = new ArrayList<Profesor>();
public Class( Subject subject){
this.name = subject.getName();
this.subject = subject;
this.blocks = subject.getBlocks();
this.profesorsThatCanTeachThis = subject.getProfessors();
}
public int getBlocks(){
return blocks;
}
public String[] getPosHours() {
ArrayList<String[]>posHours = new ArrayList<String[]>();
ArrayList<String>poshours = new ArrayList<String>();

for(int i = 0; i<profesorsThatCanTeachThis.size(); i++){
}
for(int x = 0; x<posHours.size();x++){
for(int p = 0; p< posHours.get(x).length;p++){
}
}
String[]PosHours = new String[poshours.size()];
poshours.toArray(PosHours);
return PosHours;
}
public String getName(){
return name;
}
}


Candidate class:

package timetable;

public class Candidate {
static String template [][] = new String[Main.days][Main.blocks];

private Class[][] timetable = new Class[Main.days][Main.blocks];
private int fitnnes;
public Candidate(Class[][] timetable){
this.timetable = timetable;
this.fitnnes = getFitnes();
}
public Class[][]getTimetable(){
return this.timetable;
}
public int getFitnnes(){
return fitnnes;
}
private int getFitnes(){
template[0][0]= "lua";
template[0][1]= "lub";
template[0][2]= "luc";
template[0][3]= "lud";
template[0][4]= "lue";
template[0][5]= "luf";
template[0][6]= "lug";

template[1][0]= "maa";
template[1][1]= "mab";
template[1][2]= "mac";
template[1][4]= "mae";
template[1][5]= "maf";
template[1][6]= "mag";

template[2][0]= "mia";
template[2][1]= "mib";
template[2][2]= "mic";
template[2][3]= "mid";
template[2][4]= "mie";
template[2][5]= "mif";
template[2][6]= "mig";

template[3][0]= "jua";
template[3][1]= "jub";
template[3][2]= "juc";
template[3][3]= "jud";
template[3][4]= "jue";
template[3][5]= "juf";
template[3][6]= "jug";

template[0][0]= "via";
template[0][1]= "vib";
template[0][2]= "vic";
template[0][3]= "vid";
template[0][4]= "vie";
template[0][5]= "vif";
template[0][6]= "vig";

int fitnnes = 1000;
boolean allFilled = true;
boolean[]filled = new boolean[Main.classes.size()];
for (int t = 0; t<Main.classes.size(); t++){
filled [t] = false;
}
int[] counter = new int [Main.classes.size()];
for (int s = 0; s<Main.classes.size(); s++){
counter [s] = 0;
}
for(int p = 0; p<Main.classes.size();p++){
for(int i = 0; i<Main.days; i++){
for(int x=0; x<Main.blocks;x++){
if(timetable[i][x] == null){continue;}
if(timetable[i][x].getName().equals(Main.classes.get(p).getName())){
counter[p]++;
}
}

}
}
for(int p=0;p<Main.classes.size();p++){
if(counter[p]== Main.classes.get(p).getBlocks()){
filled[p] = true;
}
}

for(boolean f : filled){
if(f == false){
allFilled = false;

}
}
if(allFilled == false){
fitnnes -= 100;
}
for(int i = 0; i< Main.days; i++){
for(int x = 0; x< Main.blocks; x++){
if(timetable[i][x] == null){
continue;
}
String posHours [] = timetable[i][x].getPosHours();
boolean avalide = false;
for(int y = 0; y<posHours.length;y++){
if(template[i][x] == posHours[y]){
avalide = true;
}
}
if(!avalide){
fitnnes -= 50;
}

}

}
for(int q = 0; q<Main.days;q++){
for(int a = 0; a<Main.blocks; a++){
for(int aa = a+1;aa<Main.blocks; aa++){

}
}
}
return fitnnes;
}
public void set(int x, int y, Class xy) {
this.timetable[x][y] = xy;

}

}


profesors.txt:

The first word is the name and rest are the valid blocks they have to teach.

Petidfgtti    mif mig vif vig
Chdanales luc lud mac mad mic mid juc jud
Lucdero   lub luc lud lue mab mac mad mae mib mic mid mie jub juc jud jue vib vic vid vie
Ergamdsahi    lua luf maa maf mia mif jua juf via vif
Mazza mab mac jub juc
Puedfgbla lua lub luc lud maa mab mac mad mia mib mic mid jua jub juc jud via vib bic bid
Chisdgatti    mib mic mid mie jub juc jud jue
Jimensdfgdz   maa mab jua jub
Rfdsgubino    mab mac mad mae maf mib mic mid mie mif
Velafghsfghsco    vib vic vid vie vif
Lucsgdro lub luc lud lue mab mac mad mae mib mic mid mie jub juc jud jue vib vic vid vie
Atefghnas vib vic vid vie
Fustghr lue luf lug mae maf mag mie mif mig jue juf jug vie vif vig


Subjects.txt:

The first word is the name of the subject, the number is the number of blocks that that subject has, and the other is the professors that can teach it.

Matematica 2 Pettiti
Apesca 3 Canales
NavegacionI 4 Lucero
TecfsPessc 2 Bergamaschi
MeteofrodlogiaI 1 Mazza
ComsdfunicacdfionesI 1 Puebla
IndTecI 2 Chiatti
Ssdpervisdfvencia 1 Jimenez
ManiobraI 3 Rubino
MaqufdsdasI 1 Velasco
Equidfsfronicos 1 Lucero
PrimerosAux 1 Atenas
CargaEstiva 1 Fuster


The program works to a certain amount. The best fitness from the first generation is the best fitness in all the generations.

This code is not completely working. fitnnesComparator is missing. But still there is a lot of effort. In case you are not aware Code review is only for code that works.

You didn't add what you were expecting so I guess you were expecting a fix. Sorry.

I won't solve the problem but I will add some general things that can be improved in the code.

Use for-each loop if you don't need the index

for(int i = 0; i<subjects.size(); i++){
}


you can use

for (Subject subject : subjects) {
}


Avoid manual loops where you can

    //fills profesorsName
//Starts at 2 because 0 its name 1 its blocks
for(int i = 2; i<lineSplitS.length; i++){
}


use this

List<String> professors = Arrays.asList(lineSplitS).subList(2, lineSplitS.length)


The bottom line is manual loops give you a lot of errors. Off by one errors. Avoid them if you can.

Use equals not == in Java to compare Strings. Always

Didn't check but this may be a bug. Always use equals. You don't want to get surprised.

if(template[i][x] == posHours[y]){
avalide = true;
}


Local variables are initalized. No need to do that again

So this

int[] counter = new int[classes.size()];
for (int s = 0; s < classes.size(); s++) {
counter[s] = 0;
}


does not need the loop.

• Smaller methods
• Less global variables