首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >遗传算法的时间复杂度

问遗传算法的时间复杂度
EN

Stack Overflow用户
提问于 2012-02-05 09:11:34
回答 4查看 15.9K关注 0票数 9

可以计算出遗传算法的时间复杂度吗?

代码语言:javascript
复制
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)

谢谢

更新:

代码语言:javascript
复制
 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

健身:Davies–Bouldin index

EN

回答 4

Stack Overflow用户

发布于 2012-02-05 10:04:05

它是不是有点像O(P *G*O(适应度)* ((Pc *O(交叉))+ (Pm *O(变异)

即复杂度与项数、代数和每代的计算时间相关

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

票数 10
EN

Stack Overflow用户

发布于 2012-02-05 10:18:55

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

现在,如果你在问,对于N代和M代的人口,大O会是什么,这是不同的,但正如你提前知道所有变量所说的那样,所花费的时间与你的输入是恒定的。

票数 4
EN

Stack Overflow用户

发布于 2012-05-03 10:56:47

遗传算法不是混沌的,它们是随机的。复杂性取决于遗传算子、它们的实现(这可能对整体复杂性有非常重要的影响)、个体和群体的表示,显然还取决于适应度函数。给定通常的选择(点突变、一点交叉、轮盘赌选择),遗传算法的复杂度为O(g(nm + nm + n)),其中g表示世代数,n表示种群大小,m表示个体大小。因此,复杂度是O(Gnm)的数量级。

这是忽略适应度函数的原因,该函数取决于应用程序。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/9146086

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档