13
$\begingroup$

It is quite frequent that optimization algorithms have quite some parameters controlling their behavior (cooling schedule of a Simulated Annealing, length of the tabu list for a Tabu Search, population size for a Genetic Algorithm, etc...).

One will typically spend quite some time fine tuning those parameters using a "representative" set of instances. However it can happen that a set of parameters will work very well on one instance but quite poorly on another one (particularly if the set of representative instances is quite heterogeneous).

It would seem interesting, based on some instance characteristics to determine (probably using supervised learning techniques) before solving which parameters values are the most likely to give good results.

I have tried to find some information about this idea in the literature but could not find anything. Do you know of any success/failure stories related to this idea?

On a related note I know about Adaptive Large Neighborhood Search (ALNS), where one tries to figure out during the search which neighborhoods are the most efficient for the instance being currently solved. I am more interested about an approach where the parameters are completely determined before starting the actual solving process.

$\endgroup$
9
$\begingroup$

The problem you are referring to is hyper-parameter optimization and a simple search in google will bring up many blogs (and of course) research that has been done in this area.

You haven't asked this, but since you mentioned a few algorithms (SA, Tabu search, ...), in case you are also interested to select the best algorithm for different data sets, then you are looking at meta learning.

A few other useful links to give you an idea of the research in this area can be:

$\endgroup$
  • $\begingroup$ My understanding was that hyperparameter optimization was about finding the best set of parameter values for all instances of a given set. Did I misunderstood it? Is it really about being able to determine a priori which set of parameter is the best to solve a given instance ? $\endgroup$ – Renaud M. Jun 7 '19 at 15:30
  • $\begingroup$ You are trying to find out a set of parameters to work well on an instance. If you want to find the (hopefully) best set of parameters for a given instance, then you need to have solved (or trained) on different instances (one algorithm or multiple). Having the performance metric of each, then maybe use regression to predict for the new instances. I updated my answer to add a link to a lit review of this topic and similar ones. $\endgroup$ – EhsanK Jun 7 '19 at 15:54
8
$\begingroup$

You are touching three similar but different subjects in your question.

Choosing the set of parameter values for an algorithm and a set of instances is a task known as offline parameter tuning, algorithm configuration, or (as indicated in @EhsanK) hyper-parameter tuning (mostly in machine learning, where the term parameters means something else). There is now a considerable amount of research in the area, for example irace, SMAC, ParamILS, GGA, mrlMBO, Spearmint and many more, both from OR and ML. These are all general-purpose configurators that can be applied to different algorithms. Other specialized tuners exist for specific software, e.g. Opentuner for GCC.

This is different from online tuning, as you note, where one tries to find at runtime the best parameter configuration to solve the instance currently being tackled.

Instance features are usually considered in algorithm selection, where an instance is analyzed to select the best algorithm to solve it. See e.g. this recent survey and this comprehensive literature list. Instance features are often problem-specific.

To the best of my knowledge, the use of features in algorithm configuration has not been studied as much as general-purpose offline algorithm configuration and problem-specific algorithm selection. Some works in this category are Hydra and ISAC, but there is certainly room for more research here.

$\endgroup$
5
$\begingroup$

There was a similar question on Cross Validated and as in my comment there, I would look into the use of statistical experimental design, specifically factorial designs and fractional factorial designs. There is a very good book on that topic Box, Hunter & Hunter and here is a paper on its use in hyperparameter optimization Design of Experiments for the Tuning of Optimisation Algorithms.

$\endgroup$
5
$\begingroup$

To my understanding, the tuning process you just mentioned is also an learning technique where your training set is your set of representative instances. The problem is with generalization because your training has been too biased or representative set has not been a good training set. In parameter tuning, you may wish to do cross validations similar to ML. Moreover, the combinatorial problems are very unpredictable and one cannot fix a parameter and hope that it works well for all instances. For this reason, one may come up with a set of rules to determine the value of a search parameter (e.g., in root node use primal simplex and in the child nodes use dual simplex when you want to decide on what LP algorithm to use in branch-and-cut) instead having one fix a predetermined value.

You may find these works interesting as well:

Cheers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.