Cheap and Secure Web Hosting Provider : See Now

Can the reproduction function of an evolutionary algorithm consider gene strength?

, , No Comments
Problem Detail: 

I am trying to solve the Zen Garden puzzle using an evolutionary algorithm. My question relates to evolutionary algorithms in general.

Bit about evolutionary algorithms: An evolutionary algorithm is an algorithm which tries to solve a given problem in a semi-random way. Most often I have seen it is implemented thusly: for a given starting state of the problem a generation of random solution approaches for is generated. Each speciemen (approach) has a set of genes which define it. Each speciemen is then used to try and find a solution to the problem. If no solutions are found, then we try to determine the fitness of each speciemen by some set of rules. For example- if the problem was to collect all treasures on a map, then the fitness a speciemen could be determined by the ammount of treasures it managed to collect. Once we determine their fitness we try to crossbreed the speciemen semi-randomly, giving higher chance of reproduction to those with higher fitness. This way we create a new generation of speciemen, where each of them has some genes from both of its parents. Then we try to solve the problem using the new generation of speciemen and the cycle goes on until a solution is found or we reach some kind of pre-determined limit of max-generations.

Question: Can the reproduction function which determines how speciemen (solution attempts) reproduce take into account some kind of gene strength to also determine which genes are best to be passed down to the child of two speciemen? What I mean by that is that for example if I could measure how much a certain gene contributed to the solution attempt can I give the gene a higher chance to be passed on or should child genes be passed on randomly?

Asked By : PeterTheLobster
Answered By : manlio

Can the reproduction function which determines how speciemen (solution attempts) reproduce take into account some kind of gene strength to also determine which genes are best to be passed down to the child of two speciemen?

Of course it can.

Anyway, consider that in GA this already happens implicitly. Using the established methods and genetic operators of genetic algorithms (not only reproduction but also crossover and mutation) the Holland's schema theorem states that low-order schemata with above-average fitness increase exponentially in successive generations.

(a schema is a template that identifies a subset of strings with similarities at certain string positions)

In Genetic Programming things are different:

  1. GA representations are often fixed size whereas GP representations and usually variable sized;
  2. GA normally have a semantic interpretation for a given location in a chromosome while GP solutions often do not exhibit location dependent meanings.

John Koza attempted to explain why genetic programming works by extending Holland's schema model and theorem to GP but with various differences / limitations (the class of problems and problem representations for which block processing is useful remains a challenging and open research topic in GP).

In GP your idea is the base of the modularization approach, e.g.

  • The encapsulation operation is a genetic operation that identifies a potential useful subtree and gives it a name so that it can be referenced and used later (see Genetic Programming: On the Programming of Computers by Means of Natural Selection)
  • Better yet, Adapting Representation through Learning (ARL). With ARL New subroutines are created using blocks of genetic material from the pool given by the current population.

    The detection of what are salient blocks of code is based on two notions: differential offspring-parent fitness and "active" blocks.

    The process of discovering building blocks and creating new subroutines based on simple blocks of code is applied recursively so that subroutines of any complexity can be discovered.

    Subroutines beneficial to some individuals could be invoked also by other individuals. The end result is the collection of subroutines that acquires the necessary structure for solving the problem (take a look at Towards Automatic Discovery of Building Blocks in Genetic Programming by Justinian Rosca for a complete description).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56694

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback