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
%**************************************************************************
Sutrisno W. Ibrahim 
Pingback: Kuliah Artificial Intelligence (Kecerdasan Buatan) | Sutrisno W. Ibrahim