Chapter-8 随机算法.pptVIP

随机算法Random Algorithm 随机数发生器 随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。线性同余法是产生伪随机数的最常用的方法。由线性同余法产生的随机序列a0,a1,…,an满足 其中b=0，c=0，d=m。d称为该随机序列的种子。如何选取该方法中的常数b、c和m直接关系到所产生的随机序列的随机性能。这是随机性理论研究的内容，已超出本书讨论的范围。从直观上看，m应取得充分大，因此可取m为机器大数，另外应取gcd(m,b)=1，因此可取b为一素数。 圆周率计算 随机非重复采样问题 设有n 个样本，要求从中随机选出m 个样本(mn/2)。请设计一个随机算法来完成该任务，并分析该算法的时间复杂度。 思路： 将n个样本存放于数组Sample[1…n]中。数组Result[1…m]存放选中的m个样本。 定义一个长度为n的标志数组Flag[1…n]。Flag[i]=true表示对应位置的样本已经被选中；否则为未选中。 随机生成一个落在区间[1,n]的随机数r。若Flag[r]为false，Sample[r]追加到数组Result中,并将Flag[r]置为true；若Flag[r]为true,则重新生成随机数r，直到Flag[r]为false。重复此步骤，直到m个样本选择完成。 测试串的相等性 通信问题：发射端A发送信号x（x一般为很长的二进制串），接收端B收到信号y，要确定是否x = y。 生成指纹 模式匹配问题 问题描述：给一个字模式串X=x1x2…xn，模式串Y=y1y2…ym，其中mn，问：模式串Y是否在模式串X中出现？不失一般性，假设模式串定义在字符集{0,1}上。 最直观的方法：沿模式串X滑动Y，逐个比较子模式串X(j)=xj…xj+m-1和Y。时间复杂度：最坏情况下为O(mn)，例如： X=′000000000000000000000000000000000000000001′ Y=′000001′ 随机算法 思想：同样沿着模式串X滑动Y，但不是直接将模式串Y与每个子模式串X(j)=xj…xj+m-1进行比较；而是借鉴指纹匹配的思想，将Y的指纹与子模式串X(j)的指纹比较，从而判断Y是否与X(j)相同。 直接使用上述方法时间复杂性不能有效降低，因为指纹计算同样要耗费时间。 然而，分析可以发现：新串X(j+1)的指纹可以很方便地从X(j)的指纹计算出来，即： Ip(X(j+1))=(2Ip(X(j)) – 2mxj + xj+m) (mod p) 为何有上述结论？ 遗传算法Genetic Algorithm (GAs) 赌轮选择示例 S2 0.45 S1 0.11 S4 0.15 S3 0.29 　　上述按概率选择的方法可用一种称为赌轮的原理来实现。 即做一个单位圆, 然后按各个染色体的选择概率将圆面划分为相应的扇形区域(如图所示)。这样, 每次选择时先转动轮盘, 当轮盘静止时,上方的指针所正对着的扇区即为选中的扇区,从而相应的染色体即为所选定的染色体。 例如, 假设种群S中有4个染色体: s1,s2, s3, s4,其选择概率依次为: 0.11, 0.45, 0.29, 0.15, 则它们在轮盘上所占的份额如图中的各扇形区域所示。 　　在算法中赌轮选择法可用下面的子过程在计算机上进行模拟:  　　① 在［0, 1］区间内产生一个均匀分布的伪随机数r。 　　② 若r≤q1,则染色体x1被选中。 　　③ 若qk-1r≤qk(2≤k≤N), 则染色体xk被选中。  其中的qi称为染色体xi(i=1, 2, …, n)的积累概率, 其计算公式为 　　交叉 (crossover)亦称交换、交配或杂交,就是互换两个染色体某些位上的基因。例如,设染色体s1 s2 交换其后4位基因, 即 则得新串s1′s2′s1′和s2′可以看做是原染色体s1和s2的子代染色体。  　　变异 (mutation)亦称突变,就是改变染色体某个(些)位上的基因。例如,把染色体s第三位上的0变为1, 则得到新染色体s′ 0100 | 1011 1001 | 0101 0100 | 0101 1001 | 1011 基本遗传算法 　　简单来讲, 遗传算法就是对种群中的染色体反复做三种遗传操作, 使其朝着适应度增高的方向不断更新换代, 直至出现了适应度满足目标条件的染色体为止。 　　在算法的具体步骤中, 还需给出若干控制参数, 如种群规模、最大换代数、交叉率和变异