Genetic algorithm only using selection

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

Topic genetic-algorithms

Category Data Science

1
answered at

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.

About

Geeks Mental is a community that publishes articles and tutorials about Web, Android, Data Science, new techniques and Linux security.