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

Owner
Nicholas Lee
Student
Nicholas Lee
This repository provides some codes to demonstrate several variants of Markov-Chain-Monte-Carlo (MCMC) Algorithms.

Demo-of-MCMC These files are based on the class materials of AEROSP 567 taught by Prof. Alex Gorodetsky at University of Michigan. Author: Hung-Hsiang

Sean 1 Feb 05, 2022
A priority of preferences for teacher assignment problem

Genetic-Algorithm-for-Assignment-Problem A priority of preferences for teacher assignment problem Keywords k-partition; clustering; education 4.0 Abst

hades 2 Oct 31, 2022
GoldenSAML Attack Libraries and Framework

WhiskeySAML and Friends TicketsPlease TicketsPlease: Python library to assist with the generation of Kerberos tickets, remote retrieval of ADFS config

Secureworks 43 Jan 03, 2023
Python sample codes for robotics algorithms.

PythonRobotics Python codes for robotics algorithm. Table of Contents What is this? Requirements Documentation How to use Localization Extended Kalman

Atsushi Sakai 17.2k Jan 01, 2023
Python algorithm to determine the optimal elevation threshold of a GNSS receiver, by using a statistical test known as the Brown-Forsynthe test.

Levene and Brown-Forsynthe: Test for variances Application to Global Navigation Satellite Systems (GNSS) Python algorithm to determine the optimal ele

Nicolas Gachancipa 2 Aug 09, 2022
Python package to monitor the power consumption of any algorithm

CarbonAI This project aims at creating a python package that allows you to monitor the power consumption of any python function. Documentation The com

Capgemini Invent France 36 Nov 11, 2022
Genius Square puzzle solver in Python

Genius Square puzzle solver in Python

James 3 Dec 15, 2022
Official implementation of "Path Planning using Neural A* Search" (ICML-21)

Path Planning using Neural A* Search (ICML 2021) This is a repository for the following paper: Ryo Yonetani*, Tatsunori Taniai*, Mohammadamin Barekata

OMRON SINIC X 82 Jan 07, 2023
Multiple Imputation with Random Forests in Python

miceforest: Fast, Memory Efficient Imputation with lightgbm Fast, memory efficient Multiple Imputation by Chained Equations (MICE) with lightgbm. The

Samuel Wilson 202 Dec 31, 2022
Supplementary Data for Evolving Reinforcement Learning Algorithms

evolvingrl Supplementary Data for Evolving Reinforcement Learning Algorithms This dataset contains 1000 loss graphs from two experiments: 500 unique g

John Co-Reyes 42 Sep 21, 2022
Genetic algorithm which evolves aoe2 DE ai scripts

AlphaScripter Use the power of genetic algorithms to evolve AI scripts for Age of Empires II : Definitive Edition. For now this package runs in AOC Us

6 Nov 04, 2022
Implementation of an ordered dithering algorithm used in computer graphics

Ordered Dithering Project In this project, we use an ordered dithering method to turn an RGB image, first to a gray scale image and then, turn the gra

1 Oct 26, 2021
An open source algorithm and dataset for finding poop in pictures.

The shitspotter module is where I will be work on the "shitspotter" poop-detection algorithm and dataset. The primary goal of this work is to allow for the creation of a phone app that finds where yo

Jon Crall 29 Nov 29, 2022
Distributed Grid Descent: an algorithm for hyperparameter tuning guided by Bayesian inference, designed to run on multiple processes and potentially many machines with no central point of control

Distributed Grid Descent: an algorithm for hyperparameter tuning guided by Bayesian inference, designed to run on multiple processes and potentially many machines with no central point of control.

Martin 1 Jan 01, 2022
All algorithms implemented in Python for education

The Algorithms - Python All algorithms implemented in Python - for education Implementations are for learning purposes only. As they may be less effic

1 Oct 20, 2021
A Python description of the Kinematic Bicycle Model with an animated example.

Kinematic Bicycle Model Abstract A python library for the Kinematic Bicycle model. The Kinematic Bicycle is a compromise between the non-linear and li

Winston H. 36 Dec 23, 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 01, 2022
implementation of the KNN algorithm on crab biometrics dataset for CS16

crab-knn implementation of the KNN algorithm in Python applied to biometrics data of purple rock crabs (leptograpsus variegatus) to classify the sex o

Andrew W. Chen 1 Nov 18, 2021
A Python implementation of Jerome Friedman's Multivariate Adaptive Regression Splines

py-earth A Python implementation of Jerome Friedman's Multivariate Adaptive Regression Splines algorithm, in the style of scikit-learn. The py-earth p

431 Dec 15, 2022
Primedice like provably fair algorithm

Primedice like provably fair algorithm

Ryu juheon 3 Dec 02, 2022