第九章概率算法

第九章概率算法第一页，共三十八页，2022年，8月28日2023/3/291计算机算法设计与分析概率计算概率计算就是在算法中可采用随机选择计算的步骤、元素或参数等。它的基本特征是计算具有不确定性。它的解也不一定是最优解。它在很大程度上能降低算法的复杂度。在非标准算法中普遍了应用概率方法，主要有：(1)直接用概率进行数值计算；(2)用概率/随机进行选择；(3)利用概率加速搜索或避免陷于局部最优。第二页，共三十八页，2022年，8月28日2023/3/292计算机算法设计与分析直接用概率进行数值计算设f(x)是[0,1]上的连续函数，求I=∫f(x)dx。01y=f(x)G假设向单位正方形内随机投入n个点(xi,yi)，若有m个点落入G中，则I≈m/n。doubleDarts(intn){doublex,y;intk=0;staticRandomNumberdart;for(inti=1;i<=n;i++){x=dart.fRandom();y=dart.fRandom();if(y<=f(x))k++;}returnk/double(n);}第三页，共三十八页，2022年，8月28日2023/3/293计算机算法设计与分析划分基准的随机选择在快速排序算法中，若用拟中位数作为划分标准，可保证在线性时间内完成。但是确定拟中位数要付出额外开销。若选用第一个元素为划分基准，最坏时的时间复杂性为O(n2)。若在算法中采用随机选择一个元素作为划分标准，便可既保证算法的线性时间平均性能，又避免了计算拟中位数的麻烦。也可先对数组进行“洗牌”，然后再进行确定的排序算法。这样依然可取得同样的效果。第四页，共三十八页，2022年，8月28日2023/3/294计算机算法设计与分析“洗牌”后的快速排序voidShuffle(Typea[],intn){//随机洗牌算法

staticRandomNumbermd;for(inti=1;i<n;i++){intj=md.Random(n–i+1)+i;Swap(a[i],a[j]);}}VoidQuiksortByShuffle(Typea[],intn){Shuffle(a,n);//将数组a洗牌

Quiksort(a,n);}第五页，共三十八页，2022年，8月28日2023/3/295计算机算法设计与分析随机抽样在n个元素的集合中随机抽取m(0<m≤n)个无重复的元素。为简单起见，假定所有元素的值都位于1至n之间。第六页，共三十八页，2022年，8月28日2023/3/296计算机算法设计与分析随机抽样我们采用下面的方法进行选择：1、首先将n个元素都标记为“未选择”；2、重复下列步骤直到抽取了m个不同的元素⑴产生一个1至n间的随机数r；⑵如果r标记为“未选择”，将它标记为“已选择”，并加入到抽样中。第七页，共三十八页，2022年，8月28日2023/3/297计算机算法设计与分析随机抽样intRandomSampling(S[n],A[m],m){mark[1..n]=False;count=0;while(count<m){r=random(1,n);if(mark[r]==False){count++;A[count]=S[r];mark[r]=True;}}}第八页，共三十八页，2022年，8月28日2023/3/298计算机算法设计与分析判定素数的概率算法

判定自然数是否是素数，不仅有重要理论意义，而且在密码学中具有重要实用价值。最简单的素数判定方法是依次测定从2到n½

中是否存在n的因子，该算法的复杂度为O(n½)。筛法：将小于n的合数预先筛掉，而不用判断其是否为n的因子。它虽然没有降低算法的复杂度，但实际运行速度比前者要快得多。概率算法，保证一定概率的前提下简单判断。第九页，共三十八页，2022年，8月28日2023/3/299计算机算法设计与分析Fermat素数测试法Fermat定理：若p是素数，则对任意整数a，gcd(a,p)=1，则有ap–1≡1(modp)。显然，对素数p有pp–1≡1(modp)。对于一般的整数n，满足nn–1≡1(modn)的数目很少。满足的称为伪素数。就用是否满足nn–1≡1(modn)来判断n是否为素数。第十页，共三十八页，2022年，8月28日2023/3/2910计算机算法设计与分析Fermat素数测试法BoolFermat_Prime(intn){a=2;power=n–1;other=1;while(power>1){if(power%2=

=1){other*=a;other%=n;}power/=2;a=a*a%n;}if(a*other%n==1)returnTrue;returnFalse;}第十一页，共三十八页，2022年，8月28日2023/3/2911计算机算法设计与分析合数的见证者设n为测试的自然数，不妨设n是大于2的奇数，则有n–1=2im，其中i是非负整数，m是正奇数。取一自然数b，1<b<n，记W(b)为条件：①bn–1≠1(modn)或②i，使得m=(n–1)/2i

