Envolutionary Algorithm

进化算法

进化算法：

• 后设启发式算法：适合多种最优化问题，但不保证找到全局最优

Genetic Algorithm

遗传算法：模拟自然界生物进化过程，采用人工进化的方式对目标 空间进行搜索

• 本质是高效、并行、全局搜索方法
• 能在搜索过程中自动获取、积累有关搜索空间的知识，并自适应 的控制搜索过程以求的最佳解

思想

• 将问题域中可能解看作是染色体，将其编码为符号串的形式
• 对染色体群体反复进行基于遗传学的操作：选择、交叉、变异
• 根据预定目标适应度函数对每个个体进行评价，不断得到更优 群体，从中全局并行搜索得到优化群体中最优个体

实体

• population：群体，GA的遗传搜索空间
• individual：个体，搜索空间中可能解
• chromosome：染色体，个体特征代表
  • 由若干段基因组成
  • GA中基本操作对象
• gene：基因
  • 染色体片段
• fitness：适应度，个体对环境的适应程度

基本操作

• selection：选择，根据个体适应度在群体中按照一定概率 选择个体作为父本

  • 适应度大个体被选择概率高
  • 体现了适者生存、优胜劣汰的进化规则

• crossover：交叉，将父本个体按照一定概率随机交换基因 形成新个体

• mutate：变异，按照一定概率随机改变某个体基因值

串编码方式

• 把问题的各种参数用二进串进行编码构成子串
• 把子串拼接成染色体

  • 串长度、编码方式对算法收敛影响极大

二进制编码方式

二进制法：使用二进制染色体表示所有特征

• 优点

  • 编码、解码操作简单
  • 交叉、变异等遗传操作便于实现
  • 符合最小字符集编码原则
  • 利于模式定理对算法理论分析

• 缺点

  • 连续函数离散化存在误差，染色体长度短时达不到精度 要求，较长时解码难度大、搜索空间增大
  • 对连续函数优化问题，随机性使得其局部搜索能力较差， 接近最优值时不稳定

浮点编码

浮点法：个体的每个基因值用某一范围内的一个浮点数表示

• 必须保证基因之在给定区间限制范围内

  • 交叉、变异等遗传算子结果也必须在限制范围内

• 优点

  • 适用于在遗传算法中表示范围较大的数
  • 精度较高
  • 便于较大空间的遗传搜索
  • 改善了遗传算法的计算复杂性，提高了运算效率
  • 便于遗传算法与经典优化方法的混合使用
  • 便于设计针对问题的专门知识的知识型遗传算子
  • 便于处理复杂的决策变量约束条件

符号编码法

符号法：个体染色体编码串基因值取自无意义字符集

• 优点
  • 符合有意义积木块编码原则
  • 方便利用所求解问题的专门知识
  • 访问GA和相关近似算法的混合使用

Fitness Function

适应度/对象函数

• 一般可以把问题模型函数作为对象函数

• 过程

  • 解码个体，得到个体表现型
  • 由个体表现型计算个体目标函数值
  • 根据最优化问题类型，由目标函数值按一定转换规则求出 个体适应度

操作

选择函数

• Roulette Wheel Selection：轮盘赌选择，个体进入下一代 概率为其适应度与整个种群适应度之比

  • 放回式随机抽样
  • 选择误差较大

• Stochastic Tournament：随机竞争选择，每次按轮盘赌选择 一对个体，选择适应度较高者，重复直到选满

• 最佳保留选择：按轮盘赌选择方法执行遗传算法选择操作，然后 t将当前群体中适应度最高的个体结构完整地复制到下一代群体中

• Excepted Value Selection：无回放随机选择，根据每个个体 在下一代群体中的生存期望来进行随机选择运算

  • 计算群体中每个个体在下一代群体中的生存期望数目N
  • 若体被选中参与交叉运算，则它在下一代中的生存期望数目 减去0.5，否则在下一代中的生存期望数目减去1.0
  • 随着选择过程的进行，当个体的生存期望数目小于0时，则 该个体就不再有机会被选中。

• 确定式选择：按照一种确定的方式来进行选择操作

  • 计算群体中各个体在下一代群体中的期望生存数目N
  • 用N的整数部分确定个体在下一代群体中的生存数目
  • 用N的小数部分对个体进行降序排列，顺序取前M个个体加入 到下一代群体
  • 完全确定出下一代群体中Ｍ个个体

• 无回放余数随机选择

  • 可确保适应度比平均适应度大的一些个体能够被遗传到 下一代群体中
  • 选择误差比较小

• 均匀排序：对群体中的所有个体按期适应度大小进行排序，基于 这个排序来分配各个个体被选中的概率

• 最佳保存策略：当前群体中适应度最高的个体不参与交叉运算 和变异运算，而是用它来代替掉本代群体中经过交叉、变异等 操作后所产生的适应度最低的个体

• 随机联赛选择：每次选取几个个体中适应度最高个体遗传到 下一代群体中。

• 排挤选择：新生成的子代将代替或排挤相似的旧父代个体，提高 群体的多样性

Cross Over

• One-point Crossover：单点交叉，在个体编码串中只随机 设置一个交叉点，然后再该点相互交换两个配对个体的部分 染色体

• Two-point Crossover：两点交叉，在个体编码串中随机设置 两个交叉点，然后再进行部分基因交换

• Multi-point Crossover：多点交叉

• Uniform Crossover：均匀交叉/一致交叉，两个配对个体的 每个基因座上的基因都以相同的交叉概率进行交换，从而形成 两个新个体

• Arithmetic Crossover：算术交叉，由两个个体的线性组合 而产生出两个新的个体

  • 操作对象一般是由浮点数编码表示的个体

Mutation

• Simple Mutation：基本位变异，对个体编码串中以变异概率 、随机指定的某一位或某几位仅因座上的值做变异运算

• Uniform Mutation：均匀变异，用符合某一范围内均匀分布 的随机数，以较小的概率来替换个体编码串中各个基因座上原有 基因值

  • 适用于在算法的初级运行阶段

• Boundary Mutation：边界变异，随机的取基因座上的两个 对应边界基因值之一去替代原有基因值

  • 适用于最优点位于或接近于可行解的边界时的一类问题

• 非均匀变异：对原有的基因值做一随机扰动，以扰动后的结果 作为变异后的新基因值

  • 对每个基因值都以相同的概率进行变异运算之后，相当于 整个解向量在解空间中作了一次轻微的变动

• 高斯近似变异：进行变异操作时用符号均值为P、方差$P^2$的 正态分布的一个随机数来替换原有的基因值

GA超参设置

• 群体大小$n$：过小难以求出最优解，过大难收敛，一般取 $n = 30 ~ 160$

• 交叉概率$P_c$：太小难以前向搜索，太大容易破坏高适应 值结构，一般取$P_c = 0.25 ~ 0.75$

• 变异概率$P_m$：太小难以产生新结构，太大则变为单纯 随机搜索，一般取$P_m = 0.01 ~ 0.2$

算法

1. 随机初始化种群
2. 估初始种群：为种群每个个体计算适应值、排序
3. 若没有达到预定演化数，则继续，否则结束算法
4. 选择父体
   • 杂交：得到新个体
   • 变异：对新个体变异
5. 计算新个体适应值，把适应值排名插入种群，淘汰最后个体
6. 重复3

Differential Evolution

差分进化算法：

Particle Swarm Optimization

粒子群/微粒群算法：