Problem 642528 · medium · Level 06 Heuristics & Optimization

Lowest Point on Rough Ground

particle swarm optimisation · black-box optimisation · local minima

A survey robot must find the lowest point of a patch of rough ground in dim dimensions. The ground is full of small dips, so walking downhill from one spot usually ends in a hollow that is not the lowest. You cannot see the ground: you can only measure the height at a point.

Write find_lowest(f, dim, bounds, budget) that returns the lowest point you can find, as a list of dim numbers.

  • f(x) returns the height at x (lower is better; the lowest point has height 0).
  • bounds is [(-5.0, 5.0)] * dim; points outside are pulled back to the edge when scored.
  • You may call f at most budget times. One more call raises BudgetExceeded.

The tests run survey_terrain(find_lowest, terrain, dim, budget, seed), which hides a terrain ("ripples", "dunes" or "craters"), shifted by the seed, and reports the height at the point you return. Try it with Run: print(survey_terrain(find_lowest, "ripples", 4, 800, 1)).

How this problem is scored

A point passes if it is at least as low as the best of budget points drawn uniformly at random in the box (the checker draws them itself). Its quality (0 to 100) is measured on a logarithmic scale from that random-search height down to the goal height 1e-6: every factor of ten counts the same, and reaching the goal scores 100.

Examples

Input:  survey_terrain(find_lowest, "ripples", 10, 2000, 1)
Output: {"terrain": "ripples", "dim": 10, "budget": 2000, "seed": 1, "value": ..., "evaluations": ...}
        passes when value is no higher than the best of 2000 random points

Constraints

  • 8 <= dim <= 12, 1500 <= budget <= 3000
  • Use random for any randomness (the tests seed it), and bound your loops by the number of evaluations, not by the clock, so the result is the same on every run.

Goals

  • Search a rugged landscape with many cooperating candidates
  • Combine each candidate's own memory with the best found by the group
  • Spend a fixed evaluation budget without getting stuck in the first dip
Starting Python…