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.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
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 {
readFiles("profesors.txt", "subjects");
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);
population.add((i), child1);
population.add((i)+1, child2);
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);
population.add(generateCandidate());
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>();
FileReader profesorsTxt = new FileReader(pathProfesors);
FileReader subjectsTxt = new FileReader(pathSubjects);
BufferedReader readerProfesors = new BufferedReader(profesorsTxt);
BufferedReader readerSubjects = new BufferedReader(subjectsTxt);
//Fills Professors
String lineP;
String[] lineSplitP;
ArrayList<String> avalideHoursP = new ArrayList<String>();
lineP = readerProfesors.readLine();
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++){
avalideHoursP.add(lineSplitP[i]);
}
profesors.add(new Profesor(lineSplitP[1], avalideHoursP));
lineP = readerProfesors.readLine();
}
//Fills Subjects
String lineS;
String[] lineSplitS;
ArrayList<String> profesorsName = new ArrayList<String>();
ArrayList<Profesor> profesorsThatCanTeachThis = new ArrayList<Profesor>();
lineS = readerSubjects.readLine();
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++){
profesorsName.add(lineSplitS[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))){
profesorsThatCanTeachThis.add(profesors.get(x));
}
}
}
subjects.add(new Subject(lineSplitS[0], Integer.parseInt(lineSplitS[1]), profesorsThatCanTeachThis));
lineS = readerSubjects.readLine();
}
//Fills classes
for(int i = 0; i<subjects.size(); i++){
classes.add(new Class(subjects.get(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++){
posHours.add(profesorsThatCanTeachThis.get(i).getHours());
}
for(int x = 0; x<posHours.size();x++){
for(int p = 0; p< posHours.get(x).length;p++){
poshours.add(posHours.get(x)[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][3]= "mad";
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.
