UCSPy-Engine

An extensible framework for solving the University Course Scheduling Problem (UCSP).

Related documentation

• to learn more about what is UCSP and why this framework exists, read this.
• to learn more about the design of the system, read this.

Getting started

Dependencies

• python 3.6 (or above)
• pip3

Check whether you have the correct version of python and pip installed with:

python3 --version
pip3 --version

Installation

Clone this repo and cd into the project root directory:

git clone <clone-url>
cd UCSPy-Engine

Initialize a new python virtual environment with venv:

python3 -m venv .venv

Activate the virtual environment:

# For Linux/Unix/Mac
source ./.venv/bin/activate

# For Windows
.venv\Scripts\activate

Install requirements using pip:

pip install -r requirements.txt

If you're using a Mac with Apple Silicon, run the commands below instead of the previous one:

brew install openblas
pip install --upgrade pip
OPENBLAS="$(brew --prefix openblas)" pip install -r requirements.arm.txt

Usage

The general usage is as follows:

python cli.py <service>

There are 3 main services offered by UCSPy-Engine:

• solve - used to solve a course scheduling problem.
• plot - used to plot the performance of the solver i.e. fitness at each epoch.
• inspect - used to inspect the quality of the solution provided, by showing detailed constraint violations.

configuration

The solve and inspect services require valid a json configuration file (named ucsp.config.json by default) to be present at the root of the project. Learn more about the configuration file here.

solve

Running the solver through the cli

To solve UCSP, use the solve command:

python cli.py solve

Once executed, the engine starts running an algorithm to solve the ucsp instance specified on the configuration file. It iteratively prints the fitness value of the solution generated by the algorithm at each epoch/generation, until the epoch limit is reached, or the user presses ctrl+c, or if min_acceptable_fitness is reached.

The algorithm to use is specified in the configuration file. The available algorithms as of now are:

• Genetic Algorithm (default)
• Memetic Algorithm

Customizing parameters of the algorithm

Each algorithm has a set of unique parameters that can be provided as command-line arguments. To learn more about them, use:

python cli.py solve --show_args

For example, the number of epochs could easily be changed to 500 like so:

python cli.py solve --epochs=500

The following tables describe the parameters of each available algorithm.

For Genetic Algorithm:

algo parameter	description
epochs	the maximum number of iterations before termination. (default: 100)
population_size	The size of the population in a generation. (default: 100)
elite_pct	The % of elites in the population. (default: 10)
mateable_pct	The % of the population that has a chance to perform crossover. (default: 50)
mutable_pct	The % of the population that could be mutated. (default: 20)

For Memetic Algorithm:

algo parameter	description
epochs	the maximum number of iterations before termination. (default: 100)
population_size	The size of the population in a generation. (default: 100)
elite_pct	The % of elites in the population. (default: 10)
mateable_pct	The % of the population that has a chance to perform crossover. (default: 50)
lcl_search_pct	The % of the population that performs a local search. (default: 10)
lcl_search_iters	The number of iterations of local search for each selected individual. (default: 30)

plot

When solver is run with the save_logs flag set to true, it'll save the logs generated in a file under the folder data/logs/ with the datetime as the log's name <datetime>.log.

These logs can be used to automatically generate performance plots of the fitness over each epoch like this:

And it is done by using the plot command, which takes the path of the log file like so:

python cli.py plot <filpath>

To plot from the sample log file (data/logs/sample.log), run:

python cli.py plot

inspect

When solver is run with the save_schedule flag set to true, it'll save the final schedule in two forms as csv - one in numerical form (e.g. sch-num-<datetime>.csv), and the other in a human readable string form (e.g. sch-str-<datetime>.csv).

The numerical schedule can be used to inspect the constraint violations and the quality of the schedule generated, using the inspect command.

python cli.py inspect <filpath>

For example, to inspect the fitness of the sample schedule (data/schedules/sch-num-sample.csv), run:

python cli.py inspect

NOTE: make sure you set the correct schedule_param and constraints that were used to generate the schedule in the first place. Otherwise, results will be erroneous.

Testing

To run automated tests, use:

python test.py

NOTE: this only tests the operation of the high-level services as of now.

Additional info

For help or synopsis use:

python cli.py -
python cli.py --help
python cli.py <service> -- --help

NOTE

• it is very important that your schedule_params follow the standard order and notation as shown in the default params.
• all .csv files are ignored by git as mentioned in the .gitignore patterns, except for the default schedule_params. You may update your .gitignore to track yours.

Contributing To UCSPy-Engine

Contributions to UCSPy-Engine are welcome! Feel free to make pull requests to the master branch.

License

MIT.