[数据结构与算法]启发式算法

• 想了好久，还是准备要写下这篇文章，好好总结之前项目中遇到的一些相关算法，然后学习其他相关算法，希望扩充自己的知识面。慢慢写，希望善始善终
• 21.8.8 目前的目标是对每个算法的基本思路和步骤了解清楚，并且逐步开始从具体问题对算法进行练习，在这些工作全部完成之后，可以开始了解和应用算法中的其他变体。
• python实例源码：

写在前面

• 最优化算法、启发式算法。本篇主角启发式算法区别于精确算法，启发式算法指：一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间） 下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度一般不能被预计
• 但是传统启发式算法存在一些问题：一是传统启发式算法依赖于算法的组织结构信息，通用性不高，二是容易困在局部最优解中···
• 随着启发式算法的发展，出现了区别于传统启发式算法的元启发式算法（题外话：如何理解meta元？），元启发式算法简单来说，在传统启发式算法的思想上增加了随机搜索的思想，并且不过分依赖于算法的组织结构信息
• 启发式算法中的传统启发式算法和元启发式算法都不能保证获得全局最优解，但是元启发式算法由于增加了随机搜索的思想，反复执行可能收敛到全局最优解，并且元启发式算法不过分依赖算法组织结构信息，拥有更加通用启发式策略
• 分类如下：
  

传统启发式算法

贪心算法

• 思路：贪心算法是指一种在求解问题时总是采取当前状态下最优的选择从而得到最优解的算法，但是缺乏对整体最优的考虑。贪心算法的思路是：建立数学模型来描述问题，把求解的问题分成若干个子问题，对每个子问题求解，得到子问题的局部最优解，把子问题的解局部最优解合成原来问题的一个解
• Dijkstra算法

局部搜索

爬山算法

元启发式算法

禁忌搜索

模拟退火算法

• 思想：模拟退火算法思路来自于物理退火过程，在系统温度越高，退火现象指物体逐渐降温的物理现象，最终达到结晶状态，系统的能量状态最低。
• 细节：系统从高温降温过程中，随机选取可行解邻域内值，计算目标函数的增量值，如果系统能量下降，则接受该可行解，否则依照概率接受该解。在达到结束条件时结束循环
• 步骤：
  1. 初始化温度和终止温度，最大迭代次数，可行解
  2. 随机选取可行解的邻域值，计算系统能量增量，如果增量小于0则无条件接受该值；否则按照概率接受该值
  3. 降低温度
  4. 如果达到终止温度/最大迭代次数，则停止算法；否则跳回2
• 从状态$1$到状态$2$，Metropolis接受准则：

$$p(1\to 2)=\{\begin{array}{ll}1& E(x_{new})<E(x_{old})\\ exp(?\frac{E(x_{new})?E(x_{old})}{T})& E(x_{new}>=E(x_{old})\end{array}$$

• 目标函数

遗传算法

• 思想：遗传算法的思路来自于遗传与进化理论，主要包含三个阶段：自然选择，基因重组，变异。
• 细节：每一条染色体对应一种解决方案，首先要寻找一种从表现型到基因型的数字化编码方式，即我们需要的表现到数字化的表示过程，然后再随机初始化种群/染色体群，为了选择出适应度强的个体，我们需要构造适应度函数。随后的过程就是：选择、交叉、变异，并且为了保证种群个数不变，在选择时按照适应度高低决定被保留的概率；交叉类似于基因重组，有单点交叉、多点交叉、均匀交叉，交叉点间之间的部分依照交叉概率进行交换，最终形成新的个体；变异即是染色体任意位置编码值以一定概率反转。
• 选择：优胜劣汰，适者生存
• 交叉：丰富种群，持续优化
• 变异：随机扰动，避免局部最优
• 步骤：
  1. 随机初始化种群
  2. 评估每条染色体的适应度
  3. 遵循适应度越高，被抽取概率越大的原则，从种群中选取个体作为父母本
  4. 父母本染色体进行交叉，产生子代
  5. 对自带染色体进行变异
  6. 在未达到循环终止条件时，跳回2
• 适应度函数用于评价某个个体的适应度，表现出群体中不同个体的好坏，一般总是非负的，由目标函数变换而来
• 选择函数用于抽取亲代中的个体，常用的选择算子有：轮盘赌选择，随即竞争选择，最佳保留选择······

蚁群算法

粒子群优化算法

• 思想：粒子群优化算法的思路来自于鸟类觅食，粒子群优化算法思路是：每个粒子根据个人信息和团队信息改变搜索方向，以寻找最优解
• 细节：每个粒子都有一个由目标函数决定的适应值，并且知道自己到目前为止发现的最好位置和现在的位置。这个可以看作是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置，这个可以看作是群体信息。
• 步骤：
  1. 初始化一群微粒(群体规模为N)，包括随机位置和速度；
  2. 并评价每个微粒的适应度；
  3. 对每个微粒，将其适应值与其经过的自己最好位置pbest作比较，如果较好，则将其作为当前的自己最好位置pbest；
  4. 对每个微粒，将其适应值与其经过的全局最好位置gbest作比较，如果较好，则将其作为当前的全局最好位置gbest；
  5. 调整微粒速度和位置；
  6. 未达到结束条件则转第2步。
• 第$k$次迭代，微粒位置和速度调整公式（此处公式为向量化后的公式）：
  $$\begin{gathered} V^k=w{V}^{k?1}+c_1{r}_1(pbest?X^{k?1})+c_2{r}_2(gbest?X_{k?1}) \\ {X}^k=X^{k?1}+V^k \\ {c}_1,c_2为加速度常数 \\ {r}_1,r_2为0到1的随机数 \\ w为惯性权重 \end{gathered}$$
• 优势：在于简单容易实现并且没有许多参数的调节。目前已被广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域
• 适应度函数和目标函数

超级启发式算法

参考

1. 个人博客
2. PSOcsdn博客
3. PSOcsdn博客
4. PSOgithub
5. SAcsdn博客
6. GAcsdn博客
7. GA简书