人工智能：8.2 遗传算法基本原理

8.1.1        
遗传算法的基本内容

遗传算法是一种基于群体进化的计算模型，它通过群体中的个体之间的信息交换及其结构重组一步步地逼近问题的最优解。对个体的遗传操作主要采用选择、交叉和变异这三个基本的遗传算子，遗传进化操作过程简单、容易理解，它形成了遗传算法的一个统一的实现框架―― 基本遗传算法(Simple Genetic Algorithms, Goldgerg ’89)。下面介绍 SGA 的基本组成及其实现技术。

1.     基本遗传算法的组成

基本 遗传算法 可 用于解决一类静态 的 最优化问题 ，通常一个无约束的优化问题可以表示成如下的形式 ：

max {f(x)}

x = [x ₁,
x ₂, ⋯,x _n]

a_i≤x
_i≤b_i(i = 1,2, ⋯,n
)

很明显， 遗传算法就是模拟生物遗传与进化机理， 从给出的原始解
群体 中不断进化产生新的解，最后收敛到一个特定 解附近 ， 从而 求出 问题的 最优解 ，这一过程主要包括如下内容。

(1) 个体的编码过程。遗传算法把问题的 设计变量 表示成
个体( 染色体) ，多个个体构成的群体则表示了问题中一个解的集合，将设计变量与个体之间的映射称为编码过程。编码的方式有多种，其中较为常用的是采用固定长度的
二进制字符串来进行编码，这种编码方式的特点是使问题的表现形式比较简单，计算机实现容易，便于利用模式理论进行理论分析等。

（ 2 ）适应度函数的建立。用适应度函数衡量群体进化的优良程度，它指导着个体的遗传操作过程，以概率的方式选择下一代优良个体，使整个群体向着最优的方向移动。因此，适应度函数的正确选择对遗传算法的求解会产生一定的影响，在函数优化中，一般可以将目标函数作适当的转换后，作为遗传算法的适应度函数。

（ 3 ） 遗传操作。遗传算法使用三种遗传操作或遗传算子，它们是选择算子、

・230 ・

第 8 章   进化计算

交叉算子和变异算子。选择是遗传算法的 基本算子，它从上一代群体中选择一定数量的个体，作为参与下一代群体繁殖的父代个体，体现了 “适者生存”的自然选择原则。个体的选择是依据适应度大小进行的，适应度大的个体被复制，适应度小的被淘汰，而新群体个体的总数保持不变。交叉算子和变异算子是产生新个体的主要操作，挖掘群体中个体的多样性，克服可能陷于局部解的现象，使得遗传算法的搜索能力得以较大的提高。

（ 4 ） 运行与控制参数。在遗传算法进化过程时，需要预先确定一些有关的

运行参数。首先，需要确定进化群体的大小，即群体中个体的数量，对于一般简 单的优化问题可取 20 ～ 50 ，而较复杂的问题，则要更大的群体，如 50 ～ 100 以上。另外，由于遗传算法中的操作算子是以概率进行的，因此需要确定相应的操作概
率，选择算子的概率为 0.4 ～ 0.8 ，变异算子的概率一般很小，可取为 0.001 ～ 0.01 。遗传算法是一种反复迭代的计算过程，它通过多次进化计算逐渐逼近问题的最优 解，而不是恰好达到最优解。因此，需要确定遗传算法的终止计算条件，一般情
况是规定遗传算法的进化代数，取 100 ～ 500 ，也可以通过目标函数的偏差或个体适应度变化大小来决定算法的终止。

2.     基本遗传算法迭代运算的过程

基本
遗传算法 的 迭代运算的一般过程如图 8.5
所示，可以将其表述为如下算

法形式。

procedure SGA; begin

initial an initial population;

repeat

determine the fitness of each individual; perform selection;

perform crossover;
perform mutation; form a new population;

F¢ F¢max

F¢avg F¢min

O

Fmin  
 Favg   Fmax F

图 8.5 线性定标

end

determine
the fitness of each individual; until termination criterion satisfied

根据以上对遗传算法的基本原理分析和算法描述，可以很容易地用计算机语

・231 ・

人工智能技术与方法

言加以具体实现。概括地讲，遗传算法用于优化的主要
步骤如下 ：

(1)      确定问题的设计变量、约束条件以及问题优化的 目标函数 ；

(2)      设计变量与个体的映射关系( 编码与解码) ，选择适应度函数 ；

(3)      确定算法的运行参数和控制参数 ；

(4)      随机产生初始群体 ；

(5)      计算个体的适应度 ；

(6)      根据遗传概率，运用遗传算子产生新群体 ；

