I have being trying to implement GA in java. please ccan anyone guid me on how to go about implementing it for a school that offer 13 subjects with 8 periods per day for 5days. They have 7 staffs of which some of them teach morethan one (1) subjects and some of this subject has workloads. with about 3 sections.

if you need to see what i have being doing i can attached some of the source code.

Thank you in advance

Am not sure if what i have done below is actual implementation of GA but when you run the TestGA.java it generate a timetable for 5days and replace any subject with "-" that exceed 5times per week. some of the challenge is how do i restrain this subject to their workload time and if realy what am doin is makin any scence towards GA.

thanks

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Algo;

import java.util.*;

/**
 *
 * 
 */
public class ChromosomeObj {

    private double score = 0.0; 
    private Set<SubjectTeacher> unschedulegensSetobj;
    private SubjectTeacher[] arrayunschedulegens;    
    public List<SubjectTeacher> subjectTeaherList = new ArrayList<>();
    private SubjectTeacher[] genObj = new SubjectTeacher[8];
    private List<SubjectTeacher>  genObjList = new ArrayList<SubjectTeacher>();

    public ChromosomeObj(SubjectTeacher[] arraySubjectTeacher, 
            List<SubjectTeacher> stList) {

        this.subjectTeaherList = stList;
        this.genObj = arraySubjectTeacher;

        //convert to list
        genObjList.addAll(Arrays.asList(arraySubjectTeacher));

        this.unscheduleGensObj();
        this.repairChromoObj();
    }

    public ChromosomeObj(SubjectTeacher[] arraySubjectTeacher) {
        this.genObj = arraySubjectTeacher;
        genObjList.addAll(Arrays.asList(arraySubjectTeacher));
    }

    //chromo shouldn't contain duplicate subject
    private void repairChromoObj() {

        Map<SubjectTeacher, Integer> map = new HashMap<>();
        Random rand = new Random();

        for (SubjectTeacher g : genObj ) {

            if(map.containsKey(g)){
                int count = map.get(g);
                map.put(g, count+1);
                //System.out.println(g.subjectName + "counts: "+ map.get(g));
            }else
                map.put(g, 1);
                //System.out.println(g.subjectName + "counts: "+ map.get(g));
        }


        for(SubjectTeacher s : map.keySet()) {

            int count = map.get(s);

            if(count > 1)
            {
                count--;
                for( int g=0; g<count; g++) {

                    int index = genObjList.indexOf(s);
                    int randun = rand.nextInt( arrayunschedulegens.length);
                    SubjectTeacher newshedule = arrayunschedulegens[randun];

                    while( newshedule == null ){
                        randun = rand.nextInt(arrayunschedulegens.length);
                        newshedule = arrayunschedulegens[ randun];
                    }

                    genObjList.set(index, newshedule);
                    arrayunschedulegens[randun] = null;
                }

            }
        }
        //put back to array
        genObj = (SubjectTeacher[]) genObjList.toArray(new SubjectTeacher[0]);


        //score chromo
        //scoreChromo();
    }

    private void scoreChromo() {
        Map<String, Integer> map = new HashMap<>();

        //number of clashes
        for (SubjectTeacher s : genObjList) {

        }

    }

    private void unscheduleGensObj() {  

        unschedulegensSetobj = new HashSet<SubjectTeacher>();        
        //iterate over the phenotype to check if any subject was excluded
        for(int p=0; p<subjectTeaherList.size()-1; p++) {
            SubjectTeacher pp = (SubjectTeacher) subjectTeaherList.get(p);

            if(!genObjList.contains(pp)) {
                unschedulegensSetobj.add(pp);
            }
        }

        arrayunschedulegens = unschedulegensSetobj.toArray(new SubjectTeacher[0]);
    }

    public SubjectTeacher[] getGenObj() {
        return genObj;
    }

    public void setGenObj(SubjectTeacher[] genObj) {
        this.genObj = genObj;
    }

    @Override
    public String toString(){

        StringBuilder str = new StringBuilder();

        for(int p=0; p<genObj.length; p++){
             str.append( genObj[p].getSubjectName()).append(",")   ;
         }

        return str.toString();
    }

}

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Algo;

