智能优化计算
简介
第十章 智能优化计算简介
本章对目前常用的几种智能优化计算
算法作简单介绍，以使读者对它们有个基本
认识。内容包括神经网络、遗传算法、模拟
退火算法和神经网络混合优化学习策略。
10.1 人工神经网络与神经网络优化算法
? 人工神经网络是近年来得到迅速发展的一
个前沿课题。神经网络由于其大规模并行
处理、容错性、自组织和自适应能力和联
想功能强等特点，已成为解决很多问题的
有力工具。本节首先对神经网络作简单介
绍，然后介绍几种常用的神经网络，包括
前向神经网络,Hopfield网络。
10.1 人工神经网络与神经网络优化算法
10.1.1 人工神经网络发展简史
? 最早的研究可以追溯到 20世纪 40年代 。 1943年,
心理学家 McCulloch和数学家 Pitts合作提出了形
式神经元的数学模型 。 这一模型一般被简称 M-P
神经网络模型, 至今仍在应用, 可以说, 人工神
经网络的研究时代, 就由此开始了 。
? 1949年，心理学家 Hebb提出神经系统的学习规
则，为神经网络的学习算法奠定了基础。现在，
这个规则被称为 Hebb规则，许多人工神经网络
的学习还遵循这一规则。
10.1 人工神经网络与神经网络优化算法
? 1 9 5 7 年, F.Rosenblatt 提出, 感知
器, (Perceptron)模型, 第一次把神经网络的
研究从纯理论的探讨付诸工程实践, 掀起了人工
神经网络研究的第一次高潮 。
? 20世纪 60年代以后，数字计算机的发展达到全
盛时期，人们误以为数字计算机可以解决人工智
能、专家系统、模式识别问题，而放松了对, 感
知器, 的研究。于是，从 20世纪 60年代末期起，
人工神经网络的研究进入了低潮。
10.1 人工神经网络与神经网络优化算法
? 1982年, 美国加州工学院物理学家 Hopfield提
出了离散的神经网络模型, 标志着神经网络的研
究又进入了一个新高潮 。 1984年, Hopfield又
提出连续神经网络模型, 开拓了计算机应用神经
网络的新途径 。
? 1986年,Rumelhart和 Meclelland提出多层网
络的误差反传 (back propagation)学习算法，
简称 BP算法。 BP算法是目前最为重要、应用最
广的人工神经网络算法之一。
10.1 人工神经网络与神经网络优化算法
? 自 20世纪 80年代中期以来，世界上许多国
家掀起了神经网络的研究热潮，可以说神
经网络已成为国际上的一个研究热点。
10.1 人工神经网络与神经网络优化算法
10.1.2 人工神经元模型与人工神经网络模
型
? 人工神经元是一个多输入, 单输出的非线
性元件, 如图 10-1所示 。
? 其输入, 输出关系可描述为
10.1 人工神经网络与神经网络优化算法
? (10-1-1)
? 式中,是从其它神经元传来的
输入信号； 是阈值； 表示从神经元
到神经元 的连接权值； 为传递函数。
??
?
?
?
?
?? ?
?
)(
1
jj
n
i
jiijj
Xfy
xX ??
),,2,1( nix i ??
j? ij? i
j )(?f
10.1 人工神经网络与神经网络优化算法
yj
θj
x0=1
∑ f
ω nj
x1
x2
,
,
,
xn
ω 2j
ω 1j
图 10-1
10.1 人工神经网络与神经网络优化算法
? 人工神经网络是由大量的神经元互连而成的网络，
按其拓扑结构来分，可以分成两大类：层次网络
模型和互连网络模型。层次网络模型是神经元分
成若干层顺序连接，在输入层上加上输入信息，
通过中间各层，加权后传递到输出层后输出，其
中有的在同一层中的各神经元相互之间有连接，
有的从输出层到输入层有反馈；互连网络模型中，
任意两个神经元之间都有相互连接的关系，在连
接中，有的神经元之间是双向的，有的是单向的，
按实际情况决定。
10.1 人工神经网络与神经网络优化算法
? 10.1.3 前向神经网络
(1)多层前向网络
一个 M层的多层前向网络可描述为,
? ① 网络包含一个输入层 （ 定义为第 0层 ） 和
M-1个隐层, 最后一个隐层称为输出层；
? ②第层包含 个神经元和一个阈值单元
（定义为每层的第 0单元），输出层不含阈
值单元；
lN
10.1 人工神经网络与神经网络优化算法
③ 第 层第 个单元到第个单元的权值表为；
④第 层（ >0）第 个（ >0）神经元的
输入定义为,输出定义
为,其中 为隐单元激励函数，
常采用 Sigmoid函数，即 。
输入单元一般采用线性激励函数,
阈值单元的输出始终为 1；
1?l i
llij,1??
l l j j
? ?
?
??? 1
0
1,1l
N
i
l
i
ll
ij
l
j yx ?
)( ljlj xfy ? )(?f
1)]ex p (1[)( ???? xxf
xxf ?)(
10.1 人工神经网络与神经网络优化算法
⑤ 目标函数通常采用,
（ 10-1-2）
其中 P为样本数,为第 p个样本的第 j个输
出分量。
? ??
? ?
?
?
?
???
P
p
N
j
pj
M
pj
P
p
p
M
tyEE
1 1
2
,
1
,
1
1
)(
2
1
pjt,
10.1 人工神经网络与神经网络优化算法
⑵ BP算法
BP算法是前向神经网络经典的有监督学习算
法，它的提出，对前向神经网络的发展起
过历史性的推动作用。对于上述的 M层的
人工神经网络,BP算法可由下列迭代式描
述，具体推导可参见神经网络的相关书目。
10.1 人工神经网络与神经网络优化算法
（ 10-1-3）
?
?
??
???
??
?????
P
p
l
pi
l
pj
ll
ij
ll
ij
ll
ij
ll
ij
kykk
kEkk
1
1
,,
,1
,1,1,1
)()()(
)(/)()1(
???
????
10.1 人工神经网络与神经网络优化算法
(10-1-4)
其中,为学习率。
?
?
?
?
?
??
???
?
?
?
?
??
1
1
11
,,
'
,
'
,,
,
1,,2),()()]([
1)],([])([
)( lN
m
l
jm
l
pm
l
pj
l
pjpj
l
pj
l
pj
Mlkkkxf
Mlkxftky
k
???
?
?
10.1 人工神经网络与神经网络优化算法
实质上,BP算法是一种梯度下降算法，算法
性能依赖于初始条件，学习过程易于陷入
局部极小。数值仿真结果表明,BP算法的
学习速度、精度、初值鲁棒性和网络推广
性能都较差，不能满足应用的需要。实用
中按照需要适当改进。
10.1 人工神经网络与神经网络优化算法
10.1.4 Hopfield 网络
1982年,Hopfield开创性地在物理学、神经生物
学和计算机科学等领域架起了桥梁，提出了
Hopfield 反馈神经网络模型 (HNN),证明在高
强度连接下的神经网络依靠集体协同作用能自发
产生计算行为。 Hopfield 网络是典型的全连接
网络，通过在网络中引入能量函数以构造动力学
系统，并使网络的平衡态与能量函数的极小解相
对应，从而将求解能量函数极小解的过程转化为
网络向平衡态的演化过程。
10.1 人工神经网络与神经网络优化算法
(1) 离散型 Hopfield 网络
离散型 Hopfield 网络的输出为二值型，网络
采用全连接结构。令 为各神经元
的输出,为各神经元与第 个神
经元的连接权值,为第 神经元的阈值，
则有
nvvv,,,21 ?
niii ??? ?,,21 i
i? i
10.1 人工神经网络与神经网络优化算法
（ 10-1-5）
??
?
?
?
??
?
???? ?
?
? 0,1
0,1
)()(
1 i
i
i
n
ij
j
ijjii
u
u
ufvfv ??
10.1 人工神经网络与神经网络优化算法
能量函数定义为
则其变化量为
? ??
? ?
?
?
???
n
i
n
i
ii
n
ij
j
jiij vvvE
1 112
1
??
10.1 人工神经网络与神经网络优化算法
（ 10-1-6）
也就是说，能量函数总是随神经元状态的变
化而下降的。
0)(
1 11
??????
?
?
?? ? ??
?
?
??
n
i
n
ij
j
jjjii
n
i
i
i
vvv
v
E
E ??
10.1 人工神经网络与神经网络优化算法
(2) 连续型 Hopfield 网络
连续型 Hopfield 网络的动态方程可简化描述
如下,
（ 10-1-7）
??
?
?
?
?
??? ?
?
)(
1
ii
n
i
i
i
i
jji
i
i
ugv
I
R
u
vT
dt
du
C
10.1 人工神经网络与神经网络优化算法
其中,分别为第 神经元的输入和输出,
具有连续且单调增性质的神经元激励函数，
为第 i神经元到 j第神经元的连接权,为施
加在第 i神经元的偏置,和 为相应的电
容和电阻,。
ii vu,i
)(?g
ijT
iI
0?iC iQ
?
?
??
n
j
jiii TQR
1
/1/1
10.1 人工神经网络与神经网络优化算法
定义能量函数
（ 10-1-8）
则其变化量
(10-1-9)
? ??? ?
?
?
?? ?
????
n
i
v
i
n
i
ii
n
i
n
j
jiij
i RdvvgvIvvTE
1 0
1
11 1
/)(21
?
? ?
?? n
i
i
i dt
dv
v
E
dt
dE
1
10.1 人工神经网络与神经网络优化算法
其中,
dt
dv
vgCvTT
dt
du
CvTT
I
R
u
vTvTT
I
R
u
vTvT
v
E
i
ii
n
j
jjiij
i
i
n
j
jjiij
i
i
i
n
j
jji
n
j
jjiij
i
i
i
n
j
n
j
jjijij
i
)()()(
2
1
)(
2
1
2
1
2
1
'1
11
11
1 1
?
??
??
? ?
????????
?
?
?
?
?
?
?
?
??????
?????
?
?
??
??
? ?
10.1 人工神经网络与神经网络优化算法
于是, 当 时,
(10-1-10)
jiij TT ?
0)(
2
1
'1 ??
?
?
?
?
?
?? ?
?
?
dt
dv
vgC
dt
dE in
i
ii
10.1 人工神经网络与神经网络优化算法
且当 时 。
因此, 随时间的增长, 神经网络在状态空间
中的轨迹总是向能量函数减小的方向变化,
且网络的稳定点就是能量函数的极小点 。
连续型 Hopfield 网络广泛用于联想记忆和优
化计算问题。
0?dtdv i 0?
dt
dE
10.2 遗传算法
遗传算法是模拟生物在自然环境中的遗传和
进化过程而形成的一种自适应全局优化概
率搜索算法。它最早由美国密执安大学的
Holland教授提出，起源于上世纪 60年代
对自然和人工自适应系统的研究。上世纪
70年代,De Jong基于遗传算法的思想在
计算机上进行了大量的纯数值函数优化计
算实验。
10.2 遗传算法
? 在一系列研究工作的基础上，上世纪 80年
代由 Goldberg进行归纳总结，形成了遗传
算法的基本框架。
10.2 遗传算法
10.2.1 遗传算法概要
对于一个求函数最大值的优化问题, 一般可
描述为下述数学规划模型,
(10-2-1)
?
?
?
?
?
?
?
?
?
UΡ
RX
X
..
)(m a x
ts
f
10.2 遗传算法
式中, 为决策变量, f(X)为目标
函数, U是基本空间, R是 U的一个子集 。
遗传算法中，将 n维决策向量用 n个记号
所组成的符号串 X来表示,
Tnxxx ],,,[ 21 ??X
),,2,1( nii ??X
T
nn xxx ],,,[ 2121 ?? ??? XXXXX
10.2 遗传算法
? 把每一个 看作一个遗传基因，它的所有
可能取值称为等位基因，这样,X就可看
作是由 n个遗传基因所组成的一个染色体。
染色体的长度可以是固定的，也可以是变
化的。等位基因可以是一组整数，也可以
是某一范围内的实数值，或者是记号。最
简单的等位基因是由 0和 1这两个整数组成
的，相应的染色体就可表示为一个二进制
符号串。
iX
10.2 遗传算法
? 这种编码所形成的排列形式 X是个体的基
因型，与它对应的 X值是个体的表现型。
染色体 X也称为个体 X,对于每一个个体 X，
要按照一定的规则确定出其适应度。个体
的适应度与其对应的个体表现型 X的目标
函数值相关联,X越接近于目标函数的最
优点，其适应度越大；反之，其适应度越
小。
10.2 遗传算法
? 遗传算法中，决策变量 X组成了问题的解
空间。对问题最优解的搜索是通过对染色
体 X的搜索过程来进行的，从而由所有的
染色体 X就组成了问题的搜索空间。
? 生物的进化是以集团为主体的。与此相对
应，遗传算法的运算对象是由 M个个体所
组成的集合，称为群体。
10.2 遗传算法
? 与生物一代一代的自然进化过程相似，遗
传算法的运算过也是一个反复迭代过程，
第 t代群体记做 P(t),经过一代遗传和进化后，
得到第 t+1代群体，它们也是由多个个体
组成的集合，记做 P(t+1)。 这个群体不断
地经过遗传和进化操作，并且每次都按照
优胜劣汰的规则将适应度较高的个的个体
更多地遗传到下一代，这样最终在群体中
将会得到一个优良的个体 X,它所对应的
表现型 X将达到或接近于问题的最优解 。 *X
10.2 遗传算法
? 生物的进化过程主要是通过染色体之间的
交叉和染色体的变异来完成的。遗传算法
中最优解的搜索过程也模仿生物的这个进
化过程，使用所谓的遗传算子 (genetic
operators)作用于群体 P(t)中，进行下述
遗传操作，从而得到新一代群体 P(t+1)。
10.2 遗传算法
? 选择 (selection):根据各个个体的适应度，
按照一定的规则或方法，从第 t代群体 P(t)
中选择出一些优良的个体遗传到下一代群
体 P(t+1)中。
? 交叉 (crossover):将群体 P(t)内的各个个
体随机搭配成对，对每一个个体，以某个
概率 (称为交叉概率,crossover rate)交
换它们之间的部分染色体。
10.2 遗传算法
? 变异 (mutation):对群体 P(t)中的每一个
个体，以某一概率 (称为变异概率，
mutation rate)改变某一个或一些基因座
上基因值为其它的等位基因。
10.2 遗传算法
10.2.2 遗传算法的特点
遗传算法是一类可用于复杂系统优化计算的鲁棒搜
索算法，与其他一些优化算法相比，主要有下述
几个特点,
? 遗传算法以决策变量的编码作为运算对象。传统
的优化算法往往直接利用决策变量的实际值本身
进行优化计算，但遗传算法不是直接以决策变量
的值，而是以决策变量的某种形式的编码为运算
对象，从而可以很方便地引入和应用遗传操作算
子。
10.2 遗传算法
? 遗传算法直接以目标函数值作为搜索信息。
传统的优化算法往往不只需要目标函数值，
还需要目标函数的导数等其它信息。这样
对许多目标函数无法求导或很难求导的函
数，遗传算法就比较方便。
10.2 遗传算法
? 遗传算法同时进行解空间的多点搜索。传
统的优化算法往往从解空间的一个初始点
开始搜索，这样容易陷入局部极值点。遗
传算法进行群体搜索，而且在搜索的过程
中引入遗传运算，使群体又可以不断进化。
这些是遗传算法所特有的一种隐含并行性。
10.2 遗传算法
? 遗传算法使用概率搜索技术 。遗传算法属
于一种自适应概率搜索技术，其选择、交
叉、变异等运算都是以一种概率的方式来
进行的，从而增加了其搜索过程的灵活性。
实践和理论都已证明了在一定条件下遗传
算法总是以概率 1收敛于问题的最优解。
10.2 遗传算法
? 10.2.3 遗传算法的发展
? 上世纪 60年代，美国密植安大学的
Holland教授及其学生们受到生物模拟技
术的启发，创造出了一种基于生物遗传和
进化机制的适合于复杂系统计算优化的自
适应概率优化技术 -----遗传算法。下面是
在遗传算法的发展进程中一些关键人物所
做出的一些主要贡献。
10.2 遗传算法
? J.H.Holland
20世纪 60年代,Holland认识到了生物的遗传和
自然进化现象与人工自适应系统的相似关系，运
用生物遗传和进化的思想来研究自然和人工自适
应系统的生成以及它们与环境的关系，提出在研
究和设计人工自适应系统时，可以借鉴生物遗传
的机制，以群体的方法进行自适应搜索，并且充
分认识到了交叉、变异等运算策略在自适应系统
中的重要性。
10.2 遗传算法
20世纪 70年代,Holland提出了遗传算法的
基本定理 ---模式定理 (Schema
Theorem),奠定了遗传算法的理论基础。
1975年,Holland出版了第一本系统论述
遗传算法和人工自适应系统的专著《自然
系统和人工系统的自适应性（ Adaptation
in Natural and Artificial Systems）》。
10.2 遗传算法
20世纪 80年代,Holland实现了第一个基于
遗传算法的机器学习系统 ----分类器系统，
开创了基于遗传算法学习的新概念，为分
类器系统构造出了一个完整的框架。
10.2 遗传算法
? J.D.Bagley
1967年,Holland的学生 Bagley在其博士论文中
首次提出了, 遗传算法, 一词，并发表了遗传算
法应用方面的第一篇论文。他发展了复制、交叉、
变异、显性、倒位等遗传算子，在个体编码上使
用了双倍体的编码方法。这些都与目前遗传算法
中所使用的算子和方法类似。他还敏锐地意识到
了在遗传算法执行的不同阶段可以使用不同的选
择率，这将有利于防止遗传算法的早熟现象，从
而创立了自适应遗传算法的概念。
10.2 遗传算法
? K.A.De Jong
1975年,De Jong在其博士论文中结合模
式定理进行了大量的纯数值函数优化计算
实验，树立了遗传算法的工作框架，得到
了一些重要且具有指导意义的结论。他推
荐了在大多数优化问题中都比较适用的遗
传算法参数，还建立了著名的 De Jong 五
函数测试平台，定义了评价遗传算法性能
的在线指标和离线指标。
10.2 遗传算法
? D.J.Goldberg
1989年,Goldberg出版了专著《搜索、优
化和机器学习中的遗传算法》。该书系统
总结了遗传算法的主要研究成果，全面而
完整地论述了遗传算法的基本原理及其应
用。
10.2 遗传算法
? L.Davis
1991年,Davis编辑出版了《遗传算法手
册》，书中包含了遗传算法在科学计算、
工程技术和社会经济中的大量应用实例，
该书为推广和普及遗传算法的应用起到了
重要的指导作用。
10.2 遗传算法
? J.R.Koza
1992年,Koza将遗传算法应用于计算机程
序的优化设计及自动生成，，提出了遗传
编程的概念。 Koza成功地将提出的遗传编
程方法应用于人工智能、机器学习、符号
处理等方面。
10.2 遗传算法
10.2.4 遗传算法的应用
遗传算法提供了一种求解复杂系统优化问题
的通用框架，它不依赖于问题的具体领域，
对问题的种类有很强的鲁棒性，所以广泛
应用于很多学科。下面列举一些遗传算法
的主要应用领域。
10.2 遗传算法
? 函数优化。函数优化是遗传算法的经典应
用领域，也是对遗传算法进行性能测试评
价的常用算例。对于一些非线性、多模型、
多目标的函数优化问题，用其他优化方法
较难求解，而遗传算法却可以方便地得到
较好的结果。
10.2 遗传算法
? 组合优化。遗传算法是寻求组合优化问题
满意解的最佳工具之一，实践证明，遗传
算法对于组合优化问题中的 NP完全问题非
常有效。
10.2 遗传算法
? 生产调度问题。生产调度问题在很多情况
下所建立起来的数学模型难以精确求解，
即使经过一些简化之后可以进行求解也会
因简化得太多而使求解结果与实际相差太
远。现在遗传算法已经成为解决复杂调度
问题的有效工具。
10.2 遗传算法
? 自动控制。遗传算法已经在自动控制领域
中得到了很好的应用，例如基于遗传算法
的模糊控制器的优化设计、基于遗传算法
的参数辨识、基于遗传算法的模糊控制规
则的学习、利用遗传算法进行人工神经网
络的结构优化设计和权值学习等。
10.2 遗传算法
? 机器人学。机器人是一类复杂的难以精确
建模的人工系统，而遗传算法的起源就来
自于对人工自适应系统的研究，所以机器
人学自然成为遗传算法的一个重要应用领
域。
10.2 遗传算法
? 图象处理。图像处理是计算机视觉中的一
个重要研究领域。在图像处理过程中，如
扫描、特征提取、图像分割等不可避免地
存在一些误差，这些误差会影响图像处理
的效果。如何使这些误差最小是使计算机
视觉达到实用化的重要要求，遗传算法在
这些图像处理中的优化计算方面得到了很
好的应用。
10.2 遗传算法
? 人工生命。人工生命是用计算机、机械等
人工媒体模拟或构造出的具有自然生物系
统特有行为的人造系统。。自组织能力和
自学习能力是人工生命的两大重要特征。
人工生命与遗传算法有着密切的关系，基
于遗传算法的进化模型是研究人工生命现
象的重要理论基础。
10.2 遗传算法
? 遗传编程。 Koza发展了遗传编程的概念，
他使用了以 LISP语言所表示的编码方法，
基于对一种树形结构所进行的遗传操作来
自动生成计算机程序。
? 机器学习。基于遗传算法的机器学习，在
很多领域中都得到了应用。例如基于遗传
算法的机器学习可用来调整人工神经网络
的连接权，也可以用于人工神经网络的网
络结构优化设计。
10.2 遗传算法
? 10.2.5 基本遗传算法
基本遗传算法（ Simple Genetic
Algorithms,简称 SGA） 是一种统一的最
基本的遗传算法，它只使用选择、交叉、
变异这三种基本遗传算子，其遗传进化操
作过程简单，容易理解，是其他一些遗传
算法的雏形和基础，它不仅给各种遗传算
法提供了一个基本框架，同时也具有一定
的应用价值。
10.2 遗传算法
? ⑴ 基本遗传算法的构成要素
? ① 染色体编码方法。基本遗传算法使用固
定长度的二进制符号串来表示群体中的个
体，其等位基因是由二值符号集 {0,1}所
组成的。初始群体中各个个体的基因值可
用均匀分布的随机数来生成。
10.2 遗传算法
? ② 个体适应度评价 。 基本遗传算法按与个
体适应度成正比的概率来决定当前群体中
每个个体遗传到下一代群体中的机会多少 。
为正确计算这个概率, 这里要求所有个体
的适应度必须为正数或零 。
? ③遗传算子。基本遗传算法使用下述三种
遗传算子：选择运算使用比例选择算子，
交叉运算使用单点交叉算子，变异运算使
用基本位变异算子或均匀变异算子。
10.2 遗传算法
? ④基本遗传算法的运行参数。基本遗传算
法有下述 4个运行参数需要提前设定：群体
大小 M,即群体中所含个体数目，一般取
为 20~100；遗传运算的终止进化代数 T，
一般取为 100~500； 交叉概率 Pc,
一般取为 0.4~0.99； 变异概率 Pm,一般取
为 0.0001~0.1。
10.2 遗传算法
? ⑤ 基本遗传算法的形式化定义
基本遗传算法可定义为一个 8元组,
(10-2-2)
),,,,,,,( 0 TMPECS G A ????
10.2 遗传算法
式中, C---个体的编码方法；
E---个体适应度评价函数；
P0---初始群体；
M---群体大小；
Φ---选择算子；
Γ---交叉算子；
T---遗传运算终止条件。
10.2 遗传算法
⑵ 基本遗传算法的实现
? ① 个体适应度评价
? 在遗传算法中，以个体适应度的大小来确定该个
体被遗传到下一代群体中的概率。个体适应度越
大，该个体被遗传到下一代的概率也越大；反之，
个体的适应度越小，该个体被遗传到下一代的概
率也越小。基本遗传算法使用比例选择算子来确
定群体中各个个体遗传到下一代群体中的数量。
为正确计算不同情况下各个个体的遗传概率，要
求所有个体的适应度必须为正数或领，不能是负
数。
10.2 遗传算法
? 为满足适应度取非负值的要求, 基本遗传算法一
般采用下面两种方法之一将目标函数值变换为个
体的适应度 。
? 方法一,对于目标函数是求极大化, 方法为,
(10-2-3) ??
?
?
?
??
???
?
0)(0
0)(,)(
)(
m i n
m i nm i n
CXf
CXfCXf
XF
当，
时当
10.2 遗传算法
式中,为一个适当地相对比较小的数，
它可用下面几种方法之一来选取,预先指定
的一个较小的数；进化到当前代为止的最
小目标函数值；当前代或最近几代群体中
的最小目标值。
maxC
10.2 遗传算法
② 比例选择算子
? 比例选择实际上是一种有退还随机选择,也叫做
赌盘 (Roulette Wheel)选择,因为这种选择方式
与赌博中的赌盘操作原理非常相似 。
? 比例选择算子的具体执行过程是：先计算出群体
中所有个体的适应度之和；其次计算出每个个体
的相对适应度的大小，此值即为各个个体被遗传
到下一代群体中的概率；最后再使用模拟赌盘操
作（即 0到 1之间的随机数）来确定各个个体被选
中的次数。
10.2 遗传算法
③ 单点交叉算子
? 单点交叉算子是最常用和最基本的交叉操
作算子。单点交叉算子的具体执行过程如
下：对群体中的个体进行两两随机配对；
对每一对相互配对的个体，随机设置某一
基因座之后的位置为交叉点；对每一对相
互配对的个体，依设定的交叉概率 在其
交叉点处相互交换两个个体的部分染色体，
从而产生出两个新个体。
cp
10.2 遗传算法
④ 基本位变异算子
? 基本位变异算子的具体执行过程为：对个
体的每一个基因座，依变异概率 指定
其为变异点；对每一个指定的变异点，对
其基因值做取反运算或用其他等位基因值
来代替，从而产生出一个新的个体。
mp
10.2 遗传算法
⑶ 遗传算法的应用步骤
遗传算法提供了一种求解复杂系统优化问题
的通用框架 。 对于具体问题, 可按下述步
骤来构造,
? ①确定决策变量及其各种约束条件，即确
定出个体的表现型 X和问题的解空间；
? ②建立优化模型，即描述出目标函数的类
型及其数学描述形式或量化方法；
10.2 遗传算法
? ③ 确定表示可行解的染色体编码方法, 即
确定出个体的基因型 X及遗传算法的搜索
空间；
? ④ 确定解码方法, 即确定出由个体基因型
X到个体表现型 X的对应关系或转换方法；
? ⑤确定个体适应度的量化评价方法，即确
定出由目标函数值 到个体适应度的转
换规则；
)(Xf
10.2 遗传算法
? ⑥ 设计遗传算子, 即确定出选择运算, 交
叉运算, 变异运算等遗传算子的具体操作
方法；
? ⑦确定遗传算法的有关运行参数，即确定
出遗传算法的 等
参数。 mc ppTM,、、
10.2 遗传算法
10.2.6 遗传算法的模式定理
? Holland提出的模式定理（ schema
theorem）,是遗传算法的基本原理，从进
化动力学的角度提供了能够较好地解释遗
传算法机理的一种数学工具，同时也是编
码策略、遗传策略等分析的基础。
10.2 遗传算法
? 模式定理,在选择、交叉、变异算子的作
用下，那些低阶、定义长度短、超过群体
平均适应值的模式的生存数量，将随着迭
代次数的增加以指数规律增长。
10.3 模拟退火算法
模拟退火算法 (simulated annealing,简称
SA)的思想最早是由 Metropolis等 (1953)
提出的,1983年 Kirkpatrick等将其用于
组合优化。 SA算法是基于 Monte Carlo迭
代求解策略的一种随机寻优算法，其出发
点是基于物理中固体物质的退火过程与一
般组合优化问题之间的相似性。
10.3 模拟退火算法
模拟退火算法在某一初温下，伴随温度参数
的不断下降，结合概率突跳特性在解空间
中随机寻找目标函数的全局最优解，即在
局部优解能概率性地跳出并最终趋于全局
最优解。模拟退火算法是一种通用的优化
算法，目前已在工程中得到了广泛应用。
10.3 模拟退火算法
10.3.1 物理退火过程和 Metropolis准则
简单而言, 物理退火过程由以下三部分组成,
⑴加温过程。其目的是增强粒子的热运动，使其偏
离平衡位置。当温度足够高时，固体将溶解为液
体，从而消除系统原先可能存在的非均匀态，使
随后进行的冷却过程以某一平衡态为起点。溶解
过程与系统的熵增过程联系，系统能量也随温度
的升高而增大。
10.3 模拟退火算法
⑵ 等温过程 。 物理学的知识告诉我们, 对于
与周围环境交换热量而温度不变的封闭系
统, 系统状态的自发变化总是朝自由能减
少的方向进行, 当自由能达到最小时, 系
统达到平衡态 。
⑶冷却过程。目的是使粒子的热运动减弱并
渐趋有序，系统能量逐渐下降，从而得到
低能的晶体结构。
10.3 模拟退火算法
Metropolis等在 1953年提出了重要性采样
法，即以概率接受新状态。具体而言，在
温度 t,由当前状态 i产生新状态 j,两者的能
量分别为,若 则接受新状
态 j为当前状态；否则，若概率
大于 区间内的随机数则仍旧接受新状
态 j为当前状态，若不成立则保留 i为当前状
态，其中 k为 Boltzmann常数。
ji EE 和 ij EE ?
]/)(e x p [ ktEEp ijr ???
)1,0[
10.3 模拟退火算法
这种重要性采样过程在高温下可接受与当前
状态能量差较大的新状态，而在低温下基
本只接受与当前能量差较小的新状态，而
且当温度趋于零时，就不能接受比当前状
态能量高的新状态。这种接受准则通常称
为 Metropolis准则。
10.3 模拟退火算法
10.3.2 模拟退火算法的基本思想和步骤
1983年 Kirkpatrick等意识到组合优化与物理退火
的相似性，并受到 Metropolis准则的启迪，提出
了模拟退火算法。模拟退火算法是基于 Monte
Carlo 迭代求解策略的一种随机寻优算法，其出
发点是基于物理退火过程与组合优化之间的相似
性,SA由某一较高初温开始，利用具有概率突
跳特性的 Metropolis抽样策略在解空间中进行随
机搜索，伴随温度的不断下降重复抽样过程，最
终得到问题的全局最优解。
10.3 模拟退火算法
标准模拟退火算法的一般步骤可描述如下,
⑴ 给定初温, 随机产生初始状态,
令 ；
⑵ Repeat,
① Repeat
产生新状态 ；
0tt ? 0ss ?
0?k
)( sG e n e t es j ?
jj ssr a n d o msCsCif ???? ]1,0[) ) ] }()((e x p [,1m i n {
10.3 模拟退火算法
Until 抽样稳定准则满足；
②退温,并
令 ；
Until 算法终止准则满足；
⑶输出算法搜索结果。
)(1 kk tu p d a t et ??
1?? kk
10.3 模拟退火算法
10.3.3 模拟退火算法关键参数和操作的设
定
从算法流程上看，模拟退火算法包括三函数
两准则，即状态产生函数、状态接受函数、
温度更新函数、内循环终止准则和外循环
终止准则，这些环节的设计将决定 SA算法
的优化性能。此外，初温的选择对 SA算法
性能也有很大影响。
10.3 模拟退火算法
⑴ 状态产生函数
设计状态产生函数（邻域函数）的出发点应
该是尽可能保证产生的候选解遍布全部的
解空间。通常，状态产生函数由两部分组
成，即产生候选解的方式和候选解产生的
概率分布。
10.3 模拟退火算法
⑵ 状态接受函数
状态接受函数一般以概率的方式给出, 不同
接受函数的差别主要在于接受概率的形式
不同 。 设计状态接受概率, 应该遵循以下
原则,
①在固定温度下，接受使目标函数值下降的
候选解的概率要大于使目标值上升的候选
解的概率；
10.3 模拟退火算法
② 随温度的下降, 接受使目标函数值上升的
解的概率要逐渐减小；
③ 当温度趋于零时, 只能接受目标函数值下
降的解 。
状态接受函数的引入是 SA算法实现全局搜索
的最关键的因素,SA算法中通常采用
min[1,exp(-△ C/t)]作为状态接受函数。
10.3 模拟退火算法
⑶ 初温
初始温度、温度更新函数、内循环终止准则
和外循环终止准则通常被称为退火历程
(annealing schedule)。 实验表明，初温
越大，获得高质量解的几率越大，但花费
的计算时间将增加。因此，初温的确定应
折衷考虑优化质量和优化效率，常用方法
包括,
10.3 模拟退火算法
① 均匀抽样一组状态, 以各状态目标值的方
差为初温 。
② 随机产生一组状态, 确定两两状态间的最
大目标值差, 然后依据差值, 利用一
定的函数确定初温 。 譬如, 其中
为初始接受概率
③利用经验公式给出。
|| max?
rpt ln/0 ???
rp
10.3 模拟退火算法
⑷ 温度更新函数
温度更新函数, 即温度的下降方式, 用于在
外循环中修改温度值 。
目前，最常用的温度更新函数为指数退温函
数，即，其中且其大小可以不断变化。
10.3 模拟退火算法
⑸ 内循环终止准则
内循环终止准则，或称 Metropolis抽样稳定
准则，用于决定在各温度下产生候选解的
数目。在非时齐 SA算法理论中，由于在每
个温度下只产生一个或少量候选解，所以
不存在选择内循环终止准则的问题。
10.3 模拟退火算法
而在时齐 SA算法理论中, 收敛条件要求在每
个温度下产生候选解的数目趋于无穷大,
以使相应的马氏链达到平稳概率分布, 显
然在实际应用算法时这是无法实现的 。 常
用的抽样准则包括,
① 检验目标函数的均值是否稳定；
② 连续若干步的目标值变化较小；
③按一定的步数抽样。
10.3 模拟退火算法
⑹ 外循环终止准则
外循环终止准则，即算法终止准则，用于决
定算法何时结束。设置温度终值是一种简
单的方法。 SA算法的收敛性理论中要求温
度终值趋于零，这显然不合实际。通常的
做法是,
10.3 模拟退火算法
① 设置终止温度的阈值；
② 设置外循环迭代次数；
③ 算法收敛到的最优值连续若干步保持不变；
④检验系统熵是否稳定。
10.4 神经网络权值的混合优化学习策略
鉴于 GA,SA的全局优化特性和通用性，即
优化过程无需导数信息，我们可以基于实
数编码构造 BPSA,BPGA混合优化学习策
略，以提高前向网络学习的速度、精度，
特别是避免陷入局部极小的能力。
10.4 神经网络权值的混合优化学习策略
10.4.1 BPSA混合学习策略
在 BPSA混合学习策略中, 采用以 BP为主框
架, 并在学习过程中引入 SA策略 。 这样做,
既利用了基于梯度下降的有指导学习来提
高局部搜索性能, 也利用了 SA的概率突跳
性来实现最终的全局收敛, 从而可提高学
习速度和精度 。
BP-SA混合学习策略的算法步骤如下,
10.4 神经网络权值的混合优化学习策略
⑴ 随机产生初始权值, 确定初温, 令
⑵ 利用 BP计算 。
利用 SA进行搜索,
① 利用 SA状态产生函数产生新权值,
,其中 为随机扰动。
)0(? 1t 1?k
)(k?
)(' k?
??? ?? )()(' kk )1,1(???
10.4 神经网络权值的混合优化学习策略
② 计算 的目标函数值与 的目标函
数值之差 。
③ 计算接受概率 。
④ 若,则取 ；
否则 保持不变。
)(' k? )(k?
C?
)]/ex p (,1m i n [ kr tCP ???
)1,0[r a n d o mP r ? )()( ' kk ?? ?
)(k?
10.4 神经网络权值的混合优化学习策略
(4) 利用退温函数 进行退温, 其中 为退
温速率 。
若 对应的目标函数满足要求精度,则终
止算法并输出结果；否则，令,转
步骤⑵。
kk vtt ??1 )1,0(?v
)(k? ?
1?? kk
10.4 神经网络权值的混合优化学习策略
10.4.2 BPGA混合学习策略
神经网络的连接权包含着神经网络系统的全部知
识。反向传播的 BP神经网络 (back
propagation network)的学习算法是基于梯
度下降的，因而具有以下缺点：网络训练速度
慢、容易陷入局部极小值、全局搜索能力差等。
而遗传算法的搜索遍及整个解空间，因此容易
得到全局最优解，而且遗传算法不要求目标函
数连续、可微，甚至不要求目标函数有显函数
的形式，只要求问题可计算。
10.4 神经网络权值的混合优化学习策略
因此，将擅长全局搜索的遗传算法和局部寻
优能力较强的 BP算法结合起来，可以避免
陷入局部极小值，提高算法收敛速度，很
快找到问题的全局最优解。
BP算法和遗传算法结合训练神经网络权重的
主要步骤为,
10.4 神经网络权值的混合优化学习策略
(1) 以神经网络节点之间的连接权重和节点
的阈值为参数, 采用实数编码 。 采用三层
神经网络, 设输入节点数为 p,输出节点数
为 q,隐层节点数为 r,则编码长度 n为,
（ 10-4-1） qrrpn ?????? )1()1(
10.4 神经网络权值的混合优化学习策略
(2)设定神经网络节点连接权重的取值范
围,产生相应范围的均匀分布
随机数赋给基因值, 产生初始群体；
(3)对群体中个体进行评价 。 将个体解码赋
值给相应的连接权 (包括节点阈值 ),引入
学习样本计算出学习误差 E,个体的适应度
定义为,
, （ 10-4-2）
Ef ?? 1
1
],[ m a xm i n xx
10.4 神经网络权值的混合优化学习策略
(4)对群体中的个体执行遗传操作,
① 选择操作 。 采用比例选择算子, 若群体规
模为 M,则适应度为的个体被选中进入下
一代的概率为,
,
（ 10-4-3）
?
?
?
M
i
i
i
i
f
f
p
1
10.4 神经网络权值的混合优化学习策略
② 交叉操作 。 由于采用实数编码, 故选择算
术交叉算子 。 父代中的个体 和 以交叉概
率 进行交叉操作, 可产生的子代个体为,
（ 10-4-4）
和
（ 10-4-5）
其中 a为参数 。
1X 2X
cp
21'1 )1( XaaXX ???
21'2 )1( aXXaX ???
)1,0(?a
10.4 神经网络权值的混合优化学习策略
③ 变异操作 。 采用均匀变异算子 。 个
体 的各个基因位以变异概率 发生变异,
即按概率用 区间中的均匀分布随机
数代替原有值 。
⑸ 引入最优保留策略。
iX m
p
],[ m a xm i n xx
10.4 神经网络权值的混合优化学习策略
⑹ 判断满足遗传算法操作终止条件否？ 不满
足则转步骤 ⑶ 。 否则转步骤 ⑺ 。
⑺ 将遗传算法搜索的最优个体解码，赋值给
神经网络权重 (包括节点阈值 )，继续采用
BP算法优化神经网络的权重和阈值。
10.4 神经网络权值的混合优化学习策略
10.4.3 GASA混合学习策略
采用三层前馈网络, GA和 SA结合训练神经
网络权重的步骤如下,
⑴ 给定模拟退火初温, 令 ；
⑵ 以神经网络节点之间的连接权重和节点的
阈值为参数，采用实数编码。采用三层神
经网络，设输入节点数为 p,输出节点数为
q,隐层节点数为 r,则编码长度 n为,
0t 1?k
10.4 神经网络权值的混合优化学习策略
（ 10-4-6）
⑶ 设定神经网络节点连接权重的取值范
围, 产生相应范围的均匀分布随机数赋
给基因值, 产生初始群体；
⑷ 对群体中个体进行评价 。 将个体解码赋值给
相应的连接权 (包括节点阈值 ),引入学习样本
计算出学习误差 E,个体的适应度定义为,
, （ 10-4-7）
qrrpn ?????? )1()1(
],[ m a xm in xx
Ef ?? 1
1
10.4 神经网络权值的混合优化学习策略
⑸ 对群体中的个体执行遗传操作,
① 选择操作 。 采用比例选择算子, 若群体规模
为 M,则适应度为 的个体 被选中进入下
一代的概率为,
, （ 10-4-8）
if
iX
?
?
?
M
i
i
i
i
f
f
p
1
10.4 神经网络权值的混合优化学习策略
② 交叉操作 。 由于采用实数编码, 故选择
算术交叉算子 。 父代中的个体 和 以交
叉概率 进行交叉操作, 可产生的子代个
体为,
（ 10-4-9）
和
（ 10-4-10）
其中 a为参数 。
1X 2
X
cp
21'1 )1( XaaXX ???
21'2 )1( aXXaX ???
)1,0(?a
10.4 神经网络权值的混合优化学习策略
③ 变异操作 。 采用均匀变异算子 。 个
体 的各个基因位以变异概率 发生变异,
即按概率 用区间 中的均匀分布
随机数代替原有值 。
⑹ 引入最优保留策略。
⑺ 对群体中每一个个体引入模拟退火操作,
iX
mp
mp ],[ m a xm in xx
10.4 神经网络权值的混合优化学习策略
① 利用 SA 状态产生函数产生新基因
值,, 其中 为随
机扰动 。
② 计算 的目标函数值与 的目标函数
值之差 。
③ 计算接受概率 。
)(' kg ??? )()(' kgkg )1,1(???
)(' kg )(kg
C?
)]/ex p (,1m i n [ kr tCP ???
10.4 神经网络权值的混合优化学习策略
④ 若, 则取 ；否
则 保持不变 。
⑤ 引入最优保留策略 。
⑥ 利用退温函数 进行退温，其
中 为退温速率。
)1,0[r a n d o mP r ? )()( ' kgkg ?
)(kg
kk vtt ?? 1
)1,0(?v
10.4 神经网络权值的混合优化学习策略
⑻ 判断满足遗传算法操作终止条件否？ 不满
足则转步骤 ⑷ 。 否则转步骤 ⑼ 。
⑼ 将遗传算法搜索的最优个体解码，赋值给神
经网络权重 (包括节点阈值 )。
10.5 应用举例
? 略,
简介
第十章 智能优化计算简介
本章对目前常用的几种智能优化计算
算法作简单介绍，以使读者对它们有个基本
认识。内容包括神经网络、遗传算法、模拟
退火算法和神经网络混合优化学习策略。
10.1 人工神经网络与神经网络优化算法
? 人工神经网络是近年来得到迅速发展的一
个前沿课题。神经网络由于其大规模并行
处理、容错性、自组织和自适应能力和联
想功能强等特点，已成为解决很多问题的
有力工具。本节首先对神经网络作简单介
绍，然后介绍几种常用的神经网络，包括
前向神经网络,Hopfield网络。
10.1 人工神经网络与神经网络优化算法
10.1.1 人工神经网络发展简史
? 最早的研究可以追溯到 20世纪 40年代 。 1943年,
心理学家 McCulloch和数学家 Pitts合作提出了形
式神经元的数学模型 。 这一模型一般被简称 M-P
神经网络模型, 至今仍在应用, 可以说, 人工神
经网络的研究时代, 就由此开始了 。
? 1949年，心理学家 Hebb提出神经系统的学习规
则，为神经网络的学习算法奠定了基础。现在，
这个规则被称为 Hebb规则，许多人工神经网络
的学习还遵循这一规则。
10.1 人工神经网络与神经网络优化算法
? 1 9 5 7 年, F.Rosenblatt 提出, 感知
器, (Perceptron)模型, 第一次把神经网络的
研究从纯理论的探讨付诸工程实践, 掀起了人工
神经网络研究的第一次高潮 。
? 20世纪 60年代以后，数字计算机的发展达到全
盛时期，人们误以为数字计算机可以解决人工智
能、专家系统、模式识别问题，而放松了对, 感
知器, 的研究。于是，从 20世纪 60年代末期起，
人工神经网络的研究进入了低潮。
10.1 人工神经网络与神经网络优化算法
? 1982年, 美国加州工学院物理学家 Hopfield提
出了离散的神经网络模型, 标志着神经网络的研
究又进入了一个新高潮 。 1984年, Hopfield又
提出连续神经网络模型, 开拓了计算机应用神经
网络的新途径 。
? 1986年,Rumelhart和 Meclelland提出多层网
络的误差反传 (back propagation)学习算法，
简称 BP算法。 BP算法是目前最为重要、应用最
广的人工神经网络算法之一。
10.1 人工神经网络与神经网络优化算法
? 自 20世纪 80年代中期以来，世界上许多国
家掀起了神经网络的研究热潮，可以说神
经网络已成为国际上的一个研究热点。
10.1 人工神经网络与神经网络优化算法
10.1.2 人工神经元模型与人工神经网络模
型
? 人工神经元是一个多输入, 单输出的非线
性元件, 如图 10-1所示 。
? 其输入, 输出关系可描述为
10.1 人工神经网络与神经网络优化算法
? (10-1-1)
? 式中,是从其它神经元传来的
输入信号； 是阈值； 表示从神经元
到神经元 的连接权值； 为传递函数。
??
?
?
?
?
?? ?
?
)(
1
jj
n
i
jiijj
Xfy
xX ??
),,2,1( nix i ??
j? ij? i
j )(?f
10.1 人工神经网络与神经网络优化算法
yj
θj
x0=1
∑ f
ω nj
x1
x2
,
,
,
xn
ω 2j
ω 1j
图 10-1
10.1 人工神经网络与神经网络优化算法
? 人工神经网络是由大量的神经元互连而成的网络，
按其拓扑结构来分，可以分成两大类：层次网络
模型和互连网络模型。层次网络模型是神经元分
成若干层顺序连接，在输入层上加上输入信息，
通过中间各层，加权后传递到输出层后输出，其
中有的在同一层中的各神经元相互之间有连接，
有的从输出层到输入层有反馈；互连网络模型中，
任意两个神经元之间都有相互连接的关系，在连
接中，有的神经元之间是双向的，有的是单向的，
按实际情况决定。
10.1 人工神经网络与神经网络优化算法
? 10.1.3 前向神经网络
(1)多层前向网络
一个 M层的多层前向网络可描述为,
? ① 网络包含一个输入层 （ 定义为第 0层 ） 和
M-1个隐层, 最后一个隐层称为输出层；
? ②第层包含 个神经元和一个阈值单元
（定义为每层的第 0单元），输出层不含阈
值单元；
lN
10.1 人工神经网络与神经网络优化算法
③ 第 层第 个单元到第个单元的权值表为；
④第 层（ >0）第 个（ >0）神经元的
输入定义为,输出定义
为,其中 为隐单元激励函数，
常采用 Sigmoid函数，即 。
输入单元一般采用线性激励函数,
阈值单元的输出始终为 1；
1?l i
llij,1??
l l j j
? ?
?
??? 1
0
1,1l
N
i
l
i
ll
ij
l
j yx ?
)( ljlj xfy ? )(?f
1)]ex p (1[)( ???? xxf
xxf ?)(
10.1 人工神经网络与神经网络优化算法
⑤ 目标函数通常采用,
（ 10-1-2）
其中 P为样本数,为第 p个样本的第 j个输
出分量。
? ??
? ?
?
?
?
???
P
p
N
j
pj
M
pj
P
p
p
M
tyEE
1 1
2
,
1
,
1
1
)(
2
1
pjt,
10.1 人工神经网络与神经网络优化算法
⑵ BP算法
BP算法是前向神经网络经典的有监督学习算
法，它的提出，对前向神经网络的发展起
过历史性的推动作用。对于上述的 M层的
人工神经网络,BP算法可由下列迭代式描
述，具体推导可参见神经网络的相关书目。
10.1 人工神经网络与神经网络优化算法
（ 10-1-3）
?
?
??
???
??
?????
P
p
l
pi
l
pj
ll
ij
ll
ij
ll
ij
ll
ij
kykk
kEkk
1
1
,,
,1
,1,1,1
)()()(
)(/)()1(
???
????
10.1 人工神经网络与神经网络优化算法
(10-1-4)
其中,为学习率。
?
?
?
?
?
??
???
?
?
?
?
??
1
1
11
,,
'
,
'
,,
,
1,,2),()()]([
1)],([])([
)( lN
m
l
jm
l
pm
l
pj
l
pjpj
l
pj
l
pj
Mlkkkxf
Mlkxftky
k
???
?
?
10.1 人工神经网络与神经网络优化算法
实质上,BP算法是一种梯度下降算法，算法
性能依赖于初始条件，学习过程易于陷入
局部极小。数值仿真结果表明,BP算法的
学习速度、精度、初值鲁棒性和网络推广
性能都较差，不能满足应用的需要。实用
中按照需要适当改进。
10.1 人工神经网络与神经网络优化算法
10.1.4 Hopfield 网络
1982年,Hopfield开创性地在物理学、神经生物
学和计算机科学等领域架起了桥梁，提出了
Hopfield 反馈神经网络模型 (HNN),证明在高
强度连接下的神经网络依靠集体协同作用能自发
产生计算行为。 Hopfield 网络是典型的全连接
网络，通过在网络中引入能量函数以构造动力学
系统，并使网络的平衡态与能量函数的极小解相
对应，从而将求解能量函数极小解的过程转化为
网络向平衡态的演化过程。
10.1 人工神经网络与神经网络优化算法
(1) 离散型 Hopfield 网络
离散型 Hopfield 网络的输出为二值型，网络
采用全连接结构。令 为各神经元
的输出,为各神经元与第 个神
经元的连接权值,为第 神经元的阈值，
则有
nvvv,,,21 ?
niii ??? ?,,21 i
i? i
10.1 人工神经网络与神经网络优化算法
（ 10-1-5）
??
?
?
?
??
?
???? ?
?
? 0,1
0,1
)()(
1 i
i
i
n
ij
j
ijjii
u
u
ufvfv ??
10.1 人工神经网络与神经网络优化算法
能量函数定义为
则其变化量为
? ??
? ?
?
?
???
n
i
n
i
ii
n
ij
j
jiij vvvE
1 112
1
??
10.1 人工神经网络与神经网络优化算法
（ 10-1-6）
也就是说，能量函数总是随神经元状态的变
化而下降的。
0)(
1 11
??????
?
?
?? ? ??
?
?
??
n
i
n
ij
j
jjjii
n
i
i
i
vvv
v
E
E ??
10.1 人工神经网络与神经网络优化算法
(2) 连续型 Hopfield 网络
连续型 Hopfield 网络的动态方程可简化描述
如下,
（ 10-1-7）
??
?
?
?
?
??? ?
?
)(
1
ii
n
i
i
i
i
jji
i
i
ugv
I
R
u
vT
dt
du
C
10.1 人工神经网络与神经网络优化算法
其中,分别为第 神经元的输入和输出,
具有连续且单调增性质的神经元激励函数，
为第 i神经元到 j第神经元的连接权,为施
加在第 i神经元的偏置,和 为相应的电
容和电阻,。
ii vu,i
)(?g
ijT
iI
0?iC iQ
?
?
??
n
j
jiii TQR
1
/1/1
10.1 人工神经网络与神经网络优化算法
定义能量函数
（ 10-1-8）
则其变化量
(10-1-9)
? ??? ?
?
?
?? ?
????
n
i
v
i
n
i
ii
n
i
n
j
jiij
i RdvvgvIvvTE
1 0
1
11 1
/)(21
?
? ?
?? n
i
i
i dt
dv
v
E
dt
dE
1
10.1 人工神经网络与神经网络优化算法
其中,
dt
dv
vgCvTT
dt
du
CvTT
I
R
u
vTvTT
I
R
u
vTvT
v
E
i
ii
n
j
jjiij
i
i
n
j
jjiij
i
i
i
n
j
jji
n
j
jjiij
i
i
i
n
j
n
j
jjijij
i
)()()(
2
1
)(
2
1
2
1
2
1
'1
11
11
1 1
?
??
??
? ?
????????
?
?
?
?
?
?
?
?
??????
?????
?
?
??
??
? ?
10.1 人工神经网络与神经网络优化算法
于是, 当 时,
(10-1-10)
jiij TT ?
0)(
2
1
'1 ??
?
?
?
?
?
?? ?
?
?
dt
dv
vgC
dt
dE in
i
ii
10.1 人工神经网络与神经网络优化算法
且当 时 。
因此, 随时间的增长, 神经网络在状态空间
中的轨迹总是向能量函数减小的方向变化,
且网络的稳定点就是能量函数的极小点 。
连续型 Hopfield 网络广泛用于联想记忆和优
化计算问题。
0?dtdv i 0?
dt
dE
10.2 遗传算法
遗传算法是模拟生物在自然环境中的遗传和
进化过程而形成的一种自适应全局优化概
率搜索算法。它最早由美国密执安大学的
Holland教授提出，起源于上世纪 60年代
对自然和人工自适应系统的研究。上世纪
70年代,De Jong基于遗传算法的思想在
计算机上进行了大量的纯数值函数优化计
算实验。
10.2 遗传算法
? 在一系列研究工作的基础上，上世纪 80年
代由 Goldberg进行归纳总结，形成了遗传
算法的基本框架。
10.2 遗传算法
10.2.1 遗传算法概要
对于一个求函数最大值的优化问题, 一般可
描述为下述数学规划模型,
(10-2-1)
?
?
?
?
?
?
?
?
?
UΡ
RX
X
..
)(m a x
ts
f
10.2 遗传算法
式中, 为决策变量, f(X)为目标
函数, U是基本空间, R是 U的一个子集 。
遗传算法中，将 n维决策向量用 n个记号
所组成的符号串 X来表示,
Tnxxx ],,,[ 21 ??X
),,2,1( nii ??X
T
nn xxx ],,,[ 2121 ?? ??? XXXXX
10.2 遗传算法
? 把每一个 看作一个遗传基因，它的所有
可能取值称为等位基因，这样,X就可看
作是由 n个遗传基因所组成的一个染色体。
染色体的长度可以是固定的，也可以是变
化的。等位基因可以是一组整数，也可以
是某一范围内的实数值，或者是记号。最
简单的等位基因是由 0和 1这两个整数组成
的，相应的染色体就可表示为一个二进制
符号串。
iX
10.2 遗传算法
? 这种编码所形成的排列形式 X是个体的基
因型，与它对应的 X值是个体的表现型。
染色体 X也称为个体 X,对于每一个个体 X，
要按照一定的规则确定出其适应度。个体
的适应度与其对应的个体表现型 X的目标
函数值相关联,X越接近于目标函数的最
优点，其适应度越大；反之，其适应度越
小。
10.2 遗传算法
? 遗传算法中，决策变量 X组成了问题的解
空间。对问题最优解的搜索是通过对染色
体 X的搜索过程来进行的，从而由所有的
染色体 X就组成了问题的搜索空间。
? 生物的进化是以集团为主体的。与此相对
应，遗传算法的运算对象是由 M个个体所
组成的集合，称为群体。
10.2 遗传算法
? 与生物一代一代的自然进化过程相似，遗
传算法的运算过也是一个反复迭代过程，
第 t代群体记做 P(t),经过一代遗传和进化后，
得到第 t+1代群体，它们也是由多个个体
组成的集合，记做 P(t+1)。 这个群体不断
地经过遗传和进化操作，并且每次都按照
优胜劣汰的规则将适应度较高的个的个体
更多地遗传到下一代，这样最终在群体中
将会得到一个优良的个体 X,它所对应的
表现型 X将达到或接近于问题的最优解 。 *X
10.2 遗传算法
? 生物的进化过程主要是通过染色体之间的
交叉和染色体的变异来完成的。遗传算法
中最优解的搜索过程也模仿生物的这个进
化过程，使用所谓的遗传算子 (genetic
operators)作用于群体 P(t)中，进行下述
遗传操作，从而得到新一代群体 P(t+1)。
10.2 遗传算法
? 选择 (selection):根据各个个体的适应度，
按照一定的规则或方法，从第 t代群体 P(t)
中选择出一些优良的个体遗传到下一代群
体 P(t+1)中。
? 交叉 (crossover):将群体 P(t)内的各个个
体随机搭配成对，对每一个个体，以某个
概率 (称为交叉概率,crossover rate)交
换它们之间的部分染色体。
10.2 遗传算法
? 变异 (mutation):对群体 P(t)中的每一个
个体，以某一概率 (称为变异概率，
mutation rate)改变某一个或一些基因座
上基因值为其它的等位基因。
10.2 遗传算法
10.2.2 遗传算法的特点
遗传算法是一类可用于复杂系统优化计算的鲁棒搜
索算法，与其他一些优化算法相比，主要有下述
几个特点,
? 遗传算法以决策变量的编码作为运算对象。传统
的优化算法往往直接利用决策变量的实际值本身
进行优化计算，但遗传算法不是直接以决策变量
的值，而是以决策变量的某种形式的编码为运算
对象，从而可以很方便地引入和应用遗传操作算
子。
10.2 遗传算法
? 遗传算法直接以目标函数值作为搜索信息。
传统的优化算法往往不只需要目标函数值，
还需要目标函数的导数等其它信息。这样
对许多目标函数无法求导或很难求导的函
数，遗传算法就比较方便。
10.2 遗传算法
? 遗传算法同时进行解空间的多点搜索。传
统的优化算法往往从解空间的一个初始点
开始搜索，这样容易陷入局部极值点。遗
传算法进行群体搜索，而且在搜索的过程
中引入遗传运算，使群体又可以不断进化。
这些是遗传算法所特有的一种隐含并行性。
10.2 遗传算法
? 遗传算法使用概率搜索技术 。遗传算法属
于一种自适应概率搜索技术，其选择、交
叉、变异等运算都是以一种概率的方式来
进行的，从而增加了其搜索过程的灵活性。
实践和理论都已证明了在一定条件下遗传
算法总是以概率 1收敛于问题的最优解。
10.2 遗传算法
? 10.2.3 遗传算法的发展
? 上世纪 60年代，美国密植安大学的
Holland教授及其学生们受到生物模拟技
术的启发，创造出了一种基于生物遗传和
进化机制的适合于复杂系统计算优化的自
适应概率优化技术 -----遗传算法。下面是
在遗传算法的发展进程中一些关键人物所
做出的一些主要贡献。
10.2 遗传算法
? J.H.Holland
20世纪 60年代,Holland认识到了生物的遗传和
自然进化现象与人工自适应系统的相似关系，运
用生物遗传和进化的思想来研究自然和人工自适
应系统的生成以及它们与环境的关系，提出在研
究和设计人工自适应系统时，可以借鉴生物遗传
的机制，以群体的方法进行自适应搜索，并且充
分认识到了交叉、变异等运算策略在自适应系统
中的重要性。
10.2 遗传算法
20世纪 70年代,Holland提出了遗传算法的
基本定理 ---模式定理 (Schema
Theorem),奠定了遗传算法的理论基础。
1975年,Holland出版了第一本系统论述
遗传算法和人工自适应系统的专著《自然
系统和人工系统的自适应性（ Adaptation
in Natural and Artificial Systems）》。
10.2 遗传算法
20世纪 80年代,Holland实现了第一个基于
遗传算法的机器学习系统 ----分类器系统，
开创了基于遗传算法学习的新概念，为分
类器系统构造出了一个完整的框架。
10.2 遗传算法
? J.D.Bagley
1967年,Holland的学生 Bagley在其博士论文中
首次提出了, 遗传算法, 一词，并发表了遗传算
法应用方面的第一篇论文。他发展了复制、交叉、
变异、显性、倒位等遗传算子，在个体编码上使
用了双倍体的编码方法。这些都与目前遗传算法
中所使用的算子和方法类似。他还敏锐地意识到
了在遗传算法执行的不同阶段可以使用不同的选
择率，这将有利于防止遗传算法的早熟现象，从
而创立了自适应遗传算法的概念。
10.2 遗传算法
? K.A.De Jong
1975年,De Jong在其博士论文中结合模
式定理进行了大量的纯数值函数优化计算
实验，树立了遗传算法的工作框架，得到
了一些重要且具有指导意义的结论。他推
荐了在大多数优化问题中都比较适用的遗
传算法参数，还建立了著名的 De Jong 五
函数测试平台，定义了评价遗传算法性能
的在线指标和离线指标。
10.2 遗传算法
? D.J.Goldberg
1989年,Goldberg出版了专著《搜索、优
化和机器学习中的遗传算法》。该书系统
总结了遗传算法的主要研究成果，全面而
完整地论述了遗传算法的基本原理及其应
用。
10.2 遗传算法
? L.Davis
1991年,Davis编辑出版了《遗传算法手
册》，书中包含了遗传算法在科学计算、
工程技术和社会经济中的大量应用实例，
该书为推广和普及遗传算法的应用起到了
重要的指导作用。
10.2 遗传算法
? J.R.Koza
1992年,Koza将遗传算法应用于计算机程
序的优化设计及自动生成，，提出了遗传
编程的概念。 Koza成功地将提出的遗传编
程方法应用于人工智能、机器学习、符号
处理等方面。
10.2 遗传算法
10.2.4 遗传算法的应用
遗传算法提供了一种求解复杂系统优化问题
的通用框架，它不依赖于问题的具体领域，
对问题的种类有很强的鲁棒性，所以广泛
应用于很多学科。下面列举一些遗传算法
的主要应用领域。
10.2 遗传算法
? 函数优化。函数优化是遗传算法的经典应
用领域，也是对遗传算法进行性能测试评
价的常用算例。对于一些非线性、多模型、
多目标的函数优化问题，用其他优化方法
较难求解，而遗传算法却可以方便地得到
较好的结果。
10.2 遗传算法
? 组合优化。遗传算法是寻求组合优化问题
满意解的最佳工具之一，实践证明，遗传
算法对于组合优化问题中的 NP完全问题非
常有效。
10.2 遗传算法
? 生产调度问题。生产调度问题在很多情况
下所建立起来的数学模型难以精确求解，
即使经过一些简化之后可以进行求解也会
因简化得太多而使求解结果与实际相差太
远。现在遗传算法已经成为解决复杂调度
问题的有效工具。
10.2 遗传算法
? 自动控制。遗传算法已经在自动控制领域
中得到了很好的应用，例如基于遗传算法
的模糊控制器的优化设计、基于遗传算法
的参数辨识、基于遗传算法的模糊控制规
则的学习、利用遗传算法进行人工神经网
络的结构优化设计和权值学习等。
10.2 遗传算法
? 机器人学。机器人是一类复杂的难以精确
建模的人工系统，而遗传算法的起源就来
自于对人工自适应系统的研究，所以机器
人学自然成为遗传算法的一个重要应用领
域。
10.2 遗传算法
? 图象处理。图像处理是计算机视觉中的一
个重要研究领域。在图像处理过程中，如
扫描、特征提取、图像分割等不可避免地
存在一些误差，这些误差会影响图像处理
的效果。如何使这些误差最小是使计算机
视觉达到实用化的重要要求，遗传算法在
这些图像处理中的优化计算方面得到了很
好的应用。
10.2 遗传算法
? 人工生命。人工生命是用计算机、机械等
人工媒体模拟或构造出的具有自然生物系
统特有行为的人造系统。。自组织能力和
自学习能力是人工生命的两大重要特征。
人工生命与遗传算法有着密切的关系，基
于遗传算法的进化模型是研究人工生命现
象的重要理论基础。
10.2 遗传算法
? 遗传编程。 Koza发展了遗传编程的概念，
他使用了以 LISP语言所表示的编码方法，
基于对一种树形结构所进行的遗传操作来
自动生成计算机程序。
? 机器学习。基于遗传算法的机器学习，在
很多领域中都得到了应用。例如基于遗传
算法的机器学习可用来调整人工神经网络
的连接权，也可以用于人工神经网络的网
络结构优化设计。
10.2 遗传算法
? 10.2.5 基本遗传算法
基本遗传算法（ Simple Genetic
Algorithms,简称 SGA） 是一种统一的最
基本的遗传算法，它只使用选择、交叉、
变异这三种基本遗传算子，其遗传进化操
作过程简单，容易理解，是其他一些遗传
算法的雏形和基础，它不仅给各种遗传算
法提供了一个基本框架，同时也具有一定
的应用价值。
10.2 遗传算法
? ⑴ 基本遗传算法的构成要素
? ① 染色体编码方法。基本遗传算法使用固
定长度的二进制符号串来表示群体中的个
体，其等位基因是由二值符号集 {0,1}所
组成的。初始群体中各个个体的基因值可
用均匀分布的随机数来生成。
10.2 遗传算法
? ② 个体适应度评价 。 基本遗传算法按与个
体适应度成正比的概率来决定当前群体中
每个个体遗传到下一代群体中的机会多少 。
为正确计算这个概率, 这里要求所有个体
的适应度必须为正数或零 。
? ③遗传算子。基本遗传算法使用下述三种
遗传算子：选择运算使用比例选择算子，
交叉运算使用单点交叉算子，变异运算使
用基本位变异算子或均匀变异算子。
10.2 遗传算法
? ④基本遗传算法的运行参数。基本遗传算
法有下述 4个运行参数需要提前设定：群体
大小 M,即群体中所含个体数目，一般取
为 20~100；遗传运算的终止进化代数 T，
一般取为 100~500； 交叉概率 Pc,
一般取为 0.4~0.99； 变异概率 Pm,一般取
为 0.0001~0.1。
10.2 遗传算法
? ⑤ 基本遗传算法的形式化定义
基本遗传算法可定义为一个 8元组,
(10-2-2)
),,,,,,,( 0 TMPECS G A ????
10.2 遗传算法
式中, C---个体的编码方法；
E---个体适应度评价函数；
P0---初始群体；
M---群体大小；
Φ---选择算子；
Γ---交叉算子；
T---遗传运算终止条件。
10.2 遗传算法
⑵ 基本遗传算法的实现
? ① 个体适应度评价
? 在遗传算法中，以个体适应度的大小来确定该个
体被遗传到下一代群体中的概率。个体适应度越
大，该个体被遗传到下一代的概率也越大；反之，
个体的适应度越小，该个体被遗传到下一代的概
率也越小。基本遗传算法使用比例选择算子来确
定群体中各个个体遗传到下一代群体中的数量。
为正确计算不同情况下各个个体的遗传概率，要
求所有个体的适应度必须为正数或领，不能是负
数。
10.2 遗传算法
? 为满足适应度取非负值的要求, 基本遗传算法一
般采用下面两种方法之一将目标函数值变换为个
体的适应度 。
? 方法一,对于目标函数是求极大化, 方法为,
(10-2-3) ??
?
?
?
??
???
?
0)(0
0)(,)(
)(
m i n
m i nm i n
CXf
CXfCXf
XF
当，
时当
10.2 遗传算法
式中,为一个适当地相对比较小的数，
它可用下面几种方法之一来选取,预先指定
的一个较小的数；进化到当前代为止的最
小目标函数值；当前代或最近几代群体中
的最小目标值。
maxC
10.2 遗传算法
② 比例选择算子
? 比例选择实际上是一种有退还随机选择,也叫做
赌盘 (Roulette Wheel)选择,因为这种选择方式
与赌博中的赌盘操作原理非常相似 。
? 比例选择算子的具体执行过程是：先计算出群体
中所有个体的适应度之和；其次计算出每个个体
的相对适应度的大小，此值即为各个个体被遗传
到下一代群体中的概率；最后再使用模拟赌盘操
作（即 0到 1之间的随机数）来确定各个个体被选
中的次数。
10.2 遗传算法
③ 单点交叉算子
? 单点交叉算子是最常用和最基本的交叉操
作算子。单点交叉算子的具体执行过程如
下：对群体中的个体进行两两随机配对；
对每一对相互配对的个体，随机设置某一
基因座之后的位置为交叉点；对每一对相
互配对的个体，依设定的交叉概率 在其
交叉点处相互交换两个个体的部分染色体，
从而产生出两个新个体。
cp
10.2 遗传算法
④ 基本位变异算子
? 基本位变异算子的具体执行过程为：对个
体的每一个基因座，依变异概率 指定
其为变异点；对每一个指定的变异点，对
其基因值做取反运算或用其他等位基因值
来代替，从而产生出一个新的个体。
mp
10.2 遗传算法
⑶ 遗传算法的应用步骤
遗传算法提供了一种求解复杂系统优化问题
的通用框架 。 对于具体问题, 可按下述步
骤来构造,
? ①确定决策变量及其各种约束条件，即确
定出个体的表现型 X和问题的解空间；
? ②建立优化模型，即描述出目标函数的类
型及其数学描述形式或量化方法；
10.2 遗传算法
? ③ 确定表示可行解的染色体编码方法, 即
确定出个体的基因型 X及遗传算法的搜索
空间；
? ④ 确定解码方法, 即确定出由个体基因型
X到个体表现型 X的对应关系或转换方法；
? ⑤确定个体适应度的量化评价方法，即确
定出由目标函数值 到个体适应度的转
换规则；
)(Xf
10.2 遗传算法
? ⑥ 设计遗传算子, 即确定出选择运算, 交
叉运算, 变异运算等遗传算子的具体操作
方法；
? ⑦确定遗传算法的有关运行参数，即确定
出遗传算法的 等
参数。 mc ppTM,、、
10.2 遗传算法
10.2.6 遗传算法的模式定理
? Holland提出的模式定理（ schema
theorem）,是遗传算法的基本原理，从进
化动力学的角度提供了能够较好地解释遗
传算法机理的一种数学工具，同时也是编
码策略、遗传策略等分析的基础。
10.2 遗传算法
? 模式定理,在选择、交叉、变异算子的作
用下，那些低阶、定义长度短、超过群体
平均适应值的模式的生存数量，将随着迭
代次数的增加以指数规律增长。
10.3 模拟退火算法
模拟退火算法 (simulated annealing,简称
SA)的思想最早是由 Metropolis等 (1953)
提出的,1983年 Kirkpatrick等将其用于
组合优化。 SA算法是基于 Monte Carlo迭
代求解策略的一种随机寻优算法，其出发
点是基于物理中固体物质的退火过程与一
般组合优化问题之间的相似性。
10.3 模拟退火算法
模拟退火算法在某一初温下，伴随温度参数
的不断下降，结合概率突跳特性在解空间
中随机寻找目标函数的全局最优解，即在
局部优解能概率性地跳出并最终趋于全局
最优解。模拟退火算法是一种通用的优化
算法，目前已在工程中得到了广泛应用。
10.3 模拟退火算法
10.3.1 物理退火过程和 Metropolis准则
简单而言, 物理退火过程由以下三部分组成,
⑴加温过程。其目的是增强粒子的热运动，使其偏
离平衡位置。当温度足够高时，固体将溶解为液
体，从而消除系统原先可能存在的非均匀态，使
随后进行的冷却过程以某一平衡态为起点。溶解
过程与系统的熵增过程联系，系统能量也随温度
的升高而增大。
10.3 模拟退火算法
⑵ 等温过程 。 物理学的知识告诉我们, 对于
与周围环境交换热量而温度不变的封闭系
统, 系统状态的自发变化总是朝自由能减
少的方向进行, 当自由能达到最小时, 系
统达到平衡态 。
⑶冷却过程。目的是使粒子的热运动减弱并
渐趋有序，系统能量逐渐下降，从而得到
低能的晶体结构。
10.3 模拟退火算法
Metropolis等在 1953年提出了重要性采样
法，即以概率接受新状态。具体而言，在
温度 t,由当前状态 i产生新状态 j,两者的能
量分别为,若 则接受新状
态 j为当前状态；否则，若概率
大于 区间内的随机数则仍旧接受新状
态 j为当前状态，若不成立则保留 i为当前状
态，其中 k为 Boltzmann常数。
ji EE 和 ij EE ?
]/)(e x p [ ktEEp ijr ???
)1,0[
10.3 模拟退火算法
这种重要性采样过程在高温下可接受与当前
状态能量差较大的新状态，而在低温下基
本只接受与当前能量差较小的新状态，而
且当温度趋于零时，就不能接受比当前状
态能量高的新状态。这种接受准则通常称
为 Metropolis准则。
10.3 模拟退火算法
10.3.2 模拟退火算法的基本思想和步骤
1983年 Kirkpatrick等意识到组合优化与物理退火
的相似性，并受到 Metropolis准则的启迪，提出
了模拟退火算法。模拟退火算法是基于 Monte
Carlo 迭代求解策略的一种随机寻优算法，其出
发点是基于物理退火过程与组合优化之间的相似
性,SA由某一较高初温开始，利用具有概率突
跳特性的 Metropolis抽样策略在解空间中进行随
机搜索，伴随温度的不断下降重复抽样过程，最
终得到问题的全局最优解。
10.3 模拟退火算法
标准模拟退火算法的一般步骤可描述如下,
⑴ 给定初温, 随机产生初始状态,
令 ；
⑵ Repeat,
① Repeat
产生新状态 ；
0tt ? 0ss ?
0?k
)( sG e n e t es j ?
jj ssr a n d o msCsCif ???? ]1,0[) ) ] }()((e x p [,1m i n {
10.3 模拟退火算法
Until 抽样稳定准则满足；
②退温,并
令 ；
Until 算法终止准则满足；
⑶输出算法搜索结果。
)(1 kk tu p d a t et ??
1?? kk
10.3 模拟退火算法
10.3.3 模拟退火算法关键参数和操作的设
定
从算法流程上看，模拟退火算法包括三函数
两准则，即状态产生函数、状态接受函数、
温度更新函数、内循环终止准则和外循环
终止准则，这些环节的设计将决定 SA算法
的优化性能。此外，初温的选择对 SA算法
性能也有很大影响。
10.3 模拟退火算法
⑴ 状态产生函数
设计状态产生函数（邻域函数）的出发点应
该是尽可能保证产生的候选解遍布全部的
解空间。通常，状态产生函数由两部分组
成，即产生候选解的方式和候选解产生的
概率分布。
10.3 模拟退火算法
⑵ 状态接受函数
状态接受函数一般以概率的方式给出, 不同
接受函数的差别主要在于接受概率的形式
不同 。 设计状态接受概率, 应该遵循以下
原则,
①在固定温度下，接受使目标函数值下降的
候选解的概率要大于使目标值上升的候选
解的概率；
10.3 模拟退火算法
② 随温度的下降, 接受使目标函数值上升的
解的概率要逐渐减小；
③ 当温度趋于零时, 只能接受目标函数值下
降的解 。
状态接受函数的引入是 SA算法实现全局搜索
的最关键的因素,SA算法中通常采用
min[1,exp(-△ C/t)]作为状态接受函数。
10.3 模拟退火算法
⑶ 初温
初始温度、温度更新函数、内循环终止准则
和外循环终止准则通常被称为退火历程
(annealing schedule)。 实验表明，初温
越大，获得高质量解的几率越大，但花费
的计算时间将增加。因此，初温的确定应
折衷考虑优化质量和优化效率，常用方法
包括,
10.3 模拟退火算法
① 均匀抽样一组状态, 以各状态目标值的方
差为初温 。
② 随机产生一组状态, 确定两两状态间的最
大目标值差, 然后依据差值, 利用一
定的函数确定初温 。 譬如, 其中
为初始接受概率
③利用经验公式给出。
|| max?
rpt ln/0 ???
rp
10.3 模拟退火算法
⑷ 温度更新函数
温度更新函数, 即温度的下降方式, 用于在
外循环中修改温度值 。
目前，最常用的温度更新函数为指数退温函
数，即，其中且其大小可以不断变化。
10.3 模拟退火算法
⑸ 内循环终止准则
内循环终止准则，或称 Metropolis抽样稳定
准则，用于决定在各温度下产生候选解的
数目。在非时齐 SA算法理论中，由于在每
个温度下只产生一个或少量候选解，所以
不存在选择内循环终止准则的问题。
10.3 模拟退火算法
而在时齐 SA算法理论中, 收敛条件要求在每
个温度下产生候选解的数目趋于无穷大,
以使相应的马氏链达到平稳概率分布, 显
然在实际应用算法时这是无法实现的 。 常
用的抽样准则包括,
① 检验目标函数的均值是否稳定；
② 连续若干步的目标值变化较小；
③按一定的步数抽样。
10.3 模拟退火算法
⑹ 外循环终止准则
外循环终止准则，即算法终止准则，用于决
定算法何时结束。设置温度终值是一种简
单的方法。 SA算法的收敛性理论中要求温
度终值趋于零，这显然不合实际。通常的
做法是,
10.3 模拟退火算法
① 设置终止温度的阈值；
② 设置外循环迭代次数；
③ 算法收敛到的最优值连续若干步保持不变；
④检验系统熵是否稳定。
10.4 神经网络权值的混合优化学习策略
鉴于 GA,SA的全局优化特性和通用性，即
优化过程无需导数信息，我们可以基于实
数编码构造 BPSA,BPGA混合优化学习策
略，以提高前向网络学习的速度、精度，
特别是避免陷入局部极小的能力。
10.4 神经网络权值的混合优化学习策略
10.4.1 BPSA混合学习策略
在 BPSA混合学习策略中, 采用以 BP为主框
架, 并在学习过程中引入 SA策略 。 这样做,
既利用了基于梯度下降的有指导学习来提
高局部搜索性能, 也利用了 SA的概率突跳
性来实现最终的全局收敛, 从而可提高学
习速度和精度 。
BP-SA混合学习策略的算法步骤如下,
10.4 神经网络权值的混合优化学习策略
⑴ 随机产生初始权值, 确定初温, 令
⑵ 利用 BP计算 。
利用 SA进行搜索,
① 利用 SA状态产生函数产生新权值,
,其中 为随机扰动。
)0(? 1t 1?k
)(k?
)(' k?
??? ?? )()(' kk )1,1(???
10.4 神经网络权值的混合优化学习策略
② 计算 的目标函数值与 的目标函
数值之差 。
③ 计算接受概率 。
④ 若,则取 ；
否则 保持不变。
)(' k? )(k?
C?
)]/ex p (,1m i n [ kr tCP ???
)1,0[r a n d o mP r ? )()( ' kk ?? ?
)(k?
10.4 神经网络权值的混合优化学习策略
(4) 利用退温函数 进行退温, 其中 为退
温速率 。
若 对应的目标函数满足要求精度,则终
止算法并输出结果；否则，令,转
步骤⑵。
kk vtt ??1 )1,0(?v
)(k? ?
1?? kk
10.4 神经网络权值的混合优化学习策略
10.4.2 BPGA混合学习策略
神经网络的连接权包含着神经网络系统的全部知
识。反向传播的 BP神经网络 (back
propagation network)的学习算法是基于梯
度下降的，因而具有以下缺点：网络训练速度
慢、容易陷入局部极小值、全局搜索能力差等。
而遗传算法的搜索遍及整个解空间，因此容易
得到全局最优解，而且遗传算法不要求目标函
数连续、可微，甚至不要求目标函数有显函数
的形式，只要求问题可计算。
10.4 神经网络权值的混合优化学习策略
因此，将擅长全局搜索的遗传算法和局部寻
优能力较强的 BP算法结合起来，可以避免
陷入局部极小值，提高算法收敛速度，很
快找到问题的全局最优解。
BP算法和遗传算法结合训练神经网络权重的
主要步骤为,
10.4 神经网络权值的混合优化学习策略
(1) 以神经网络节点之间的连接权重和节点
的阈值为参数, 采用实数编码 。 采用三层
神经网络, 设输入节点数为 p,输出节点数
为 q,隐层节点数为 r,则编码长度 n为,
（ 10-4-1） qrrpn ?????? )1()1(
10.4 神经网络权值的混合优化学习策略
(2)设定神经网络节点连接权重的取值范
围,产生相应范围的均匀分布
随机数赋给基因值, 产生初始群体；
(3)对群体中个体进行评价 。 将个体解码赋
值给相应的连接权 (包括节点阈值 ),引入
学习样本计算出学习误差 E,个体的适应度
定义为,
, （ 10-4-2）
Ef ?? 1
1
],[ m a xm i n xx
10.4 神经网络权值的混合优化学习策略
(4)对群体中的个体执行遗传操作,
① 选择操作 。 采用比例选择算子, 若群体规
模为 M,则适应度为的个体被选中进入下
一代的概率为,
,
（ 10-4-3）
?
?
?
M
i
i
i
i
f
f
p
1
10.4 神经网络权值的混合优化学习策略
② 交叉操作 。 由于采用实数编码, 故选择算
术交叉算子 。 父代中的个体 和 以交叉概
率 进行交叉操作, 可产生的子代个体为,
（ 10-4-4）
和
（ 10-4-5）
其中 a为参数 。
1X 2X
cp
21'1 )1( XaaXX ???
21'2 )1( aXXaX ???
)1,0(?a
10.4 神经网络权值的混合优化学习策略
③ 变异操作 。 采用均匀变异算子 。 个
体 的各个基因位以变异概率 发生变异,
即按概率用 区间中的均匀分布随机
数代替原有值 。
⑸ 引入最优保留策略。
iX m
p
],[ m a xm i n xx
10.4 神经网络权值的混合优化学习策略
⑹ 判断满足遗传算法操作终止条件否？ 不满
足则转步骤 ⑶ 。 否则转步骤 ⑺ 。
⑺ 将遗传算法搜索的最优个体解码，赋值给
神经网络权重 (包括节点阈值 )，继续采用
BP算法优化神经网络的权重和阈值。
10.4 神经网络权值的混合优化学习策略
10.4.3 GASA混合学习策略
采用三层前馈网络, GA和 SA结合训练神经
网络权重的步骤如下,
⑴ 给定模拟退火初温, 令 ；
⑵ 以神经网络节点之间的连接权重和节点的
阈值为参数，采用实数编码。采用三层神
经网络，设输入节点数为 p,输出节点数为
q,隐层节点数为 r,则编码长度 n为,
0t 1?k
10.4 神经网络权值的混合优化学习策略
（ 10-4-6）
⑶ 设定神经网络节点连接权重的取值范
围, 产生相应范围的均匀分布随机数赋
给基因值, 产生初始群体；
⑷ 对群体中个体进行评价 。 将个体解码赋值给
相应的连接权 (包括节点阈值 ),引入学习样本
计算出学习误差 E,个体的适应度定义为,
, （ 10-4-7）
qrrpn ?????? )1()1(
],[ m a xm in xx
Ef ?? 1
1
10.4 神经网络权值的混合优化学习策略
⑸ 对群体中的个体执行遗传操作,
① 选择操作 。 采用比例选择算子, 若群体规模
为 M,则适应度为 的个体 被选中进入下
一代的概率为,
, （ 10-4-8）
if
iX
?
?
?
M
i
i
i
i
f
f
p
1
10.4 神经网络权值的混合优化学习策略
② 交叉操作 。 由于采用实数编码, 故选择
算术交叉算子 。 父代中的个体 和 以交
叉概率 进行交叉操作, 可产生的子代个
体为,
（ 10-4-9）
和
（ 10-4-10）
其中 a为参数 。
1X 2
X
cp
21'1 )1( XaaXX ???
21'2 )1( aXXaX ???
)1,0(?a
10.4 神经网络权值的混合优化学习策略
③ 变异操作 。 采用均匀变异算子 。 个
体 的各个基因位以变异概率 发生变异,
即按概率 用区间 中的均匀分布
随机数代替原有值 。
⑹ 引入最优保留策略。
⑺ 对群体中每一个个体引入模拟退火操作,
iX
mp
mp ],[ m a xm in xx
10.4 神经网络权值的混合优化学习策略
① 利用 SA 状态产生函数产生新基因
值,, 其中 为随
机扰动 。
② 计算 的目标函数值与 的目标函数
值之差 。
③ 计算接受概率 。
)(' kg ??? )()(' kgkg )1,1(???
)(' kg )(kg
C?
)]/ex p (,1m i n [ kr tCP ???
10.4 神经网络权值的混合优化学习策略
④ 若, 则取 ；否
则 保持不变 。
⑤ 引入最优保留策略 。
⑥ 利用退温函数 进行退温，其
中 为退温速率。
)1,0[r a n d o mP r ? )()( ' kgkg ?
)(kg
kk vtt ?? 1
)1,0(?v
10.4 神经网络权值的混合优化学习策略
⑻ 判断满足遗传算法操作终止条件否？ 不满
足则转步骤 ⑷ 。 否则转步骤 ⑼ 。
⑼ 将遗传算法搜索的最优个体解码，赋值给神
经网络权重 (包括节点阈值 )。
10.5 应用举例
? 略,
