2
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I'm not sure what you mean by "gene strength". However, if you can measure "gene strength" then you can certainly use it in your reproduction probability. $\endgroup$
    – Ray
    Commented Apr 24, 2016 at 21:14
  • $\begingroup$ @Ray 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 to the next generation or should child genes be mixed randomly? $\endgroup$
    – PeterTheLobster
    Commented Apr 24, 2016 at 21:23
  • 1
    $\begingroup$ Can you? Of course you can. There are no rules here. You can add the "gene strength" to the fitness function. You can do anything you want as long as it makes the solution converge faster. $\endgroup$
    – Ray
    Commented Apr 24, 2016 at 21:30
  • $\begingroup$ @Ray Great thanks! I was just wondering wether that was against a certain standard or definition. I personally believe that you should do whatever works best, but this is for an assignement so I wanted make sure. $\endgroup$
    – PeterTheLobster
    Commented Apr 24, 2016 at 21:36
  • 2
    $\begingroup$ Sounds related to the common GA concept of elitism; since your best incumbent solution is your best scoring individual, you can make sure to keep one or a few copies of this individual in each new generation (elitism), or use a few copies as base for "good individuals" with only few random mutations without crossover (bringing these to next gen.). This will implicitly bring good genes over to your scoring functions, as the genes of the best individual (via elitism) will, probabilistically after say tournament selection, contribute to new individuals via e.g. mutations/crossover etc. $\endgroup$
    – dfri
    Commented Apr 24, 2016 at 21:37

1 Answer 1

Reset to default
2
$\begingroup$

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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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