Problem 688507 · medium · Phase 06 Heuristics & Optimization

Tuning Knobs in the Dark

black-box optimization · local search · step size

A machine has dim knobs, each set between -5 and 5. You cannot see how it works: you can only try a setting and read how badly it performs. Write tune(f, dim, bounds, budget) that returns the best setting you can find, as a list of dim numbers.

  • f(x) returns the badness of setting x (lower is better, 0 is perfect). Every call counts.
  • bounds is [(-5.0, 5.0)] * dim.
  • You may call f at most budget times. One more call raises BudgetExceeded.

The tests run minimise_within(tune, landscape, dim, budget, seed), which gives your function a hidden landscape and reports the value at the point you return. Try it with Run, for example print(minimise_within(tune, "bowl", 3, 300, 1)).

How this problem is scored

A setting passes if it is at least as good as the best of budget random settings. Its quality (0 to 100) measures, on a logarithmic scale, how much closer to the perfect 0 you get than random search: every factor of ten counts the same.

Examples

Input:  minimise_within(tune, "bowl", 3, 200, 1)
Output: {"value": ..., "evaluations": ..., "random_search": ...}
        passes when value <= random_search

Constraints

  • 3 <= dim <= 8, 200 <= budget <= 3000
  • The landscapes are smooth bowls and a curved valley; each has one best setting.

Goals

  • Optimise a function you can only evaluate, not inspect
  • Spend a fixed evaluation budget wisely
  • Adapt the step size of a search
Starting Python…