(7)     
重复步骤(5) ～ (6) 的 操作，直到满足终止条件，选择最佳个体作为遗传算法的结果为止 。

下面，我们对以上遗传算法实现步骤中的主要部分作具体讨论。

8.1.2        
适应度函数

适应度函数是用于衡量群体中个体进化的一个重要指标  ，一般个体的适应度越高，个体的性能越好，则有更多的机会进入到下一代的繁殖中 
；反之，适应度越低的个体，其性能就越差，这样的个体将面临被淘汰的危险，其繁殖机会相对
就较小。因此，适应度函数反映出个体的进化优良程度，即个体有可能达到或接 近问题的最优解的程度 ，它在遗传算法中是对个体进行遗传操作的依据 ，因而对算法的效率和性能
会产生直接影响 。如果将适应度函数与问题优化的目标函数建立某种映射关系，就可以通过群体的进化来实现对优化问题目标函数的寻优了。

在许多问题求解中，需要求解目标函数 
f
(x ) 的最小值，并且函数的取值范围有可能为负。而在遗传算法中，由于适应度函数提供作为个体进化的概率计算依 据，因此适应度函数的值应该取正。于是，需要建立将目标函数转换为适应度函 数的一种映射关系 。一般优化问题可分为两大类 ：一类是求解目标函数的最大值， 另一类则是求解目标函数的最小值。

为了把目标函数最小值问题转换为最大化问题，只需要将其乘以－ 1 即可， 同时 为了保证适应度函数为正，还要适当地选择一个较大的数 C _max ：

F(x) =

当 f (x) + C_max
< 0

其他情况

其中， C _max 为一个适当较大的数，也可以选择为群体中 f (x ) 的最大值或进化至今

・232 ・

过程中 f (x )
的最大值。

第 8 章   进化计算

同样，可以将目标函数的最大值问题转换为相应的适应度函数最大化问题，

为保证适应度函数为正，也需要适当地选择一个较小的数
C _min 。

F(x) =

当 f (x) + C_max
> 0

其他情况

其中， C _min 为一个适当较小的数，也可以选择为群体中 f (x ) 的最小值或进化至今过程中 f(x ) 的最小值。

在遗传算法的初始阶段 ，各个个体的适应度比较分散 ，有些个体的适应度高， 有些则很低，这些适应度很高的个体将会被多次选择进入下一代个体的繁殖，并 在后代群体中占有很大的比例。而那些适应度很低的个体则很快被淘汰，在后代
群体中所占比例急速下降。这样，遗传算法中基于多点的搜索过程就会蜕变成为 基于少数点的搜索，容易陷入局部求解区，从而影响了全局的搜索能力，这种现 象称为遗传算法的早期收敛( 或早熟现象) 。

此时，虽然通过选择与变异操作也会产生优异个体，个体的多样性还得以保

留，但是，由于群体的平均适应度已经接近最佳个体的适应度，最佳个体与其他大多数个体在选择机会上几乎相等，因而个体的选择失去了应有的作用，竞争力减弱，导致群体的进化进入一个十分缓慢的过程，其搜索也将停留在某一个局部的最优点附近。为了克服这种现象，需要在遗传算法运行的后期阶段，设法提高个体之间的竞争能力，可以通过采取对部分个体适应度的缩放调整措施，来扩大与其他个体适应度之间的差异程度，从而限制一些个体的复制数量，维护群体的多样性。这种适应度缩放调整称为适应度定标(Fitne ss  Scaling)
，它是保证进化过程中群体个体之间竞争能力的一种重要技术手段，常用的方法有 线性定标、乘幂定标和指数定标等，下面主要介绍线性定标。

设原适应度为 F ，新适应度为 F ¢ ，线性定标采用下式表示 ：

F¢ =
aF + b

其中， a 和 b 为系数，正常的变换情况如图
8.5 所示。

在进行线性定标中，一般希望满足两个条件，一个是保持定标前后的平均适应度不变，即 Fa¢_vg = F _avg； 另一个是定标后的最大适应度为其平均适应度的指定

倍数，即 Fm¢ax     =  C_m×F _avg 。其中，条件一是为了保证群体适应度接近平均适应度

・233 ・

人工智能技术与方法

的个体有期望的数 量进入下一代群体之中 ；条件二则是为了群体中最好的个体能够以希望的倍数 C _m  复制到新一代群体中，从而控制其他个体的复制数量，提高优异个体的竞争力。

需要注意的是线性定标可能出现负适应度，这是因为在搜索过程的后期阶

段，群体中个体的最大适应度和个体的

