Problem 659480 · easy · Level 06 Heuristics & Optimization

One Generation of Seed Breeding

genetic algorithm · selection · crossover · mutation · elitism

A plant breeder describes each seed line by a string of 0s and 1s (one character per gene). A line's fitness is the number of positions where it agrees with the ideal string target. Write next_generation(pop, target, elite, tournaments, cuts, flips) that returns the next generation, built with these rules:

  1. Keep the best. The elite fittest lines of pop are copied unchanged to the front of the new generation, fittest first. Equal fitness: the line that comes earlier in pop goes first.
  2. Pick parents. Each entry of tournaments is a list of indices into pop. Its winner is the fittest of those lines (equal fitness: the smaller index wins).
  3. Cross. Winners are used in pairs: tournaments 0 and 1 give parents a and b of pair 0, tournaments 2 and 3 give pair 1, and so on. Pair k is cut at position c = cuts[k] and gives two children, first a[:c] + b[c:], then b[:c] + a[c:]. Children are appended in this order until the new generation has len(pop) lines; a child that no longer fits is dropped.
  4. Mutate. Each (k, p) in flips flips character p of child k (k counts the children that were kept, from 0; elite lines are never mutated). Flips are applied in the order given.

Return the new generation as a list of strings.

Examples

Input:  pop = ["0110", "1010", "1111", "0001"], target = "1011", elite = 1,
        tournaments = [[0, 3], [2, 0], [1, 3], [0, 2]], cuts = [1, 3], flips = [(1, 0)]
Output: ["1010", "0111", "0001", "1011"]
Explanation: fitnesses are 1, 3, 3, 2, so the elite is "1010" (it beats "1111" on index).
Pair 0 is "0001" x "1111" cut at 1: "0111" and "1001". Pair 1 is "1010" x "1111" cut at 3:
"1011" (its second child does not fit). Flipping character 0 of child 1 turns "1001" into "0001".

Constraints

  • 1 <= len(pop) <= 60; all lines and target have the same length L, 1 <= L <= 64
  • 0 <= elite <= len(pop); with m = len(pop) - elite children needed, tournaments has 2 * ceil(m / 2) non-empty lists and cuts has ceil(m / 2) values with 0 <= c <= L
  • every (k, p) in flips has 0 <= k < m and 0 <= p < L

Goals

  • Apply tournament selection, one-point crossover and bit-flip mutation by hand
  • Keep the best individuals unchanged from one generation to the next
  • Follow a precise specification with tie-breaking rules
Starting Python…