《高级算法设计》课件 第6、7章 在线算法；启发式算法

高级算法设计与分析在线算法目录基本概念确定性在线算法在线最小生成树时间序列搜索随机在线算法租买问题在线二分图最大匹配概述离线算法在前面讨论的算法中，问题实例的所有数据在计算时，都是已知的，称为离线算法在线算法问题实例的数据是逐渐到来的，但是又需要对已经到来的数据进行计算，也就是说算法必须在输入数据不是很完全可知的情况下，完成相应的计算并输出结果如股票买卖、物流中的装车问题在线算法是近似算法概述人工智能算法试图从以往的数据中寻找出规律，并根据目前的分配状态，来智能的分配目前到达的任务在线算法数据完全未知假设存在一个对手(adversary)：这个对手对设计的算法了如指掌，所以能够针对算法给出最坏数据到达实例(称为最坏实例)，来使得算法的效率最低，所以设计在线算法时，通常需要分析在最坏实例下算法的性能。概述：流程股票买卖为例概述：定义竞争度ρ概述：定义在线算法的下界下界表达式给出了在最差实例下，任意在线算法ALG和OPT存在大于等于的关系，如果某算法ALG′的ρ=α，且c=0,b=0，说明在线算法ALG′的性能已经最优，因为所有在线算法在最坏实例下都是大于等于竞争度ρ的，当在线算法ALG′的竞争度是小于等于ρ，显然ALG′已经最优。确定性在线算法：在线最小生成树在线最小生成树图中的顶点不是一开始就已知，而是逐个到达，并要求一旦一个顶点到达就需要加入到树中，且让生成的树总代价尽量小。一个比较简单的在线算法是让到达的顶点通过离树内最近的顶点加入到树中。如，在第k个顶点到达时，选取前面k−1个顶点中和第k个顶点距离最近的顶点，通过此顶点将第k个顶点加入到树中。我们把这种算法称为最小生成树的贪心在线算法。确定性在线算法：在线最小生成树在线最小生成树确定性在线算法：在线最小生成树确定性在线算法：在线最小生成树确定性在线算法：在线最小生成树确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索目录基本概念确定性在线算法在线最小生成树时间序列搜索随机在线算法租买问题在线二分图最大匹配随机在线算法策略的做出是随机性，形成随机在线算法，随机在线算法的好处是，假设的对手无法猜测算法的策略。随机在线算法：租买问题随机在线算法：租买问题随机在线算法：租买问题随机在线算法：租买问题随机在线算法：租买问题随机在线算法：租买问题随机在线算法：租买问题回到上面租买问题的例子ρ=4/3

的竞争度，这个竞争度比任意的确定性算法都要好，但这个竞争度是实例{I1,I2,I3}下的最优竞争度吗随机在线算法：租买问题随机实例下确定性算法费用和竞争度的计算随机在线算法：租买问题随机在线算法：租买问题随机在线算法：租买问题随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配按秩进行贪心匹配的确定性算法随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配在小数二分图匹配中，一个到达的顶点(a∈A)可以和B中的顶点(可以有多个)部分匹配随机在线算法：在线二分图最大匹配一个非常简单的算法是:当一个顶点ai到达时，和所有可匹配的顶点进行均匀匹配水位算法(waterlevelalgorithm)是一个非常著名的确定性在线算法，当A中的一个顶点a到达时，算法依据顶点a所有邻顶点的匹配状态，将a的匹配分配到这些邻顶点中，使得分配后，所有的邻顶点的匹配总量相似随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配高级算法设计与分析启发式算法内容概述模拟退火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),并能够感知信息素的存在及其浓度,以此指导自己的运动方向,倾向于朝着信息素浓度高的方向移动于是,蚁群的