Home » Programming » University exam scheduling using GA

University exam scheduling using GA

This code is my final project for one of my master course in KSU (course name:Computer Simulation of Engineering).  My project title is ” Systems Scheduling University Exam Using Genetic Algorithm: Study Case in ‎Electrical Engineering Department, King Saud University‎”. The code is long enough and maybe some parts is not clear (I did not give enough comment/descriptions). But, I hope by posting here maybe you will get benefit from it. [Contact me or write comment bellow if you have a question about the code]

Intro:

University exam scheduling is a complex problem since it has to be solved manually. Where scheduling is done manually, conflict and unfairness are inevitable. In this work, we use Genetic Algorithm (GA) to solve the problem of scheduling exam for bachelor degree in Electrical Engineering Department, King Saud University. Two different form of GA are used in this work: Simple Genetic Algorithm (SGA) and Steady State Genetic Algorithm (SSGA). The simulation is carried out by using MATLAB. Base on the results, it is observed that the SSGA exhibit better performance than SGA for exam scheduling.  The population size must be coupled with increasing levels of problem complexity.

MATLAB CODE

File: main.m

%**************************************************************************

%        Scheduling University Exam Using Genetic Algorithm: Study Case

%            in Electrical Engineering Dept., King Saud University

% ————————————————————————-

% By     : Sutrisno

% Contact: sutrisno_link@yahoo.com             Last update: May 31, 2011

% ————————————————————————-

% This program is developed to generate schedule for university exam using

% Simple Genetic Algorithm (SGA) and Steady State Genetic Algorithm (SSGA)

%

% There are 4  parts in this program:

% 1. Main program of GAs (main.m)

% 2. Function to read/determine input data (data.m)

% 3. Function for initialization (initialise.m)

% 4. Function to calculate fitness (fitness.m)

% 5. Function to perform selection (roulette.m)

% 6. Function to perform crossover (crossover.m)

% 7. Function to perform mutation(mutation.m)

% 8. Function to print the results and generate schedule (printresults.m)

%

% Inputs (data.m):

% n_courses : number of courses

% “courses” : is a 47×2 matrix contain information about level(semester)

%             and field study on each subject/course. 1=EPE,2=CEE,3=general.

% n_section : number of sections/classes

% “sections”: is a 60×2 matrix contain information about course and lecturer

%             on each section/class

% n_lecturer: number of lecturer

% n_days    : number of days available for exam

% n_session : number of slots/session per day for exam

% n_rooms   : number of rooms available for exam

% n_slots   : number of total slots available for exam

%

% Outputs:

% bestshedule  : matrix 1×60 represent the best gererated schedule

% finalpenalty : matrix 1×5 record all penalty for the gererated schedule

% finalfitness : value that represent the goodness of schedule

%**************************************************************************

%**************************************************************************

%                   The Program Start Here

%*————————————————————————

function [finalfitness bestshedule finalpenalty]=main()

clc;

clear;

% parameters for shedulle

[n_courses courses n_section sections n_lecturer n_rooms n_days n_slots]=data();

% parameters for GA

popsize=500;

stringlength=n_section;

pc=0.95;

pm=0.2;

ipop=initialise(popsize,stringlength,n_slots);

%———————————————————————–

pop=ipop;

maxitr=150;

for itr=1:maxitr

% Fitness calculation

[fitnessvalue, penalty]=fitness(pop,courses,sections,n_days);

% Selection

% In steady state selection, big part of chromosomes should survive to next

% generation. In every generation is selected a few (good – with high

% fitnesschromosomes for creating a new offspring. Then some (bad – with

% low fitness) chromosomes are removed and the new offspring is placed in

% their place. The rest of population survives to new generation. In this

%   case we use 1/4 from total population as selected parent)

n_parents=0.75*(popsize-mod(popsize,4)); % to make sure interger

%        n_parents=popsize;

if mod(n_parents,2)==1,n_parents=n_parents+1;end % to make sure even

[selectedparent]=roulette(pop,fitnessvalue,n_parents);

% crossover

parent1=selectedparent(1:n_parents/2,:);

parent2=selectedparent(n_parents/2+1:n_parents,:);

