遗传算法的时间复杂度

Question

是否有可能计算遗传算法的时间复杂度？

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)

谢谢

更新:

 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

健身:戴维斯 - 布尔丁指数

Answer 1

不是像O(P*G*O(适应)*((Pc*O(交叉))+(Pm*O(突变))))

IE的复杂性与项目数,代数和每代计算时间有关

如果P,G,Pc和Pm是常数,真正简化为O(O(适应)*(O(突变)+ O(交叉)))

Answer 2

如果代数和种群规模是恒定的，只要你的变异函数、交叉函数和适应度函数需要已知的时间，那么大 o 就是 O(1) - 它需要恒定的时间。

现在，如果你问一个人口为 N 且世代数为 M 的大 O 是多少，那是不同的，但正如你提前知道所有变量的情况所述，所花费的时间是恒定的您的输入。