This project is elaborated as an assignment for the Nature Inspired Computing course (SS 2019/2020) at FIIT STU by Denis Mitana and Miroslav Sumega.
Detailed description of our solution is in the attached paper.
Santa's Workshop Tour 2019 is a Kaggle competition that defines scheduling optimization problem. The goal of this task is to schedule the families to Santa's Workshop in a way that minimizes the penalty cost to Santa. Every family must be scheduled for one and only one day. The proposed nature-inspired optimization method of Artificial Immune System algorithm (AIS) is used for finding optimal day to visit the workshop for each family while minimizing Santa's costs.
Provided data consists of 5,000 families that have listed their top 10 preferences for the dates they'd like to attend Santa's workshop tour. Dates are integer values representing the days before Christmas. Each family also has a number of people attending.
The AIS algorithm is tested with three and two different methods of mutation and selection, respectively, showing that more informed mutations and less selected Antibodies for the next generation can significantly improve results. Experiments also showed that negative selection is more appropriate than positive selection, which got stuck in the local minimum. Our best achieved score is 2,789,989. The results show that AIS algorithm is suitable for the given scheduling optimization task.
- Clone the repository.
$ git clone [email protected]:dmitana/santas_workshop_tour_2019.git- Install requirements.
$ pip install -r requirements.txt-
Download data and move it to the
data/directory. -
Show help about program usage and command line arguments.
$ python -m santas_workshop_tour -h
usage: santas_workshop_tour [-h] --data-file-path DATA_FILE_PATH --clonator
{basic} --mutator {basic,preference} --selector
{basic,percentile} --affinity-threshold
AFFINITY_THRESHOLD --population-size
POPULATION_SIZE --n-generations N_GENERATIONS
[--logging-level {critical,error,warning,info,debug}]
[--n-cpu N_CPU] [--interactive-plot]
[--output-directory OUTPUT_DIRECTORY]
Program to solve the Santa's Workshop Tour 2019 problem.
optional arguments:
-h, --help show this help message and exit
--logging-level {critical,error,warning,info,debug}
Logging level (default: 20).
--n-cpu N_CPU Number of CPU to be used (default: 1).
--interactive-plot Whether plot is rendering during optimization
(default: False).
--output-directory OUTPUT_DIRECTORY
Directory where output files (plot, best solution and
logs) will be saved (default: output).
required named arguments:
--data-file-path DATA_FILE_PATH
Path to the data to be optimized.
cloning algorithm required named arguments:
--clonator {basic} Cloning algorithm to be used.
mutation algorithm required named arguments:
--mutator {basic,preference}
Mutation algorithm to be used.
selection algorithm required named arguments:
--selector {basic,percentile}
Selection algorithm to be used.
--affinity-threshold AFFINITY_THRESHOLD
Threshold according to which the selection is done.
artificial immune system algorithm required named arguments:
--population-size POPULATION_SIZE
Size of population.
--n-generations N_GENERATIONS
Number of generations.- Run the optimization using the Artificial Immune System algorithm.
$ python -m santas_workshop_tour <arguments>