MutateEvolve - akilmarshall/procedural-image-generation Wiki

MutateEvolve is a naive genetic algorithm that attempts to optimize a population through a culling and mutation step.

  1. Initialize the population randomly
  2. for t time steps
  3. order the population by fitness
  4. cull the bottom half
  5. copy the fit half, mutating each at a random position
  6. goto 3.

Analysis

This algorithm experimentally fails to improve a population, for example a population of 500 5x5 images had their average fitness plotted over 3 consecutive episodes of 100 steps each.

Obviously the algorithm does not work, average fitness falls to $\approx0$ rapidly and then stays there forever. Primarily I believe this is due to the algorithm having little stability with respect to the individuals that are culled and with the new individuals that are accepted into the population.

Variations

How can MutateEvolve be tweaked or modified in order improve its performance (either increase fitness scores, or decrease time required to maximize fitness).

MutateImprove

Modify the mutation step:

  1. select a random location
  2. neighboring tiles are forced to conform to the neighbor function

Fitness decays notably slower than the unmodified algorithm, however still tends to 0 over time.