5
$\begingroup$

I've had a bit of experience programming Neural networks but I am fairly new with genetic algorithms (I'm only 17). I have a major issue that I can't understand. If a child get's one chromatid from one parent and another from another parent, then the genes are crossed over, how do you determine which alleles are active in the child? How do other people go about mating with genetic algorithms. No need to go deep into it because I also want to work somethings out for myself but a general idea would be good enough. Thanks in advance.

$\endgroup$
  • $\begingroup$ How is that a CS question? You can use/model whatever you like in an algorithm. How it works in nature is more a question for Biology. $\endgroup$ – Raphael Aug 5 '13 at 20:38
  • 1
    $\begingroup$ in some GAs the biology analogies of "genes" and "alleles" might roughly correspond to real features, in others not. generally in GAs there is only a loose ref to "genes" as strings and nothing further/deeper. crossover sometimes happens between objects more complex than strings eg parse trees etc. $\endgroup$ – vzn Aug 7 '13 at 18:15
5
$\begingroup$

Generally speaking, evolutionary algorithms stop well short of trying to model real biology, and this is one example of something that occurs in nature but not in commonly used evolutionary algorithms.

Instead, we tend to use a system where all individuals have only one value for each gene, and they're all "active". Replication, mutation, and recombination are considered to be atomic operations with no concern given to any intermediate stages. Consider the simplest case of a binary encoding. You might have two parents, A and B, as

A = 0101101001
B = 1001010010

To do crossover, we simply create an offspring by choosing exactly one parent for each bit in the offspring to copy from. We can formalize this a bit with something called a mask -- a bit string where a 1 indicates that we choose the value from A and a 0 indicates we choose from B. Thus, one point crossover might have a mask like

M = 0000001111

with our parents A and B, we would then get a child C as

A = 0101101001
          ^^^^
B = 1001010010
    ^^^^^^
C = 1001011001

So here, the offspring C has gotten copies of the first six genes of parent B and the last four of parent A, but at no point do we consider the process by which chromosomes would be copied in a biological system. We simply allocated a new variable and did a memory copy to instantaneously duplicate parts of the parents.

If we want to mutate the offspring, we might simply pick a bit at random and flip it. Again, we don't worry about biology here and how mutations actually occur in nature. We just define mutation to be the flipping of a single bit in memory and do it.

One point crossover is about the simplest thing you could do, but essentially all commonly used methods look similar in that the child gets a single value for each position and no explicit notion of binding or connection to the parents is considered. We don't really think of crossover in terms of chromatids -- we just directly copy allele values using some well-defined (but probably not biologically plausible) crossover operator. So there's never any question of which allele values are active -- they all are.

$\endgroup$
  • $\begingroup$ Thanks, that was very informative. Can you therefore give me more advice on this: How should I chose the mask? If I personally program every organism to have the same mask, then it would limit the amount of variation that could happen. Should I randomly generate a mask at the onset of reproduction? $\endgroup$ – Samuel Mungy Aug 4 '13 at 14:02
  • $\begingroup$ The mask is sort of an theoretical device used to explain things. In practice, one typically chooses one of a few well-defined operators. One-point, two-point, and uniform crossover are popular for bit strings. There are other options like SBX for real-valued encodings, numerous choices for permutations. For one point, you'd randomly choose a crossover point each time. For uniform, you just randomly choose for each independent gene each time you do crossover. You don't have to bother with really creating the mask string. $\endgroup$ – deong Aug 4 '13 at 16:02
  • $\begingroup$ Thanks, I heard about uniform crossovers. I will try that. Sorry, but I wish to ask one more thing. When making my 'organism' what would you advise me to start with? Programming the nature of the genes or programming the neural network? Which should I start with so I can have a smoother experience. $\endgroup$ – Samuel Mungy Aug 4 '13 at 16:46
  • $\begingroup$ I don't think it really matters much where you start. You can test the neural net without a GA, but you can't test the GA without some sort of fitness function, so you might lean towards doing the neural net first, but like I said, I think it's just personal preference either way. $\endgroup$ – deong Aug 4 '13 at 22:48

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.