An NUS timetable generator which uses a genetic algorithm to optimise timetables to suit the needs of NUS students.

Overview

Where Got Time(table)?

A timetable optimiser for NUS which uses an evolutionary algorithm to "breed" a timetable suited to your needs.



Try it out here!

Inspiration

Planning the best fit timetable to suit our needs can be an absolute nightmare. Different sets of modules can result in a seemingly limitless combinations of timetable. Comparing and choosing the best timetable can take hours or even days. The struggle is real

Having chanced upon an article on genetic algorithm, we thought that this would be the best approach to tackling an optimization problem involving timetabling/scheduling. This project aims to provide the most optimized timetable given a set of pre-defined constraints.

What It Does

Users can input the following:

  • Modules codes for the particular semester
  • Adjustable start and end time
  • Select free days
  • Maximize lunch timings
  • Determine minimum hours of break between classes

Based on user inputs, the most optimized timetable is generated.





Why It Works

A Genetic Algorithm mimics the process of natural selection and evolution by combining the "elite" timetables to form the "next generation" of timetables.

The evolutionary process:

  1. Extracting, cleaning and generating our own data structure from NUSMods API
  2. Initialise the first generation which includes a population of timetables
  3. Grading each timetable with a fitness score
  4. Cross-over fittest "parents" to generate 2 "child" timetables with mutations
  5. Assign these timetables to the next generation
  6. Repeat this process until the fitness score across a generation converges
  7. If the soft and hard constraints were not met after reaching the generation limit, the most optimised timetable is returned to the user

How We Built It

Our main algorithm was written with Python. It utilizes NUSMods API to fetch the relevant module data. Some filtering and cleaning up of the data grants us a workable data structure. Implementation of the genetic algorithm returns a link that is sent to the web page which generates an image for the user.

Firstly, we generate a population of timetables. Using a scoring algorithm, we rate the fitness of each timetable. Timetables with a better fitness score gets to produce the next generation of timetables through cross-overs and mutation.

We repeat this process until the average fitness score of the entire generation converges to within a tolerance range. The fittest timetable from the final generation is returned to the user.

Challenges We Ran Into

Managing large data structures comes with confusing errors that are hard to pinpoint. NUS offers more than 6000 modules, some classes are fixed while others are variable. This results in multiple varying data structures for different modules. As such, our code needs to be robust enough to handle the unique data structures. Integration of front and backend code was much harder than expected.

Accomplishments We're Proud Of

We are proud to have come up with a minimum viable product.

What We Learned

As this is our first group project, we learnt how to work on Git Flow, how to push and pull information via Git and version control. One of us even deleted a whole file and had to rewrite from scratch We also learnt how to approach optimization problems and how to use the NUSMods API for parsing data into our program.

What's Next For Where Got Time(table)?

Improve the UI/UX of the landing page to facilitate better user experience. Allow more user constraints such as "Minimal Time Spent in School". We will further fine-tune the program which could possibly be used as an extension for the official NUSMods. A possible feature that can be added includes a GIF of the user's timetable evolving across generations from start to finish.

Try It Out

Where Got Time(table)?

Credits/Reference

Using Genetic Algorithm to Schedule Timetables

You might also like...
A minimal implementation of the IQRM interference flagging algorithm for radio pulsar and transient searches

A minimal implementation of the IQRM interference flagging algorithm for radio pulsar and transient searches. This module only provides the algorithm that infers a channel mask from some spectral statistic that measures the level of RFI contamination in a time-frequency data block. It should be useful as a reference implementation to developers who wish to integrate IQRM into an existing pipeline / search code.

Greedy Algorithm-Problem Solving

MAX-MIN-Hackrrank-Python-Solution Greedy Algorithm-Problem Solving You will be given a list of integers, , and a single integer . You must create an a

An implementation of ordered dithering algorithm in python as multimedia course project
An implementation of ordered dithering algorithm in python as multimedia course project

One way of minimizing the size of an image is to simply reduce the number of bits you use to represent each pixel.

Fedlearn algorithm toolkit for researchers
Fedlearn algorithm toolkit for researchers

