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

高级算法设计与分析启发式算法林海lin.hai@B站：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：相关概念邻域所谓邻域，简单的说即是给定点附近其他点的集合。邻域就是指对当前解进行一个操作(这个操作可以称之为邻域动作)可以得到的所有解的集合。邻域动作邻域动作是一个函数，通过这个函数，对当前解s，产生其相应的邻居解集合。例如：对于一个bool型问题，其当前解为：s=1001，当将邻域动作定义为翻转其中一个bit时，得到的邻居解的集合N(s)={0001,1101,1011,1000}，其中N(s)∈S。Tabusearch：相关概念禁忌表禁忌对象：由于需要避免一些操作的重复进行，就要将一些元素放到禁忌表中以禁止对这些元素进行操作，这些元素就是我们指的禁忌对象（通常指找到的局部最优解）。禁忌长度：禁忌长度是被禁对象不允许选取的迭代次数。一般是给被禁对象x一个数（禁忌长度）t，要求对象x在t步迭代内被禁，在禁忌表中采用tabu(x)=t记忆，每迭代一步，该项指标做运算tabu(x)=t−1，直到tabu(x)=0时解禁。侯选集合侯选集合由邻域中的邻居组成。常规的方法是从邻域中选择若干个目标值或评价值最佳的邻居入选。Tabusearch：相关概念评价函数（目标函数）评价函数是侯选集合元素选取的一个评价公式，侯选集合的元素通过评价函数值来选取。特赦规则在禁忌搜索算法的迭代过程中，会出现侯选集中的全部对象都被禁忌，或有一对象被禁，但若解禁则其目标值将有非常大的下降情况。在这样的情况下，为了达到全局最优，我们会让一些禁忌对象重新可选。这种方法称为特赦，相应的规则称为特赦规则。Tabusearch：算法Step1：禁忌表H=空集，并选定一个初始解x1；step2：在xi的邻域N(xi)中选择候选集Can_N(xi)；在Can_N(xi)中选一个评价值最佳的解xi+1，xi+1不在禁忌表中，选为当前解xi+1在禁忌表中，满足破禁条件，xi+1为当前解，否则从不在禁忌表解中，选择一个最优解step3：重复step2，直到满足停止条件Tabusearch：例子求下图的旅行商回路Tabusearch：例子随机选择一个城市序列：21543，路径长度889交换城市长度1⟷58041⟷58043⟷4907禁忌表15⟷123Tabusearch：例子最优访问顺序：25143，最优长度804当前访问顺序：25143，长度804交换城市长度5⟷410981⟷49285⟷1889禁忌表14⟷125⟷13Tabusearch：例子最优访问顺序：25143，最优长度804当前访问顺序：25413，长度928交换城市长度5⟷110855⟷410625⟷3786禁忌表15⟷324⟷135⟷1Tabusearch：例子最优访问顺序：23415，最优长度786当前访问顺序：23415，长度786交换城市长度4⟷19463⟷47682⟷31098禁忌表13⟷425⟷334⟷1Tabusearch：例子最优访问顺序：24315，最优长度768当前访问顺序：24315，长度768交换城市长度4⟷59644⟷17371⟷5907禁忌表14⟷123⟷435⟷3破禁Tabusearch：例子迭代5次最优访问顺序：21345，最优长度737内容概述模拟退火Tabusearch遗传算法蚁群算法遗传算法：引例遗传算法：引例在一代代演化的过程中，父母扇贝的基因组合产生新扇贝，所以遗传算法会选择两个原有的扇贝，然后对这两个扇贝的染色体进行随机交叉形成新的扇贝迭代演化也会造成基因突变，遗传算法让新产生扇贝的基因以较小的概率发生变异。也就是说，染色体的像素值随机改变对扇贝像素值和Firefox图标进行逐一比较，颜色相差得越大的显然表示越不像。这个评价的函数叫做“适应度函数”，它负责评价扇贝和Firefox的相似程度遗传算法：交叉遗传算法：变异遗传算法：引例遗传算法遗传算法遗传算法遗传算法遗传算法遗传算法遗传算法遗传算法遗传算法遗传算法：流程遗传算法：流程遗传算法：应用遗传算法：应用遗传算法：应用遗传算法：旅行商问题遗传算法：旅行商问题可能出现非法解遗传算法：旅行商问题遗传算法：旅行商问题遗传算法：旅行商问题内容概述模拟退火Tabusearch遗传算法蚁群算法蚁群算法蚂蚁几乎是没有视力的，它们是如何找到食物和家之间的路径的?在觅食过程中,蚂蚁在它所经过的路径上留下浓度与食物源质量成比例的信息素(pheromone),并能够感知信息素的存在及其浓度,以此指导自己的运动方向,倾向于朝着信息素浓度高的方向移动于是,蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大,因此质量好、距离近的食物源会吸引越来越多的蚂蚁,信息素浓度的增长速度会更快.蚂蚁个体之间就是通过这种信息的交流达到寻找食物和蚁穴之间最短路径的目的蚁群算法：例子蚁群算法路径选择概率蚁群算法：基本蚁群算法城市i和城市j间路径的信息素更新为：

蚁群算法：基本蚁群算法蚁群算法：蚁群系统对基本蚁群算法的改进在路径选择中采用了利用(exploitation)和探索(exploration)相结合的方法蚁群算法：蚁群系统对基本蚁群算法的改进信息素的更新采用了全局更新和局部更新相结合的方案局部更新是所有蚂蚁完成一次移动后执行蚁群算法：蚁群系统对基本蚁群算法的改进信息素的更新采用了全局更新和局部更新相结合的方案全局更新是在所有的蚂蚁完成了旅行商回路后执行，全局更新仅仅对目前的最优回路上的路径(边