Monto-Carlo方法及模拟退火算法都归属 后者（随机搜索算法）。当目标函数具 有为数不多的极值点时，确定型算法常 表现出较高的计算效率，但同时也暴露 出算法复杂、对目标函数的性质要求高、 可靠性差等缺点。相比而言，随机搜索 方法具有较强的鲁棒性，算法容易实现， 但常有计算效率低的缺点。
仿生类算法是近二十年来才发展起来的一类新型 全局优化搜索技术，它们通过向自然界学习，借 鉴生物进化机制求解问题。这类算法的主要优点 在于其本质上的并行性、广泛的可适用性（如对 目标函数的性态无特殊要求，特别可以没有明确 的表达式）和较强的鲁棒性、简明性与全局优化 性能。虽然从基本思想的产生至今已有三十年的 历史，但广泛用于求解优化问题还是近二十年的 事。初步研究及广泛的应用实践已显示出它们作 为可靠、有效的全局优化算法的巨大潜力和诱人 前景。
（
Pi (k ) = P( xi (k ) is selected) =
J(x i (k ))
模拟进化计算 （Simulated Evolutionary Computation) 是近十几年来信息科学、 人工智能与计算机科学的一大研究领域， 由此所派生的求解优化问题的仿生类算 法（遗传算法、演化策略、进化程序）， 由于其鲜明的生物背景、新颖的设计原 理、独特的分析方法和成功的应用实践， 正日益形成全局搜索与多目标优化理论 的一个崭新分支。
从以上描述，我们看到，模拟进化算法与 传统的确定性算法有以下明显区别： 第一，模拟进化算法的作用对象是由多个 可行解组成的集合，而非单个可行解； 第二，模拟进化算法只利用函数的适应值 信息，而无需应用梯度等其它辅助信息； 第三，模拟进化算法利用概率机制而非确 定性迭代过程描述。正是这些有别于确定 型方法的特征决定了模拟进化算法应用的 广泛性、描述的简单性、本质上的并行性 和良好的鲁棒性。
1 2
' s' P s 以概率 对中间个体 m (4) 1 、 2 进行变异，产生两个新
个体 s1 、 s2
对这2M II-2 计算由步 II-1 所产生的2M 个新个体的适应性，
新个体连同Y (k )由某种选择规则确定 N 个个体组成新一代 种群Y (k + 1) = {Y1(k + 1),..., YN (k + 1)}
X (0) = {X 1(0),..., X N (0)} ，设 X (0) 的染色体编码为 ， Y ( 0 ) i i
并记Y (0) = {Y1(0),..., YN (0)} ； I-3 计算Yi (0) 的适应性值J (Yi (0)) ； I-4 置k = 0
步 II. 种群进化: II-1 执行 M (一般 M ≥ N / 2 )步如下操作: (1) 对每一 Yi (k ) 依据其适应性赋一繁殖概率 Pi (k ) ; (2) 以概率 Pi (k ) (1 ≤ i ≤ N ) 从 Y (k )中随机选 取两 个个 体，分别记作 Yi1 (k ) 和Yi 2 (k ) ； (3) 以概率 Pc 对 Yi1 (k ) 、Yi 2 (k ) 进行杂交，产生两个中间 个体 s ' 和 s ' ；
模拟进化算法在计算智能的广泛领域（如组合 优化问题求解，人工神经网络的训练与结构优 化，程序设计自动化中的查错处理，知识库的 维护等）已得到广泛而成功的应用，但正如我 们在下一节将要指出的，这类算法的研究目前 还尚处于起步上升阶段，特别是作为全局优化 的一类算法，其理论基础还没有完全建立起来。 Ì 模拟进化算法的典型执行策略 依历史发展与不同的应用侧重,模拟进化算法通 常分为遗传算法、演化策略与进化程序三个典 型的执行策略(也可视为三个不同的发展方向)。
第四章 模拟进化与遗传算法
参考文献： [1] Goldberg D. E. , Genetic Algorithms in Search, Optimization, and Machine learning, Reading, MA: Addison Weley, 1989 [2] 徐宗本，张讲社，郑亚林，计算智能中的仿 生学：理论与算法，科学技术出版社，2003
GEN++
杂交（Crossover）
变异（Mutation）
判断是否停止
N
Y
停止
常规遗传算法（GA）的流程图：
Gen=0
随机产生初始种群
终止判据是否满足？
是
否
输出结果 计算种群中每个个体的适应性
结束
GEN++
i=0
是
i=M ?
①
②
①
②
否
随机选择遗传 算子
Pc 杂交
Pr 繁殖
按适应度进行选择 个体，Selection
繁殖是现存物种得以生存、延续的必要条件。 生物界中最常见且被科学实验证明最有利于 进化的繁殖方式是有性生殖 （ sexual reproduction ) ； 变异是生物进化的根本保证； 竞争是规模有无限扩大趋势的生物体分享有限 生存资源的直接结果； 最后在竞争的环境下，自然界不可避免地 会对生物的生存进行选择。
仿生类算法，就其目前发展而言，可分为仿生 过程算法与仿生结构算法两大类，前者以模拟 进化算法为代表，后者以神经网络为典型。 Ì 生物进化过程 建立在达尔文进化论与孟德尔遗传变异规律基 础上的现代生物学认为，生物进化是从低级向 高级、从简单向复杂、趋势向上、而又呈现出 多枝齐头并进多样化发展的演化过程。生物的 进化表现为“适者生存，不适者被淘汰”，也就 是“优胜劣汰”。绝大多数生物的进化通过繁殖 （reproduction）、变异（mutation）、竞争 （competition）、选择（selection）四个基本 过程实现。
假定考虑全局优化问题（P）。遗传算法基于 以下两条基本策略求解问题： n 1 （1）对于给定的目标函数 F : Ω ⊂ R → R 它使用Ｆ的任一适应性（fitness)函数（换言 之，一个值域非负、与Ｆ有相同极值点的函 数）； （２）代替直接作用于优化变量Ｘ，它作用于 Ｘ的可称之为染色体（chromosome) 的某种 编码（换言之，Ｘ的某种离散化近似表示。 例如，长度为Ｌ且取值于某种字母表的数 串）。
于是，求解问题（P）的一个不变规模 （例如设为N）的模拟进化算法可抽象 地描述如下： 步1. 随机确定初始种群：
X（0） = （X 1 (0),⋅ ⋅ ⋅, X n (0)), 置K = 0;
步 2. 计算当前种群中每一个体 X i ( K ) 的适应性(i=1,2, … ,N),并依据适应性指 定其相应个体的繁殖概率;依据所指定的 繁殖概率,通过遗传机制(杂交、变异） 产生适量的新一代种群的侯选种群，最 后依据某种选择规则，从侯选种群中确 定新一代种群 X ( K + 1) 步 3. 检验当前种群是否产生满意解或已达 到预设的进化时限，如已满足，停止， 否则令K：=K+1 转步2 。
Pm 变异
按适应度选 两个个体 杂交 （或交叉） Crossover
按适应度选择 个体
繁殖 Reproduction
变异 Mutation异后的新个 体加到新种群中
i++
在上述算法中，种群进化步II，反映了遗传算法 对生物进化过程的类比特征。如果说算法从父代种群 Y(k)产生子代种群是某种遗传算子的作用，则根据算 法定义，遗传算子将由以下特指的选择算子、杂交算 子和变异算子复合构成： 1）选择算子：它由算法步II-1和II-2定义,其作用效 果反映在对父代种群中每一个体所赋予的允许繁殖 概率及其从2M个中间个体中如何选择子代种群的机 制上。对于每一个体的允许繁殖概率 Pi ( k ) 的确定, 通常按照“适应性强的多复制,适应性差的遭淘汰,而 具有平均适应性的基本不变”的原则。常见的赋值方 法有“比例选择规则”:

解全局优化问题的模拟进化算法本质上 是一类建立在模拟生物进化过程基础上 的随机搜索方法,其基本思想可概括为: 将待优化问题的目标函数理解作(或转换 到)某生物种群对环境的适应性（fitness） 将优化变量对应作生物种群的个体 (individual) 将所发展的求解优化问题的算法与生物 种群的进化过程类比
这样,假定我们考虑全局优化问题：
n n 1 max{ F ( x ) : x ∈ Ω ⊂ R }, F : Ω ⊂ R → R (p):
则(P)的多个可行解的一个集合可称之为 一个种群(population),种群中的每一元素 (可行解)可称之为是一个个体 ( individual),种群中个体的数目称之为此 种群的规模。
遗传算法（Genetic Algorithm, 简称GA）是通过模拟生物进化 过程来完成优化搜索的。
科学研究、工程实际与国民经济发展的 众多问题可归结为“最大效益、最小代价” 这类典型的优化模型。求解这类模型导致 寻求某个目标函数（有解析表达式或无解 析表达式）在特定区域上的最优解。
传统的建立在梯度计算基础上的非线性规 划类方法，当目标函数仅具有单极点时， 通常表现出较高的计算效率，但当目标函 数具有多极值点时，由于其本身固有的局 部优化性及不稳健等缺陷，而被广泛认为 不适于全局优化问题的求解。 近二十年来，人们相继发展了许多求解全 局优化问题的方法，一般可分为确定型与 非确定型（如随机搜索）算法。
步 III. 检验终止判据：如果Y (k +1) 满足预先设定的停机准 则，则终止演化，并输出最优解；否则，置k := k +1 ， 返回步 II。
遗传算法的一般流程：
生成第一代 （First generation）,GEN=1
计算每个个体的适应性（Fitness）
按适应性进行选择（Selection）
Ì
模拟进化算法 模拟进化算法的核心思想源于这样的基本认识：体 现在 “ 优胜劣汰 ” 这一自然规律的生物进化过程本身 是一个自然的、并行发生的、鲁棒的优化过程，这 一优化过程的目标是对环境的适应性（fitness)，而 生物种群通过生物体的遗传、变异来达到优化（亦 即进化）之目的，对生物进化的这种优化观点早在 六十年代就引起J.H.Holland、 I.Recenberg及 L.J.Fogel等计算智能学者的特别兴趣,并相继创立了 现 在 被 称 之 为 遗 传 算 法 ( g e n e t i c algorithms)、演化策略(evolution strategies)和进化程 序 (evolutionary programming)的模拟进化算法.