Tuning a multivariate process automatically

Question

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?

Answer 1

I would try to use a genetic algorithm. A simple representation of the problem in terms of a genetic algorithm would go like this:

• A "gene" represents one of the parameters.
• An "individual" consists of assigning a value to each parameter.

An "individual" represents a candidate solution, and it can be evaluated using the objective function. The goal is that at every iteration, a candidate solution is more likely to be selected if it performs well according to the objective function.

The standard genetic algorithm works like this:

1. Randomly pick a set of say 100 individuals (first generation)
2. Calculate the "performance" of every individual
3. Select say the top 10 individuals according to their performance, then produce the next generation of 100 individuals by cross-over among these top 10. A cross-over means picking two individuals A and B from the top 10 and producing a new individual with the value of every gene/instance taken from the same gene in either A or B (this choices between A or B is also made randomly for every gene).
4. Optionally add some random mutations to the new individuals' genes.
5. Iterate again from step 2. Keep iterating unless some stop condition is satisfied, for example the average performance over the last 5 generations doesn't increase anymore (or just stop based on manual inspection).

There are probably some good genetic learning libraries around but I've never used any myself (the basic method is fairly simple to implement).