智能优化算法(模拟退火、遗传、差分进化算法)笔记
1.现代优化算法概论（Modern Optimization Algorithms, MOA）
现代优化算法又称智能优化算法或启发式算法，是一种具有全局优化性能强、通用性强、且适用于并行处理的算法。
基本思路：都是从任意解出发，按照某种机制，以一定的概率在整个求解空间中探寻最优解。由于他们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。
特点：
- 基于客观世界中的一些自然现象；
- 建立在计算机迭代计算的基础上；
- 具有普适性，可解决实际应用问题。
- 不依赖于初始条件
- 收敛速度慢，能获得全局最优，适用于求解空间未知的情况
- SA、GA可应用于大规模、多峰多态函数、含离散变量等全局优化问题；求解速度和质量远超过常规方法。
2.模拟退火算法 (Simulated Annealing Algorithm, SA)
算法目的：
- 解决NP复杂性问题
- 克服优化过程中陷入局部最小
- 克服初始值依赖性
数学表达：若在温度T，当前状态i → 新状态j，若Ej
文章图片
算法描述：
随机产生一个初始解 x0 ,令xbest = x0 ,并计算目标函数值E( x0 );
设置初始温度T = T0,迭代次数 i = 1 ;
do while T > Tmin
for j = 1 ~ k
对当前最优解 xbest 按照某一邻域函数，产生一新的解 xnew 计算新的目标函数值E(xnew )，并计算目标函数值的增量 ?E= E(xnew )- E(xbest );
if ?E <0
xbest = xnew ;
if ?E >0
p = exp (- ?E / T(i));
if c = random[0,1]原则：产生的候选解因遍布全部解空间（保证全局最优）
方法：在当前状态的邻域结构内以一定概率方式（均匀分布，指数分布，正态分布等）产生
优点：质量高、初始鲁棒性强、简单通用易实现
缺点：由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。
改进：略
3.遗传算法 (Genetic Algorithm, GA)
遗传算法是一种基于自然群体遗传进化机制的自适应全局优化概率搜索算法。
基本思想(传统简单遗传算法)：遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按照某种指标从解群中选取较优的个体，利用遗传算子（选择、交叉和变异）对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛标准为止。
进化规则：“适者生存”：较好的解被保留，较差的解被淘汰
个体：模拟生物个体是对问题中对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。
种群：模拟生物种群是由若干个个体组成的群体，它一般是整个搜索空间的一个很小的子集。
适应度：借鉴生物个体对环境的适应程度，对问题中的个体对象所设计的表征其优劣的一种测度。
适应度函数：全体个体与其适应度之间的一个对应关系。它一般是一个实值函数，该函数就是遗传算法中指导搜索的评价函数。
染色体：问题中个体的某种字符串形式的编码表示。
基因：字符串中的字符
如何设计遗传算法：
- 如何进行编码
- 如何产生初始种群
- 如何定义适应度函数
- 如何进行遗传操作（选择、交叉和变异）
- 如何产生下一代种群
- 如何定义停止规则
轮盘赌：
-
- 将种群中所有染色体编号，并根据各自的适应值计算按比例分配的概率
- 依次计算染色体累加概率
- 产生（0，1）间的随机数，若其最多能大于序列中第m个值，则第m个染色体被选择
- 在［0, 1］区间内产生一个均匀分布的随机数r。
- 若r≤q1,则染色体x1被选中。
- 若qk-1
文章图片
交叉：每次作用在从交配池中随机选取的两个个体上（交叉概率Pc）
GA利用选择和交叉操作可以产生具有更高平均适应值和更好染色体的群体
变异：以变异概率pm改变染色体id某个基因，当以二进制编码时，变异的基因由0变成1，或者由1变成0。变异概率pm一般介于1/种群规模与1/染色体长度之间，平均约1%-2%
【智能优化算法(模拟退火、遗传、差分进化算法)笔记】比起选择和交叉操作，变异操作是GA中的次要操作，但是它在恢复群体失去的多样性方面具有潜在的作用。
停止准则：
- 种群中的个体的最大适应值超过预设定值
- 种群中个体的平均适应值超过预设定值
- 种群中个体的进化代数超过预设定值
- 随机产生初始种群
- 计算种群体中每个个体的适应度值，判断是否满足停止条件，若不满足，则转第(c)步，否则，转第（f）步；
- 按由个体适应值所决定的某个规则选择进入下一代的个体；
- 按交叉概率pc进行交叉操作，产生新个体
- 按变异概率pm进行变异操作，产生新个体；
- 输出种群中适应值最优的染色体作为问题的最优解或满意解
基于群体差异的启发式随机搜索算法
特点：原理简单，受控参数少，鲁棒性强
与遗传算法十分相似
流程：变异、交叉和选择
选择策略：竞标赛选择
交叉操作方式与遗传算法大体相同
变异操作方面使用差分策略：
利用群体中个体的差分量对个体进行扰动，实现个体变异
差分策略的变异方式，有效利用群体分布特征，提高算法的搜索能力，避免遗传算法中变异方式的不足
算法流程：
- 初始化种群
- 变异操作：
文章图片
- 交叉操作
文章图片
- 为了确保变异中间体{vi(g+1)}的每个“染色体”至少有一个“基因”遗传给下一代，第一个交叉操作的基因是随机取出vi(g+1)中的第jrand位“基因”作为交叉后“染色体”ui(g+1)第jrand位等位“基因”。后续的交叉过程，则是通过交叉概率CR来选取xi(g)还是vi(g+1)的等位基因作为ui(g+1)的等位基因。
- 选择操作：
文章图片
缺点：随着代数的增加，个体间的差异会逐渐降低。个体差异性的减小又影响变异所带来的多样性，从而导致算法过早收敛到局部极值附近时，形成早收敛现象。
改进：略
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 人工智能|干货！人体姿态估计与运动预测
- 数据库设计与优化
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列