问一种装箱遗传算法的时间复杂度

EN

假设终止条件是迭代次数，并且它是常数，那么通常情况下，它看起来如下所示：

O(p * Cp * O(Crossover) * Mp * O(Mutation) * O(Fitness))
p - population size
Cp - crossover probability
Mp - mutation probability

正如你所看到的，它不仅取决于诸如例如。种群规模的实现还取决于交叉、变异操作和适应度函数的实现。在实践中，会有更多的参数，如染色体大小等。

你不会在出版物中看到太多关于时间复杂性的东西，因为研究人员大部分时间都会用收敛时间来比较遗传算法。

编辑收敛时间

每个GA都有某种终止条件，通常是收敛准则。假设我们想要找到一个数学函数的最小值，那么我们的收敛准则就是函数的值。总之，在优化过程中，当我们不再值得继续优化时，我们就达到了收敛，因为我们最好的个体并没有显着地改善。请看一下这张图表：

​

​

您可以看到，经过大约10000次迭代之后，适应度并没有太大的改善，而且直线也在变平。最好的情况场景在大约9500次迭代时达到收敛，在那之后我们没有观察到任何改进，或者它是微不足道的。假设每条线表现出不同的遗传算法，那么最优情形具有最佳的收敛时间，因为它首先达到收敛准则。