遗传算法概述

生物学概念

生物遗传进化简单来说就是 优胜劣汰
种群繁衍产生变异的后代、其中一些更能适应自然、于是便在自然的生存法则中存活了下来，并且产生带有自己优良性状的后代，群体数量不断增加，循环往复。

而在计算机中，因为用0、1表示，于是我们可以将不同的0、1片段看作不同的DNA序列，任意截取两段0、1序列的片段即可组成新的0、1序列，而变异即使序列中的0变成1，或是1变为0。

简单理解遗传算法

遗传算法(GA)是一种优化(optimize)算法，来自于生物学生物进化的概念。
从指向目标函数的初始种群的候选解开始，随后的种群通过选择（selection）、交叉（crossover）、变异（mutation从初代中进化。

怎么进化——二进制的例子

• 选择
  在父代到子代的遗传中保持最好的二进制序列
  有利于繁殖的父代(performing well)：
  –parent1 = [1 0 1 0 0 1 1 0 0 0]
  –parent2 = [1 0 0 1 0 0 1 0 1 0]

• 交叉
  –parent1 = [1 0 1 0 0 1 1 0 0 0]
  –parent2 = [1 0 0 1 0 0 1 0 1 0]
  –child = [1 0 0 0 0 1 1 0 1 0]

• 变异
  –parent = [1 0 1 0 0 1 1 0 0 0]
  –child = [0 1 0 1 0 1 0 0 0 1]

遗传算法原理

去源于达尔文的“物竞天择，适者生存”。
它是一种自适应全局优化概率搜索算法。存在很多的随机性，因此产生更多可能性。

优点

隐含并行性（个体之间可以同步进行而不相互影响）
全局解空间搜索

主要应用领域

1. 函数优化
   非线性、多模型、多目标函数
2. 组合优化
   规模较大时
3. 自动控制
   控制器参数优化
4. 机器人
   结构优化和行为调节
5. 图像处理
   各个方面

时间限制要求不高时GA十分有用

遗传算法的搜索机制

• 每次迭代保留一组候选解
• 按某种指标从解群中选取较优个体，利用遗传算子（选择、交叉、变异）对这些个体进行组合
• 产生新一代的候选解群

重复直至满足收敛标准

遗传算法的基本操作

• 选择（selection）
  根据一定的规则从t代群体P(t)中选择一些个体遗传到下一代P(t+1)

• 交叉（crossover）
  将P(t)内的各个个体随机配对，每个个体以交叉概率Pc交换他们之间的部分染色体

• 变异（mutation）
  对P(t)内每一个个体，以遗传概率Pm改变某一基因为它的等位基因

设计遗传算法

编码

基因型空间为01序列

选择

选择优良表现型个体

常见的选择方法有很多，这里主要介绍轮盘赌选择（Roulette wheel selection）

1. 种群中所有染色体适应值相加求和、并且适应值按比例转化为选择概率Ps
2. 产生一个随机数m∈(0,l) l为总和
3. 令S=Σf(xi)（i=1,2,3…n.并且f(xi)为第i个染色体的适应值）求和直到S≥m

即 轮盘上的片分配给染色体，使得每一个片的大小与染色体的适应值成比例，每从群体中选择一个染色体可视为旋转一次轮盘，停止时指针所指的片所对应的染色体就是所要选择的染色体

ps：选择后得到的新群体称作交配池（P(t)和P(t+1)之间的中间群体）

交叉

该步骤产生新的个体
遗传交叉（杂交、交配、有性重组）产生具有双亲部分基因的染色体，从而检测搜索空间中新的点

交叉有很多形式，这里主要讨论单点交叉和双点交叉

单点交叉：

1. 随机产生交叉点
2. 交叉点位置分离双亲染色体
3. 互换交叉点右端染色体，产生两个子代染色体
4. 交叉概率Pc常取60%-90%，平均80%
   
   图自百度

两点交叉：
随机选择起点和终点
交叉起点终点之间的片段

多点交叉：
点对点的交叉

变异

改变染色体的某个基因，变异概率Pm平均约为1%-2%
二进制即为1变0，0变1

ps：比起选择和交叉、变异是GA中的次要操作，但在恢复群体中失去的多样性方面具有潜在作用

适应函数

GA在搜索中仅以适应函数（fitness function）为依据，利用每个染色体的适应值来搜索
适应函数的常见形式：

• 直接将目标函数转化为适应函数
  –最大化问题：
  Fitness(f(x)) = f(x)
  –最小化问题：
  Fitness(f(x)) = -f(x)
• 界限构造法
  –目标函数最大化问题
  其中Cmin为f(x)的最小估计值
  $\ Fitness(f(x)) = f(x)-C_{min}, f(x)>C_{min}$ Fitness(f(x))=f(x)−Cmin​,f(x)>Cmin​
  其他情况均为0
  –目标函数最小化问题
  其中Cmax为f(x)的最大估计值
  $\ Fitness(f(x)) = f(x)-C_{max}, f(x)<C_{max}$ Fitness(f(x))=f(x)−Cmax​,f(x)<Cmax​其他情况均为0

停止准则

• 种群中个体的最大适应值超过预定值
• 种群中个体的平均适应值超过预定值
• 种群中个体的进化代数超过预定

总结

欢迎指正，侵删