简介

现代优化算法是 80 年代初兴起的启发式算法。这些算法包括禁忌搜索（tabu
search），模拟退火（simulated annealing），遗传算法（genetic algorithms），人工神经网 络（neural networks）。它们主要用于解决大量的实际应用问题。目前，这些算法在理论 和实际应用方面得到了较大的发展。无论这些算法是怎样产生的，它们有一个共同的目 标－求 NP-hard 组合优化问题的全局最优解。虽然有这些目标，但 NP-hard 理论限制它 们只能以启发式的算法去求解实际问题

模拟退火

算法解析

统计力学表明材料中粒子的不 同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和 重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（这个过 程被称为退火），粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形 成处于低能状态的晶体。

物理学中模拟退火的思 想应用于优化问题就可以得到模拟退火寻优方法

算法步骤

1. 确定退火过程的温度初值 ,随机生成该温度下的粒子状态及一个解 ，计算目标函数值f即该状态下的内能 。
2. 进入下一个冷却温度。
3. 对当前的解 添加扰动，及产生个新的解 ，计算相应的内能 ，根据Metropolis准则判断是否接受新的解，更新局部最优解和全局最优解。
4. 在不同的冷却温度 下，重复m次对x的扰动，即产生m个新的解，并执行2~3.
5. 判断T是否已经到达了最低温度限制 ，一般设定为 ，是则终止算法；否继续执行2~4.

算法实际上由两层循环所控制，外层循环控制降温过程的温度；内层循环控制对解x的扰动。算法的初始温度 较高，这样使得内能增大的初始解也可能被接受，因为能够跳出局部最小值的陷阱，然后通过慢慢的降低温度，对解不断地添加扰动，使得算法最终可能收敛到全局最优解。

遗传算法GA

简介

遗传算法的实质是通过群体搜索技术，根据适者生存的原则逐代进化，最终得到最优解或准最优解。它必须做以下操作：初始群体的产生、求每一个体的适应度、 根据适者生存的原则选择优良个体、被选出的优良个体两两配对，通过随机交叉其染色 体的基因并随机变异某些染色体的基因后生成下一代群体，按此方法使群体逐代进化，直到满足终止条件。

实现方法

算法步骤

1.编码

2.初始种群

3.目标函数

4.交叉操作

在每完成一次进化后，都要计算每一条染色体的适应度，然后采用如下公式计算每一条染色体的适应度概率。那么在进行交叉过程时，就需要根据这个概率来选择父母染色体。适应度比较大的染色体被选中的概率就越高。这也就是为什么遗传算法能保留优良基因的原因。

染色体i被选择的概率 = 染色体i的适应度 / 所有染色体的适应度之和

单点交叉，如下图在4的位置交叉生成子代。交叉方式有多种。

注：每次进化中，为了保留上一代优良的染色体，需要将上一代中适应度最高的几条染色体直接原封不动地复制给下一代。

假设每次进化都需生成N条染色体，那么每次进化中，通过交叉方式需要生成N-M条染色体，剩余的M条染色体通过复制上一代适应度最高的M条染色体而来。

5.变异

随机修改基因的值，从而给现有的染色体引入了新的基因，突破了当前搜索的限制，更有利于算法寻找到全局最优解。

6.选择

采用确定性的选择策略，也就是说选择目标函数值最小的M个个体进化到下一代，这 样可以保证父代的优良特性被保存下来

禁忌搜索算法

简介

禁忌搜索算法的特点是采用了禁忌技术。所 谓禁忌就是禁止重复前面的工作。

禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点。

相关概念

禁忌搜索算法实现的技术问题是算法的关键。禁忌搜索算法涉及侯选集合、禁忌 对象、评价函数、特赦规则、记忆频率信息等概念。

邻域

在一点附近搜索另一个下降的点是组合优化数值求解的基本思想。

候选集合

侯选集合由邻域中的邻居组成。常规的方法是从邻域中选择若干个目标值或评价 值最佳的邻居入选。

禁忌对象和禁忌长度

禁忌表中的两个主要指标是禁忌对象和禁忌长度。将一些元素放到禁忌表中以禁止对这些元素进行操作。禁忌长度是被禁对象不允许选取的迭代次数，设置为t，每次减一，到0可继续迭代。

评价函数

评价函数是侯选集合元素选取的一个评价公式，侯选集合的元素通过评价函数值 来选取。以目标函数作为评价函数是比较容易理解的。目标值是一个非常直观的指标， 但有时为了方便或易于计算，会采用其他函数来取代目标函数。

特赦规则

在禁忌搜索算法的迭代过程中，会出现侯选集中的全部对象都被禁忌，或有一对象被禁，但若解禁则其目标值将有非常大的下降情况。在这样的情况下，为了达到全局 最优，我们会让一些禁忌对象重新可选。这种方法称为特赦，相应的规则称为特赦规则。

记忆频率信息

在计算的过程中，记忆一些信息对解决问题是有利的。如一个最好的目标值出现
的频率很高，这使我们有理由推测：现有参数的算法可能无法再得到更好的解。根据解 决问题的需要，我们可以记忆解集合、被禁对象组、目标值集合等的出现频率。

频率信息有助于进一步加强禁忌搜索的效率。我们可以根据频率信息动态控制禁
忌的长度。一个最佳的目标值出现的频率很高，有理由终止计算而将此值认为是最优值

蚁群算法

简介

基于蚂蚁这种行为而提出的蚁群算法具有群体合作，正反馈选择，并行 计算等三大特点，并且可以根据需要为人工蚁加入前瞻、回溯等自然蚁所没有的特点。 在使用蚁群算法求解现实问题时，先生成具有一定数量蚂蚁的蚁群，让每一只蚂 蚁建立一个解或解的一部分，每只人工蚁从问题的初始状态出发，根据“激素”浓度来 选择下一个要转移到的状态，直到建立起一个解，每只蚂蚁根据所找到的解的好坏程度 在所经过的状态上释放与解的质量成正比例的“激素”。之后，每只蚂蚁又开始新的求 解过程，直到寻找到满意解。为避免停滞现象，引入了激素更新机制。

算法

参考

模拟退火算法及matlab程序实现 - 知乎 (zhihu.com)

数学建模算法大全

10分钟搞懂遗传算法(含源码) - 知乎 (zhihu.com)