遗传算法及其应用范围

发表于 算法 2017-04-23 阅读数: 88

遗传算法( GA , Genetic Algorithm ): 利用自然界中的自然选择、交叉、变异求得一些函数的最优解。

如我们要解答1/(|x1|+|x2|+|x3|+|x4|+1)的最大值,步骤如下:

  1. 初始化X条染色体
  2. 进行初始适应性评估,评估函数是:1/(|x1|+|x2|+|x3|+|x4|+1),标准答案是1
  3. 选出初始最优适应值
  4. 开始繁衍(即开始循环迭代,比如两千代)
  5. 求出适应值的和,以及每条染色体与总适应值的比
  6. 对染色体进行选择,根据比值淘汰最弱的染色体,通过轮盘赌保留优秀染色体
  7. 对染色体进行配对交叉
  8. 染色体变异
  9. 重新评估适应值,并检测是否有更大的最优适应值,有则更新
  10. 重复2-9的步骤

遗传算法

这样在子代中,经常会产生优秀的染色体,不断地更新后,最优适应值总会靠近标准答案。

见我的测试结果:

遗传算法

但也并非总能获得非常优秀的答案,如:

遗传算法

主要原因在于以下几点:

  1. 适应性函数的选择不太恰当,它可能会使得答案陷入局部最优。
  2. 初始种群太小,无法获得准确答案
  3. 种群有一定几率过早地收敛

但是遗传算法总是能得到良好的解。至少在我的测试数据里结果经常是0.93,离标准答案的差是7%,这是还能够接受的水平

详细地代码将于后天讲解,若您有兴趣的话可以上网搜索遗传算法,先试试看。

欢迎关注微信公众号:幻象客https://www.huanxiangke.com

欢迎进入极致分享:https://alltoshare.com

幻象客 二维码

Add comment