evolutionary algorithms with a "dynamic population"

Question

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?

Answer 1

Rather then going with an ad-hoc solution with unknown properties I'd propose first trying some related well-known techniques such as:

• elitism
• truncation selection
• steady state genetic algorithm

You've already mentioned elitism. The truncation selection is somehow connected with the elitism principle. And you may specifically be interested in the steady state selection (aka steady state genetic algorithm) which eliminates the concept of a generation at all.

As a good overview of wide variety of related optimization methods (including the mentioned ones) I can recommend the book "Essentials of Metaheuristics" by Sean Luke (which is freely available; but you can also buy it to thank the author).

Answer 2

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.

Answer 3

There is no such thing as "logical reasons" for most evolutional approaches. In general - creating some "custom", "personal" implementation of the evolutional method is not a good idea. There are dozens of developed methods, tested, evaluated, criticised and corrected. Assuming, that one idea in form of "oh, I will do this that way" will be better than those heavily discussed methods of scientists is rather naive. What is even more important - such approaches are not really a "true" machine learning methods - these are just "fuzzy" (not in the mathematical sense) heuristics to avoid complete random guessing. And as such - for almost all of them there is no true mathematics behind it. There are at least three main ways:

• If you want a "logical reasons" then select some existing, mathematically correct model for your problem, maybe some Gaussian Process, Multi-Armed Bandit based method, etc.If you have limited possibility of actually testing and evaluting (which seems to be the case as you need an user input) this looks like the best choice - so no evolution.
• If you have some time to spare, and you can perform some experiments - then select one of existing evolutional approaches which seems based suited for your needs - hundreads of scientists already faced similar issues - just google for their papers
• if you have huge amounts of time then think about your own strategy, and test it, evaluate, modify - this is very complex (and expensive) process, which does not guarantee any results (but will give you some answers regarding your intuition)

I am not a specialist in the field of evolutionary algorithms, but I've already seen very similar models and algorithms to the one outlined here, so it is rather probable that you can find papers with evaluation of such approaches and some valuable discussion sections.