import java.util.*;

/**
 *
 * @author hakeem
 */
public class Population {

    private int periods = 8;
    private int days = 5;
    public int popsize = 5;
    private double mutateratio = .001;
    private double crossRate = .7;    


    public List<ChromosomeObj> populations = new ArrayList<>();
    public List<ChromosomeObj> newpopulations = new ArrayList<>();

    public List<ChromosomeObj> clashChromo = new ArrayList<>();

    private Map<SubjectTeacher, Integer> mapTeacherWorklaod; 

    public List subjectTeachers = new ArrayList<>();
    public SubjectTeacher[] arraySubjectTeacher;

    public int popfitness = 0;
    private Random rand = new Random();
    public  String[] phenotypes = {"math","phy","chem","bio","geo", "agric", "comm", 
        "acct", "hausa", "td"};

    public List<String> phenotypesList = new ArrayList<String>();

    public Population (List<SubjectTeacher> sts) {
        this.subjectTeachers = sts;
        this.arraySubjectTeacher =  sts.toArray(new SubjectTeacher[0]);

    }

    public Population() {

        phenotypesList.addAll(Arrays.asList(phenotypes));


    }

    public int getChromLen() { return populations.size(); }
    public List<ChromosomeObj> getPop() { return populations; }

    public Map<SubjectTeacher, Integer> getMapSubjectWorkload() {
        return this.mapTeacherWorklaod;
    }

     public List<ChromosomeObj> genPopulationObj() {
        SubjectTeacher[] gens;
        populations.clear();
        List<SubjectTeacher> subTeachList = subjectTeachers;
        initializeMapTeachWrd(subjectTeachers);

            for(int d=0; d<popsize; d++) {  

                gens = new SubjectTeacher[periods];
                for( int p=0; p<periods; p++) {
                    gens[p] = subTeachList.get(rand.nextInt(subTeachList.size()));
                    setWorkload(gens[p]);
                }

                populations.add( new ChromosomeObj( gens, subjectTeachers ) );

            } //end loop

        return populations;

    }

    public void genPopulation(){
        String[] gens;
        //int len = phenotypes.length;

        for( int pz= 0; pz<1; pz++){

            for(int d=0; d<periods; d++){

                gens = new String[periods];

                for( int p=0; p<periods; p++){
                    gens[p] = phenotypes[ rand.nextInt(phenotypes.length ) ];

                }

                //populations.add( new Chromosomes( gens, phenotypesList ) );
            }

        }
        //cal fitness of population
        calpopFitness(populations);

    }

    public int calpopFitness(List<ChromosomeObj> p){

        return popfitness;

    }

    //picking 2 rows from the list and checking if subject fails thesam periods
    public int detectConflict(List<ChromosomeObj> chroms) {
         int counters = 0;
         boolean isClashing;
         //System.out.println( "Chromosize: "+ chroms.size());
         Map<String, Integer> map = new HashMap<>();  

         SubjectTeacher[] subTeacherBottom;

         for( int i=0; i<chroms.size(); i++) {
             if( i > (chroms.size()-2)  ) break;
             //System.out.println("i: "+ i);
             isClashing = false;
             SubjectTeacher[] subTeacherCurrent =  chroms.get(i).getGenObj();

             //compare with bottom row             
             for(int j=0; j<periods; j++) {                  
                    columnClash(map, subTeacherCurrent[j].getSubjectName() );
                    subTeacherBottom = chroms.get(i+1).getGenObj();
                    if( subTeacherCurrent[j].equals(subTeacherBottom[j])) {


                        isClashing = true;
                        counters++;
                    }

            }

            if(isClashing) {
                clashChromo.add( chroms.get(i) );
                clashChromo.add( chroms.get(i+1));
            }
         }



        return counters;
    }