Fedlearn algorithm toolkit for researchers

A custom prime algorithm, implementation, and performance code & review
A custom prime algorithm, implementation, and performance code & review

Colander A custom prime algorithm, implementation, and performance code & review Pseudocode Algorithm 1. given a number of primes to find, the followi

Sorting Algorithm Visualiser using pygame
Sorting Algorithm Visualiser using pygame

SortingVisualiser Sorting Algorithm Visualiser using pygame Features Visualisation of some traditional sorting algorithms like quicksort and bubblesor

This project is an implementation of a simple K-means algorithm
This project is an implementation of a simple K-means algorithm

Simple-Kmeans-Clustering-Algorithm Abstract K-means is a centroid-based algorithm, or a distance-based algorithm, where we calculate the distances to

Search algorithm implementations meant for teaching

Search-py A collection of search algorithms for teaching and experimenting. Non-adversarial Search There’s a heavy separation of concerns which leads

8-puzzle-solver with UCS, ILS, IDA* algorithm
8-puzzle-solver with UCS, ILS, IDA* algorithm

Eight Puzzle 8-puzzle-solver with UCS, ILS, IDA* algorithm pre-usage requirements python3 python3-pip virtualenv prepare enviroment virtualenv -p pyth

Owner
Nicholas Lee
Student
Nicholas Lee
A genetic algorithm written in Python for educational purposes.

Genea: A Genetic Algorithm in Python Genea is a Genetic Algorithm written in Python, for educational purposes. I started writing it for fun, while lea

Dom De Felice 20 Jul 6, 2022
🧬 Training the car to do self-parking using a genetic algorithm

?? Training the car to do self-parking using a genetic algorithm

Oleksii Trekhleb 652 Jan 3, 2023
Genetic Algorithm for Robby Robot based on Complexity a Guided Tour by Melanie Mitchell

Robby Robot Genetic Algorithm A Genetic Algorithm based Robby the Robot in Chapter 9 of Melanie Mitchell's book Complexity: A Guided Tour Description

Matthew 2 Dec 1, 2022
A Python project for optimizing the 8 Queens Puzzle using the Genetic Algorithm implemented in PyGAD.

8QueensGenetic A Python project for optimizing the 8 Queens Puzzle using the Genetic Algorithm implemented in PyGAD. The project uses the Kivy cross-p

Ahmed Gad 16 Nov 13, 2022
This is an Airport Scheduling Time table implemented using Genetic Algorithm

This is an Airport Scheduling Time table implemented using Genetic Algorithm In this The scheduling is performed on the basisi of that no two Air planes are arriving or departing at the same runway at the same time and day there are total of 4 Airplanes 3 and 3 Runways.

null 1 Jan 6, 2022
N Queen Problem using Genetic Algorithm

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.

Mahdi Hassanzadeh 2 Nov 11, 2022
Genetic algorithms are heuristic search algorithms inspired by the process that supports the evolution of life.

Genetic algorithms are heuristic search algorithms inspired by the process that supports the evolution of life. The algorithm is designed to replicate the natural selection process to carry generation, i.e. survival of the fittest of beings.

Mahdi Hassanzadeh 4 Dec 24, 2022
Using A * search algorithm and GBFS search algorithm to solve the Romanian problem

Romanian-problem-using-Astar-and-GBFS Using A * search algorithm and GBFS search algorithm to solve the Romanian problem Romanian problem: The agent i

Mahdi Hassanzadeh 6 Nov 22, 2022
A fast python implementation of the SimHash algorithm.

This Python package provides hashing algorithms for computing cohort ids of users based on their browsing history. As such, it may be used to compute cohort ids of users following Google's Federated Learning of Cohorts (FLoC) proposal.

Hybrid Theory 19 Dec 15, 2022
TikTok X-Gorgon & X-Khronos Generation Algorithm

TikTok X-Gorgon & X-Khronos Generation Algorithm X-Gorgon and X-Khronos headers are required to call tiktok api. I will provide you API as rental or s

TikTokMate 31 Dec 1, 2022