[child1, child2]=crossover(parent1, parent2, pc);

children(1:n_parents/2,:)=child1;

children(n_parents/2+1:n_parents,:)=child2;

% New generation

[xx index]=sort(fitnessvalue);

for j=1:n_parents

% replace bad individues

pop(index(j),:)=children(j,:);

end

% mutation

[pop]=mutation(pop, pm,n_slots);

% record best fitness and individu each iteration

[bestfitness(itr) indbest(itr)]=max(fitnessvalue);

[averagefitness(itr)]=mean(fitnessvalue);

bestiindividu(itr,:)=pop(indbest(itr),:);

penalties(itr,:)=penalty(indbest(itr),:);

[averagepenalty(itr)]=mean(penalty(:,1));

end

%———————————————————————–

% determine the optimal value and optimal x

[finalfitness idx]=max(bestfitness);

[bestshedule]=bestiindividu(idx,:);

[finalpenalty]=penalties(idx,:);

% Plot average of fitness

subplot(1,2,2);

p1=plot(1:maxitr,averagefitness);

xlabel(‘Iteration’);

ylabel(‘Average Fitness’);

axis([0 maxitr 0 1]);

set(p1,’Color’,’blue’)

hold (subplot(1,2,2), ‘on’);

% Plot average of penalty

subplot(1,2,1);

p2=plot(1:maxitr,averagepenalty);

xlabel(‘Iteration’);

ylabel(‘Average penalty’);

set(p2,’Color’,’blue’)

hold (subplot(1,2,1), ‘on’);

% Print results

printresults(bestshedule,finalfitness,finalpenalty);

end

%**************************************************************************

%                   Ending of Program

%**************************************************************************

 

File: data.m

%**************************************************************************

%       Function to read/determine input data (data.m)

%————————————————————————–

function [n_courses courses n_section sections n_lecturer n_rooms n_days n_slots]=data()

% number of courses

n_courses=47;

% “courses” is a 47×2 matrix contain information about level(semester)

% and field study on each subject/course. 1=EPE,2=CEE,3=general.

courses=[3 3;4 3;4 3;4 3;4 3;5 3;5 3;5 3;5 3;5 3;6 3;6 3;6 3;6 3;6 3;6 3;…

6 3;7 2;7 1;7 1;7 1;7 2;7 1 ;7 1;8 1;8 2;8 2;8 1;8 2;8 1;8 1;8 1;…

8 1;9 2;9 1;9 2;9 1;9 2;9 1;9 2;9 2;10 1;10 1;10 2;10 1;10 2;10 1];

% number of sections/classes

n_section=60;

% “sections” is a 60×2 matrix contain information about course and lecturer

% on each section/class

sections=[42 15;34 36;2 7;2 41;2 16;2 42;6 7;6 8;25 38;26 24;26 26;11 17;…

27 19;27 32;7 16;3 5;12 17;12 19;28 23;29 31;43 37;8 12;8 13;13 14;…

13 15;30 27;44 13;18 4;35 19;36 25;19 25;45 35;14 9;14 10;15 23;20 22;…

31 13;37 12;1 1;1 2;1 3;21 20;9 17;46 40;4 11;22 22;38 34;32 28;…

33 28;5 4;10 6;23 21;24 24;16 29;16 30;39 23;40 39;17 4;41 33;47 8];

% number of lecturer

n_lecturer=42;

% number of days available for exam

n_days=17;

% number of slots/session per day for exam

% session 1: 08.00-11.00 a.m

% session 2: 01.00-04.00 p.m

% session 1: 06.00-09.00 p.m

n_slots_per_day=3;

% number of rooms available for exam

n_rooms=11;

% number of total slots available for exam

% |<——————- day 1 <——————-| …..  |<– day 17 –>|

% |<—- session 1 —-> … |<—- session 3 —>|

% |room 1| … |room 11|     |room 1| … |room 11|

% |slot 1||slot 2|<——————- ….. ——————->|slot 561|

n_slots=n_days*n_slots_per_day*n_rooms;

end

%**************************************************************************

%                   Ending of Function

%**************************************************************************

 

File: initialise.m

%**************************************************************************

%           Function for initialization (initialise.m)

