Untangling Overlapping Peaks

A spectrometer records a signal at 51 points x = 0.0, 0.2, ..., 10.0. The signal is the sum of k bell-shaped peaks plus a little measurement noise, and the peaks overlap, so two peaks can look like one. Recover them: write fit_peaks(xs, ys, k) that returns k triples (height, centre, width) whose curve

curve(x) = sum of height * exp(-(x - centre)**2 / (2 * width**2))

matches the readings ys as closely as possible, measured by the sum of squared differences.

The tests call fit_peaks(*spectrum(k, seed), k). spectrum(k, seed) returns the readings (xs, ys), and fit_error(xs, ys, peaks) computes the error of a list of triples. Both are available in your code, so you can try them with Run.

How this problem is scored

A fit passes if every triple is in range and its error is no larger than that of the simple rule "on each of the k highest local maxima of the readings (a reading larger than the one before it and at least the one after it), put a peak of width 0.5 as high as that reading" (if there are fewer than k maxima, the missing peaks get height 0). Its quality (0 to 100) is measured on a logarithmic scale from that rule's error down to the smallest error we know: every factor of ten counts the same.

Examples

Input:  xs, ys = spectrum(2, 1); fit_peaks(xs, ys, 2)
Output: a list such as [(2.77, 6.61, 0.81), (1.88, 7.28, 1.22)]
Explanation: this fit has error about 0.143. The highest-maxima rule has error about 40.3: it
sees one tall bump near x = 6.8 and puts its second peak on a noise wiggle.

Constraints

• 2 <= k <= 5; every triple must have height >= 0, 0 <= centre <= 10 and 0.1 <= width <= 3, and the triples may come in any order
• Each test must finish in well under a second in your browser. Limit your loops by a number of generations, not by the clock, so the result is the same on every run.

Goals

• Fit a nonlinear model with many local optima
• Evolve real-valued vectors with difference-based mutation
• Respect parameter bounds during the search