Time Complexity of Genetic Algorithm

Question

Is it possible to calculate the time complexity of genetic algorithm?

These are my parameter settings:

    Population size (P) = 100
    # of Generations (G) = 1000
    Crossover probability (Pc) = 0.5 (fixed)
    Mutation probability (Pm) = 0.01 (fixed)

Thanks

Updated:

 problem: document clustering
 Chromosome: 50 genes/chrom, allele value = integer(document index)
 crossover: one point crossover (crossover point is randomly selected)
 mutation: randomly change one gene
 termination criteria: 1000 generation

fitness: Davies–Bouldin index

Solution 1

isnt it something like O(P * G * O(Fitness) * ((Pc * O(crossover)) + (Pm * O(mutation))))

IE the complexity is relative to the number of items, the number of generations and the computation time per generation

If P, G, Pc, and Pm are constant that really simplifies to O( O(Fitness) * (O(mutation) + O(crossover)))

Solution 2

If the number of generations and population size is constant, as long as your mutation function, crossover function, and fitness function takes a known amount of time, the big o is O(1) - it takes a constant amount of time.

Now, if you are asking what the big O would be for a population of N and a number of generations M, that is different, but as stated where you know all the variables ahead of time, the amount of time taken is constant with respect to your input.

Solution 3

Genetic Algorithms are not chaotic, they are stochastic. The complexity depends on the genetic operators, their implementation (which may have a very significant effect on overall complexity), the representation of the individuals and the population, and obviously on the fitness function. Given the usual choices (point mutation, one point crossover, roulette wheel selection) a Genetic Algorithms complexity is O(g(nm + nm + n)) with g the number of generations, n the population size and m the size of the individuals. Therefore the complexity is on the order of O(gnm)).
This is of cause ignoring the fitness function, which depends on the application.

Comments

[shen ke]

Following your idea, the time complexity should be O(P * G * O(fitness) + G * (Pc * O(crossover) + Pm * O(mutation))).

[shen ke]

The original answer multiples O(Fitness) with O(Mutation) (or O(crossover)), which produces a square of time. In my opinion, crossover or mutation operations usually do not require fitness evaluation.