平均适应度比较接近，而一些较差个体的适应度则远小于平均适应度。于是，
为了满足条件二而将 F ¢_max 和
F _avg 拉开 C _m倍数时，那些低适应度值就会在定标 后变成负值，如图 8.6 所示。一种解决
的方法是将最小适应度 F _min 映射成为 F¢_min=0 ，并保证能够满足条件一即可。 综上所 述，线性定标参数 a 和 b 的

F¢ F¢max

F¢avg

O

F¢min

图 8.6    线性定标( 异常)

计算方法应该满足两个条件，即通过这两点确定该曲线。首先，需要进行适应度定标的非负判断

Fmin

> CFavg – Fmax

C –1

如果上面不等式满足，表明不会出现定标后的负适应度，则可以按照正常情况定标：

a =       C – 1      F                 b
= Fmax – CFavg F

Fmax

–  Favg

avg

Fmax

–  Favg

avg

如果表达式不成立，表明定标后会出现负适应度，则按照异常情况来定标。第一个点满足条件一，第二点则映射成为 F ¢_min=0 ，此时的 a 、b 参数如下 ：

a =       Favg Favg – Fmin

b = –( Fmin ´ Favg )

Favg – Fmin

8.1.3        
遗传算法的编码

遗传算法是对生物遗传与进化过程的一种模拟计算模型
，它通过对群体中个体(
染色体)
进行一系列的遗传操作，从而使得群体向着最优方向进化。遗传算法中的遗传操作是对具有某种结构化形式的个体进行结构重组处理
，不断搜索出群

・234 ・

第 8 章   进化计算

体中的优良个体，逐步逼近问题的全局最优解。因此，遗传算法是不能直接处理 问题空间的设计变量的，而是需要将设计变量转换成具有一定结构形式的个体， 然后才能运用遗传操作进行优化，将这种转换的过程称为对个体的编码。

一般来 说，由于遗传算法具有较强的鲁棒特性，因而它对个体的编码并无特别严格的要求。但是，遗传算法中的遗传操作会直接受到编码方式的影响，一个
好的编码方法，有可能使遗传操作能够简单实现和进 行； 而一个差的编码方法则会增加遗传操作的难度，甚至产生一些无效解，从而影响遗传算法的运行效率。 设计一个好的编码方案一直是个难点 ，人们提出了许多编码方案
，如二进制编码、浮点编码、符号编码等等。

二进制编码是一种常用的编码方法，它使用 0
和 1
所组成的字符集，构成一

个二进制字符串来描述个体结构。该字符串的长度为
l ，可产生 2^l种编码。假设优化问 题中的设计变量变化范围为[ U_min， U_max ] ，则编码的映射关系如下 ：

00    0     = 
 0

00    1     = 
 1

U min

U min + δ

11      1      = 
2 ^l－ 1                            U

其中，二进制的编码精度为

o = U max
–U min

2^l–1

例如，对于[15 ， 30]
的十进制数，其取值范围为 U _max － U_min = 31 － 15
= 16 ， 可以采用 4 位的二进制字符串进行编码，即

0000                15 

0001                16 

0010                17 

1111                     30 

在有些优化问题中 ， 设计变量往往较多，此时编码采用级联的方式进行，即各个设计变量的编码共同组成一个长的字符串。设有
3 个设计 变量 x
₁ 、x
₂ 和 x
₃ ， 分别用 3
位、4
位、5
位二进制字符串进行编码，然后将它们的编码按照一定的顺序连接在一起，共同组成一个全部变量的编码，如

X ： {  010        1010      01101 }

该
X 编码表示 x
₁=2 ，x
₂=10 和 x
₃=13 。

・235 ・

人工智能技术与方法

二进制编码的优点在于其编码、解码的操作简单易行，进行遗传操作时也十分方便、容易被计算机的处理与实现，此外，该种编码方法还便于利用模式理论进行深入分析与研究。二进制编码的局限性在于其存在精度的误差，字符串长度较短时，其编码精度可能达不到要求 ； 如果采用长的字符串编码，虽然 精度能够提高，但字符串长度的增加会导致搜索空间的急剧扩大，并降低遗传算法的运行效率。

对于一些高精度的优化问题，采用二进制编码方案不太合适，于是人们提出

了一种浮点编码的方法。该方法是指用浮点数值来表示问题中的设计变量，个体的编码长度为设计变量的个数。比如，某优化问题中有 4 个设计变量 x ₁ ，x
₂ ，x
₃ 和 x
₄ ，每个变量都有各自的取值范围，将这些变量顺序连接起来构成个体的基因型，如

X
：

表 示 一 个 个 体 基 因 型 ， 其 对 应 的 基 因 表 现 型 为 x
^T = [6.12    3.20     5 .61

7.10]。浮点编码的优点是能够满足高精度的优化要求，适合范围较大的数据、便于较大空间的搜索、改善遗传算法的复杂性计算、提高了运算效率，等等。

