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