近似算法的特点与计算方法、分类及概率算法的计算过程与应用(共11页).doc

精选优质文档-倾情为你奉上近似算法和概率算法的特点与计算方法、分类及概率算法的计算过程与应用一 近似算法1近似算法的计算方法设D是一个最优化问题，A是一个算法，若把A用于D的任何一个实例 I，都能在|I|的多项式时间内得到I的可行解，则称算法A为问题D的一个近似算法，其中|I|表示实例I的规模或输入长度，进而，设实例I的最优值为OP（I），而算法A所得到实例I的可行解之值为A（I），则称算法A解实例I的性能比为RA（I）的性能比为RA（D），同时称D有RA近似解其中 A ( I) OP(I) ， 若D为最小化问题.R A ( I) = OP(I) ， 若D为最大化问题. A ( I)RA(D)=infr|RA(I)r，ID2近似算法的特点（1）解同一个问题的近似算法可能有多个（2）算法的时间复杂性：近似算法的时间复杂性必须是多项式阶的，这是设计近似算法的基本目标。（3）解的近似程度：近似最优解的近似程度也是设计近似算法的重要目标。近似程度可能与近似算法本身、问题规模，乃至不同的输入实例都有关。3近似算法的分类（1） 基于线性规划的近似算法（2） 基于动态规划的近似算法（3） 绝对近似类（4） 相对近似类（5） PTAS类和FPTAS类（6） 随机近似算法二 概率算法1概率算法的计算方法概率算法允许算法在执行的过程中随机选择下一个计算步骤。许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。2概率算法的特点（1） 不可再现性。概率算法的一个特点是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。（2） 分析困难。要求有概率论、统计学和数论的知识。3概率算法的分类（1）数值概率算法。数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解。而且近似解的精度随计算时间的增加不断提高。在许多情况下，要计算出问题的精确解是不可能或没有必要的，因此用数值概率算法可得到相当满意的解。（2）蒙特卡罗（Monte Carlo）算法。用于求问题的准确解。对于许多问题来说，近似解毫无意义。例如，一个判定问题其解为“是”或“否”，二者必居其一，不存在任何近似解答。又如，我们要求一个的因子时所给出的解答必须是准确的，一个整数的近似因子没有任何意义。用能求得问题的一个解，但这个解未必是正确的。求得正确解的概率依赖于算法所用的时间。算法所用的时间越多，得到正确解的概率就越高。的主要缺点就在于此。一般情况下，无法有效判断得到的解是否肯定正确。Monte Carlo 算法偶然会犯错，但它无论对何实例均能以高概率找到正确解。当算法出错时，没有警告信息。偏真偏假的概念只在Monte Carlo 算法里出现。Def1：设 p 是一个实数，且 1/2<p<1，若一个 MC 算法以不小于 p 的概率返回一个正确的解，则该 MC 算法称为 p-正确，算法的优势（advantage）是 p-1/2。Def2：若一个 MC 算法对同一实例决不给出两个不同的正确解，则该算法称是相容的（consistent）或一致的。基本思想：为了增加一个一致的、p-正确算法成功的概率，只需多次调用同一算法，然后选择出现次数最多的解。Def：(偏真算法)为简单起见，设 MC(x)是解某个判定问题，对任何 x，若当MC(x)返回 true 时解总是正确的，仅当它返回 false 时才有可能产生错误的解，则称此算法为偏真的(true-biased)。Def：(偏 y0 算法)更一般的情况不再限定是判定问题，一个 MC 是偏 y0 的(y0 是某个特定解)，如果存在问题实例的子集 X 使得：若被解实例x X，则算法 MC(x)返回的解总是正确的(无论返回 y0 还是非 y0)。（3）拉斯维加斯（Las Vegas）算法。不会得到不正确的解，一旦用拉斯维加斯算法找到一个解，那么这个解肯定是正确的。但是有时候用可能找不到解。与类似。得到正确解的概率随着它用的计算时间的增加而提高。对于所求解问题的任一实例，用同一反复对该实例求解足够多次，可使求解失效的概率任意小。算法的一般形式：LV(x, y, success) x 是输入的实例，y 是返回的参数，success 是布尔值， true 表示成功，false 表示失败 p(x) 对于实例 x，算法成功的概率 s(x) 算法成功时的期望时间 e(x) 算法失败时的期望时间Obstinate(x) repeat LV(x, y, success); until success; return y;设 t(x)是算法 obstinate 找到一个正确解的期望时间，则t(x) = 𝑝(𝑥)𝑠(𝑥) + (1 𝑝(𝑥)(𝑒(𝑥) + 𝑡(𝑥)t(x)是指第一次成功的期望时间，第一次失败，后面再成功就需要花费的时间。（4）舍伍德（Sherwood）算法。总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以在这个确定算法中引入随机性将它改造成一个，消除或减少问题的好坏实例间的这种差别。精髓不是避免算法的最坏情况行为，而是设法消除这种最坏行为与特定实例之间的关联性。Sherwood 算法预处理的数学模型 1. 确定性算法：f: X -> Y 2. 确定性算法的实例集合：X, size 为 n 时写作 Xn 3. Sherwood 算法用于均匀随机抽样的集合：A，size 为 n 时写作 An，|An|=|Xn| 4. 随机抽样的预处理及后处理时用到的一对函数，对应上面的 u: X × A -> Y v: A × Y -> Xu,v 满足三个性质：1(n N)(x, y Xn)(! r An)，使得 u(x, r) = y 这条对应，其中!表示有且仅有一个2(n N)(x Xn)(r An)，使得 f(x) = v(r, f(u(x, r)这条对应3函数 u,v 在最坏情况下能够有效计算Sherwood 算法的过程，确定算法f(x)可改造为 Sherwood 算法： RH(x) / 用 Sherwood 算法计算 f(x) n length*x+; / x 的 size 为 n r uniform(An); / 随机取一元素 y u(x, r); /将原实例 x 转化为随机实例 y s f(y); / 用确定算法求 y 的解 s return v(r, s); / 将 s 的解变换为 x 的解 4概率算法的应用（1）离散事件建模（2）种群概率模型的优化（3）智能计算机的应用（4）统计计算（5）密码学（6）数字信号（7）系统安全三模拟退火算法1模拟退火算法的思想在一定温度下，搜索从一个状态随机地变化到另一个状态；随着温度的不断下降直到最低温度，搜索过程以概率1停留在最优解。算法的目的是为了解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。2模拟退火算法的计算原理Step1 设定初始温度t = tmax, 任选初始解r = r0Step2 内循环 Step2.1 从r的邻域中随机选一个解rt, 计算r和rt对应目标函 数值, 如rt对应目标函数值较小，则令r = rt; 否则若 exp(-(E(rt)-E(r)/t)>random(0,1), 则令r=rt. Step2.2 不满足内循环停止条件时，重复Step2.1Step3 外循环 Step3.1 降温t = decrease(t) Step3.2 如不满足外循环停止条件，则转Step2；否则算法结束三 遗传算法遗传（Genetic ）是一类借鉴生物界的进化规律（，遗传机制）演化而来的化搜索方法。它是由的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用化的寻优方法，能自动获取和优化的搜索，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于优化、机器学习、信号处理、和人工生命等。它是现代有关中的。2遗传算法的运算过程遗传算法的过程如下：a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。b)个体评价：计算群体P(t)中各个个体的。c):将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的评估基础上的。d)交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。e)：将变异算子作用于群体。即是对群体中的个体串的某些上的基因值作变动。群体P(t)经过选择、交叉、之后得到下一代群体P(t 1)。f)终止条件判断:若t=T,则以进化过程中所得到的具有最大个体作为输出，终止计算。3遗传算法的应用随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和、以及等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（Evolution Programming,EP）以及（Evolution Strategy,ES）等进化日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。四 人工神经网络1人工神经网络的思想人工神经网络是由大量处理单元互联组成的非线性、自适应信息处理系统。它是在现代研究成果的基础上提出的，试图通过模拟大脑神经网络处理、记忆信息的方式进行信息处理。人工神经网络具有四个基本特征：（1）非线性 关系是自然界的普遍特性。大脑的智慧就是一种非线性现象。人工神经元处于激活或抑制二种不同的状态，这种行为在数学上表现为一种非线性关系。具有阈值的神经元构成的网络具有更好的性能，可以提高容错性和存储容量。（2）非局限性 一个通常由多个神经元广泛连接而成。一个系统的整体行为不仅取决于单个神经元的特征，而且可能主要由单元之间的相互作用、相互连接所决定。通过单元之间的大量连接模拟大脑的非局限性。联想是非局限性的典型例子。（3）非常定性 人工神经网络具有自适应、自学习能力。神经网络不但处理的信息可以有各种变化，而且在处理信息的同时，非线性动力系统本身也在不断变化。经常采用迭代过程描写动力系统的演化过程。（4）非凸性 一个系统的演化方向，在一定条件下将取决于某个特定的状态函数。例如函数，它的极值相应于系统比较稳定的状态。非凸性是指这种函数有多个极值，故系统具有多个较稳定的，这将导致系统演化的多样性。人工神经网络中，神经元处理单元可表示不同的对象，例如特征、字母、概念，或者一些有意义的抽象模式。网络中处理单元的类型分为三类：输入单元、输出单元和隐单元。输入单元接受外部的信号与数据；输出单元实现系统处理结果的输出；隐单元是处在输入和输出单元之间，不能有系统外部观察的单元。神经元间的连接权值反映了单元间的连接强度，信息的表示和处理体现在网络处理单元的连接关系中。人工神经网络是一种非程序化、大脑风格的信息处理 ，其本质是通过网络的变换和动力学行为得到一种并行分布式的信息处理功能，并在不同程度和层次上模仿人脑神经系统的信息处理功能。它是涉及、计算机科学等多个领域的交叉学科。人工神经网络是并行，采用了与传统人工智能和信息处理技术完全不同的机理，克服了传统的基于逻辑符号的人工智能在处理直觉、方面的缺陷，具有自适应、自组织和实时学习的特点。2人工神经网络的分析方法研究神经网络的性质，主要采用系统理论、非线性规划理论和统计理论，来分析神经网络的演化过程和吸引子的性质，探索神经网络的协同行为和集体计算功能，了解神经机制。为了探讨神经网络在整体性和方面处理信息的可能，的概念和方法将会发挥作用。是一个相当难以精确定义的。一般而言，“混沌”是指由确定性方程描述的动力学系统中表现出的非确定性行为，或称之为确定的随机性。“确定性”是因为它由内在的原因而不是外来的噪声或干扰所产生，而“随机性”是指其不规则的、不能预测的行为，只可能用统计的方法描述。系统的主要特征是其状态对的灵敏依赖性，混沌反映其内在的随机性。混沌理论是指描述具有混沌行为的非线性动力学系统的基本理论、概念、方法，它把动力学系统的复杂行为理解为其自身与其在同外界进行物质、和过程中内在的有结构的行为，而不是外来的和偶然的行为，混沌状态是一种定态。混沌动力学系统的定态包括：静止、平稳量、准同 期性和混沌解。混沌轨线是整体上稳定与局部不稳定相结合的结果，称之为。一个有如下一些特征：（1）奇异吸引子是一个，但它既不是不动点，也不是周期解；（2）奇异吸引子是不可分割的，即不能分为两个以及两个以上的吸引子；（3）它对初始值十分敏感，不同的初始值会导致极不相同的行为。五 粒子群算法1粒子群算法粒子群算法，也称（Particle Swarm Optimization），缩写为 PSO， 是近年来发展起来的一种新的(（Evolu2tionary Algorithm - EA）。PSO 算法属于的一种，和相似，它也是从随机解出发，通过迭代寻找，它也是通过来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”(Crossover) 和“”(Mutation) 操作，它通过追随当前搜索到的来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在中搜索。PSO 初始化为一群随机粒子(随机解)。然后通过迭代找到。在每一次迭代中，粒子通过跟踪两个"极值"来更新自己。第一个就是粒子本身所找到的，这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。在找到这两个时，粒子根据如下的公式来更新自己的速度和新的位置：v = w * v + c1 * rand() * (pbest - present) + c2 * rand() * (gbest - present) (a)present = present + v (b)v 是粒子的速度, w是惯性权重,persent 是当前粒子的位置. pbest and gbest 如前定义 rand () 是介于（0， 1）之间的随机数. c1, c2 是学习因子. 通常 c1 = c2 = 2.程序的伪代码如下For each particleInitialize particleEND DoFor each particleCalculate fitness valueIf the fitness value is better than the best fitness value (pBest) in history set current value as the new pBestEndChoose the particle with the best fitness value of all the particles as the gBestFor each particleCalculate particle velocity according equation (a)Update particle position according equation (b)EndWhile maximum iterations or minimum error criteria is not attained在每一维粒子的速度都会被限制在一个最大速度Vmax，如果某一维更新后的速度超过用户设定的Vmax，那么这一维的速度就被限定为Vmax。专心-专注-专业