0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ yes. but using tournament selection without replacement, how many generations would it take to get a population consisting only by the same individual repeated N times? $\endgroup$ – ruben Dec 20 '19 at 12:01
  • $\begingroup$ I edited the original answer. $\endgroup$ – Carlos Mougan Dec 20 '19 at 14:28

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.