This repository demonstrates how the Presentation Scheduling problem, which is analogous to the famous University Course Timetabling Problem (UCTP), can be solved using the Hybrid Genetic Algorithm-Simulated Annealing (HGASA) algorithm.
Ray Jasson
Yi Qing
24/07/2020
Presentation Scheduling problem, which is analogous to the famous University Course Timetabling Problem (UCTP), involves allocating a set of presentations and resources including speakers, supervisors and venues to different time slots while considering various constraints. Supervisors have different preferences including choosing to attend certain number of consecutive presentations, choosing number of days to complete all the presentations and deciding whether they want to change venue while attending consecutive presentations. The problem is defined according to the following groups:
n
presentations will be scheduled to m
slots in which each slot is a combination of a venue and a time slot. For example, the timetable below has a total of 10 slots for 2 venues:
Day | Venue | 0900-1000 | 1000-1100 | 1100-1200 | 1300-1400 | 1400-1500 |
---|---|---|---|---|---|---|
Monday | Room A | 1 | 2 | 3 | 4 | 5 |
Monday | Room B | 6 | 7 | 8 | 9 | 10 |
Each presentation is presented by a speaker and supervised by three supervisors. There are k
supervisors available. There are two types of constraints: hard constraints and soft constraints. Hard constraints cannot be violated to prevent generating an infeasible schedule, whereas soft constraints might be violated, however, the number of violations must be minimized.
In this repository, there are n = 118
presentations, m = 300
slots and k = 47
supervisors. There are 4 venues: Viva Room (VR), Meeting Room (MR), Interaction Room (IR) and BJIM Discussion Room (BJIM). Each day has 15 slots in which each slot lasts for 30 minutes. 300 slots are shceduled from Monday until Friday.
:unlock: Note that each slot is a combination of a venue and a timeslot.
There are 6 input files:
SupExaAssign.csv
specifies supervisors that are in charge of the presentationsHC03
specifies unavailable venuesHC04
specifies unavailable supervisors on specific slotsSC01
specifies supervisors' preferred number of consecutive presentationsSC02
specifies supervisors' preferred number of days to complete all the presentationsSC03
specifies supervisors' preferences of changing venue during consecutive presentations, yes
indicates supervisors prefer to attend consecutive presentations without changing venue, whereas no
indicates supervisors do not want to change venue while attending consecutive presentationsHybrid genetic algorithm-simulated annealing (HGASA) algorithm is the combination of genetic algorithm (GA) with simulated annealing as a local search method to accelerate the convergence speed. The figure below shows the flowchart of HGASA algorithm.
Flowchart of HGASA algorithm
Refer to hybrid_system
function in hybrid_system.py
for more details.
The initial set of candidate solutions and sets of constraints are represented using matrix. The matrices are generated using given data from input files and through the process of matrix multiplication. The figure below shows three required matrices that are generated through load()
function in data.py
.
From left, slot-by-presentation matrix, presentation-by-presentation matrix and supervisor-by-preference matrix
The slot-by-presentation
matrix is the chromosome in genetic algorithm and the candidate in simulated annealing. Other matrices are required by the penalty function for evaluation of penalty points. 0
indicates the slots are available, whereas -1
indicates the slots are unavailable due to the hard constraints. When initializing the population, 1
indicates a presentation has been assigned to a specific slot.
The penalty function is used to evaluate the fitness of the solution, which is the resulting presentation schedule. It is used to evaluate any violations of HC02
, SC01
, SC02
and SC03
. Each violation increases the penalty points by 10. The higher the penalty points, the lower the fitness of the solution.
:unlock: Note that if the number of consecutive presentations is less than the supervisor's preference, each difference will increase the penalty point by 1 in order to encourage the generated schedule to have consecutive presentations.
Refer to penalty_function.py
for more details.
Steady-state genetic algorithm is different from the generational genetic algorithm in which only two chromosomes are selected to undergo crossover and mutation to generate two children. Two worst chromosomes will be chosen from the population to be replaced by the new children. It updates the population in a piecemeal fashion rather than all at one time.
The size of population is initialized to 10 which is an adequate size considering the size of this presentation scheduling problem. A random slot is assigned to each presentation in a chromosome. Note that the slots are assigned in a way such that the schedule does not violate HC03
and HC04
. Empty slot indicates no presentation is assigned to this slot previously so HC01
and HC05
will not be violated. Each 1
s in the slot-by-presentation
matrix (chromosome) represents the assigned presentation in its respective slot. Penalty of chromosome is evaluated and added to the population of penalty points.
Refer to generate_chromosome
function in genetic_algorithm.py
and hybrid_system.py
for more details.
Tournament selection with tournament size of 2 is carried out twice. In each tournament selection, two random chromosomes are selected and the chromosome with the lowest penalty point among them is selected.
Refer to selection
function in genetic_algorithm.py
for more details.
Two-point crossover is carried out to reduce the probability of breaking up good pairs in the chromosome which is more frequent in one-point crossover and uniform crossover. The parent chromosomes selected in tournament selection exchange their presentations between the cutpoints to produce two new children. The figure below shows two parent chromosomes exchange their presentations between c1
and c2
to generate two new child chromosomes.
Crossover of two parent chromosomes
Repair is carried out after crossover in which the presentation is assigned to another available and empty slot if there are more than 1 presentations assigned for the slot. The purpose of this operation is to ensure HC01
and HC05
are not violated.
Refer to crossover
and repair
functions in genetic_algorithm.py
for more details.
Two random presentations have their slots exchanged. If both presentations have slots that are not exchangeable, indicating the slots are unavailable for either one of the presentation, another presentation and slot are selected randomly. The figure below shows the mutation process.
Mutation of a chromosome
Refer to mutation
function in genetic_algorithm.py
for more details.
Two chromosomes with the highest penalty points are replaced by two new child chromosomes generated through crossover and mutation. Their penalty points are updated as well.The maximum number of generations is set to be 100
generations in this case. In each generation, 6 processes are executed iteratively: selection, crossover, repair, mutation, penalty evaluation and replacement until the maximum generation is reached.
Refer to replacement
and reproduction
functions in genetic_algorithm.py
for more details.
Simulated annealing (SA) is used in HGASA algorithm as a local search algorithm. SA is a metaheuristic inspired by statistical physics. SA has the ability to avoid being trapped in local minima and it is proven that SA is able to find the global optimum if given infinite time.
The initial candidate of SA is the chromosome with the lowest penalty point from the previous GA. The basic procedure of SA is to generate neighbouring solutions and evaluate them. If the neighbouring solution generated is better than the best solution, the best solution is updated. If otherwise, the neighbouring solution is accepted based on a probability density function. The best solution will only be updated when the neighbouring solution is better than the best solution. A poor neighbouring solution will be accepted by probability as the candidate to generate a new neighbouring solution, but not as the best solution. The figure below shows the process of SA.
Process of Simulated Annealing
In each iteration, one neighbourhood structure will be randomly selected to be applied to the candidate solution to produce a neighbouring solution. A neighbouring solution is a solution that is slightly different from the candidate solution. There are in total four neighbourhood structures implemented:
Refer to neighbourhood_structure1
, neighbourhood_structure2
, neighbourhood_structure3
and neighbourhood_structure4
functions in simulated_annealing.py
for more details.
SA is carried out for a number of iterations until stopping criterion has been met. The procedure is described by the following steps:
R
that is uninformedly distributed between 0 and 1 is generated and the probability density function value, e-δ/T is calculated. If the probability density function value is higher than R
, the neighbouring solution is accepted as the candidate solution to generate a new neighbouring solution.Refer to anneal
function in simulated_annealing.py
for more details.
Four external packages are used to implement HGASA algorithm:
@njit(cache=True)
decorator. @njit()
compiles the decorated function in nopython mode so the compiled code runs without the involvement of Python interpreter. cache=True
indicates the result of function compilation will be saved into a file-based cache to save compilation time when invoking decorated functions.The table below shows the experimental result of running HGASA algorithm using the given input files where there are n = 118
presentations, m = 300
slots and k = 47
supervisors.
Experimental Run | Run 1 | Run 2 | Run 3 |
---|---|---|---|
Hard Constraints Violated | 0 | 0 | 0 |
Soft Constraints Violated | 2 | 1 | 2 |
Penalty Points | 255 | 245 | 245 |
Runtime (seconds) | 62.60 | 55.75 | 54.02 |
:unlock: Note that all the parameters used in HGASA algorithm are purely empirical and should be adjusted for other problems.
The generated presentation schedule is in csv
format as shown below:
P9, null, null, P48, P36, null, ...
The fragmented schedule above indicates that P9
, P48
and P36
are scheduled for slot 1
, slot 4
and slot 5
respectively. null
indicates no presentation is scheduled for a particular slot. An example of a timetable generated by PrettyTable that shows the final presentation schedule is shown below.
+------+------------------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+
| Day | Venue | 0900-0930 | 0930-1000 | 1000-1030 | 1030-1100 | 1100-1130 | 1130-1200 | 1200-1230 | 1230-1300 | 1400-1430 | 1430-1500 | 1500-1530 | 1530-1600 | 1600-1630 | 1630-1700 | 1700-1730 |
+------+------------------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+
| Mon | Viva Room | P58 | P35 | | P73 | P118 | | | | | | | | | | |
| | Meeting Room | P78 | P100 | P116 | | P40 | P3 | | | P92 | P50 | P75 | | | | |
| | Interaction Room | | P6 | | | | | | | P71 | P11 | | | | | |
| | BJIM | | | | | P57 | P24 | P2 | | | P25 | P88 | P81 | P96 | | |
| | | | | | | | | | | | | | | | | |
| Tues | Viva Room | P70 | P80 | | P39 | P99 | P23 | P98 | | | | P14 | | | | |
| | Meeting Room | | | P77 | P52 | P17 | | | | P105 | P62 | P61 | P18 | P9 | | |
| | Interaction Room | P84 | P91 | | | | P65 | | | | P5 | | P83 | P108 | P112 | |
| | BJIM | | P48 | P32 | P86 | P34 | P21 | | | | P33 | P117 | P37 | P38 | | |
| | | | | | | | | | | | | | | | | |
| Wed | Viva Room | | | | | | | | | | | | P95 | P51 | P106 | |
| | Meeting Room | | | | | P69 | P1 | P90 | | | | | | | | |
| | Interaction Room | | | | P103 | | | | | | | P19 | P15 | | | |
| | BJIM | P49 | P13 | P101 | | | | P41 | | | | | | | | |
| | | | | | | | | | | | | | | | | |
| Thu | Viva Room | P102 | P85 | P56 | P79 | P115 | P16 | | | | | | | | | |
| | Meeting Room | | | | P26 | P109 | P113 | | | | P68 | P82 | P46 | | | |
| | Interaction Room | | P60 | P114 | P36 | P10 | | | | P87 | P28 | P94 | P53 | P30 | | |
| | BJIM | | | P27 | P89 | P55 | | | | | | P31 | P76 | | | |
| | | | | | | | | | | | | | | | | |
| Fri | Viva Room | | | P44 | P63 | P67 | P7 | | | | | P20 | P47 | P22 | | |
| | Meeting Room | | | P72 | P110 | P64 | | | | | | | | P42 | P43 | |
| | Interaction Room | P29 | P93 | P97 | P111 | | P59 | | | | | P45 | P66 | P4 | | |
| | BJIM | | P8 | P74 | P54 | P107 | | P104 | | | | | | P12 | | |
| | | | | | | | | | | | | | | | | |
+------+------------------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+
A graph of penalty points over number of iterations will be saved in png
format. An example of the graph is shown below. The graph illustrates the improvement of presentation scheduling as number of iterations increases.
Graph of penalty points over number of iterations
Refer to write
function in data.py
for more details.
Windows commands for Python package installation:
NumPy
$ pip install numpyNumba
$ pip install numbaMatplotlib
$ pip install matplotlibPrettyTable
$ pip install PTableThere should be a folder named input_files
in the same directory that contains all the csv
files (SupExaAssign.csv
, HC03.csv
, HC04.csv
, SC01.csv
, SC02.csv
and SC03.csv
).
Run hybrid_system.py
.
:unlock: Modify data.py
and input_files
for other data formats, such as json
or txt
.