第九章概率算法课件.ppt

1、2022-12-16计算机算法设计与分析1概率计算n概率计算就是在算法中可采用随机选择计算的步骤、元素或参数等。n它的基本特征是计算具有不确定性。n它的解也不一定是最优解。n它在很大程度上能降低算法的复杂度。n在非标准算法中普遍了应用概率方法，主要有：n(1)直接用概率进行数值计算；n(2)用概率/随机进行选择；n(3)利用概率加速搜索或避免陷于局部最优。2022-12-16计算机算法设计与分析2直接用概率进行数值计算n设f(x)是0,1上的连续函数，求I=f(x)dx。01y=f(x)Gn假设向单位正方形内随机投入n个点(xi,yi)，若有m个点落入G中，则Im/n。ndouble Dart

2、s(int n)double x,y;int k=0;n static RandomNumber dart;n for(int i=1;i=n;i+)x=dart.fRandom();n y=dart.fRandom();if(y=f(x)k+;n return k/double(n);2022-12-16计算机算法设计与分析3划分基准的随机选择n在快速排序算法中，若用拟中位数作为划分标准，可保证在线性时间内完成。但是确定拟中位数要付出额外开销。若选用第一个元素为划分基准，最坏时的时间复杂性为O(n2)。n若在算法中采用随机选择一个元素作为划分标准，便可既保证算法的线性时间平均性能，又避免了计

3、算拟中位数的麻烦。n也可先对数组进行“洗牌”，然后再进行确定的排序算法。这样依然可取得同样的效果。2022-12-16计算机算法设计与分析4“洗牌”后的快速排序nvoid Shuffle(Type a,int n)/随机洗牌算法n static RandomNumber md;n for(int i=1;i n;i+)n int j=md.Random(n i+1)+i;n Swap(ai,aj);nVoid QuiksortByShuffle(Type a,int n)n Shuffle(a,n);/将数组a洗牌n Quiksort(a,n);2022-12-16计算机算法设计与分析5随机抽

4、样 n在n个元素的集合中随机抽取m(0mn)个无重复的元素。为简单起见，假定所有元素的值都位于1至n之间。2022-12-16计算机算法设计与分析6随机抽样n我们采用下面的方法进行选择：n1、首先将n个元素都标记为“未选择”；n2、重复下列步骤直到抽取了m个不同的元素n产生一个1至n间的随机数r；n如果r标记为“未选择”，将它标记为“已选择”，并加入到抽样中。2022-12-16计算机算法设计与分析7随机抽样nint RandomSampling(Sn,Am,m)n mark1.n=False;count=0;n while(count 1)n if(power%2=1)other*=a;ot

5、her%=n;n power/=2;a=a*a%n;n if (a*other%n=1)return True;n return False;n2022-12-16计算机算法设计与分析11合数的见证者n设n为测试的自然数，不妨设n是大于2的奇数，则有n 1=2im，其中i是非负整数，m是正奇数。取一自然数b，1 b n，记W(b)为条件：n bn1 1(mod n)或ni，使得m=(n1)/2i 且 1 gcd(bm1,n)b。n若或中有一个为真，就认为W(b)满足，则n必定是合数，我们称b是n为合数的见证者。n若n有见证者，则n必定为合数。2022-12-16计算机算法设计与分析12合数的见

6、证者多于一半nMiller已经证明，存在常数c，使得当n为合数时，在1,c(log n)2范围内有见证者。nRabin证明了：如果n是合数，则|b|1bn，W(b)满足|(n1)/2 即，在小于n的自然数中有多半是n的见证者。n任取一个自然数b n，若b不是n的见证者，则n是合数的概率小于1/2。若随机取m个数都不是见证者，则n是合数的概率小于1/2m。2022-12-16计算机算法设计与分析13Miller-Rabin素数判定概率算法 nBool Miller_Rabin_Prime(int n)n b1.m=RandomSampling(n,m);n/*随机选取m个大于1小于n的无重复的自

7、然数nfor(j=1;j=m;j+)n if(W(bj)满足)return False;n return True;nn若m=100，则n不是素数的概率小于1/2100。2022-12-16计算机算法设计与分析14Las Vegas算法nLas Vegas算法的特点是随机性地进行决策。n例如对n后问题，Las Vegas算法是随机地产生一组王后放置的位置。若成功了，便找到了一个解；若失败了，就整个重来，再随机产生另外一组王后的位置。这样作，直至找到解。n此算法能显著地改进算法的有效性，甚至对迄今为止找不到有效算法的问题，也能得到满意的结果。2022-12-16计算机算法设计与分析15瞎子爬山法

8、与局部最优n更一般的求解问题的方法是瞎子爬山法。n一个瞎子从山脚开始，试探着一步一步向上爬，就可以一直爬到山顶。n可是，他爬上的可能只是个小山头，更高的山还在后面。而他无法从小山头下来，也就无法爬到更高的山头了。n这种情形就被称为陷入了局部最优。n如何避免陷入局部最优是求解问题中要注意的一个重要问题。2022-12-16计算机算法设计与分析16进化算法(Evolutionary Algorithm)n达尔文的进化论：适者生存，优胜劣汰。n1975年霍兰(Holland)提出了遗传算法，通过模拟生物进化的过程概率搜索最优解。n遗传算法首先产生所谓的个体种群，每个个体是编码的二进制串(又称为染色体

9、)。n然后对个体进行随机的选择，再经过复制、交叉和变异产生下一代的种群。n就这样经过一代一代的进化，最终获得满意的个体(即问题的解)。2022-12-16计算机算法设计与分析17进化计算中的基本算子n适应值f(xi)：给出个体xi优劣；n选择算子：对个体进行概率选择。个体的概率为p(xi)=f(xi)/f(xj)，优秀的个体具有较高的概率。最常用的选择算子为轮盘赌的方法。这样优秀个体具有较高的被选中的概率。同时差的个体也有被选中的可能。n复制算子copy：对选中的个体进行复制。n交叉算子：将两个个体染色体中的某个位彼此交换，从而形成两个新的个体。n变异算子m：改变一个个体的染色体的某些位，得到

10、一个新的个体。n停止准则：决定算法停止的准则2022-12-16计算机算法设计与分析18进化算法的基本框架nt=0/t为代数；n初始化：P(0)=a1(0),an(0)/初始种群P(0)n度量：P(0):f(a1(0),f(an(0);nwhile(P(t)不满足停止准则)n 交叉：P(t)=(P(t);n 变异：P(t)=m(P(t);n 度量：P(t)：f(a1(t),f(an(t);n 选择：P(t+1)=P(t)Q;n t=t+1;2022-12-16计算机算法设计与分析19进化计算的优缺点n是一种通用的计算方法，一旦问题表示为种群后，算法便不在依赖于问题。n求解不依赖于初始状况，通常

11、具有较好的收敛性，也不容易陷于局部最优。n依然有可能陷入局部最优(早熟收敛)。n选择问题的表示方案和适应值度量的优劣、选择种群的规模大小、代数、控制执行各种算子的参数、停止准则等的好坏都可影响算法的功能和效果。2022-12-16计算机算法设计与分析20模拟退火算法n1982年Kirkpatrick将固体退火过程应用于组合优化问题的求解，提出一种有效的近似算法，称为模拟退火算法。n模拟退火算法从初始解i=i0开始，在当前解i的邻域Si中按照Metropolis准则搜索新解j以取代当前解i。这个过程不断进行下去，直到达到目标函数最优。2022-12-16计算机算法设计与分析21固体退火过程n退火

12、是固体由高温下粒子排列的无序的液态冷却而凝固成粒子排列有序的固体晶态的过程。n退火是系统的熵不断减小，能量趋于最小值的过程。它遵循热力学中的自由能减少定律：F=E TSn其中F、E和S分别表示自由能、能量和熵。n系统从非平衡态自发变化到平衡态，都是能量和熵竞争的结果，温度决定二者孰重。2022-12-16计算机算法设计与分析22Metropolis接受准则n设i是一个状态，j是由i可得到的一个新状态。它们的能量分别为Ei和Ej。n若EjEi，则状态j可以取代状态i。n否则固体处于状态i和状态j的几率为r=exp(Ei Ej)/kT)其中k是Boltzmann常数，T为绝对温度，r1。n设是(0

13、,1)中的随机数，若r ，则状态j可以取代状态i。2022-12-16计算机算法设计与分析23模拟退火算法的框架nk=0;i=i0;t=t0;/初始化nwhile(不满足停止准则)n Gen(Si);/产生i的邻域Si，|Si|=Lkn for(jSi)/用Metropolis准则对Si中的n if(f(i)random(0,1)i=j;n k=k+1;t=tk;/降温；进入下一轮迭代n 2022-12-16计算机算法设计与分析24算法的性能n算法可以渐进地收敛于整体最优解。nMetropolis准则给算法引入了随机性，使算法进程方向呈现跳跃性，从而可能避开局部最优，但不能完全避开局部收敛。n

14、最终解不依赖于初始解。n温度t和|Si|(即Lk)决定算法的收敛速度。n算法的复杂性为O(kLP(n)，其中k为迭代次数，L=max|Si|，P(n)是问题规模n的多项式函数。求高质量的近似解的耗费也较高。2022-12-16计算机算法设计与分析25模拟退火算法的应用n(1)确定解问题、能量函数和初始解：解空间是所有可行解的集合；能量函数是优化目标的数学描述；初始解是开始计算的起点。n(2)新解的产生和接受准则：从当前解产生新解；用Metropolis准则判断新解是否可替代当前解；然后用新解/当前解进行下一轮实验。n(3)冷却进度表及其它参数：Lk由新解来确定，冷却温度tk用冷却进度表或衰减函

15、数给出。应用模拟退火算法的工作如下：2022-12-16计算机算法设计与分析26用模拟退火算法解TSPn解空间为所有的排列，初始解为。n能量函数f为发、该排列的周游路线长度。即 nf()=mindikdik+1+din di1 k=1n产生新解：用某种方法将旧排列变换成新排列。例如：在排列中任选u,v，交换u,v，并将u和v之间的顺序逆转。比如：取u=2，v=3：或者：在排列中任选u,v，和w，将u和v之间的子串插在w之后。比如：选u,v,w分别为2,5,6:2022-12-16计算机算法设计与分析27算法中参数的讨论n冷却进度表：用参数t的一个递减序列tk和与之对应的Lk的序列来控制算法的进

16、程。通常选tk的小衰减量以避免过大的Lk值。n只要tk和Lk与停止准则选择恰当，算法不仅收敛而且提高收敛速度。nt0值过小导致解质量差，过大增加求解时间。如何选择t0是个重要问题。n当tk减小时Lk则增大。一般用个多项式P(n)来限制。一般选迭代次数650次为停止准则。2022-12-16计算机算法设计与分析28人工神经网络n1943年McCulloch和Pitts提出神经元的数学模型，即MP模型。n1957年Rosenblatt设计制作了“感知机”。这是第一个多层的人工神经网络。第一个高潮期。n1969年之后进入低潮。n1980年以后重新进入高潮，并得到蓬勃的发展。n目前人们普遍认为突破图林

17、机模型的将是人工神经网络。这是下一代计算机的主体。2022-12-16计算机算法设计与分析29神经元n右图是一个神经元：n神经元的构造为若干根输入的突轴和一根输出的树轴。n神经元可以有抑制和激活这两种状态。当输入的信号达到一定的程度，神经元便被激活产生输出信号。2022-12-16计算机算法设计与分析30神经元的数学模型(MP模型)n右图是MP模型的示意图：y=f(iwixi )其中：f称为激活函数，为阈值，wi为权重。n激活函数的形式通常有两种形式：2022-12-16计算机算法设计与分析31人工神经网络n人工神经网络就是人工神经元所构成的网络。主要有前馈网络和反馈网络两种形式。n前馈网络有

18、若干层神经元组成，第i层的神经元只接受第i1层输出的信息，而不接受同层或高层的输出信息。n反馈网络中的神经元可以接受外加输入和其它神经元包括自身的反馈输入。2022-12-16计算机算法设计与分析32人工神经网络的学习n神经元的计算主要依赖于权重wi，而权重wi是通过学习获得的。n所谓学习(又称训练)是首先给权重赋予一个初值，然后将大量的训练样板(包括正例和反例)输入计算机，人工神经网络自己不断地调整相应的权重。n学习的方式主要分为：有监督的学习和自适应的学习两种形式，以及它们的改进。2022-12-16计算机算法设计与分析33BP神经网络nBP神经网络是一个三层前馈网络，分别为输入层LA，隐

19、含层LB和输出层LC。每层分别有若干个神经元。如下图所示：2022-12-16计算机算法设计与分析34BP学习算法nBP网络的学习算法是一种监督的学习过程。它是一个误差逆向分配调整的过程。nBP学习算法的步骤如下：n(1)初始化：给LB 和LC中的神经元随机赋予权重wij和阈值i。n(2)依次输入训练样本，并根据该训练样本调整LB 和LC中每个神经元权重和阈值。n(3)重复第(2)步直到误差足够小或为零。2022-12-16计算机算法设计与分析35BP学习算法中的逆向误差调整n计算LB层的实际输出bi=f(wijxi i)；n计算LC层的实际输出yj=f(iwijbi j);n计算LC层的输出

20、误差ej=yj(1yj)(djyj);n计算LB层的输出误差ej=yj(1yj)iwijei;n调整LB层到LC层的权重wij=biei;n调整LC层的阈值j=ei;n调整LA层到LB层的权重wij=yiei;n调整LB层的阈值i=ei;n其中和称为学习率，0,1。2022-12-16计算机算法设计与分析36用神经网络求解“异或”问题n求解“异或”问题的神经网络如右图：n激活函数取为：f(x)=(1+ex)1；n学习率取为：=0.6；n权重和阈值随机取一较小的初始值。2022-12-16计算机算法设计与分析37精品课件精品课件！2022-12-16计算机算法设计与分析38精品课件精品课件！2022-12-16计算机算法设计与分析39