I have a process to optimize which involves multiple algorithms. These algorithms are mostly interchangeable, but can have different performance benefits depending upon the input, and depending upon other tasks that are happening in parallel. They are also layered, so one algorithm can defer to another algorithm for the next stage. This detail isn't too important, just to say the interactions between the algorithms are complex. Finally, the size and shape of the input can have a large and varied impact upon the individual algorithms.
I have a system whereby I can change some variables (unsigned integers, each between 0 and ~100,000,000) to change when particular algorithms get used. There are roughly 20 of these variables in total. These 20 variables represent the kind of cartesian product of (input shape x algorithm x stage of the process). The actual value of these variables I'm tuning is the size of input at which to start using this algorithm. These variables will be sorted by value (highest first) and the algorithm will be picked based upon the first matching variable. My goal is to come up with the best possible set of values for these variables.
To test my results, I have a fitness / loss function that times runs of my process with multiple representative inputs and returns the sum of
time in nanoseconds / input size for all inputs as the loss / fit.
So in total I have:
- 20 dependent input variables to tune, uint between 0 and 100,000,000
- A fitness function returning one value, sum of runtimes across many runs of my process
So far I have tried:
- Manually tuning the variables based on intuition (best results so far, exceptionally slow process)
- Monte Carlo experiments (poor results, too many possible input values to test all of them)
- Constrained versions of Monte Carlo experiments, with smaller possible input ranges (poor results, still too many dependent variables and situations to test)
- Genetic algorithm with random mutation from the best known result (poor results, rarely made progress)
- Bayesian optimizer: completely unusable results, not sure if the implementation was incorrect (likely) or if user error was involved (very likely)
So I'm trying to find a better method. Googling around for other optimization algorithms to use has left me mostly confused.
At the moment, I'm hoping that I can at least get a tuning as good as the one I did manually, but naturally the aim is to find a tuning that provides better results overall.
Does anyone have any suggestions on where to look in order to get started with solving this problem? In particular, algorithms and techniques that can be applied in this situation?