Search code examples
machine-learninggenetic-algorithmevolutionary-algorithm

evolutionary algorithms with a "dynamic population"

I want to solve a problem using a evolutionary/genetic algorithm. It has something to do with art - people watching the algorithm should try out one chromosome (= possible solution) and should evaluate it according to their taste.

Using this setup, the evaluation process is (so to say) quite costly - it takes a lot of time for each chromosome to be tested. To make sure that a progress is taking place in feasible time (which means frequent change of generations), I have to accept a small population size (which has drawbacks as well). The other option would be to have a bigger population size but only few generations.

I thought of a different solution which I'd like to call "dynamic population". It would work like this:

  1. With population size x, to setup the algorithm, x chromosomes are created randomly and numbered from 1 to x which indicates their age.
  2. The fitness of the initial population's chromosomes is evaluated.
  3. One new chromosome is created using crossover and/or mutation mechanisms. age = 1 is assigned to this new chromosome. All other chromosomes grow one step older (age = age + 1). Chromosome with age > x are removed from the population. (In those cases where the crossover mechanism produces two chromosomes as offspring, one child is chosen to get age = 1 the other gets age = 2 and for the other chromosomes age = age + 2)
  4. Repeat 1 - 3 until a solution is found.

(This process could certainly easily be adopted to use elitism.)

Using such a mechanism, there would be a (possible) progress with every (new) chromosome and (what is more important in my case) whith every evaluation.

I can however also think of some disadvantages...

Are there logical reasons such an implementation using a "dynamic population" is not accomodating with an evolutionary algorithm?

Solution

  • I don't see any reason to use your approach since your generations will overlap. You give up the ability of the GA to sample different regions of the solution space and you more or less fall back to some kind of trajectory-based algorithm. I am also not sure how selection will work and how do you choose the parents to produce only one child individual.

    Regarding your idea about user interaction, I saw a paper some time ago: http://hal.inria.fr/docs/00/81/86/41/PDF/vizgec2013.pdf

    Hope this helps.