Saturday, January 3, 2015

Stopping criteria for meta-heuristics

When running a really small non-convex MIQP problem with GAMS+Localsolver I see:

LocalSolver 5.0 (Win64, build 20141120)
Copyright (C) 2014 Innovation 24, Aix-Marseille University, CNRS.
All rights reserved (see Terms and Conditions for details).

Searching for equations that define variables... found 5
Instance:       20 Variables
                 9 Constraints
                82 Expressions
               132 Operands

    time |           iterations |         #infeas
      0s |                    0 |               4
    time |           iterations |       objective
      1s |               583495 | 2.66000000e+002
      2s |              1406684 | 2.66000000e+002
      3s |              2235323 | 2.66000000e+002
      4s |              3073170 | 2.66000000e+002
      . . . . lots of lines with the same objective
    998s |            677978972 | 2.66000000e+002
    999s |            678600000 | 2.66000000e+002
   1000s |            679218601 | 2.66000000e+002

Stopped due to time limit.
Feasible solution found.
Objective Value: 2.66000000e+002

Obviously the default stopping condition (max time = 1000s) is not very good for this case: we are just sitting there for 99.99% 99.9% of the time already at the optimal solution doing nothing useful. (266 is indeed the global optimum). In general these heuristics have no idea how close they are to an optimal solution, and just rely on the user to provide these time or iteration limits. (MIP solvers have this very powerful bounding information where we can say at any moment in time what the gap is between the best solution found an the best solution possible).

Is there nothing better we can do? There is some research on probabilistic stopping rules for these kind of algorithms (i.e. stop as soon as we think the probability we will find a better solution is small):

  • Ribeiro, Rosseti, Souza, “Effective probabilistic stopping rules for randomized metaheuristics: GRASP implementations”, Learning and Intelligent Optimization, Lecture Notes in Computer Science Volume 6683, 2011, pp 146-160
  • Boender, Rinnooy Kan, "Bayesian stopping rules for multistart global optimization methods", Mathematical Programming, 37:59–80, 1987.
  • Dorea, "Stopping rules for a random optimization method", SIAM Journal on Control and Optimization, 28:841–850, 1990.
  • Hart, "Sequential Stopping Rules for Random Optimization Methods with Applications to Multistart Local Search", SIAM Journal on Optimization, 1998, Vol. 9, No. 1 : pp. 270-290
  • Safe, Carballido, Ponzoni, Brignole, “On Stopping Criteria for Genetic Algorithms”, Advances in Artificial Intelligence – SBIA 2004, Lecture Notes in Computer Science, 405-413, 2004

I would guess such a thing could well be a better default stopping rule.

PS Look at these iteration numbers. Don’t care here about a million iterations more or less. (Of course that is the whole purpose of this algorithm: do as many evaluations as possible).