Intro to Genentic Algorithm

  • genentic algorithm
  • 是一种由进化的灵感的来的算法，基于生物进化的机制
  • 可用于解决类似于单染色体类型的数据结构
  • 也可以被视为函数优化器
  • 适合于使用大型潜在的搜索空间并且引导他们。并且找到最优的组合。
  • 由john Holland提出的
  • 可以为优化和机器学习提供便捷有效的方法

思想

  • 一定数量的种群的解根据时间进化，并且在每一代进化之后都变得更加健壮
  • 并且每一个子代都是有父代交叉并且随机变化，还有其他的基因操作

组成

  • 基本的基因数量（基因，染色体）
    • 二进制字符串
    • 实数
    • 有规则
  • 初始化(创造)
  • 父母选择（产生后代）
    • 随机选择父母（通过贝叶斯概率分布）
    • 染色体的改动
      • 交叉和重组
        • 交叉
          • 导致搜索空间中的移动
          • 在种群中存储丢失的信息
        • 重组
          • 这个可以在种群进化的初期加快搜索速度
          • 它会导致一个有效的基因模板组合
      • 一个Evaluator是连接传统遗传算法和他解决的问题的唯一连接
        • 他会解码染色体并且分配给他一个健壮的方案
  • 进化函数（环境）
  • 基因操作（随机重组）
  • 参数设置（训练）

好处

  • 概念容易理解
  • 模式和应用分离开来
  • 支持多对象优化
  • 适合噪音比较多的环境
  • 总能找到答案，并且答案随着时间的变化而变好
  • 总是并行的，容易分布
  • 如果已经获得了那个遗传算法应用的知识，那么有很多种方法来加速和改进遗传算法
  • 容易去使用或者利用以前的或者自动的求解结果

什么时候要用

  • 交替的结果太慢或者太复杂
  • 需要一个实验性的工具来检测新的逼近
  • 一个和曾经被解决的问题很相似的问题
  • 相混合一个已经存在的解法

算法流程

  • 伪代码
1
2
3
4
5
6
7

initialize node poupulation;
evaluate node population;
while(Termination){
    select parent nodes for reproduction;
    perform recombination and mutation;
    evaluate population;
}

我的看法

  • 就是不停地优化后代
Algorithm
Comments

Comments