且1<gcd(bm–1,n)<b。若①或②中有一个为真，就认为W(b)满足，则n必定是合数，我们称b是n为合数的见证者。若n有见证者，则n必定为合数。第十二页，共三十八页，2022年，8月28日2023/3/2912计算机算法设计与分析合数的见证者多于一半Miller已经证明，存在常数c，使得当n为合数时，在[1,c(logn)2]范围内有见证者。Rabin证明了：如果n是合数，则|{b|1<b<n，W(b)满足}|≥(n–1)/2即，在小于n的自然数中有多半是n的见证者。任取一个自然数b<n，若b不是n的见证者，则n是合数的概率小于1/2。若随机取m个数都不是见证者，则n是合数的概率小于1/2m。第十三页，共三十八页，2022年，8月28日2023/3/2913计算机算法设计与分析Miller-Rabin素数判定概率算法BoolMiller_Rabin_Prime(intn){b[1..m]=RandomSampling(n,m);/*随机选取m个大于1小于n的无重复的自然数for(j=1;j<=m;j++)if(W(b[j])满足)returnFalse;returnTrue;}若m=100，则n不是素数的概率小于1/2100。第十四页，共三十八页，2022年，8月28日2023/3/2914计算机算法设计与分析LasVegas算法LasVegas算法的特点是随机性地进行决策。例如对n后问题，LasVegas算法是随机地产生一组王后放置的位置。若成功了，便找到了一个解；若失败了，就整个重来，再随机产生另外一组王后的位置。这样作，直至找到解。此算法能显著地改进算法的有效性，甚至对迄今为止找不到有效算法的问题，也能得到满意的结果。第十五页，共三十八页，2022年，8月28日2023/3/2915计算机算法设计与分析瞎子爬山法与局部最优更一般的求解问题的方法是瞎子爬山法。一个瞎子从山脚开始，试探着一步一步向上爬，就可以一直爬到山顶。可是，他爬上的可能只是个小山头，更高的山还在后面。而他无法从小山头下来，也就无法爬到更高的山头了。这种情形就被称为陷入了局部最优。如何避免陷入局部最优是求解问题中要注意的一个重要问题。第十六页，共三十八页，2022年，8月28日2023/3/2916计算机算法设计与分析进化算法(EvolutionaryAlgorithm)达尔文的进化论：适者生存，优胜劣汰。1975年霍兰(Holland)提出了遗传算法，通过模拟生物进化的过程概率搜索最优解。遗传算法首先产生所谓的个体种群，每个个体是编码的二进制串(又称为染色体)。然后对个体进行随机的选择，再经过复制、交叉和变异产生下一代的种群。就这样经过一代一代的进化，最终获得满意的个体(即问题的解)。第十七页，共三十八页，2022年，8月28日2023/3/2917计算机算法设计与分析进化计算中的基本算子适应值f(xi)：给出个体xi优劣；选择算子：对个体进行概率选择。个体的概率为p(xi)=f(xi)/∑f(xj)，优秀的个体具有较高的概率。最常用的选择算子为轮盘赌的方法。这样优秀个体具有较高的被选中的概率。同时差的个体也有被选中的可能。复制算子copy：对选中的个体进行复制。交叉算子：将两个个体染色体中的某个位彼此交换，从而形成两个新的个体。变异算子m：改变一个个体的染色体的某些位，得到一个新的个体。停止准则：决定算法停止的准则第十八页，共三十八页，2022年，8月28日2023/3/2918计算机算法设计与分析进化算法的基本框架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’’(t)));

选择：P(t+1)=P’’(t)∪Q;t=t+1;}第十九页，共三十八页，2022年，8月28日2023/3/2919计算机算法设计与分析进化计算的优缺点是一种通用的计算方法，一旦问题表示为种群后，算法便不在依赖于问题。求解不依赖于初始状况，通常具有较好的收敛性，也不容易陷于局部最优。依然有可能陷入局部最优(早熟收敛)。选择问题的表示方案和适应值度量的优劣、选择种群的规模大小、代数、控制执行各种算子的参数、停止准则等的好坏都可影响算法的功能和效果。第二十页，共三十八页，2022年，8月28日2023/3/2920计算机算法设计与分析模拟退火算法1982年Kirkpatrick将固体退火过程应用于组合优化问题的求解，提出一种有效的近似算法，称为模拟退火算法。模拟退火算法从初始解i=i0开始，在当前解i的邻域Si中按照Metropolis准则搜索新解j以取代当前解i。这个过程不断进行下去，直到达到目标函数最优。第二十一页，共三十八页，2022年，8月28日2023/3/2921计算机算法设计与分析固体退火过程退火是固体由高温下粒子排列的无序的液态冷却而凝固成粒子排列有序的固体晶态的过程。退火是系统的熵不断减小，能量趋于最小值的过程。它遵循热力学中的自由能减少定律：F=E–TS其中F、E和S分别表示自由能、能量和熵。系统从非平衡态自发变化到平衡态，都是能量和熵竞争的结果，温度决定二者孰重。第二十二页，共三十八页，2022年，8月28日2023/3/2922计算机算法设计与分析Metropolis接受准则设i是一个状态，j是由i可得到的一个新状态。它们的能量分别为Ei和Ej。若Ej＜Ei，则状态j可以取代状态i。否则固体处于状态i和状态j的几率为r=exp((Ei–Ej)/kT)其中k是Boltzmann常数，T为绝对温度，r＜1。设是(0,1)中的随机数，若r＞，则状态j可以取代状态i。第二十三页，共三十八页，2022年，8月28日2023/3/2923计算机算法设计与分析模拟退火算法的框架k=0;i=i0;t=t0;//初始化while(不满足停止准则){Gen(Si);//产生i的邻域Si，|Si|=Lkfor(j∈Si)//用Metropolis准则对Si中的

if(f(i)<f(j))i=j;//每个状态j检测是否可替代ielseif(exp((f(i)–f(j))/t)>random(0,1))i=j;k=k+1;t=tk;//降温；进入下一轮迭代

}第二十四页，共三十八页，2022年，8月28日2023/3/2924计算机算法设计与分析算法的性能算法可以渐进地收敛于整体最优解。Metropolis准则给算法引入了随机性，使算法进程方向呈现跳跃性，从而可能避开局部最优，但不能完全避开局部收敛。最终解不依赖于初始解。温度t和|Si|(即Lk)决定算法的收敛速度。算法的复杂性为O(kLP(n))，其中k为迭代次数，L=max{|Si|}，P(n)是问题规模n的多项式函数。求高质量的近似解的耗费也较高。第二十五页，共三十八页，2022年，8月28日2023/3/2925计算机算法设计与分析模拟退火算法的应用(1)确定解问题、能量函数和初始解：解空间是所有可行解的集合；能量函数是优化目标的数学描述；初始解是开始计算的起点。(2)新解的产生和接受准则：从当前解产生新解；用Metropolis准则判断新解是否可替代当前解；然后用新解/当前解进行下一轮实验。(3)冷却进度表及其它参数：Lk由新解来确定，冷却温度tk用冷却进度表或衰减函数给出。应用模拟退火算法的工作如下：第二十六页，共三十八页，2022年，8月28日2023/3/2926计算机算法设计与分析用模拟退火算法解TSP解空间为所有的排列，初始解为<1,2,…,n>。能量函数f为发、该排列的周游路线长度。即

nf(<di1di2…din>)=min{∑dikdik+1+dindi1}

k=1产生新解：用某种方法将旧排列变换成新排列。例如：在排列中任选u,v，交换u,v，并将u和v之间的顺序逆转。比如：取u=2，v=3：<1,2,3,4,5,6,7><1,5,4,3,2,6,7>或者：在排列中任选u,v，和w，将u和v之间的子串插在w之后。比如：选u,v,w分别为2,5,6:<1,2,3,4,5,6,7><1,5,2,6,3,4,7>第二十七页，共三十八页，2022年，8月28日2023/3/2927计算机算法设计与分析算法中参数的讨论冷却进度表：用参数t的一个递减序列{tk}和与之对应的Lk的序列来控制算法的进程。通常选tk的小衰减量以避免过大的Lk值。只要tk和Lk与停止准则选择恰当，算法不仅收敛而且提高收敛速度。t0值过小导致解质量差，过大增加求解时间。如何选择t0是个重要问题。当tk减小时Lk则增大。一般用个多项式P(n)来限制。一般选迭代次数6~50次为停止准则。第二十八页，共三十八页，2022年，8月28日2023/3/2928计算机算法设计与分析人工神经网络1943年McCulloch和Pitts提出神经元的数学模型，即MP模型。1957年Rosenblatt设计制作了“感知机”。这是第一个多层的人工神经网络。第一个高潮期。1969年之后进入低潮。1980年以后重新进入高潮，并得到蓬勃的发展。目前人们普遍认为突破图林机模型的将是人工神经网络。这是下一代计算机的主体。第二十九页，共三十八页，2022年，8月28日2023/3/2929计算机算法设计与分析神经元右图是一个神经元：神经元的构造为若干根输入的突轴和一根输出的树轴。神经元可以有抑制和激活这两种状态。当输入的信号达到一定的程度，神经元便被激活产生输出信号。第三十页，共三十八页，2022年，8月28日2023/3/2930计算机算法设计与分析神经元的数学模型(MP模型)右图是MP模型的示意图：y=f(∑iwixi–)其中：f称为激活函数，

为阈值，wi为权重。激活函数的形式通常有两种形式：第三十一页，共三十八页，2022年，8月28日2023/3/2931计算机算法设计与分析人工神经网络人工神经网络就是人工神经元所构成的网络。主要有前馈网络和反馈网络两种形式。前馈网络有若干层神经元组成，第i层的神经元只接受第i–1层输出的信息，而不接受同层或高层的输出信息。反馈网络中的神经元可以接受外加输入和其它神经元包括自身的反馈输入。第三十二页，共三十八页，2022年，8月28日2023/3/2932计算机算法设计与分析人工神经网络的学习神经元的计算主要依赖于权重wi，而权重wi是通过学习获得的。所谓学习(又称训练)是首先给权重赋予一个初值，然后将大量的训练样板(包括正例和反例)输入计算机，人工神经网络自己不断地调整相应的权重。学习的方式主要分为：有监督的学习和自适应的学习两种形式，以及它们的改进。第三十三页，共三十八页，2022年，8月28日2023/3/2933计算机算法设计与分析BP神经网络BP神经网络是一个三层前馈网络，分别为输入层LA，隐含层LB和输出层LC。每层分别有若干个神经元。如下图所示：第三