Problem 646290 · hard · Level 06 Heuristics & Optimization

Readings You Cannot Trust

black-box optimization · noisy optimisation · evolution strategies

A chemical reactor has dim controls, each between -5 and 5. The impurity of its product is a smooth function of the controls with a single best setting, where the impurity is 0. The trouble is the sensor: every reading adds a fresh random error, drawn from a normal distribution with mean 0 and standard deviation 1. Reading the same setting twice gives two different numbers.

Write calibrate(f, dim, bounds, budget) that returns the setting you believe is best, as a list of dim numbers.

  • f(x) returns a noisy impurity reading at x. Every call counts.
  • bounds is [(-5.0, 5.0)] * dim; values outside are pulled back to the edge.
  • You may call f at most budget times. One more call raises BudgetExceeded.
  • You are scored on the true impurity at the setting you return, without noise.

The tests run noisy_lab(calibrate, dim, budget, seed), which hides a reactor and reports the true impurity at your setting. Try it with Run: print(noisy_lab(calibrate, 4, 1000, 1)).

How this problem is scored

The judge also runs random search that trusts its readings: it reads budget random settings once each and keeps the one with the lowest reading. A setting passes if its true impurity is no higher than that setting's true impurity. Its quality (0 to 100) is measured on a logarithmic scale from there down to the best true impurity known for the test (found offline by many runs of stronger methods with the same budget): every factor of ten counts the same, and reaching the best known value scores 100.

Examples

Input:  noisy_lab(calibrate, 4, 1000, 1)
Output: {"value": ..., "evaluations": ..., "random_search": 0.7313...}
        passes when value <= random_search; best known 0.0055

Constraints

  • 4 <= dim <= 8, 1000 <= budget <= 3000
  • The noise comes from the judge's own seeded generator, so a run is repeatable. Use random for your own randomness (the tests seed it) and bound loops by evaluations, never by the clock.

Goals

  • Optimise a function whose every evaluation carries random error
  • See why trusting the single best reading goes wrong
  • Average away noise with a population instead of repeated readings
Starting Python…