    //total workload for teacher per week
    public Map<SubjectTeacher, Integer> teachersWorklaod(List<ChromosomeObj> chroms) {        
        Map<SubjectTeacher, Integer> load = new HashMap<>();         
         for(int i=0; i<chroms.size(); i++) {

             SubjectTeacher[] subTeacherCurrent =  chroms.get(i).getGenObj();

             for(SubjectTeacher subj : subTeacherCurrent) {
                 if(load.containsKey(subj)) {
                     int counter = load.get(subj);
                     load.put(subj, counter+1);
                 }else {
                     load.put(subj, 1);
                 }
             }
         }


         return load;

    }


    public Map<SubjectTeacher, Integer> initializeMapTeachWrd(List<SubjectTeacher> sub) {

        mapTeacherWorklaod = new HashMap<>();   
        for( SubjectTeacher subT : sub) {
            mapTeacherWorklaod.put(subT, 0);
        }
        return mapTeacherWorklaod;
    }

    public int getWorkload(SubjectTeacher sub) {

        return mapTeacherWorklaod.get(sub);
    }

     public void setWorkload(SubjectTeacher sub) {

        int count = mapTeacherWorklaod.get(sub);
        mapTeacherWorklaod.put(sub, count+1);
    }

     public int totalWrkload() {
         int count =0;
         for(SubjectTeacher teacher : mapTeacherWorklaod.keySet()) {
             count += mapTeacherWorklaod.get(teacher);
         }
         return count;
     }

    public int checkWorkload(Map<SubjectTeacher, Integer> mapWorkload) {

         int counter = 0;
         for(SubjectTeacher teacher : mapWorkload.keySet()) {

             if(mapWorkload.get(teacher) > teacher.getWorkload()) {
                 counter++;
             }
             //System.out.println("Wrkload: " +mapWorkload.get(teacher) + teacher.getSubjectName());
         }

         //System.out.println("workload Fitness: "+ counter);
         return counter;
    }


    public void displayWorkload(Map<SubjectTeacher, Integer> mapWorkload) {
        for(SubjectTeacher teacher : mapWorkload.keySet()) {
             System.out.println("Wrkload: " +mapWorkload.get(teacher) + teacher.getSubjectName());
         }
    }

    public void displayPop( List<ChromosomeObj> chromos)
    {
        System.out.println("--------Printing--------");
        for (Iterator it = chromos.iterator(); it.hasNext();) {
            ChromosomeObj c = (ChromosomeObj) it.next();
            System.out.println(c);
        }

        //System.out.println("Total clash: "+ this.popfitness );
    }


    public List<ChromosomeObj> crossOverObj(List<ChromosomeObj> chroms) {
        newpopulations.clear();
        SubjectTeacher[] c1;
        SubjectTeacher[] c2;

        int halfsize = periods/2;

        SubjectTeacher[] gench1 = new SubjectTeacher[periods];
        SubjectTeacher[] gench2 = new SubjectTeacher[periods];

        for(int size = 2; size < chroms.size(); size+=2) {
            int counter = 0;

            c1 = chroms.get(size-1).getGenObj();
            c2 = chroms.get(size).getGenObj();

            for( int p = periods-1; p >= 4; p--) {

                gench1[counter] =  c1[p];
                gench2[counter]  = c2[p];
                counter++;
            }

            for( int p= 0;  p<halfsize; p++) {

                gench1[counter]= c1[p];
                gench2[counter] = c2[p];
                counter++;
            }

            ChromosomeObj child1 = new ChromosomeObj(  gench1, subjectTeachers );
            ChromosomeObj child2 = new ChromosomeObj( gench2, subjectTeachers );

            newpopulations.add(child1);
            newpopulations.add(child2);
        }


        int sizerem = chroms.size()-1;
        if(sizerem > 0)    newpopulations.add(chroms.get(sizerem));

        return newpopulations;

    }

