Genetic algorithm only using selection

Question

Suppose you have a population of N individuals with fitness 1, 2, . . . , N (i.e., all individuals have a
unique fitness value). Suppose you repeatedly apply tournament selection without replacement with
tournament size s = 2 to this population, without doing crossover, mutation, and replacement.

In other words, you run a genetic algorithm with selection alone.
After a certain number of generations you will end up with a population consisting of N copies of
the same individual. 
Can you give an estimate of the number of generations needed to achieve that?

Is the answer to this just log(n) ?

Carlos Mougan · Answer

The complexity of one generation will be O(N/2). In order to make the whole population the same, you will need N generations. My answer will be O(N**2).

You can also evaluate the time complexity by actually measuring the run time and averaging.

If you don't do crossover, mutation or replacement you are just selecting the best of your individuals.

Genetic algorithm only using selection

One Answer

Add your own answers!

Ask a Question