《近似算法的特点与计算方法分类及概率算法的计算过程与应用DOC》由会员分享，可在线阅读，更多相关《近似算法的特点与计算方法分类及概率算法的计算过程与应用DOC（11页珍藏版）》请在金锄头文库上搜索。
1、近似算法和概率算法的特点与计算方法、分类及概率算法的计算过程与应用一 近似算法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，
2、ID2近似算法的特点（1）解同一个问题的近似算法可能有多个（2）算法的时间复杂性：近似算法的时间复杂性必须是多项式阶的，这是设计近似算法的基本目标。（3）解的近似程度：近似最优解的近似程度也是设计近似算法的重要目标。近似程度可能与近似算法本身、问题规模，乃至不同的输入实例都有关。3近似算法的分类（1） 基于线性规划的近似算法（2） 基于动态规划的近似算法（3） 绝对近似类（4） 相对近似类（5） PTAS类和FPTAS类（6） 随机近似算法二 概率算法1概率算法的计算方法概率算法允许算法在执行的过程中随机选择下一个计算步骤。许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省
3、时。2概率算法的特点（1） 不可再现性。概率算法的一个特点是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。（2） 分析困难。要求有概率论、统计学和数论的知识。3概率算法的分类（1）数值概率算法。数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解。而且近似解的精度随计算时间的增加不断提高。在许多情况下，要计算出问题的精确解是不可能或没有必要的，因此用数值概率算法可得到相当满意的解。（2）蒙特卡罗（Monte Carlo）算法。蒙特卡罗算法用于求问题的准确解。对于许多问题来说，近似解毫无意义。例如，一个判定问题其解为“是”或“否”，二者必居其一，不存在任何近似解答
4、。又如，我们要求一个整数的因子时所给出的解答必须是准确的，一个整数的近似因子没有任何意义。用蒙特卡罗算法能求得问题的一个解，但这个解未必是正确的。求得正确解的概率依赖于算法所用的时间。算法所用的时间越多，得到正确解的概率就越高。蒙特卡罗算法的主要缺点就在于此。一般情况下，无法有效判断得到的解是否肯定正确。Monte Carlo 算法偶然会犯错，但它无论对何实例均能以高概率找到正确解。当算法出错时，没有警告信息。偏真偏假的概念只在Monte Carlo 算法里出现。Def1：设 p 是一个实数，且 1/2p Y 2. 确定性算法的实例集合：X, size 为 n 时写作 Xn 3. Sherwo
5、od 算法用于均匀随机抽样的集合：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
6、 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复杂性问题；克服优化
7、过程陷入局部极小；克服初值依赖性。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；否则算法结束三 遗传算法遗传算法（GeneticAlgo
8、rithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。2遗传算法的运算过程遗传算法的基本运算过程如下：a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个
9、体作为初始群体P(0)。b)个体评价：计算群体P(t)中各个个体的适应度。c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d)交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。3遗传算法的应用随着应用领域的扩展，遗传
10、算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模
11、拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（Evolution Programming,EP）以及进化策略（Evolution Strategy,ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的智能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。四 人工神经网络1人工神经网络的思想人工神经网络是由大量处理单元互联组成的非线性、自适应信息处理系统。它是在现代神经科学研究成果的基础上提出的，试图通过模拟大脑神经网络处理、记忆信息的方式进行信息处理。人工神经网络具有四个
