《高级算法设计》课件 第7章 启发式算法.pptx

高级算法设计与分析启发式算法林海lin.hai@whu.edu.cnB站：foretmer

内容概述模拟退火Tabusearch遗传算法蚁群算法

优化问题经典优化算法通过对解空间的枚举（离散），或者对目标函数的微分（连续）求最优解默认为存在唯一最优解但很多优化问题无法通过上述方法求得最优解问题不是凸的（凸优化）解空间太大大多数问题只能求出近似解近似算法、随机算法启发式算法

启发式算法启发式算法(heuristicalgorithm)指通过对过去经验的归纳推理以及实验分析来解决问题的方法，即借助于某种直观判断或试探的方法，以求得问题的次优解或以一定的概率求其最优解，所以可以认为启发式算法一种基于经验或者实验算法的统称元启发式算法(metaheuristic)元启发式算法都从自然界的一些现象取得灵感(e.g.模拟退火、遗传算法)，通过这些现象获取的求解过程(元启发式算法)来解决实际的一些问题

启发式算法元启发式算法看成构造启发式算法的一些基础方法，而启发式算法就是利用元启发式算法，结合被求解问题的特征，设计出来的面向特定问题的算法

启发式算法通常基于自然界中发现的一些规律或者准则能够被计算机计算和处理目标是得出最优解的近似解，但不能确定得到的解就是最优解但通常得到的解比局部最优解要好适用于不同的问题，并能同时考虑一些约束条件

启发式算法

启发式算法局部有哪些信誉好的足球投注网站方法经典的启发式算法（元启发式算法）模拟退火（Simulatedannealing）禁忌有哪些信誉好的足球投注网站（Tabusearch）遗传算法（Geneticalgorithms）蚁群算法（Antcolonies）

局部有哪些信誉好的足球投注网站：2-opt算法2-opt变换在旅行商问题中，去除某一回路l的两条边e1和e2，形成了两个子图，对这两个子图重新连接形成新的回路l′，l′是通过对l的2-opt交换形成的

局部有哪些信誉好的足球投注网站：2-opt算法

局部有哪些信誉好的足球投注网站：2-opt算法

局部有哪些信誉好的足球投注网站：3-opt算法

内容概述模拟退火Tabusearch遗传算法蚁群算法

模拟退火什么是退火——物理上的由来退火（annealing）现象指物体逐渐降温的物理现象，温度愈低，物体的能量状态会低；够低后，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。大自然在缓慢降温（亦即，退火）时，可“找到”最低能量状态：结晶。但是，如果过程过急过快，快速降温（亦称「淬炼」，quenching）时，会导致不是最低能态的非晶形。

模拟退火什么是退火——物理上的由来如下图所示，首先（左图）物体处于非晶体状态。我们将固体加温至充分高（中图），再让其徐徐冷却，也就退火（右图）。加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小（此时物体以晶体形态呈现）

模拟退火算法概述若目标函数f在第i+1步移动后比第i步更优，即f(Y(i+1))=f(Y(i))，则总是接受该移动；若f(Y(i+1))f(Y(i))(即移动后的解比当前解要差)，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定）。Metroplis准则

模拟退火Metroplis准则温度越高，算法接受新解的概率越高。这个根据一定概率选择是否接受差解的方法叫做Metropolos准则

模拟退火：算法

模拟退火：算法

模拟退火：旅行商问题旅行商问题输入：旅行图、初始温度、最小温度、降温系数输出：旅行回路算法随机选择城市顺序在第i步的基础上，随机交换两个（或多个）城市的顺序（移动一步）如果第i+1步的代价更小，则作为当前哈密顿回路，否则依据Metroplis准则定义的概率作为当前回路，重复执行此步骤n次按照降温系数降低温度，重复以上步骤直到迭代次数达到预设值或者温度下降到预设值

模拟退火：旅行商问题

内容概述模拟退火Tabusearch遗传算法蚁群算法

Tabusearch从一个初始可行解出发，选择一系列的特定有哪些信誉好的足球投注网站方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS有哪些信誉好的足球投注网站中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的有哪些信誉好的足球投注网站方向，这就是Tabu表的建立。标记已经解得的局部最优解或求解过程，并在进一步的迭代中避开这些局部最优解或求解过程。局部有哪些信誉好的足球投注网站的缺点在于，太过于对某一局部区域以及其邻域的有哪些信誉好的足球投注网站，导致一叶障目。为了找到全局最优解，禁忌有哪些信誉好的足球投注网站就是对于找到的一部分局部最优解，有意识地避开它，从而或得更多的有哪些信誉好的足球投注网站区域。

Tabusearch：相关概念邻域所谓邻域，简单的说即是给定点附近其他点的集合。邻域就是指对当前解进行一个操作(这个操