Here are some explanations about the work I have presented at the META'08 conference. This post is based on the notes I used for my presentation.
In all the automatic parameter setting methods, the problem of finding the better parameter set is considered as an optimization problem, with only one objective, generally finding the best optimum, or reducing the uncertainty of the results. Sometimes, one try to improve the speed. More rarely, speed, precision or robustness are aggregated in one criterion, with an adhoc formula. In fact, one can set parameters according to several objectives (improve speed, improve robustness, etc.). One cannot find a set of parameters fitting all the potential uses of a single algorithm on a single problem instance. Thus, parameter setting is a multi-objective problem.
The key point here is that it is easier to set the parameters of a solver than to solve the problem directly. The simpler example of this idea is when you want to solve a continuous optimization problem with hundreds of variables, with a metaheuristic that have 3 parameters. Moreover, you only have to tune your parameters once, even if you will solve many problems instances later.
In this work, I only consider speed and precision, although the method may handle any performance metrics.
What is crucial in our method is that we do not want to aggregates the criterions, instead, we want the Pareto front corresponding to all the non-dominated parameters set. I use plots representing the Pareto front, that I will sometimes call the « performance » front, or performance profile.
The idea is that one can then compare more rigorously several algorithms, by comparing their respective performance fronts. We can also benefits from having a cursor, scaling from a behaviour oriented towards speed, at one extreme, or precision, at the other side. Even more interesting is the performance profile projected on the parameters space. One can see that every algorithm has its very own profile, that tells a lot on how it behaves.
The figure above shows performance profiles of 4 metaheuristics: a Simulated Annealing, a Genetic Algorithm, two Estimation of Distribution Algorithms (produced by NSGA-II, with median estimation, on the Rosenbrock-2D problem, using the parameter corresponding to the sampling density for each method with an absolute time stopping criterion).
Our results suggest that the choice of the stopping criterion has a drastic influence on the interest of the performance profile, it must be chosen carefully. Similarly, the method can not naturally find a unique profile for a set of problem instances, but is strictly valid only for an instance of a given problem. Finally, we note that the performance profiles are often convex in the objectives space, which could indicate that aggregation may be usefull.
The proposed method allows to aggregate all parameters into one, determining the position within the profile of performance, since behavior strongly oriented towards production (fast, unaccurate) to conception (slow, accurate). The projection of the profile in the space of parameters can also reflect the impact of parameters on performance, or dependence between parameters. Such information may be very relevant to better understand some complex metaheuristics. It also becomes possible to compare several metaheuristics, delaying the performance profiles on the same scale. The statistic validation also receives additional dimensions of discrimination.
In perspective, it remains to reduce the demand for calculations of the meta-optimizer, using dedicated methods (SPO, racing, etc.).. It is also possible to extend the method taking into account robustness as supplementary objectives and checking the possibility of rebuilding correlations on a set of instances.
Finally, here are the slides. I use light slides without a lot o text, so I suggest that you read the notes while looking at the presentation. You will find the abstract, the extended abstract and the slides on my professional website, at the corresponding publication page.