装箱遗传算法的时间复杂度
Time complexity of a genetic algorithm for bin packing
我正在尝试探索用于装箱问题的遗传算法 (GA)，并将其与经典的 Any-Fit 算法进行比较。然而，任何学术文章中都没有提到 GA 的时间复杂度。这是因为时间复杂度很高吗？ GA的主要目标是在不考虑时间的情况下找到最佳解决方案？基本GA的时间复杂度是多少？
假设终止条件是迭代次数并且它是常数，那么通常它看起来像这样：
O(p * Cp * O(Crossover) * Mp * O(Mutation) * O(Fitness))
p - population size
Cp - crossover probability
Mp - mutation probability
如您所见，它不仅取决于参数，例如。种群大小还与交叉、变异操作和适应度函数的实现有关。实际上会有更多参数，例如染色体大小等
您在出版物中看不到太多关于时间复杂度的信息，因为研究人员大部分时间都使用收敛时间来比较 GA。
编辑收敛时间
每个 GA 都有某种终止条件，通常是收敛标准。假设我们想要找到一个数学函数的最小值，那么我们的收敛标准就是函数的值。简而言之，当不再值得继续优化时，我们在优化过程中达到收敛，因为我们最好的个体并没有显着改善。看看这个图表：
您可以看到，在大约 10000 次迭代后，适应度并没有太大改善，并且直线变得平坦。 最佳情况 场景在大约 9500 次迭代时达到收敛，在那之后我们没有观察到任何改进，或者它很小。假设每行显示不同的 GA，那么 最佳情况 具有最佳收敛时间，因为它首先达到收敛标准。
我正在尝试探索用于装箱问题的遗传算法 (GA)，并将其与经典的 Any-Fit 算法进行比较。然而，任何学术文章中都没有提到 GA 的时间复杂度。这是因为时间复杂度很高吗？ GA的主要目标是在不考虑时间的情况下找到最佳解决方案？基本GA的时间复杂度是多少？
假设终止条件是迭代次数并且它是常数，那么通常它看起来像这样：
O(p * Cp * O(Crossover) * Mp * O(Mutation) * O(Fitness))
p - population size
Cp - crossover probability
Mp - mutation probability
如您所见，它不仅取决于参数，例如。种群大小还与交叉、变异操作和适应度函数的实现有关。实际上会有更多参数，例如染色体大小等
您在出版物中看不到太多关于时间复杂度的信息，因为研究人员大部分时间都使用收敛时间来比较 GA。
编辑收敛时间
每个 GA 都有某种终止条件，通常是收敛标准。假设我们想要找到一个数学函数的最小值，那么我们的收敛标准就是函数的值。简而言之，当不再值得继续优化时，我们在优化过程中达到收敛，因为我们最好的个体并没有显着改善。看看这个图表：
您可以看到，在大约 10000 次迭代后，适应度并没有太大改善，并且直线变得平坦。 最佳情况 场景在大约 9500 次迭代时达到收敛，在那之后我们没有观察到任何改进，或者它很小。假设每行显示不同的 GA，那么 最佳情况 具有最佳收敛时间，因为它首先达到收敛标准。