8.2.4    遗传算子

遗传算子是模拟生物基因遗传与进化的操作，它对群体中的个体实施遗传算子，使适应度较高的优良个体有较多机会被遗传到下一代中繁殖，而适应度较低的个体则被遗传的机会少，面临淘汰的危险。这样反复的对群体进行遗传操作，
使群体一代代地优化，并逼近最优解。遗传算子有三种 ： 选择、交叉和变异。

1.     选择算子

选择是遗传算法的基本算子，它从群体中选择优
良个体，淘汰劣质个体，体现了生物中“适者生存”的自然选择原则，评价个体优良或劣质是根据个体适应度的大小进行的。目前有多种选择算子，其中最常用的是比例选择算子。

比例选择算子是指个体的选择概率与其适应度大小成正比，也叫赌轮选择，

是一种回放式随机选择方法。设群体大小为 M ，个体 I 的适应度为 F
_i，则个体 i

被选中的概率为

・236 ・

第 8 章   进化计算

Psi = Fi

å Fi

i=1

显然，概率 P _si 反映了个体 I 适应度在整个群体的个体适应度总和中所占比例，个体适应度越高的个体被选中的概率也越大 ； 反之，适应度低的个体被选中的概率越低 。比如有 10 个个体 x _i(i=1,2, ⋯,10) ，其适应度为 F _i(i=1,2, ⋯,10) ，见图

8.7 。其中，第一行为
1 ～ 10 个体编号，第二行为相应的适应度值，第三行为个体适应度的累计和，总和为  57 。第四行为个体适应度在个体适应度总和中所占的比例。产生新的随机数，将该随机数与适应度累计值比较，从而确定它所位于的个体区间范围，并选中对应的个体。如随机数 10.5 ，位于个体 3
号的区间[9 ， 13] ， 因此选中 3 号个体。图中第 5 行为产生的 10 个随机数，相应的选中个体号在第六行。

图 8.7 赌轮选择示例

由上面选中的结果可知，个体的适应度越大，所 占有的区间范围将会越大，
于是被选中的机会也就越多，图 8.8 描述了这种赌轮选择的原理。值得注意的是， 虽然适应度小的个体被选中的机会较小，但并非意味着它不会被选中，如图中的 
10 号个体即被选中一次并被复制到下一代群体中，这样就保持了个体的多样性，
有利于个体的交叉与变异。

・237 ・

人工智能技术与方法

2.8

5.8

5%

11%

1.8

3%        14%

7.3

3%

1.7

8%   
4

8.9

17%

8%

4.1

14%

7.2

17%

9.4

图 8.8 赌轮选择原理

每代群体中，被复制的个体数目有概率 Psc 加以控制，一般取 0.1 ～ 0.2 ，即群体中约 10 ％的个体 被复制，相应地 10 ％个体被淘汰，以保持群体大小不变。

选择算子除了采用比例方式外，还有一些其他选择方式，如最佳个体保存方法。这种方法的基本思想是把群体中适应度最高的个体不参与遗传操作而直接进入下一代中，其优点是避免优良个体在交叉和变异操作中遭到破坏，它是遗传算法收敛性的一个主要保证。但是，这也隐含着一种危险，即局部最优个体会急剧增加，从而使进化有可能陷于局部解，所以，此方法一般要和其他选择方法结合使用。

2.     交叉算子

交叉算子是遗传算法中产生新个体的主要手段，它将两个个体的部分结构加以替换重组而生成新个体，从而使得遗传算法的搜索能力得到极大加强。交叉算子的设计和实现与具体的 优化问题有关，一般要求不要太多地破坏优良个体的优良模式，同时有能够产生一些较好的新个体模式，它主要包括两个基本内容 ： 一个是在形成的配对库中随机产生配对个体组，并依概率决定是否进行交叉操作
； 另一个是设定配对交叉点并完成交叉操作。

单点交叉又称简单交叉，是一种最常用的交叉算子，它是在个体的编码字符串中随机设定一个交叉点，然后在该交叉点前后交换两个个体的部分结构，并生

成新的两个个体。比如，两个个体
A 和 B
，分别用 6 位二进制字符串编码，下画线为此次交叉点的位置，交叉操作之后产生了新个体 A ‘ 和 B’ ：

・238 ・

第 8 章   进化计算

