1、2018/10/9,计算机算法设计与分析,1,第九章 概率算法,2018/10/9,计算机算法设计与分析,2,概率计算,概率计算就是在算法中可采用随机选择计算的步骤、元素或参数等。 它的基本特征是计算具有不确定性。 它的解也不一定是最优解。 它在很大程度上能降低算法的复杂度。 在非标准算法中普遍了应用概率方法，主要有： (1)直接用概率进行数值计算； (2)用概率/随机进行选择； (3)利用概率加速搜索或避免陷于局部最优。,2018/10/9,计算机算法设计与分析,3,直接用概率进行数值计算,设f(x)是0, 1上的连续函数，求I = f(x)dx。,01,y = f(x),G,假设向单位正方
2、形内随机投入n个点(xi, yi)，若有m个点落入G中，则Im/n。,double Darts (int n) double x, y; int k = 0; static RandomNumber dart;for (int i=1; i=n; i+) x=dart.fRandom(); y=dart.fRandom(); if (y=f(x) k+;return k/double(n); ,2018/10/9,计算机算法设计与分析,4,划分基准的随机选择,在快速排序算法中，若用拟中位数作为划分标准，可保证在线性时间内完成。但是确定拟中位数要付出额外开销。若选用第一个元素为划分基准，最坏时的
3、时间复杂性为O(n2)。 若在算法中采用随机选择一个元素作为划分标准，便可既保证算法的线性时间平均性能，又避免了计算拟中位数的麻烦。 也可先对数组进行“洗牌”，然后再进行确定的排序算法。这样依然可取得同样的效果。,2018/10/9,计算机算法设计与分析,5,“洗牌”后的快速排序,void Shuffle(Type a, int n) /随机洗牌算法static RandomNumber md;for (int i = 1; i n; i+) int j = md.Random(n i + 1) + i;Swap(ai, aj); Void QuiksortByShuffle(Type a,
4、int n) Shuffle(a, n); /将数组a洗牌Quiksort(a, n); ,2018/10/9,计算机算法设计与分析,6,随机抽样,在n个元素的集合中随机抽取m(0mn)个无重复的元素。为简单起见，假定所有元素的值都位于1至n之间。,2018/10/9,计算机算法设计与分析,7,随机抽样,我们采用下面的方法进行选择： 1、首先将n个元素都标记为“未选择”； 2、重复下列步骤直到抽取了m个不同的元素 产生一个1至n间的随机数r； 如果r标记为“未选择”，将它标记为“已选择”，并加入到抽样中。,2018/10/9,计算机算法设计与分析,8,随机抽样,int RandomSampli
5、ng(Sn, Am, m) mark1n = False; count=0;while(count m) r = random(1, n);if (markr = False) count+;Acount=Sr;markr=True; ,2018/10/9,计算机算法设计与分析,9,判定素数的概率算法,判定自然数是否是素数，不仅有重要理论意义，而且在密码学中具有重要实用价值。 最简单的素数判定方法是依次测定从2到n 中是否存在n的因子，该算法的复杂度为O(n )。 筛法：将小于n的合数预先筛掉，而不用判断其是否为n的因子。它虽然没有降低算法的复杂度，但实际运行速度比前者要快得多。 概率算法，保
6、证一定概率的前提下简单判断。,2018/10/9,计算机算法设计与分析,10,Fermat素数测试法,Fermat定理： 若p是素数，则对任意整数a，gcd(a, p) = 1，则有ap11 (mod p)。 显然，对素数p有pp1 1 (mod p)。 对于一般的整数n，满足nn11 (mod n)的数目很少。满足的称为伪素数。 就用是否满足nn11 (mod n)来判断n是否为素数。,2018/10/9,计算机算法设计与分析,11,Fermat素数测试法,Bool Fermat_Prime(int n) a = 2; power = n 1; other = 1;while(power 1
7、) if (power % 2 = = 1) other *= a; other %= n;power /= 2; a = a * a % n;if (a * other % n = 1) return True;return False; ,2018/10/9,计算机算法设计与分析,12,合数的见证者,设n为测试的自然数，不妨设n是大于2的奇数，则有n 1 = 2im，其中i是非负整数，m是正奇数。取一自然数b，1 b n，记W(b)为条件： bn1 1 (mod n) 或 i，使得m = (n1)/2i 且 1 gcd(bm1, n) b。 若或中有一个为真，就认为W(b)满足，则n必定是
8、合数，我们称b是n为合数的见证者。 若n有见证者，则n必定为合数。,2018/10/9,计算机算法设计与分析,13,合数的见证者多于一半,Miller已经证明，存在常数c，使得当n为合数时，在1, c(log n)2范围内有见证者。,Rabin证明了：如果n是合数，则 |b|1bn，W(b)满足|(n1)/2即，在小于n的自然数中有多半是n的见证者。,任取一个自然数b n，若b不是n的见证者，则n是合数的概率小于1/2。若随机取m个数都不是见证者，则n是合数的概率小于1/2m。,2018/10/9,计算机算法设计与分析,14,Miller-Rabin素数判定概率算法,Bool Miller_R
9、abin_Prime(int n)b1 m = RandomSampling(n, m); /*随机选取m个大于1小于n的无重复的自然数 for (j = 1; j = m; j+)if (W(bj) 满足) return False;return True; 若m = 100，则n不是素数的概率小于1/2100。,2018/10/9,计算机算法设计与分析,15,Las Vegas算法,Las Vegas算法的特点是随机性地进行决策。 例如对n后问题，Las Vegas算法是随机地产生一组王后放置的位置。若成功了，便找到了一个解；若失败了，就整个重来，再随机产生另外一组王后的位置。这样作，直至
10、找到解。 此算法能显著地改进算法的有效性，甚至对迄今为止找不到有效算法的问题，也能得到满意的结果。,2018/10/9,计算机算法设计与分析,16,瞎子爬山法与局部最优,更一般的求解问题的方法是瞎子爬山法。 一个瞎子从山脚开始，试探着一步一步向上爬，就可以一直爬到山顶。,可是，他爬上的可能只是个小山头，更高的山还在后面。而他无法从小山头下来，也就无法爬到更高的山头了。,这种情形就被称为陷入了局部最优。,如何避免陷入局部最优是求解问题中要注意的一个重要问题。,2018/10/9,计算机算法设计与分析,17,进化算法(Evolutionary Algorithm),达尔文的进化论：适者生存，优胜劣
11、汰。 1975年霍兰(Holland)提出了遗传算法，通过模拟生物进化的过程概率搜索最优解。 遗传算法首先产生所谓的个体种群，每个个体是编码的二进制串(又称为染色体)。 然后对个体进行随机的选择，再经过复制、交叉和变异产生下一代的种群。 就这样经过一代一代的进化，最终获得满意的个体(即问题的解)。,2018/10/9,计算机算法设计与分析,18,进化计算中的基本算子,适应值f(xi)：给出个体xi优劣； 选择算子：对个体进行概率选择。,个体的概率为p(xi) = f(xi) / f(xj)，优秀的个体具有较高的概率。 最常用的选择算子为轮盘赌的方法。这样优秀个体具有较高的被选中的概率。同时差的
12、个体也有被选中的可能。,复制算子copy：对选中的个体进行复制。 交叉算子：将两个个体染色体中的某个位彼此交换，从而形成两个新的个体。 变异算子m：改变一个个体的染色体的某些位，得到一个新的个体。 停止准则：决定算法停止的准则,2018/10/9,计算机算法设计与分析,19,进化算法的基本框架,t = 0 / t为代数； 初始化：P(0)=a1(0), , an(0)/初始种群P(0) 度量：P(0): f(a1(0), , f(an(0); while (P(t)不满足停止准则) 交叉：P(t) = (P(t);变异：P(t) = m(P(t);度量：P(t)：f(a1(t), , f(an
13、(t);选择：P(t+1) = P(t) Q;t = t +1; ,2018/10/9,计算机算法设计与分析,20,进化计算的优缺点,是一种通用的计算方法，一旦问题表示为种群后，算法便不在依赖于问题。 求解不依赖于初始状况，通常具有较好的收敛性，也不容易陷于局部最优。 依然有可能陷入局部最优(早熟收敛)。 选择问题的表示方案和适应值度量的优劣、选择种群的规模大小、代数、控制执行各种算子的参数、停止准则等的好坏都可影响算法的功能和效果。,2018/10/9,计算机算法设计与分析,21,模拟退火算法,1982年Kirkpatrick将固体退火过程应用于组合优化问题的求解，提出一种有效的近似算法，称
14、为模拟退火算法。 模拟退火算法从初始解i = i0开始，在当前解i的邻域Si中按照Metropolis准则搜索新解j以取代当前解i。这个过程不断进行下去，直到达到目标函数最优。,2018/10/9,计算机算法设计与分析,22,固体退火过程,退火是固体由高温下粒子排列的无序的液态冷却而凝固成粒子排列有序的固体晶态的过程。 退火是系统的熵不断减小，能量趋于最小值的过程。它遵循热力学中的自由能减少定律：,F = E TS 其中F、E和S分别表示自由能、能量和熵。,系统从非平衡态自发变化到平衡态，都是能量和熵竞争的结果，温度决定二者孰重。,2018/10/9,计算机算法设计与分析,23,Metropo
15、lis接受准则,设i是一个状态，j是由i可得到的一个新状态。它们的能量分别为Ei和Ej。 若EjEi，则状态j可以取代状态i。 否则固体处于状态i和状态j的几率为,r = exp (Ei Ej) / kT) 其中k是Boltzmann常数，T为绝对温度，r1。,设是(0, 1)中的随机数，若r ，则状态j可以取代状态i。,2018/10/9,计算机算法设计与分析,24,模拟退火算法的框架,k = 0; i = i0; t = t0; /初始化 while (不满足停止准则) Gen(Si); /产生i的邻域Si，|Si|=Lkfor (jSi) /用Metropolis准则对Si中的if (f
16、(i) random(0, 1) i = j;k = k + 1; t = tk; / 降温；进入下一轮迭代,2018/10/9,计算机算法设计与分析,25,算法的性能,算法可以渐进地收敛于整体最优解。 Metropolis准则给算法引入了随机性，使算法进程方向呈现跳跃性，从而可能避开局部最优，但不能完全避开局部收敛。 最终解不依赖于初始解。 温度t和|Si|(即Lk)决定算法的收敛速度。 算法的复杂性为O(kLP(n)，其中k为迭代次数，L=max|Si|，P(n)是问题规模n的多项式函数。求高质量的近似解的耗费也较高。,2018/10/9,计算机算法设计与分析,26,模拟退火算法的应用,(
17、1)确定解问题、能量函数和初始解：解空间是所有可行解的集合；能量函数是优化目标的数学描述；初始解是开始计算的起点。 (2)新解的产生和接受准则：从当前解产生新解；用Metropolis准则判断新解是否可替代当前解；然后用新解/当前解进行下一轮实验。 (3)冷却进度表及其它参数：Lk由新解来确定，冷却温度tk用冷却进度表或衰减函数给出。,应用模拟退火算法的工作如下：,2018/10/9,计算机算法设计与分析,27,用模拟退火算法解TSP,解空间为所有的排列，初始解为 。 能量函数f为发、该排列的周游路线长度。即,n f() = mindikdik+1 + din di1k=1,产生新解：用某种方
18、法将旧排列变换成新排列。,例如：在排列中任选u, v，交换u, v，并将u和v之间的顺序逆转。比如：取u = 2，v = 3： ,或者：在排列中任选u, v，和w，将u和v之间的子串插在w之后。比如：选u, v, w分别为2, 5, 6: ,2018/10/9,计算机算法设计与分析,28,算法中参数的讨论,冷却进度表：用参数t的一个递减序列tk和与之对应的Lk的序列来控制算法的进程。通常选tk的小衰减量以避免过大的Lk值。 只要tk和Lk与停止准则选择恰当，算法不仅收敛而且提高收敛速度。 t0值过小导致解质量差，过大增加求解时间。如何选择t0是个重要问题。 当tk减小时Lk则增大。一般用个多项
19、式P(n)来限制。一般选迭代次数650次为停止准则。,2018/10/9,计算机算法设计与分析,29,人工神经网络,1943年McCulloch和Pitts提出神经元的数学模型，即MP模型。 1957年Rosenblatt设计制作了“感知机”。这是第一个多层的人工神经网络。第一个高潮期。 1969年之后进入低潮。 1980年以后重新进入高潮，并得到蓬勃的发展。 目前人们普遍认为突破图林机模型的将是人工神经网络。这是下一代计算机的主体。,2018/10/9,计算机算法设计与分析,30,神经元,右图是一个神经元：,神经元的构造为若干根输入的突轴和一根输出的树轴。,神经元可以有抑制和激活这两种状态。
20、当输入的信号达到一定的程度，神经元便被激活产生输出信号。,2018/10/9,计算机算法设计与分析,31,神经元的数学模型(MP模型),右图是MP模型的示意图：,y = f(iwixi )其中：f称为激活函数， 为阈值，wi为权重。,激活函数的形式通常有两种形式：,2018/10/9,计算机算法设计与分析,32,人工神经网络,人工神经网络就是人工神经元所构成的网络。主要有前馈网络和反馈网络两种形式。 前馈网络有若干层神经元组成，第i层的神经元只接受第i1层输出的信息，而不接受同层或高层的输出信息。 反馈网络中的神经元可以接受外加输入和其它神经元包括自身的反馈输入。,2018/10/9,计算机算
21、法设计与分析,33,人工神经网络的学习,神经元的计算主要依赖于权重wi，而权重wi是通过学习获得的。 所谓学习(又称训练)是首先给权重赋予一个初值，然后将大量的训练样板(包括正例和反例)输入计算机，人工神经网络自己不断地调整相应的权重。 学习的方式主要分为：有监督的学习和自适应的学习两种形式，以及它们的改进。,2018/10/9,计算机算法设计与分析,34,BP神经网络,BP神经网络是一个三层前馈网络，分别为输入层LA，隐含层LB和输出层LC。每层分别有若干个神经元。如下图所示：,2018/10/9,计算机算法设计与分析,35,BP学习算法,BP网络的学习算法是一种监督的学习过程。它是一个误差
22、逆向分配调整的过程。 BP学习算法的步骤如下： (1)初始化：给LB 和LC中的神经元随机赋予权重wij和阈值i。 (2)依次输入训练样本，并根据该训练样本调整LB 和LC中每个神经元权重和阈值。 (3)重复第(2)步直到误差足够小或为零。,2018/10/9,计算机算法设计与分析,36,BP学习算法中的逆向误差调整,计算LB层的实际输出bi = f(wijxi i)； 计算LC层的实际输出yj = f(iwijbi j); 计算LC层的输出误差ej = yj(1yj)(djyj); 计算LB层的输出误差ej = yj(1yj) iwijei ; 调整LB层到LC层的权重wij =biei ; 调整LC层的阈值j =ei ; 调整LA层到LB层的权重wij =yiei ; 调整LB层的阈值i= ei ;,其中和称为学习率，0, 1。,2018/10/9,计算机算法设计与分析,37,用神经网络求解“异或”问题,求解“异或”问题的神经网络如右图：,激活函数取为：f(x) = (1+ex)1；,学习率取为： = = 0.6；,权重和阈值随机取一较小的初始值。,2018/10/9,计算机算法设计与分析,38,