%————————————————————————–

function [pop]=initialise(popsize,stringlength,n_slots)

% Use real number encoding

% The generated numbers are between 1 and n_slots

% Stringlength is equal to number of sections to be sheduled

pop=round(rand(popsize, stringlength)*(n_slots-1)+1);

end

%**************************************************************************

%                   Ending of Function

%**************************************************************************

 

File: fitness.m

%**************************************************************************

%             Function to calculate fitness (fitness.m)

%————————————————————————–

function [fitnessvalue penalty]=fitness(pop,courses,sections,n_days)

[popsize,stringlength]=size(pop);

for i=1:popsize

% Extract day,session and room number for each section and save in matrix

% extractslots. Matrix extractslots is 67×3 matrix

%              |day|session|room|

%              ——————

% section 1    |   |       |    |

%     :        |   |       |    |

%     :        |   |       |    |

% section 67   |   |       |    |

%              —————— 67×3

extractslots=ones(stringlength,3);

for j=1:stringlength

%   day,session,room

x=pop(i,j);

xx=mod(x,33); if xx==0, xx=33;end

day=((x-xx)/33)+1;

extractslots(j,1)=day;

xxx=mod(xx,11); if xxx==0, xxx=11;end

session=((xx-xxx)/11)+1;

extractslots(j,2)=session;

room=xxx;

extractslots(j,3)=room;

end

% Checking penalty each individu :

% at first time set penalty=0

tpenalty=0;slotsclashes=0;coursesclashes=zeros(n_days,14);studentclashes=0;scatteredexam=0;

instructorsclashes=0;

% Checking

for a=1:stringlength

courseA=sections(a,1);

instructorA=sections(a,2);

levelA=courses(courseA,1);

fieldstudyA=courses(courseA,2);

dayA=extractslots(a,1);

sessionA=extractslots(a,2);

roomA=extractslots(a,3);

for b=a+1:stringlength

courseB=sections(b,1);

instructorB=sections(b,2);

levelB=courses(courseB,1);

fieldstudyB=courses(courseB,2);

dayB=extractslots(b,1);

sessionB=extractslots(b,2);

roomB=extractslots(b,3);

% 1. Check, are there clashes slots for each section?

% That mean a certain room hold two or more different

%         % exam at a time. Give 100 penalty each clash

if (dayA==dayB)&(sessionA==sessionB)&(roomA==roomB)

tpenalty=tpenalty+100;

slotsclashes=slotsclashes+1;

end

%

% 2. Check, each student has at most two exams at a day.

% That mean sections (or courses) that offered at same level

% /semester must be hold at different day.

% Give 100 penalty each clash

if (dayA==dayB),

if (levelA==levelB)&&(fieldstudyA==fieldstudyB),

if fieldstudyA==2, levelA=levelA+4;end %1-6 general,7-10 EPE,11-14 CEE

coursesclashes(dayA,levelA)=coursesclashes(dayA,levelA)+1;

if coursesclashes(dayA,levelA)>2,

studentclashes=studentclashes+1;

tpenalty=tpenalty+100;

end

end

end

% 3. Check, different sections for one course must be hold at the

% same day and session. If not satisfied give 100 penalty.

if courseA==courseB

if (dayA==dayB)&&(sessionA==sessionB),

else

tpenalty=tpenalty+120;

scatteredexam=scatteredexam+1;

end

end

% 4. Check, instructor/lecturer just has one exam each day. If

% not satisfied give 10 penalty (soft constrain).

if (instructorA==instructorB)&&(dayA==dayB)

instructorsclashes=instructorsclashes+1;

if instructorsclashes>2, tpenalty=tpenalty+10; end

end

end

end

% Save fitness and penalty

% fitness value will be in [0 100%]

fitnessvalue(i)=100/(1+tpenalty);

penalty(i,1)=tpenalty;

penalty(i,2)=slotsclashes;

penalty(i,3)=studentclashes;

penalty(i,4)=scatteredexam;

penalty(i,5)=instructorsclashes;

end

end

%**************************************************************************

%                   Ending of Function

%**************************************************************************

 

File: roulette.m

%**************************************************************************

%           Function to perform selection (roulette.m)

