遗传算法的时间复杂度

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

健身：戴维斯-博尔丁指数

- Maggie

---

这段话写得太模糊了，无法回答。你如何评估适应度？你是如何组合基因的？你的终止条件是什么？ - templatetypedef

@templatetypedef 我相信终止条件是1000代。 - undefined

这个主题的一些论文链接可以在cs stackexchange上找到：https://cs.stackexchange.com/questions/7793/time-complexity-of-genetic-algorithms - bmaddy

Answer 1

这不是类似于 O（P * G * O（Fitness）*（（Pc * O（交叉））+（Pm * O（变异））））的东西吗？

也就是说，复杂度与物品数量、代数数量和每一代的计算时间有关。

如果P、G、Pc和Pm是常数，那么这个式子可以简化为O（O（Fitness）*（O（变异）+ O（交叉）））。

- undefined

---

根据您的想法，时间复杂度应为O（P * G * O（适应度）+ G *（Pc * O（交叉）+ Pm * O（变异）））。 - shen ke

原始答案将 O(Fitness) 与 O(Mutation)（或 O(crossover)）相乘，从而产生时间的平方。我认为，交叉或变异操作通常不需要进行适应性评估。 - shen ke

Answer 2

如果世代数量和种群大小保持不变，只要您的变异函数、交叉函数和适应度函数需要已知的时间量，那么大O表示法是O(1)——它需要恒定的时间。现在，如果您想知道在N个种群和M个世代时的大O表示法将会是什么，那就不同了，但是如上所述，只要您预先知道所有变量，那么所需的时间与输入相关是恒定的。

- Kane

Answer 3

遗传算法并非混沌，而是随机的。其复杂度取决于遗传算子的选择、实现（这可能对总体复杂度产生非常重要的影响）、个体和种群的表示方式，以及显然取决于适应度函数。 在通常的选择（点突变、单点交叉、轮盘赌选择）下，遗传算法的复杂度为O(g(nm + nm + n)), g为代数数量，n为种群大小，m为个体大小。因此，复杂度的数量级为O(gnm)。
当然，这忽略了取决于应用程序的适应度函数。

- Noah Ryan

Answer 4

能否计算遗传算法的时间和计算复杂度？

是的，Luke和Kane的答案可以（有附加条件）。

然而，大多数遗传算法本质上是混沌的。因此，计算O()可能不太有用，甚至更糟糕的是可能会误导。

有一种更好的方法来衡量时间复杂度——通过实际测量运行时间并取平均值。

- Ray