执行交叉操作的个体是随机选择的，选择概率一般在 0.4 ～ 0.8  左右，即群体中约 40 ％～ 80 ％的个体要进行交叉操作 。可以采用上面介绍的赌轮选择方法来选定被交叉的配对个体库 ，然后以此两两进行交换 。交叉点的选择也是随机产生的， 在字符串长度以内的区间上产生随机整数，作为字符串中交叉点的位置。通过交 叉操作，所产生的新个体有时和父代个体具有明显的差别，有时又会产生一定的
相似性，正是有了交叉操作，群体才保持着多样性，从而扩大遗传算法的搜索范 围，加快优化的收敛速度。

3.     变异算子

变异 也是遗传算法中产生新个体的另一种方法，它是对群体中个体的某些基因座上的基因值作变动。对于二进制字符串编码的个体，其变异操作就是将基因值取反，即将 0
变为 1 ，将 1 变为 0 。比如，个体 A 依概率 P _m 产生变异点，分别在第 3 位和第 8
位，变异后产生新个体 A ¢

A 个体

11010111

11110110           A¢个体

变异的个体以及变异的位置是依据概率来选择的，个体变异的概率很小，一 
般为 0.001 ～ 0.1 ，也就是说，对于 1
000 个字符中有 1 ～ 10 个发生变异。个体的变异主要起两个作用，一个是继续维持群体的多样性 ，防止出现未成熟 收敛现象， 保证算法过程不会产生无法进化的单一群体 ；另一个是使遗传算法具有局部的随机搜索能力，当接近最优解邻域时，通过变异可以加速最优收敛的速度。

8.2.5    模式理论

遗传算法是一种基于群体进化的一种计算模型，它通过对群体中的个体进行
遗传操作( 选择 、交叉和变异) 使群体向着最优方向移动并最后逼近问题的最优解。在这样的进化过程中包含了大量的随机性操作，这些随机性操作对群体性能优化
起到何种作用以及它们的内在本质，有必要作进一步的分析与研究。
20 世纪 70 年代 ，Holland 
教授提出基因模式理论，首先引入 “模式”(Schema) 这一概念，该理论以二进制位串为基础，深入讨论了模拟生物染色体的遗传算法的内在机制，为

・239 ・

人工智能技术与方法

遗传算法奠定了理论基础。下面介绍遗传算法的基因模式定理。

1.     模式

在遗传算法操作过程中，个体是通过适应度值来判断其优良程度的，初始群
体( 第 0
代) 中个体的适应度各不相同 。如前面 8.1.2 节求解函数优化问题的例子中，

1 号个体(01101)
适应度为 169
，2
号个体(11000)
适应度为 576
，等等。其中，适应

度值较高的个体，如 2 
号个体(11000)
和 4
号个体(10011)
的适应度分别为 576 和

361 ，它们的编码字
符串中有一些相似的结构特征，如编码字符串中左边第一位字符为“1”，可以表示为 1 
*  *  *  * ； 而适应度较低的个体，如 1 
号个体(01101) 和 3号个体(01000) 的适应度分别为 169 和 64 ，它们的编码字符串中边第一位字符为“0”，可以表示为 0 * * *
* ，这里* 表示暂时不去关心的字符，这种个体结构上所存 在的相似特征称为模式。比如，模式* 101* 代表 4 个个体的相似性{01010 ，0101 ， 11010 ，11011} ，而模式* 1010 则可以代表 2 个个体{01010 ，11010} 。

群体中个体的相似性可以通过个体模式来刻画，这些模式各不相同，有些模式的跨度要比其他的长，如与模式 1
*1** 相比 ，1 ****1 要跨越整个串长更大的部

分。为了定量地描述模式，引入模式中的两个重要参数 ： 模式阶(Order) 和定义距

(Defining length) 。

模式的阶次(Order) 是指模式中已有明确含义的字符个数，记作 O (H) 。比如上面提到的模式* 101* ，其阶次为
3 ，记作 O(*101*)=3 ，它代表
4 个个体； 而模式  O(*1000)=4
，代表两个个体。显然，模式的阶次越低，所代表的字符串个数越多，则模式的概括性越强，模式的确定性 就越高。反之，模式的阶次越高，所代表的字符串个数越多，则模式的概括性约弱，模式的确定性就越低。因此，模式的阶反映了不同模式间确定性的差异，这里可以看到，模式* 1010  在相似性方面比*101* 有更明确的表示。

模式长度(Defining Length) 是指模式中最前面和最后面两个具有明确含义的字符之间距离，记作δ(H) ，如δ(10*0*) ＝ 3 ， δ(0****) ＝ 0 。在遗传进化过程中， 模式长度越长，该模式被破坏的可能性越大。反之，模式长度越短，则该模式被破坏的可能性越小。比如，模式(0****) 比模式(10*0*) 更难被破坏。即使阶数相同的模式，也会有不同的性质，而模式的定义就反映了这种性质的差异。

