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$
算法
- 随机初始化种群
- 估初始种群：为种群每个个体计算适应值、排序
- 若没有达到预定演化数，则继续，否则结束算法
- 选择父体
- 杂交：得到新个体
- 变异：对新个体变异
- 计算新个体适应值，把适应值排名插入种群，淘汰最后个体
- 重复3
Differential Evolution
差分进化算法：
Particle Swarm Optimization
粒子群/微粒群算法：