近似算法的特点与计算方法、分类及概率算法的计算过程与应用

近似算法和概率算法的特点与计算方法、分类及概率算法的计算过程与应用近似算法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为最小化问题.RA(I)=OP(I)，若D为最大化问题.A(I)RA(D)=inf{r≥|RA(I)≤r，I∈D}2近似算法的特点（1）解同一个问题的近似算法可能有多个（2）算法的时间复杂性：近似算法的时间复杂性必须是多项式阶的，这是设计近似算法的基本目标。（3）解的近似程度：近似最优解的近似程度也是设计近似算法的重要目标。近似程度可能与近似算法本身、问题规模，乃至不同的输入实例都有关。3近似算法的分类基于线性规划的近似算法基于动态规划的近似算法绝对近似类相对近似类PTAS类和FPTAS类随机近似算法概率算法1概率算法的计算方法概率算法允许算法在执行的过程中随机选择下一个计算步骤。许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。2概率算法的特点不可再现性。概率算法的一个特点是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。分析困难。要求有概率论、统计学和数论的知识。3概率算法的分类（1）数值概率算法。数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解。而且近似解的精度随计算时间的增加不断提高。在许多情况下，要计算出问题的精确解是不可能或没有必要的，因此用数值概率算法可得到相当满意的解。（2）蒙特卡罗（MonteCarlo）算法。蒙特卡罗算法用于求问题的准确解。对于许多问题来说，近似解毫无意义。例如，一个判定问题其解为“是”或“否”，二者必居其一，不存在任何近似解答。又如，我们要求一个整数的因子时所给出的解答必须是准确的，一个整数的近似因子没有任何意义。用蒙特卡罗算法能求得问题的一个解，但这个解未必是正确的。求得正确解的概率依赖于算法所用的时间。算法所用的时间越多，得到正确解的概率就越高。蒙特卡罗算法的主要缺点就在于此。一般情况下，无法有效判断得到的解是否肯定正确。MonteCarlo算法偶然会犯错，但它无论对何实例均能以高概率找到正确解。当算法出错时，没有警告信息。偏真偏假的概念只在MonteCarlo算法里出现。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）拉斯维加斯（LasVegas）算法。拉斯维加斯算法不会得到不正确的解，一旦用拉斯维加斯算法找到一个解，那么这个解肯定是正确的。但是有时候用拉斯维加斯算法可能找不到解。与蒙特卡罗算法类似。拉斯维加斯算法得到正确解的概率随着它用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失效的概率任意小。算法的一般形式：LV(x,y,success)——x是输入的实例，y是返回的参数，success是布尔值，true表示成功，false表示失败p(x)——对于实例x，算法成功的概率s(x)——算法成功时的期望时间e(x)——算法失败时的期望时间Obstinate(x){repeatLV(x,y,success);untilsuccess;returny;}设t(x)是算法obstinate找到一个正确解的期望时间，则t(x)=𝑝(𝑥)𝑠(𝑥)+(1−𝑝(𝑥))(𝑒(𝑥)+𝑡(𝑥))t(x)是指第一次成功的期望时间，第一次失败，后面再成功就需要花费的时间。（4）舍伍德（Sherwood）算法。舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以在这个确定算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况行为，而是设法消除这种最坏行为与特定实例之间的关联性。Sherwood算法预处理的数学模型1.确定性算法：f:X->Y2.确定性算法的实例集合：X,size为n时写作Xn3.Sherwood算法用于均匀随机抽样的集合：A，size为n时写作An，|An|=|Xn|4.随机抽样的预处理及后处理时用到的一对函数，对应上面的①③u:X×A->Yv: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为nr←uniform(An);//随机取一元素y←u(x,r);//将原实例x转化为随机实例ys←f(y);//用确定算法求y的解sreturnv(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

Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。2遗传算法的运算过程遗传算法的基本运算过程如下：a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。b)个体评价：计算群体P(t)中各个个体的适应度。c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d)交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t1)。f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。3遗传算法的应用随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（EvolutionProgramming,EP）以及进化策略（EvolutionStrategy,ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的智能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。人工神经网络1人工神经网络的思想人工神经网络是由大量处理单元互联组成的非线性、自适应信息处理系统。它是在现代神经科学研究成果的基础上提出的，试图通过模拟大脑神经网络处理、记忆信息的方式进行信息处理。人工神经网络具有四个基本特征：（1）非线性非线性关系是自然界的普遍特性。大脑的智慧就是一种非线性现象。人工神经元处于激活或抑制二种不同的状态，这种行为在数学上表现为一种非线性关系。具有阈值的神经元构成的网络具有更好的性能，可以提高容错性和存储容量。（2）非局限性一个神经网络通常由多个神经元广泛连接而成。一个系统的整体行为不仅取决于单个神经元的特征，而且可能主要由单元之间的相互作用、相互连接所决定。通过单元之间的大量连接模拟大脑的非局限性。联想记忆是非局限性的典型例子。（3）非常定性人工神经网络具有自适应、自组织、自学习能力。神经网络不但处理的信息可以有各种变化，而且在处理信息的同时，非线性动力系统本身也在不断变化。经常采用迭代过程描写动力系统的演化过程。（4）非凸性一个系统的演化方向，在一定条件下将取决于某个特定的状态函数。例如能量函数，它的极值相应于系统比较稳定的状态。非凸性是指这种函数有多个极值，故系统具有多个较稳定的平衡态，这将导致系统演化的多样性。人工神经网络中，神经元处理单元可表示不同的对象，例如特征、字母、概念，或者一些有意义的抽象模式。网络中处理单元的类型分为三类：输入单元、输出单元和隐单元。输入单元接受外部世界的信号与数据；输出单元实现系统处理结果的输出；隐单元是处在输入和输出单元之间，不能有系统外部观察的单元。神经元间的连接权值反映了单元间的连接强度，信息的表示和处理体现在网络处理单元的连接关系中。人工神经网络是一种非程序化、适应性、大脑风格的信息处理，其本质是通过网络的变换和动力学行为得到一种并行分布式的信息处理功能，并在不同程度和层次上模仿人脑神经系统的信息处理功能。它是涉及神经科学、思维科学、人工智能、计算机科学等多个领域的交叉学科。人工神经网络是并行分布式系统，采用了与传统人工智能和信息处理技术完全不同的机理，克服了传统的基于逻辑符号的人工智能在处理直觉、非结构化信息方面的缺陷，具有自适应、自组织和实时学习的特点。2人工神经网络的分析方法研究神经网络的非线性动力学性质，主要采用动力学系统理论、非线性规划理论和统计理论，来分析神经网络的演化过程和吸引子的性质，探索神经网络的协同行为和集体计算功能，了解神经信息处理机制。为了探讨神经网络在整体性和模糊性方面处理信息的可能，混沌理论的概念和方法将会发挥作用。混沌是一个相当难以精确定义的数学概念。一般而言，“混沌”是指由确定性方程描述的动力学系统中表现出的非确定性行为，或称之为确定的随机性。“确定性”是因为它由内在的原因而不是外来的噪声或干扰所产生，而“随机性”是指其不规则的、不能预测的行为，只可能用统计的方法描述。混沌动力学系统的主要特征是其状态对初始条件的灵敏依赖性，混沌反映其内在的随机性。混沌理论是指描述具有混沌行为的非线性动力学系统的基本理论、概念、方法，它把动力学系统的复杂行为理解为其自身与其在同外界进行物质、能量和信息交换过程中内在的有结构的行为，而不是外来的和偶然的行为，混沌状态是一种定态。混沌动力学系统的定态包括：静止、平稳量、周期性、准同期性和混沌解。混沌轨线是整体上稳定与局部不稳定相结合的结果，称之为奇异吸引子。一个奇异吸引子有如下一些特征：（1）奇异吸引子是一个吸引子，但它既不是不动点，也不是周期解；（2）奇异吸引子是不可分割的，即不能分为两个以及两个以上的吸引子；（3）它对初始值十分敏感，不同的初始值会导致极不相同的行为。粒子群算法1粒子群算法粒子群算法，也称粒子群优化算法（ParticleSwarmOptimization），缩写为PSO，是近年来发展起来的一种新的进化算法(（Evolu2tionaryAlgorithm-EA）。PSO算法属于进化算法的一种，和遗传算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”(Crossover)和“变异”(Mutation)操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在HYPERLINK"/view/20272