Performance optimization - evolving generator configurations

[OndrejNepozitek]

The goal of this feature is to improve the performance of the algorithm by observing how it behaves on a given input and then propose improvements of the generator's configuration based on these observations.

Motivation

Currently, there is a single configuration that i used for all inputs. The goal of the bachelor thesis was to make the algorithm usable during runtime so the configuration is already much better than it was in the original paper. However, it is still far from perfect. The problem is that it is quite hard to improve the configuration without seeing how the generator behaves on the input.

So instead of trying to guess how to change the configuration by looking only at the input, I propose to run the algorithm with a given input (e.g. 1000 times), gather statistics and then look at these statistics and propose improvements. The good thing is that we can repeat this process and see whether the performance improved or not.

The resulting optimization technique will be a simple evolutionary algorithm that will start with a single individual (the initial configuration) and then apply mutations (changes to that configuration) with the goal of finding an individual with the best fitness (the configuration with the best performance).

The optimization process will take some time as we need to repeatedly run the algorithm for an extended time to collect enough data. However, it is sufficient to run this optimization once for every input so it can be done for example before releasing a game.

Phase 1

• Implement basic evolutionary algorithm
• Allow early stopping of individual evaluation if it is too bad (otherwise all the bad configurations will slow down the whole process)
• Implement some metric of similarity between generated layouts
• Measure entropy of shapes distribution for individual rooms
• Report how individuals improve/worsen the performance

Mutations

• Merge two neighbouring chains in the chain decomposition
• Change the order of chains
• Change the maximum number of iterations allowed for each chain
• Change the number of cycles and trials per cycle in simulated annealing
• Change the whole chain decomposition strategy