可以计算出遗传算法的时间复杂度吗?
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发布于 2012-02-05 10:04:05
它是不是有点像O(P *G*O(适应度)* ((Pc *O(交叉))+ (Pm *O(变异)
即复杂度与项数、代数和每代的计算时间相关
如果P、G、Pc和Pm是常数,则真正简化为O( O(适应度)*(O(变异)+O(交叉)
发布于 2012-02-05 10:18:55
如果世代数和种群大小是恒定的,只要你的变异函数、交叉函数和适应度函数需要一段已知的时间,那么大的o就是O(1) -它需要一段恒定的时间。
现在,如果你在问,对于N代和M代的人口,大O会是什么,这是不同的,但正如你提前知道所有变量所说的那样,所花费的时间与你的输入是恒定的。
发布于 2012-05-03 10:56:47
遗传算法不是混沌的,它们是随机的。复杂性取决于遗传算子、它们的实现(这可能对整体复杂性有非常重要的影响)、个体和群体的表示,显然还取决于适应度函数。给定通常的选择(点突变、一点交叉、轮盘赌选择),遗传算法的复杂度为O(g(nm + nm + n)),其中g表示世代数,n表示种群大小,m表示个体大小。因此,复杂度是O(Gnm)的数量级。
这是忽略适应度函数的原因,该函数取决于应用程序。
https://stackoverflow.com/questions/9146086
复制相似问题