4
$\begingroup$

In a classic example of a genetic algorithm, you would have a population and a certain amount of simulation time to evaluate it and breeding. Then proceed to the next generation.

Is it possible, during the simulation process, to have an isolated and small part of the population and keep it evolving in their own little island for some time while the rest of the population continues to evolve normally? After that, they could be reunited with the rest of the population and the end of the simulation would go through. After that, breed the population and continue.

This is a super important part of natural evolution and probably some know if it actually works with genetic programming?

$\endgroup$
3
$\begingroup$

There have been extensive studies within evolutionary computation in the area of island models and niching for doing exactly this.

The advantages of this approach include greater population diversity (which is particularly useful when the problem is multiobjective) and the potential for concurrent execution of each separate population.

See also the answers to the question What is niching scheme?.

With specific reference to genetic programming, here is a recent paper which uses a parallel island model.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Hi. Could you please update your last link (which is broken)? Then, please, flag this comment for deletion. $\endgroup$ – nbro Jul 7 '19 at 22:05
1
$\begingroup$

The island model and niching mentioned by NietzscheanAI are well known ways to isolate populations. However, the populations are not really isolated as individuals migrate from one population to the other. In these cases depending on the sampling strategy used to sample parents for crossover migrating individuals may dominate a population causing rapid convergence.

Co-evolution is a truly isolated population approach first introduced by Reed et al. in 1967. Two kinds of co-evolution exist namely co-operative co-evolution and competitive co-evolution. While hybrid models exist co-evolved islands such as here and here, generally co-evolution is isolated and do not migrate individuals.

Co-operative co-evolution evolves two or more populations that work together to solve a problem, and competitive co-evolution compete where a gain in one population is a loss for another.

Generally the fitness function is altered from explicit to implicit and various techniques are used to do this.

For more information

| improve this answer | |
$\endgroup$
  • $\begingroup$ The formal definition of coevolution is effectively that 'the fitness of one population is a function of (the fitness of) another', so while they are indeed 'completely isolated' with respect to migration of genetic material, they are also applicable only to problems with some dual (co-operative or adversarial) notion of fitness. $\endgroup$ – NietzscheanAI Jul 8 '19 at 17:37
0
$\begingroup$

Neuroevolution of Augmented Topologies (NEAT) and algorithm developed by Ken Stanely, does this by partitioning populations into species. This is done by storing innovation numbers for each gene (node/connection). When a never before used structure is added through mutation the innovation number is incremented, by doing this you can calculate a historical compatibility distance between any two genomes by comparing innovation numbers. This is done because adding a new structure may often times initially hurt a genomes fitness but may actually turn out to be valuable after some optimization. By using this structurally focused speciation, new structures are protected as the elitism is handled in individual species not the whole population.

| improve this answer | |
$\endgroup$
-1
$\begingroup$

If I understand you correctly, I think you're referring to elitism.

As Wikipedia explains: "A practical variant of the general process of constructing a new population is to allow the best organism(s) from the current generation to carry over to the next, unaltered. This strategy is known as elitist selection and guarantees that the solution quality obtained by the GA will not decrease from one generation to the next."

| improve this answer | |
$\endgroup$
  • $\begingroup$ Elitism ensures that the fittest in each generation survive, it doesn't actually partition the population in the manner stated by the OP. $\endgroup$ – NietzscheanAI Oct 6 '16 at 19:06
  • 1
    $\begingroup$ Yeah, I wasn't able to glean that context from the OP. Nor did I know about he Island Model method in GA. I'd recommend the OP approve your answer. $\endgroup$ – Doxosophoi Oct 6 '16 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.