在遗传进化的过程中，对个体的遗传操作实际上就是对个体模式的操作，对

・240 ・

第 8 章   进化计算

于 n 个长为 l 的二进制字符串编码个体，群体最多可以同时处理 n ´ 2^l个模式， 而不同的模式在群体进化中是不断发生着改变，关于模式的内部机制，如下的模式理论作出了分析。

2.     模式理论

设第 t
代群体为 A (t)
，该群体中基因模式 H 出现的次数为 m (H ， t) 。群体中的个体依其适应度值大小被选择和复制，其选择的概率为

n

Pi = fi

å
f j
j=1

其中， f_i为群体中第 i 个个体， n
群体大小， P _i为第 i
个个体被选择的概率。

于是，以第 t
代群体 A (t)
为基础进行选择操作后，得到第 t +1 代群体 A (t+1) ， 它包含个体 i 的个数为

n fi

å f j j=1

通过选择操作得到的个体中包含基因模式
H 的次数则为

n

m(H ,
t) n

f (H )

å
f j
j=1

其中， f
(H )
为在第 t 代群体中基因模式 H 的个体平均适应度。

因此，通过选择操作之后，在第 t+1 代群体中出现基因模式 H
的次数为

n

m(H , t
+1) = m(H , t) nf (
H )

n

å
f j
j=1

其中， å f j 为群体的适应度总和，则群体的平均适应度为 

j=1

于是，有

f  = å f j        n

j=1

m( H
, t + 1) = m( H
, t)

f (H )       f

这表明，一个特定的基因模式 H 在群体中出现的次数与该基因模式 H
的个体平均适应度和群体的平均适应度之比成正比。换言之，那些适应度高于群体平均适应度的模式在下一代中将会有更多的出现机会，而对于适应度低于种群平均适应的模式，它们在下一代中的出现机会将减少。因此，自然界生物遗传的优胜劣汰的机制在基因模式次数增长关系中得到了 充分体现。

上式还可以看出，遗传算法不同于一般的随机搜索方法，遗传算法中群体进

・241 ・

人工智能技术与方法

化的过程是向优良基因模式和适应度高的个体逼近的过程。

假设从第 0
代(t=0)
开始，群体中某一特定模式适应度保持在种群平均适应度

以上，比如为 c f– ，这里 c 为一常数，即

–

f (H )
= (1+ c)
f

则模式通过选择操作之后，该基因模式
H 在下一代(t=1)
群体中出现的次数为

–

m( H ,1) = m(H ,0)
f

–

cf     = (1 + c)m(H ,0)

           –            

f

随着群体进化，经过 t 代后，其出现次数将变为

–

m( H , t + 1) = m(
H , t ) f

–

cf     = (1 + c)m( H , t )

           –            

f

= … = (1 + c)^tm(H ,0)

显然，当 c >0 时，有(1+c
)>1 ，则(1+c )^t的值将随着群体进化(
群体代数 t 的增大)
而趋于∞，即适应度超过平均适应度的个体中基因模式 H  将按照指数增长方式被选择。同样，当 c <0 时，有(1+c
)<1 ，则(1+c )^t的值将随着群体进化(
群体代数 t 的增大) 而趋于 0
，即适应度低于平均适应度的个体中基因模式 H  将按照指数方式减少，逐渐被淘汰。

从一定程度上讲，这种选择复制的算子是在整个种 群中并行地开展着，许多

不同的模式按照上面的这种规则相应的增长或衰减，但这种选择操作只是在原有群体中进行的。个体按照其适应度大小依概率发生变化( 增长或减少)
，优良个体得到较多的选择和复制机会，相反，劣质个体则逐渐减少，整个群体进化过程没有出现新的个体，选择与复制不会搜索新的相似点，即没有搜索问题空间的新区域。因此，交叉与变异是产生新个体或新搜索区域的主要遗传操作。下面分析一下交叉和变异操作对模式的影响。

交叉操作是两个染色体之间的信息结构重组过程，对于二进制编码字符串而言，则体现两个字符串的子串依概率随机进行 交换。下面以一个 7 位(l ＝ 7)
的二

进制字符串编码的个体 A 为例进行讨论，其中，选择的两个模式为 H ₁ 和 H₂ ，它们具有相同的模式阶，但模式定义长度不一样，分别位 5 和 1 。

A      =

H1        =

H2        =

0   
1    1   1    0    0 0

*   
1    *   *    *    * 0

*   
*    *   1    0    * *

・242 ・

第 8 章   进化计算

现在对 A
进行交叉操作，随机选择一个交叉位置，如选定在 3 和 4 之间，考察一下交叉对模式 H ₁ 和 H₂ 的作用。