    public List<ChromosomeObj> mutate(List<ChromosomeObj> chromos, 
            Map<SubjectTeacher, Integer> mapWorkload) {
            List<ChromosomeObj> chromosLocal = new ArrayList<>();
            List<ChromosomeObj> copyOfChromo = chromos;
            ChromosomeObj newChromo;        
            for(SubjectTeacher teacher : mapWorkload.keySet()) {

                if(mapWorkload.get(teacher) > teacher.getWorkload()) {
                    int rr = mapWorkload.get(teacher) - teacher.getWorkload();                    
                    for(int i=chromos.size()-1; i>0; i--) {
                        if(rr==0) break;
                        chromos = copyOfChromo;
                        SubjectTeacher[] subTeacher = (SubjectTeacher[])chromos.get(i).getGenObj();
                        SubjectTeacher[] copSubTeacher = subTeacher;
                        for(int j=0; j<subTeacher.length; j++) {
                            //if equal chromo
                            if(teacher.equals(subTeacher[j])) {
                                SubjectTeacher subObj = subTeacher[j];
                                subObj.setSubjectName("-");
                                copSubTeacher[j] = subObj;
                                //chromos.get(i).setGenObj(copSubTeacher);
                                newChromo = chromos.get(i);
                                chromosLocal.add(newChromo);
                                rr--;
                                break;
                            }
                        }
//                        rr--;
                    }
                }
         }

        return chromos;
    }
    public Chromosomes mutate( Chromosomes c1 )
    {
        return c1;
    }

    public Chromosomes selectMember(List<Chromosomes> p){
        Chromosomes c;
        for( int x=0; x<p.size(); x++){
             c =  p.get(x);
            if (c.getChromoScore() < 4 ){
               p.remove(x);
                return c;
            }


        }

        c = p.get( populations.size()-1 );
        p.remove(populations.size()-1);
        return c;
    }



    @Override
    public String toString(){        
        return String.valueOf(popfitness);
    }

}


/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Algo;

import java.util.Objects;

/**
 *
 * @author hakeem
 */
public class SubjectTeacher {

    private  String subjectName;
    private final String teacherName;
    private  int workload;

    public SubjectTeacher(String sname, String tname, int workload) {
        this.subjectName = sname;
        this.teacherName = tname;
        this.workload = workload;
    }

    public void setSubjectName(String subjectName) {
        this.subjectName = subjectName;
    }

    public void setWorkload(int workload) {
        this.workload = workload;
    }



    public String getSubjectName() {
        return subjectName;
    }

    public String getTeacherName() {
        return teacherName;
    }

    public int getWorkload() {
        return workload;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final SubjectTeacher other = (SubjectTeacher) obj;
        if (!Objects.equals(this.teacherName, other.teacherName)) {
            return false;
        }
        return true;
    }

    @Override
    public int hashCode() {
        int hash = 3;
        hash = 53 * hash + Objects.hashCode(this.teacherName);
        return hash;
    }    
}


/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Algo;

import java.util.ArrayList;
import java.util.List;

public class TestAlgo {

    public  int periods = 8;
    public  String[] phenotypes = {"math","phy","chem","bio","geo", "agric", "comm", 
    "acct", "hausa", "td"};
    List subjTeacherList = new ArrayList<>();

    public TestAlgo() {

        createSubjectTeacher();
        List<ChromosomeObj> pop;
        List<ChromosomeObj> genPop = new ArrayList<>();

        Population p = new Population(subjTeacherList);        
        pop = p.genPopulationObj();
        pop = p.crossOverObj(pop);
        int subConflict = p.detectConflict(pop);

        int genConfilict = 0;
        int counter = 0;

        while(subConflict!=0) {

            //local
            pop = p.genPopulationObj();  
            pop = p.crossOverObj(pop);
            subConflict = p.detectConflict(pop);
            //System.out.println("conflict: "+ p.detectConflict(pop));
            //workloadMeasure = p.checkWorkload(p.teachersWorklaod(pop));
            counter++;
        }
        p.displayPop(pop);
        int workloadMeasure = p.checkWorkload(p.teachersWorklaod(pop));
        System.out.println("Workload_total: "+ workloadMeasure);
        p.displayWorkload(p.teachersWorklaod(pop));

           System.out.println("gen: "+ counter);

    }

    private void createSubjectTeacher() {

        int count = 0;

        for(String subject : phenotypes ) {

            subjTeacherList.add( new SubjectTeacher(subject, "teacher"+count, 4));

            ++count;
        }   

    }

    public static void main(String[] args)
    {
        new TestAlgo();
    }

}
This article has been dead for over six months. Start a new discussion instead.