%————————————————————————–

function [selectedpop]=roulette(oldpop,fx,n_parent)

[popsize,stringlength]=size(oldpop);

totalfit=sum(fx);

prob=fx/totalfit;

% Roultte Wheel

for selectedin=1:n_parent

r=rand;

s=0;

for k=1:popsize

s=s+prob(k);

if r<=s

selectedpop(selectedin,:)=oldpop(k,:);

break

end

end

end

end

%**************************************************************************

%                   Ending of Function

%**************************************************************************

 

File: roulette.m

%**************************************************************************

%           Function to perform selection (roulette.m)

%————————————————————————–

function [selectedpop]=roulette(oldpop,fx,n_parent)

[popsize,stringlength]=size(oldpop);

totalfit=sum(fx);

prob=fx/totalfit;

% Roultte Wheel

for selectedin=1:n_parent

r=rand;

s=0;

for k=1:popsize

s=s+prob(k);

if r<=s

selectedpop(selectedin,:)=oldpop(k,:);

break

end

end

end

end

%**************************************************************************

%                   Ending of Function

%**************************************************************************

 

File: crossover.m

%**************************************************************************

%         Function to perform crossover (crossover.m)

%————————————————————————–

function [child1, child2]=crossover(parent1, parent2, pc)

[popsize,stringlength]=size(parent1);

if (rand<pc)

cpoint=round(rand*(stringlength-1))+1;

child1=[parent1(:,1:cpoint) parent2(:,cpoint+1:stringlength)];

child2=[parent2(:,1:cpoint) parent1(:,cpoint+1:stringlength)];

else

child1=parent1;

child2=parent2;

end

end

%**************************************************************************

%                   Ending of Function

%**************************************************************************

 


 

File: mutation.m

%**************************************************************************

%            Function to perform mutation(mutation.m)

%————————————————————————–

function [child]=mutation(parent, pm, n_slots)

[popsize,stringlength]=size(parent);

child=parent;

for i=1:popsize

if (rand<pm)

mpoint=round(rand*(stringlength-1))+1;

child(i,mpoint)=round(rand*(n_slots-1)+1);

end

end

end

%**************************************************************************

%                   Ending of Function

%**************************************************************************

 

File: printresults.m

%**************************************************************************

%       Function to print the results and generate schedule

%————————————————————————–

function printresults(schedule,fitness,penalty)

[~, schedulelength]=size(schedule);

% Extract day,session and room number for each section and save in matrix

% extractslots. Matrix extractslots is 67×3 matrix

%              |day|session|room|

%              ——————

% section 1    |   |       |    |

%     :        |   |       |    |

%     :        |   |       |    |

% section 67   |   |       |    |

%              —————— 67×3

extractslots=ones(schedulelength,3);

for j=1:schedulelength

%   day,session,room

x=schedule(j);

xx=mod(x,33); if xx==0, xx=33;end

day=((x-xx)/33)+1;

extractslots(j,1)=day;

xxx=mod(xx,11); if xxx==0, xxx=11;end

session=((xx-xxx)/11)+1;

extractslots(j,2)=session;

room=xxx;

extractslots(j,3)=room;

end

disp(‘Schedule :’)

for day=1:14

fprintf(‘\nDay  = %d’,day);

for session=1:3

fprintf(‘\n session  = %d’,session);

for section=1:60

if (extractslots(section,1)==day)&&(extractslots(section,2)==session),

fprintf(‘\n section:%d  room: %d’,section,extractslots(section,3));

end

end

end

end

fprintf(‘\nTotal penalty       = %d’,penalty(1));

fprintf(‘\nSlots clashes       = %d’,penalty(2));

fprintf(‘\nStudent clashes     = %d’,penalty(3));

fprintf(‘\nScattered exam      = %d’,penalty(4));

fprintf(‘\nInstructors clashes = %d’,penalty(5));

fprintf(‘\nFitness             = %d’,fitness);

end

%**************************************************************************

%                   Ending of Function

%**************************************************************************

One thought on “University exam scheduling using GA

  1. Pingback: Kuliah Artificial Intelligence (Kecerdasan Buatan) | Sutrisno W. Ibrahim

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s