A     =

H1       =

H2        =

0    1  1

*    1  *

*    *  *

1   
0    0  0

*  
*   *   0 1   
0    *  *

显然，对于模式 H
₁ ，由于 A
的交叉位置在模式 H₁ 的定义长度上，模式 H₁

将会被破坏。而对于模式
H₂
，相同的交叉位置并不会受到破坏，模式 H ₂ 会保留到一个子代 中，在交叉过程中模式 H
₁ 比模式 H₂ 更不易生存，这是因为交叉点更容易落在距离最远的确定位置之间。

假设交叉位置是用均匀分布的随机数确定的 ，一般来说模式 H 被破坏的概率

为δ(H)/ (l －1)
，模式 H
生存的概率为 1 － δ(H)/(l － 1)
。本例中，模式 H₁ 被破坏的概率为 5/6 ( 生存概率为 l/6)
，模式 H₂ 被破坏的概率为 1
/6 ( 生存概率为 5/6) 。

考虑到个体交叉是以随机方式进行的，即以概率 P _c进行的交叉，而非每一个个体都进行交叉。因此，对于模式 H 经过交叉后保存下来的概率是

P ≥1 – P o (H )

s                  c   
l
– 1

如果同时考虑选择、交叉操作对模式的影响，由于选择与交叉操作是不相关的，则可得到子代模式的估计为

m(H ,t
+ 1) ≥m( H, t) f (H ) [1– P d( H) ]

–                             l – 1

上式表明，模式增长或衰减不仅依赖模式的适应度与群体平均适应度之比值，还依赖于模式具有的定义长度。那些在种群平均适应度之上且又具有短的定义长度的模式将按照指数增长。

下面再考察变异操作对模式的影响。变异操作是以概率 P _m 随机地改变一个字符串编码位上的值，也就是说每一 位的存活概率为 1
－ P _m 。对某一特定模式 H
， 其阶次为 O(H) ，这表明模式 H
中有明确含义的字符有 O( H) 个，且每位的变异都是统计独立的，于是该模式的存活概率为

Pms   =
(1 –
Pm )(1 – Pm )…(1 –
Pm ) = (1 – Pm )^{O(
H )}

一般变异的概率很小，即 P
_m＜＜ 1 ，可近似表示如下：

Pms  
= (1 – Pm )^O(H
)»
1 – O(
H )Pm

因此，在考虑选择、交叉和变异操作的共同作用下，一个特定模式在下一代

・243 ・

人工智能技术与方法

中期望出现的数目就可以近似地表示为

m(H ,t
+ 1) ≥m(H , t) f (H ) [1 – P o (H ) – O( H )P ]

f              ^c l –1                ^m

综合以上 的分析与讨论，可以得到如下遗传算法中的重要结论。

模式定理   如果基因模式的定义长度较短、基因模式的定义阶次较低、基因模式的适应度值大于群体的平均适应度值，则随着群体的进化，该基因模式在群体中出现的次数将呈指数规律增长。

模式定理是遗传算法的理论基础，它说明了模式在群体进化过程中的增加规

律，深刻地阐明了遗传算法中 “优胜劣汰”的内在原因，解释遗传算法的机理提供了一种数学工具。

由模式定理可知，具有某种结构特征的模式在群体进化过程中其样本数按指
数增长，它们的阶次较低、定义长度较短、其平均适应度高于群体的平均适应
度， 这类模式称为基因块或积木 块(Building Block) 。积木块在遗传算法中有很重要的作用，它们在遗传操作下相互结合，能够产生适应度更高的个体编码串，从而找 到更好的问题最优解，这就是积木块假设所揭示的内容。

积木块假设 短定义长度、低阶以及高平均适应度的模式( 积木块) ，在遗传操作的作用下相互结合，能够产生长定义长度、高阶及高平均适应度的模式，最终接近全局最优解。

需要说明的是，积木块假设并没有得到完整而严格的数学证明，但目前大量的应用实践支持着积木块假设的有效性，它在许多领域内都取得成功，例如平滑多 峰问题、带干扰多峰问题以及组合优化问题等。模式定理保证了较优模式的样本数呈指数增长，从而满足了求最优解的必要条件，即遗传算法存在找到全局最优解的可能性 ； 而积木块假设则指出遗传算法具备了寻找全局最优解的能力，即积木块在遗传算子的作用下能生成低阶、短距、高平均适应度的模式，最终生成全局最优解。

我们仍然利用 8.1.2
小节中的例 8.2
来讨论遗传算法中字符串和模式的变化情

