遗传算法

遗传算法($GA$):是一种基于自然选择和群体遗传机制的搜索算法,它模拟了自然选择和自然遗传过程中的繁殖,杂交和突变的现象.

能够生存下来的往往不是最强大的物种,也不是最聪明的物种,而是最能适应环境的物种。

​ - 查尔斯·达尔文

求解思想

  • 利用遗传算法求解问题时,随机产生一些个体(问题的解),
  • 根据预定的目标函数对每一个个体进行评估,给出一个适应度,选择一些个体用来产生下一代个体.选择操作体现了适者生存的原理,好的个体被用来产生下一代,坏的个体被淘汰.
  • 然后选择出来的个体经过杂交,突变再组合产生新的个体

遗传操作

  1. 选择
    • 选择是指从群体中选择优良的个体并淘汰劣质的个体,他建立在适应度评估的基础上.适应度越大的个体,被选中的概率越大,他的子孙在下一代中的数量越多.
    • 选择的方法有:轮赌盘方法,最佳个体保留法,期望值法,排序选择法,竞争法,线性标准化法.
  2. 交叉
    • 交叉是指把两个父代个体的部分结构加以替换组合而生成新的个体的操作,交叉的目的是为了产生下一代新的个体.通过交叉操作,遗传算法的搜索能力得到飞跃的提升.
    • 交叉是遗传算法获取优良个体的重要手段,交叉操作是按照一定的交叉概率在匹配库中随机的选取两个个体进行的,交叉的位置也是随机的,交叉概率一般取得很大 $0.6~0.9$.
  3. 变异
    • 变异是以很小的概率 $p$ 随机改变种群中个体的某些基因的值
    • 变异操作的过程是:
      • 产生一个$[0,1]$之间的随机数 $rand$.
      • 如果 $rand < p$ ,则进变异操作.
    • 变异操作本身是一种局部随机搜索,与选择和交叉结合一起使用,能够避免由于选择和交叉导致某些局部信息永久丢失,保证了遗传算法的有效性.保证了群体多样性.
    • 变异概率不宜取过大,如果 $p > 0.5$ ,那么遗传算法退化为随机搜索.

应用

遗传算法是一种迭代的选择算法,从初始解,以及后续繁殖出来的子解中选择最优的解.通常的做法是,将问题的解转化为二进制表示,然后进行遗传算法选择最优解.

  1. 特征选择:每个特征用二进制中的位表示,$0$ 不选择该特征,$1$ 选择该特征.则有多组特征选择,用遗传算法进行选择最优解.
  2. 背包问题
  3. 路线规划

python 相关库

  • tpot:树形传递优化技术

参考

  1. 遗传算法的基本原理
  2. 一文读懂遗传算法工作原理(附Python实现)
  3. 超详细的遗传算法(Genetic Algorithm)解析
  4. 遗传算法有哪些比较直观的应用呢? (列举一些有用的应用和蛋疼的应用,比如用于搜索神经网络参数以及k-mean的k值都是比较蛋疼的...)
  5. Genetic Drawing
  6. 攻击神经网络
  7. 遗传算法有哪些有趣应用?
  8. 如何通俗易懂地解释遗传算法?有什么例子?