1

What's the point of crossover probability in genetic algorithm?

The general procedure of a genetic algorithm is: (source)

First an initial population is generated. Then a selection method is used (in this case the tournament selection) to choose a pair of individuals that will create a pair of children.

The children are added to the children population until its size reaches the desired value.

The next step is to combine the parents population of size N and children population of size M, either by replacing one by the other, keeping the best N individuals from both populations.

N = population size
P = create parent population by randomly creating N individuals
while not done
    C = create empty child population
    while not enough individuals in C
        parent1 = select parent   ***** HERE IS WHERE YOU DO TOURNAMENT SELECTION *****
        parent2 = select parent   ***** HERE IS WHERE YOU DO TOURNAMENT SELECTION *****
        child1, child2 = crossover(parent1, parent2)
        mutate child1, child2
        evaluate child1, child2 for fitness
        insert child1, child2 into C
    end while
    P = combine P and C somehow to get N new individuals
end while

Of course we might want to perform mutation with a given probability, for instance every 1 out of 100 children will be mutated.

But I don't see the point of crossover rate. What happens when a pair of parents is selected in tournament selection and the crossover didn't happen? Should the parents be added to the children population? In this case we would end up with duplicate members in parents and children population.

The goal here is to create as many children as desired in each generation, and it has to happen by means of crossover. How to change this algorithm so that crossover rate makes any sense?

If crossover probability is 100%, then all offspring is made by crossover. If it is 0%, whole new generation is made from exact copies of chromosomes from old population (but this does not mean that the new generation is the same!). Source

If the crossover probability is 0%, then the whole generation is made of exact copies of chromosome from old population. Then how come the new generation isn't the same?

Community
  • 1
  • 1
user5539357
  • 1,024
  • 1
  • 9
  • 19
  • "Then how come the new generation isn't the same?" Mutation. – John Coleman May 10 '16 at 11:05
  • @JohnColeman it says the new chromosomes are exact copies of the chromosomes from the old population, so certainly not. – user5539357 May 10 '16 at 11:10
  • They probably misspoke, but even if both mutation and probability rates are put to 0, not every member of the population will reproduce, so the population as a whole will still be changing. – John Coleman May 10 '16 at 11:14

2 Answers2

1

It depends on the application, genetic algorithms need not be implemented in a strict way. You can see there are many vague statements in the pseudocode.

In this example, if crossover does not happen, parents and children are the same, and mutation step is applied as usual. This is not a problem because the main loop will be evaluated so many times so that there will be enough crossovers. The main goal is to improve the learning, creating lots of children may not necessarily achieve this goal in every application.

An example is that aggressive crossover might actually corrupt some really good parents so the learning quality can decrease. A crossover rate may protect that to some extent, but as I said it depends on the application.

Best.

bekce
  • 3,782
  • 29
  • 30
  • Let's say the desired population size is N, each generation. We can simply run a loop from 1 to N and each time find a pair of parents (using tournament selection), perform crossover with given probability, and if it happens, perform mutation with given probability - and add both children to the population of the next generation. If the crossover didn't happen I could add both parents to the next generation's population. I guess it makes most sense? – user5539357 May 10 '16 at 11:15
0

All childs in new generation are "clones" of one parent in old generation. But even if you have 4 parents with chromosomes "A, B, C, D", you can have 6 childs which has "A, A, A, C, C, D" chromosomes, therefore they are not same.

PS : And of course, if mutation is applied, then the difference is even bigger.

libik
  • 22,239
  • 9
  • 44
  • 87
  • So suppose I select two parents for crossover and decide whether to perform crossover or not. If the decision is no, then should I add clones of both parents to the new population? But if I get it correctly, I can still perform mutation on these clones. – user5539357 May 11 '16 at 10:01