Transcript FINAL EXAM SCHEDULER

FINAL EXAM SCHEDULER
(FES)
By
Ersan ERSOY
(Engineering Project)
Advisor: Assist.Prof.Dr. Ender ÖZCAN
Department of Computer Engineering
Faculty of Engineering & Architecture
Yeditepe University
Outline
•
•
•
•
•
•
Timetabling Problem
Timetabling Markup Language (TTML)
Genetic Algorithms (GAs)
Implementation
Experiments
Conclusion & Future Work
2
Timetabling Problem
• Assignment of variables (courses, exams etc.) to
some specific domains (time slots, rooms, etc)
based on various constraints.
• NP-complete problem.
• Hard and soft constraints.
3
Examination Timetabling
•
Represented as (V, D, C)
–
–
–
•
Constraint classifications :
–
–
–
–
–
•
V contains variables (exams),
D contains domains (time slots , rooms),
C contains constraints.
Edges.
Preset and exclusions.
Ordering.
Event-spread.
Capacity.
Aim in this project is to assign exams to time
slots.
4
Solution Approaches
•
•
•
•
•
Human based techniques.
Random search.
Simulated annealing.
Tabu search.
Evolutionary algorithms.
5
Timetabling Markup Language (TTML)
•
Standard representation for timetabling problems.
•
Based on XML and MathML
•
Consists of three parts.
–
–
–
Input-data.
Output.
Test-results.
6
TTML (Cntd.)
•
Input-data
–
–
–
–
–
–
Author.
Description.
References.
Variables.
Domains.
Constraints.
• Classifiers
• Hard
• Soft
7
TTML (Cntd.)
•
Classifiers
–
–
•
Base
Parent
Projection
–
–
–
Self
Child
Single
8
TTML (Continues)
•
Supports 11 different constraint functions.
–
–
–
–
–
–
–
–
–
–
–
notsame
nooverlap
preset
exclude
ordering
eventspr
fullspr
freespr
chksum
attrcomp
resnoclash
9
Genetic Algorithms (GAs)
•
•
•
GAs were introduced by J. Holland.
Member of Evolutionary Algorithms (EAs)
Simply explained as :
–
–
Set i to 0 and randomly generate an initial population (P(i))
Do until break criteria is satisfied
•
•
•
Evaluate the fitness of each individual
Select parents of the next generation from P(i) according to
their fitness
Produce new offspring by using crossover and mutation
operators and put them into P(i+1),set i to i+1
10
Components of GAs (Cntd.)
•
•
•
•
Chromosomes.
Gene.
Population.
Representation
– Binary encoding.
– Real value encoding.
•
Initializing Population
11
Components of GAs (Cntd.)
•
Evaluating chromosomes
– Fitness function.
•
Mate Selection.
– Fitness-based selection
– Rank-Based selection
– Tournament Selection
12
Components of GAs (Cntd.)
•
One-point Crossover
13
Components of GAs (Cntd.)
•
Two-point Crossover
14
Components of GAs (Cntd.)
•
Uniform Crossover
15
Components of GAs (Cntd.)
•
Mutation
– Randomly alters the values of genes of a chromosome
after crossover.
•
Replacement Strategy
– Trans-generational Genetic Algorithms.
– Steady-State Genetic Algorithms.
•
Elitism
16
Components of GAs (Cntd.)
•
GA Parameters
– Crossover probability.
– Mutation probability.
– Population size.
17
GAs (Cntd.)
•
Memetic Algorithms (MAs)
– In GAs, crossover and mutation usually performs
solutions near the local optima
– Memetic Algorithms (MAs) can be explained as
hybridization of GA and local search algorithms.
– Gene in GAs is called meme in MAs.
18
Implementation
•
Three different programs are implemented.
–
–
–
CONFETI generates examination problem data in
TTML format.
Final Exam Scheduler (FES) that takes problem input
in TTML format and finds the optimum solution.
FESViewer is implemented to view the output of FES
19
Implementation (CONFETI)
– Java applet.
– Support generating TTML documents for examination
timetabling problem.
– Consists:
•
•
•
•
Description
Domain
Variable
Classifiers
–
–
•
•
•
Students
Curriculum
Base Classifiers
Constraints
Capable of loading TTML documents
20
Implementation (FES)
– Java application
– Solves examination problems.
– Deals with different types of constraints that can be
converted to TTML form by CONFETI.
21
FES
•
Getting TTML Document and Basic Data
Structures.
–
–
–
–
Each course (variable) in TTML document stored in a
class (Variable) that contains duration (length of the
exam), number students, list of hard domain slots, list
of soft domain slots.
Hard domains are initialized according to hard preset
and exclude constraints.
Soft domains are initialized according to soft preset and
exclude constraints.
This class contains a function that returns random slots
according to hard and soft domain for each course.
22
FES
•
Getting TTML Document and Basic Data
Structures.
– Each student information, student id and courses that
he takes, are stored in memory after reading from input
in a array of array form with a length of student
number.
23
FES
•
Getting TTML Document and Basic Data
Structures..
–
–
–
–
FES supports nine types of constraints that CONFETI
supports. But it does not support every combination of
these constraints. The set of constraints that FES
generally does not support is:
Constraints with parent classifiers other than Students
parent classifier.
Constraints which take two base classifiers as
arguments.
For eventspr, constraints that have compare value
other than ‘<’ .
24
FES
•
Getting TTML Document and Basic Data
Structures..
– If a preset or exclude constraint is defined to a course
than, modifications are implemented on the hard and
soft domains of the courses.
– If two courses must have same slot, same slot
references are given to them.
25
FES
•
Algorithm
– A Memetic algorthm is used.
– Representation
•
Each meme contains assigned slot number of an exam.
– Evaluating chromosomes
•
Fitness function
Where w i is the weight of the
constraint ci.
26
FES
•
Algorithm
– Initializing Population
•
•
Random
With hill climbing.
– Mate Selection
•
Fitness-based selection
•
Rank based Selection
•
Tournament Selection
– Crossover
•
•
•
One-point
Two-point
Uniform
27
FES
•
Mutation
– Random
– Random & Swap
•
Hill Climbing
– Each constraint has an hill climbing function to
improve its fitness except for eventspr and some
combinations.
28
FES
•
Hill Climbing
–
Pseudo code for hill climbing function of notsame
•
If there exits a violation between course A and B
– Set counter to 0
– While counter is less than 10
» Get a random slot for B
» if violation is improved
» return;
» Increment counter by one.
– Set counter to 0
– While counter is less than 10
» Get a random slot for A
» if violation is improved
» return;
– Increment counter by one.
29
FES
•
Hill Climbing
– Two hill climbing algorithm is defined
•
HCA1
– A chromosome is selected by using tournament selection.
And hill climbing functions of all defined constraints is
applied .
30
FES
•
Hill Climbing
– HCA2
•
Select a chromosome by tournament selection
–
–
–
–
–
–
–
–
–
Step1. Select a constraint
Use hill climbing function to whole chromosome
If individual is improved go to Step1.
Step2. Select a constraint
Use hill climbing function to a part of chromosome
If individual is improved go to Step2.
Step3. Select a constraint
Use hill climbing function to one gene of chromosome
If individual is improved go to Step3.
31
FES
•
Replacement strategy
– Steady-state
– Trans-generational
•
Other Features & User Interfaces
– GA parameters, operator types, weight of constraints
can be entered.
– Any time, output ( examination schedule) can be
viewed in student, department and faculty view and can
be saved for examining later by FESViewer.
32
Implementation(FESViewer)
• Java application.
• Displays the output of FES.
33
Experiments
•
Experimental data
– Yeditepe University, Faculty of Engineering and
Architecture, 2004 second semester, final exam data are
used in the experiments.It consists of 443 courses,
1169 students
– Constraints
•
•
•
•
•
No students must have two exams in one slot (hard).
Students must have maximum 2 courses per day (hard).
Each section of the courses has to be assigned on the same slot
(Hard).
Students have at least one free slot between two exams in a day
(soft).
Also there are many preset and exclude constraints (hard or
soft).
34
Experiments
•
Experimental data
Hard constraints have a weight value of one and soft constraints
except for the fourth constraint have weight value of 0.01. Fourth
constraint’s weight is 0.075.
•
Constant parameters
35
Experiments
•
Variable parameters
Total of 24 different configuration
and 20 runs for each configuration is made.
36
Experiments
• Results
– Results are grouped by
the operator type to
make compare between
the types of each
operator.
37
Experiments
– Crossover
38
Experiments
– Mutation
39
Experiments
–
Mate Selection
40
Experiments
–
Hill Climbing
–
HCA1 with two-point crossover, random mutation, and
tournament selection can be best configuration.
41
Conclusion & Future Work
•
•
•
Experimental results show that hard constraints
are easily solved. But few soft constraint
violations remain.
An early configuration is made for the algorithm
by examining tests results
In future, CONFETI and FES can be modified to
support room assignments, and their constraints.
42
Any Questions?
43