LibRCPS

Menu
  About
  News
  Features
  Manual
  Download
  Contact

Tuning

Genetic algorithms use a whole set of parameters (e.g. mutation rates) that need to be tuned for optimal performance. Since these parameters can in theory be interdependent, this is quite a difficult optimization problem in itself. The fact that the algorithm is non-deterministic and that it may behave differently for different problem instances further complicates this.

For LibRCPS we have used a set of almost 7000 synthetic problems that cover a wide range of complexity and size. This set of problems was then calculated for each combination of the parameters and both speed and result quality saved to a database. To deal with the non-deterministic behaviour, this was done many times, resulting in many millions of solver invocations (and some months of CPU time).

The result is a highly dimensional data cube that maps parameter combinations to speed, result quality and standard deviations of these. This cube is used to find perfectly tuned parameters for LibRCPS. In the image below, you can see a cut through the data cube showing the relationship between the speed of the algorithm, the mutation rate on one chromosome and the population size.