况。图
8.9 表明经过遗传操作后群体中个体的变化情况。复制后，原群体中的
2 号个体( 优良) 个数增加，而原 3
号个体( 劣质) 遭到淘汰。通过配对并进行交叉操作后 ，2 号优良个体继续保留，同时产生了新的优良个体(3 号) ，群体的平均适应度提高。

・244 ・

第 8 章   进化计算

图 8.9  遗传算法个体变化

图 8.10
表明群体中三种模式的变化情况，下面分别进行讨论和分析。

模式 H₁ (1****)

图 8.10 遗传算法模式变化

该模式的阶次最低 O (H₁)=1
，定义长度最短 d(H₁)=0
。在初始群体中，模式

H₁ 代表 2 号个体和 4 号个体，其平均适应度
f(H₁)=(576+361)/2=468.5 ，高于群体

平均适应度 293
。于是，在下一代中模式 H ₁ 代表的个体数为

m(H1 ,t
+ 1) = m( H1 ,t) ´ f (H1 ) / f1 = 2 ´ 468 .5 / 293 = 3.20

经过实际复制后，新的群体中的 2 号、3 号、4 号三个个体都属于模式 H₁ ，与理论计算相符。

在交叉过程中，由于 d(H₁)=0
，P
_c=1
，模式 H
₁ 的存活率为

P = 1 – P o (H1 ) = 1–1´ 0 /(5 –1) = 1

s                   c
l –1

上式表明，交叉操作对模式 H
₁ 没有影响。

假设变异概率取 P _m=0.004 ，则该模式在变异操作下的存活率为

Pms = 1 – O( H1 )´ Pm =
1–1´ 0.04 = 0.996

上式表明，变异操作基本上不会破坏模式 
H₁ 。由此可见，低阶、短长、平均

・245 ・

人工智能技术与方法

适应度高的模式 H ₁ 在遗传过程中不断增长，它属于积木块。模式 H₂ (*10**)

该模式的阶次 O(H₂)=2
，定义长度 d(H₂)=1
。在初始群体中，代表 2 号个体和

4 号个体，其平均适应度为 f(H₂)=(576+64)/2=320
，高于群体平均适应度 293 ，则该模式 在下一代中代表的个体数为

m( H ₂,
t + 1) = m(
H ₂, t ) ´ f ( H ₂) / f ₂= 2´ 320 /
293 = 2.18

经过实际复制后，新的群体中的 2 号、3 号两个个体都属于模式
H₂ ，与理论计算相符。在交叉过程中， d(H₂)=1 ， P
_c=1
，模式 H₂ 的存活率为

Ps = 1 – pc

o (H1 ) =1 –1´1 /(5 –1) = 0.75

l –1

上式表明，交叉操作有可能会对模式 H
₂ 产生有影响。

假设变异概率取 P _m=0.004 ，则该模式在变异操作下的存活率为

Pms = 1 – O( H1 )´ Pm =
1– 2 ´0.004 = 0.992

上式表明，变异操作也基本上不会破坏模式 H₂ 。在经过遗传操作后，若不考虑变异时，该模式代表 的个体数目为

m(H

,t + 1) = m(H
,t ) ´
f (H 2 ) [1 – P o ( H2 ) ]

2                                    2

2

c l – 1

模式 H₃ (1***0)

= 2 ´ 320 / 293 ´ [1 –1 ´1 /(5 – 1)] = 1.64

该模式的阶次 O(H₃)=2
，定义长度 d(H₃)=4
。在初始群体中，它仅代表 2 号个体，但其平均适应度较高 f(H₃)=576/1=576 ，超过群体平均适应度 293 ，复制后则

该模式在下一代中代表的个体数应增加

m(H 3 ,t + 1) = m(H 3 , t) ´ f ( H3 ) / f3 = 1 ´ 576 / 293 = 1.97

经过实际复制后，新的群体中的 2 号、3 号两个个体都属于模式
H₂ ，与理论计算相符。在交叉过程中，由于其定义长度较长 ：d(H₂)=4
， P
_c=1
，模式 H₃ 的存活率为

P = 1 – P o (H 3 ) = 1–1´ 4 /(5 –1) = 0

s                   c
l –1

上式表明，交叉操作肯定会影响到模式 H ₃ 的存活。

假设变异概率取 P _m=0.004 ，则该模式在变异操作下的存活率为

Pms = 1 – O( H3 ) × Pm = 1– 2 ´0.004 = 0.992

上式表明 ，变异操作也基本上不会破坏模式 H ₃ 。于是 ，通过以上遗传操作后，
若不考虑变异时，模式 H ₃ 在新一代群体中所代表的个体数目为

・246 ・

m(H ,t
+ 1) = m(H
,t )