Map-Elites based Hyper Heuristic for RCPSP

Multidimensional Archive of Phenotypic Elites (MAP-Elites) is a quality diversity based algorithm which constructs an archive of solution based on genotypic and phenotypic features of an individual.

In this project we explore the automated evolution of priority rules for generating schedules for the Resource Constrained Project Scheduling Problem(RCPSP).

We provide the comparision between two methods Genetic Programming based Hyper-Heuristic(GPHH) and MAP-Elites based Hyper-Heuristic(MEHH) and demonstrate the strong improvements in diversity and performance shown by MAP-Elites over the traditional GP based approach. We also compare different archive sizes used for MAP-Elites(125, 1000, 3375 and 8000) and show the variation of coverage and performance for these sizes.

Dataset

The repo uses 5 datasets j30, j60, j90, j120, RG300 each having instances with the corresponding number of activities suggested by the name.

The training dataset consists of j30 instances only, we validate the solutions generated by the training process on a validation set composed of 10% of RG300 set and pick the best individual to be tested on the test set which comprises the remaining 90% of test set.

Requirements

The requirements for using the project are present in requirements.txt

deap==1.3.1
matplotlib==3.1.3
pygraphviz==1.5
qdpy==0.1.2.1
plotly==4.8.2
scipy==1.5.1
numpy==1.18.1
seaborn==0.11.0
networkx==2.4
adjustText==0.7.3
sympy==1.8

Usage

To run the GPHH experiment :

1. Remove the logs/gp folder (Will clear existing results)
2. Update the required parameters for the experiment in params_gp.py
3. Run using python3 params_gp.py
4. The process will automatically be parallelised on all the available CPU cores
5. After the evolving and evaluation completes the results will be available in logs/gp/set_0

To run the MEHH experiment :

1. Remove the logs/map_elites folder (Will clear existing results)
2. Update the required parameters for the experiment in params_map_elites.py
3. Run using python3 params_map_elites.py
4. The process will automatically be parallelised on all the available CPU cores
5. After the evolving and evaluation completes the results will be available in logs/map_elites/set_0

To evaluate results :

1. The analysis folder contains various files to evaluate the generated results and plot graphs
2. Ensure the logs folder is present
3. Run any script using python3

The instance file implements code for basic parsing, scheduling algorithm and priority rules. Running it would generate a table of deviation and makespan values for all the different human designed rules such as LFT, LST, FIFO, etc.

The analysis folder contains all the scripts used to analse, plot, generate results

The logs folder contains all the results after running both GP and MAP-Elites for 31 runs and 25 generations each

The precomputes folder acts as cache for speeding up certain calculations

Results

Comparison of diversity of GPHH and MEHH

As shown in the below figure MAP-Elites shows strong improvement in diversity over generations while GP loses its diversity due to not maintaining a unique features wise map of individuals.

Comparison of performance of GPHH and MEHH

MEHH also shows performance improvements on the test set composed of RG399 instances, while also having a lower standard deviation than GPHH. This is useful since it is more likely to get a good solution on the first run itself when using MEHH while GPHH in the worst case could give a poorly performing solution

Comparison of complexities of GPHH, MEHH and priority rules

MEHH evolves more complex rules than GPHH, however the complexity is compensated with the performance improvement shown by it.

Comparison of improvement of MEHH over GPHH for different instance sizes

This plot shows that MEHH shows significant improvements in performance over GPHH when the instance size becomes larger, MEHH is able to generalise to larger instances without showing a hit in performance

Performance grid for archive size 1000

The performance grid is displayed as a heatmap. The 3D performance grid has been flattened to 2D and eah dimension indicates a feature. The heatmap is made on the fitness value or percentage deviation from lowerbound, hence lower the deviation value better the individual's performance.

Example of an evolved priority rule

The tree shown is an operator tree which is used to compute the priority values for each activity in the instance

MAP-Elites Hyper Heuristic for RCPSP
Shelvin Chand, Kousik Rajesh, Rohitash Chandra
Paper under review

For queries on implementation/dataset contact : 
Kousik Rajesh 
kousik18@iitg.ac.in