遗传算法原理及其应用

《遗传算法原理及其应用》

1207

Chap1 序论

一. 遗传算法的生物学基础

1.1 遗传与变异 基本概念 Cell:细胞

Chromosome:染色体 Gene:基因 Locus:基因座 Allele:等位基因 Genotype:基因型 Phenotype:表现型 Genome:基因组 Reproduction:复制 Crossover:交叉 Mutation:变异

1.2 进化 基本术语

Evolution:进化 Population:群体 Individual:个体 Fitness:适应度

1.3 遗传与进化的系统观

特点:

1) 生物的所有遗传信息都包含在其染色体中,染色体决定了生物的性状;

2) 染色体是基因及其有规律的排列所构成,遗传和进化过程发生在染色体上; 3) 生物的繁殖过程是由其基因的复制过程完成的;

4) 通过同源染色体之间的交叉或染色体的变异会产生新的物种,使生物呈现新的性状; 5) 对环境适应性好的基因或者染色体会经常比适应性差的基因或染色体有更多的机会遗传到下一代。

二. 遗传算法简介

遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率

搜索算法。

2.1 遗传算法概要

对于一个求函数最大值的优化问题（求函数最小值也类同），一般可描述为下述数学规

max

t划模型：s..

f(X)X∈R R⊆U

T

式中，X=[x1,x2,...,xn] 为决策变量，f（X）为目标函数，第2，3式为约束条件，U是基本空间，R是U的一个子集。满足约束条件的解X称为可行解，集合R表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。

对上述最优化问题，目标函数和约束条件种类繁多，由的是线性的，有的是非线性的；有的是连续的，有的是离散的；有点是单峰的，有的是多峰的。

求最优解或近似最优解的方法主要有三种：枚举法，启发式算法和搜索算法：

枚举法：枚举出可行解集合内的所有的可行解，以求出精确最优解。对于连续1）

2） 3）

函数，首先要求对其进行离散化处理。该法效率较低。

启发式算法：寻求一种能产生可行解的启发式规则，以找到一个最优解或近似最优解。此法对每个问题都必须找出其特有的启发式规则，不具有通用性。 搜索算法：寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索操作，以找到问题的最优或者近似最优解。若适当利用一些启发式知识，可以在近似解的质量和求解效率上达到一种较好的平衡。

T

遗传算法中，将n维决策向量X=[x1,x2,...,xn] 用n个记号Xi (i=1,2,…,n) 所组成的符号串X表示：

X=X1X2...Xn⇒X=[x1,x2,...,xn]TX=X1X2...Xn⇒X=[x1,x2,...,xn]T ,

把每一个Xi 看作一个遗传基因，它的所有的可能取值称为等位基因。这样,X就可看做是由n个遗传基因组成的一个染色体。一般情况下，染色体的长度n是固定的，但对一些问题你也可以是变化的。根据不同的情况，这里的等位基因可以是一组整数，也可以是某一范围内的实数值，或者纯粹的一个记号。最简单的等位基因是由0和1这两个整数组成的，相应的染色体就可以表示为一个二进制符号串。这种编码形成的排列形式X就是个体的基因型，与之对应的X值就是个体的表现型。个体的适应度与其对应的个体表现型X的目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。

遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的，从而由所有的染色体X就组成了问题的搜索空间。遗传算法的运算过程也是一个反复迭代过程，第t代群体记做P(t), 经过一代遗传和进化后，得到第t＋1代群体，它们也是由多个个体组成的集合，记做P(t＋1)。

12．08

遗传算法中最优解的搜索过程也是模仿生物的进化过程，通过染色体之间的交叉和染色体的变异来完成。通过所谓的遗传算子（genetic operators）作用于群体P（t）中，进行遗传

操作，从而得到新一代群体P(t＋1)。

A. 选择（selection）： 根据各个个体的适应度，按照一定的规则或方法，从第t

代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t＋1)中。

B. 交叉（crossover）：将群体P（t）内的各个个体随机搭配成对，对每一对个体，

以某个概率（称为交叉概率，crossover rate）交换他们之间的染色体。 变异（mutation）：对群体P(t)中的每一个个体，以某一概率（称为变异概率，C.

mutation rate）改变某一个或

某一些基因座上的基因值为其他的等位基因。

图1－2 所示为遗传算法的运算过程示意图：

由该图可以看出，使用上述三种遗传算子（选择算子，交叉算子，变异算子）的遗传算法的主要运算过程如下所述：

步骤一：初始化。 设置进化代数计数器t

步骤二：个体评价。计算群体P(t)中各个个体的适应度。 步骤三：选择运算。将选择算子作用于群体。 步骤四：交叉运算。将交叉算子作用于群体。

步骤五：变异运算。将变异算子作用于群体。群体P(t)经过选择，交叉，变异运算之后得到下一代群体P(t＋1)。

步骤六：终止条件判断。若tT，则以进化过程中得到的具有最大适应度的个体作为最优解输出，终止计算。

2．2

遗传算法的手工模拟计算示例 求下述二元函数的最大值：

现对其主要运算过程作如下解释：

1） 个体编码。 遗传算法的运算对象是表示个体的符号串，所以必须把变量x1，x2编码为一种符号串。该例中，x1，x2取0～7之间的整数，可分别用3位无符号二进制整数来表示，将它们连接在一起所组成的6位无符号二进制整数就形成了个体的基因型，表示一个可行解。例如，基因型X=101110所对应的表现型是：X=[5,6]T。个体的表现型x和基因型X之间可通过编码和解码程序相互转换。

2）初始群体的产生。 遗传算法是对群体进行的进化操作，需要给其准备一些表示其实搜索点的初始群体数据。本例中，群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机方法产生。一个随机产生的初始群体如表1－1中第②栏所示。

3）适应度计算。 遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会的大小。结合本例情况，可直接用目标函数值作为个体的适应度。为计算函数的目标值，需对个体基因型X进行解码。表1－2中第③，④栏所示为初始群体中各个个体的解码结果，第⑤栏所示为各个个体所对应的目标函数值，它也示个体的适应度，第⑤栏还给出了群体中适应度的最大值和平均值。

4）选择运算。 选择运算（或称之为复制运算）把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代群体中。本例中，采用与适应度成正比的概率来确定各个个体复制到下一代群体中的数量。其具体操作过程是：先计算出群体中所有个体的适应度的总和体的相对适应度的大小fi/

∑f

i

；其次，计算出各个个

∑f

i

，如表中第⑥栏所示，它即为每个个体被遗传到下一代群

体中的概率，每个概率值组成一个区域，全部概率值之和为1；最后再产生一个0到1的随机数，依据该随机数落在哪个区域内就选择哪个个体。如表中第⑦，⑧栏所示为一个随机产生的选择结果。

5） 交叉运算。 交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某两个个体之间的部分染色体。本例采用单点交叉的方法，其具体操作过程是：先对群体进行随机配对，如表中第⑨栏所示为一种随机配对情况；其次随机设置的交叉位置，如表中第⑩栏所示为一随机产生的交叉点位置，其中的数字表示交叉点设置在该基因座之后；最后在相互交换配对染色体之间的部分基因。表中第⑾栏所示为交叉运算的结果。

6） 变异运算。 变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进行改变，它也是产生新个体的一种操作方法。本例中，采用基本位变异的方法来进行变异运算，具体操作过程是：首先确定出各个个体的基因变异位置，表中第（12）栏所示为随机产生的变异点位置，其中的数字表示变异点在该基因座处；然后依照某一概率将变异点的原有基因值取反。表中第（13）栏所示为变异结果。

对群体P(t)进行一轮选择，交叉，变异运算后可得到新一代的群体P(t＋1)。

三．遗传算法的特点

为了解决各种优化计算问题，人们提出了各种优化算法，如单纯形法，梯度法，动态规划法，分枝定界法等。而遗传算法是一类可用于复杂系统优化计算的鲁棒搜索算法，其特点如下：

1． 遗传算法以决策变量的编码作为运算对象。 2． 遗传算法直接以目标函数值作为搜索信息。 3． 遗传算法同时使用多个搜索点的搜索信息。 4． 遗传算法使用概率搜索技术。

四．遗传算法的发展

1．J.H.Holland 遗传算法的基本定理――模式定理（Schema Theorem）

2. J.D.Bagley 在遗传算法的不同阶段采用不同的选择率，有利于防止早熟。 3. K.A.De Jong 定义了评价遗传算法性能的在线指标和离线指标。 4. D.J.Goldberg 《搜索，优化和机器学习中的遗传算法》 5. J. R. Koza 遗传编程（Genetic Programming , 1992）

五．遗传算法的应用

1． 2． 3． 4． 5． 6． 7． 8． 9．

函数优化。 组合优化。 生产调度问题。 自动控制。 机器人学习。 图像处理。 人工生命。 遗传编程。 机器学习。

Chap2 基本遗传算法

一．基本遗传算法描述

Goldberg总结出了一种统一的最基本的遗传算法――基本遗传算法（Simple Genetic Algorithms，简称SGA），只使用选择算子，交叉算子和变异算子这三种基本遗传算子。

1．基本遗传算法的构成要素

1） 染色体编码方法。 基本遗传算法使用固定长度的二进制符号串儿来表示群体中

的个体，其等位基因是由二值符号集{0,1}所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来生成。

2） 个体适应度评价。 基本遗传算法按与个体适应度成正比的概率来决定当前群体

中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正或零。至于，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理。 3） 遗传算子。 使用下述三种遗传算子： A.. 选择运算使用比例选择算子；

B. 交叉运算使用单点交叉算子；

C．变异运算使用基本位变异算子或均匀变异算子。

4） 基本遗传算法的运行参数。 基本遗传算法有下述4个运行参数需要提前设定：

A. M：群体大小。一般取为20～100；

B. T：遗传运算终止进化代数。一般取为100～500； C. Pc：交叉概率。一般取为0.4～0.99; D. Pm：变异概率。一般取为0.0001~0.1。

2．基本遗传算法描述 基本遗传算法可定义为一个8元组：

SGA=(C，E，P0，M，Ф，Γ，Ψ，T) 式中 C――个体的编码方式； Φ――选择算子 ；

E――个体适应度评价函数； Γ――交叉算子； P0――初始群体； Ψ――变异算子；

M――群体大小； T――遗传运算终止条件。

用伪码表示算法如下：

12. 09

二．基本遗传算法的实现

1．个体适应度评价

对于求目标函数最小值的优化问题，理论

上只需要简单地对其增加一个负号转化为求目标函数最大值的优化问题，即：

3．单点交叉算子

具体执行过程：

A. 对群体中的个体进行两两随机配对。若群体大小为M，则共有【M/2】对相互配对的个体组。

B. 对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。若染色体的长度为n，则共有（n－1）个可能的交叉位置。

C. 对每一对相互配对的个体，依设定的交叉概率pc在交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。

4．基本位变异算子

基本位变异算子对于基本遗传算法来说，就是对需要变异的某一基因座上的原有的基因值进行取非操作。其执行过程是：

A．对个体的每一个基因座，依变异概率pm指定为变异点。

B．对每一个指定的变异点，对其基因值取非运算或者用其他等位基因值来代替，从而产生出一个新的个体。

三．基本遗传算法应用举例

1．遗传算法的应用步骤

A． 确定决策变量及其各种约束条件，即确定出个体的表现型X和问题的解

空间。 B． 建立优化模型，即确定出目标函数的类型（是求目标函数的最大值还是最

小值？）及其数学描述形式或量化方法。 C． 确定表示可行解的染色体编码方法，也即确定出个体的基因型X及遗传

算法的搜索空间。

D． 确定解码方法，即确定出由个体基因型X到个体表现型X的对应关系或

转换方法。

E． 确定个体适应度的量化评价方法，即确定出由目标函数值f（X）到个体

适应度F(X)的转换规则。

F． 设计遗传算子，即确定出选择运算，交叉运算，变异运算等遗传算子的具

体操作方法。

G． 确定遗传算法的有关运行参数，即确定出遗传算法的M,T,pc，pm等参数。

由上述构造步骤可以看出，可行解的编码方法，遗传算子的设计是构造遗传算法时需要考虑的两个主要问题，也是设计遗传算法时的两个关键步骤。对不同的优化问题需要使用不同的编码方法和不同操作的遗传算子，它们与所求解的具体问题密切相关，因而对所求解的理解程度是遗传算法应用成功与否的关键。

下图中所示为遗传算法的主要构造过程示意图。

2．基本遗传算法在函数优化中的应用举例

例：Rosenbrock函数的全局最大值计算。

maxs..t

f(x1,x2)=100(x12−x2)2+(1−x1)2−2.048≤xi≤2.048

(i=1,2)

(2−6)(2−7)

该函数有两个局部极大值，分别是f（2.048, -2.048）=3897.7342和f（-2.048, -2.048）

=3905.9262，其中后者为全局最大点。

下面介绍求解该问题的遗传算法的构造过程。

A. 确定决策变量和约束条件。式2－7已经给出了该问题的决策变量和约束条件。 B. 建立优化模型。式2－6已经给出了该问题的数学模型。

C. 确定编码方法。用长度为10位的二进制编码串来分别表示两个决策变量x1，x2。

10位二进制编码串可以表示从0到1023个均等的区域，包括端点在内有1024个不同的离散点。从离散点-2.048到2.048，依次让它们分别对应于0000000000（0）到1111111111（1023）之间的二进制编码。再将分别表示x1，x2的二个二进制编码串连接在一起，组成一个20位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。使用这种编码方法，解空间和遗传算法的搜索空间具有一一对应关系。

D. 确定解码方法。 编码的逆过程。

E. 确定个体评价方法。直接用目标函数值作为个体的适应度。

F. 设计遗传算子。选择运算采用比例选择算子；交叉运算采用单点交叉算子；变异运

算采用基本位变异算子。

G. 确定遗传算法的运行参数。对于本例，设定遗传算法的运行参数如下：

群体大小：M=80

终止条件：T=200

交叉概率：pc＝0.6

变异概率：pm＝0.001

通过运行后，通常将其进化过程用图表示出来。其中的横坐标表示进化代数，纵坐标表示适应度，适应度通常分别作出适应度的最大值和平均值的图形。

12.10

Chap 3. 遗传算法的基本实现技术

一． 编码方法

编码是应用遗传算法时要解决的首要问题，它除了决定了个体的染色体排列形式之外，它还决定了个体从搜索空间的基因型变换到解空间的表现型时的解码方法，还影响到交叉算子，变异算子等遗传算子的运算方法。

De Jong曾经提出了两条操作性较强的实用编码原则：

A. （有意义积木编码原则）：应使用能易于产生说求问题相关的且具有低价，短定义

长度模式的编码方案。

B. （最小字符集编码原则）：应使用能使问题得到自然表示或描述的具有最小编码字

符集的编码方案。

上述编码原则仅仅给出了设计编码方案时的一个指导性大纲，它并不适合于所有的问题。所以对于实际应用问题，仍必须对编码方法，交叉运算方法，变异运算方法，解码方法等统一考虑，以寻求到一种对问题的描述最为方便，遗传运算效率最高的编码方案。

1．二进制编码方法

二进制编码符号串的长度与问题所要求的求解精度有关。假设某一参数的取值范围

l是[Umin，Umax ],我们用长度为l 的二进制编码符号串来表示该

参数，则它总共能够产生2

种不同不编码，若使参数编码

时对应关系如下：

则二进制编码的编码

精度为：

假设某一个体的编码是：

二进制编码方法有下述一些优点：

1） 编码，解码操作简单易行；

2） 交叉，变异等遗传操作便于实现；

3） 符合最小字符集编码原则；

4） 便于利用模式定理对算法进行理论分析。

2．格雷码编码方法

二进制编码不便于反映出所求问题的结构特征，对于一些连续函数的优化问题的，也由于遗传运算的随机特性而使得其局部搜索能力较差。为此，人们提出了格雷码（Gray code）来对个体进行编码。

格雷码是这样的一种编码方法，其连续的两个整数所对应的编码值之间

仅仅只有一个码位是不同的，其余码位都完全相同。例如下表所示：

假设有一个二进制编码为

由二进制编码到

格雷码的转换公式是：

由格雷码到二进制码的转换公式是：

其中的

浮点数编码方法有下面几个优点：

1） 适合于在遗传算法中表示范围较大的数；

2） 适合于精度要求较高的遗传算法；

3） 便于较大空间的遗传搜索；

4） 改善了遗传算法的计算复杂性，提高了运算效率；

5） 5便于遗传算法与经典优化方法的混合使用；

6） 便于设计针对问题的专门知识的知识型遗传算子；

7） 便于处理复杂的决策变量约束条件。

4．符号编码方法

符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义，而只有代码含义的符号集。这个符号集可以是一个子母表，如{A,B,C,…};也可以是一个数字序列号表，如{1,2,3,…};还可以是一个代码表，如{A1,A2,A3,…}等等。

符号编码的主要优点是：

1） 符合有意义积木块编码原则；

2） 便于在遗传算法中利用所求解问题的专门知识；

3） 便于遗传算法与相近算法之间的混合使用。

5．多参数级联编码方法

将各个参数分别一某种编码方法进行编码，然后将它们的编码按一定顺序连接在一起就组成了表示全部参数的个体编码。这种编码方法称为多参数级联编码方法。

这种方法中，各个参数的编码可以是二进制，格雷码，浮点数或者符号编码等，每个参数可以具有不同的上下界，不同的编码长度或者编码精度。

6．多参数交叉编码方法

基本思想：将各个参数中起主要作用的码位集中在一起，这样他们就不易于被遗传算子破坏。 在进行多参数交叉编码时，可先对各个参数进行分组编码（假设共有n个参数，每个参数都用长度为m的二进制编码串来表示）；然后取各个参数编码串中的最高位联接到一起，以他们作为个体编码串的前n位编码；再…..

多参数交叉编码方法特别适合于各个参数之间的相互关系较强，各个参数对最优解的贡献相当时的优化问题。

12．11

二． 适应度函数

遗传算法中，使用适应度来度量群体中各个个体在优化计算中有可能达到或接近于或有助于寻找到最优解的优良程度。适应度较高的个体遗传到下一代的概率就较大；而适应度较小的个体，遗传到下一代的概率就相对小一些。度量个体适应度的函数称为适应度函数（Fitness Function）。

1．目标函数与适应度函数

评价个体适应度的一个过程是：

1) 对个体编码串进行解码处理后，可得到个体的表现型；

2) 对个体的表现型可计算出对应个体的目标函数值；

3) 根据优化问题的类型，由目标函数值按一定的转换规则求出个体的

适应度。

2．适应度尺度变换

1）早熟现象：在遗传算法运行的初期阶段，群体中可能会有少数几个个体的适应度非常高，若按照常用的比例选择算子来确定个体的遗传数量时，则可能它们占的比例非常高，甚至全部是它们组成。这样，产生新个体作用较大的交叉算子就起不了什么作用，使群体的多样性降低，所求的解停留在某一局部最优点上。

2) 在遗传算法运行的后期，群体中所有个体的平均适应度可能会接近于群体中最佳个体的适应度，它们之间的无竞争力，进化过程退化成了一种随机选择的过程，导致无法对某些重点区域进行重点搜索，从而影响遗传算法的运行效率。

为了克服第一种情况，我们希望在遗传算法的初期阶段，算法能够对一些适应度较高的个体进行限制，降低其适应度与其他个体适应度之间的差异程度，限制其遗传到下一代的数量，保证群体的多样性；为了克服第二种情况，我们希望在遗传算法的后期阶段，算法能够对个体的适应度进行适当的放大，扩大最佳个体适应度与其他个体适应度之间的差异程度，以提高个体之间的竞争性。

这种对个体适应度所做的扩大或缩小变换就称为适应度尺度变换（Fitness Scaling）。 目前常用的个体适应度尺度变换方法主要有三种：线性尺度变换，乘幂尺度变换和指数尺度变换。

A． 线性尺度变换。 变换公式如下：

F ‘ =aF+b （3－8）

系数a，b直接影响到线性尺度变换的大小，对其选取有一定的要求：

a．制度变换后全部个体的新适应度的平均值F’avg要等于其原适应度平均值

Favg。即： F’avg＝Favg （3－9）

这一条是为了保证群体中适应度接近于平均适应度的个体能够有期待的

数量被遗传到下一代群体中。

b. 尺度变换后群体中新的最大适应度F’max要等于其平均适应度Favg的指定倍

数。即： F’max＝C. Favg （3－10）

式中，C为最佳个体的期望复制数量，对于群体规模大小为50～100个个

体的情况，一般选取1.2~2。这条是为了保重群体中最好的个体能够期望

复制C倍到新一代群体中。

B． 乘幂尺度变换。 乘幂尺度变换公式为

k F ‘ =F （3－11）

k于所求解的问题有关，并且在算法的执行过程中需要不断对其进行修正

才能够使得其尺度变换满足一定的伸缩要求。

C． 指数尺度变换。 变换公式如下：

F’ ＝exp（－βF） （3－12）

式中β决定了选择的强制性，β越小，原有适应度较高的个体的新适应度就

越与其他个体的新适应度相差较大，即越增加了选择该个体的强制性。

三．选择算子

选择操作建立在对个体的适应度进行评价的基础之上。选择操作的主要目的是为了避免基因缺失，提高全局收敛性和计算效率。

1． 比例选择（Proportional Model）

2． 最优保存策略

选择最好适应度的个体作为种子选手，直接保留到下一代。其具体操作过程是：

1） 找出当前群体中适应度最高的个体和适应度最低的个体；

2） 若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度还要

高，则以当前群体的最佳个体作为新的迄今为止的最好个体；

3） 用迄今为止的最好个体替换掉当前群体中的最差个体。

最优保存策略可视为选择操作的一部分，它可以保证迄今为止所得到的最优个体不会被交叉，变异等遗传运算所破坏，它是遗传算法收敛的一个重要保证。但是另一方面，它也容易使得某个局部最优个体不易被淘汰反而快速扩散，从而使得算法的全局搜索能力不强。所以该方法一般要与其他一些选择操作方法配合起来使用，方可有良好的效果。

3．确定式采样选择（Deterministic Sampling）

其具体

操作过程是：

1） 计算群体中各个个体在下一代群体中的期望生存数模Ni ：

2） 用Ni的整数部分确定各个对应个体在下一代群体中是生存数目。由该步共可确定

处下一代群体中的个体总数M’（对其整数部分求和）；

3） 按照Ni的小数部分对个体进行降序排序，顺序取前M-M’个个体加入到下一代群

体中。至此可完全确定处下一代群体中的M个个体。

这种选择操作方法可保证适应度较大的一些个体一定能够被保留在下一代群体中。

4．无回放随机选择

这种选择操作也叫做期望值选择方法（Expected Value Model），其基本思想是根据每个个体在下一代群体中的生存期望值进行随机选择运算。

其具体操作过程是：

1） 计算群体中每个个体在下一代群体中的生存期望数目Ni：

2） 若某一个体被选中参与交叉运算，则它在下一代中的生存期望数模减去0.5，若某

一个个体未被选中参与交叉运算，则它在下一代中的生存期望数目减去1.0；

3） 随着选择过程的进行，若某个个体的生存期望数目小于0时，则这个个体再也不会

被选中。

5．无回放余数随机选择（Remainder Stochastic Sampling with Replacement）

其具体操作过程是：

1） 计算群体中每个个体在下一代群体中的生存期望数目Ni：

2） 用Ni的整数部分确定各个对应个体在下一代群体中是生存

数目。由该步共可确定

处下一代群体中的个体总数M’（对其整数部分求和）；

3） 以

12．13

6．排序选择（Rank-Based Model）

其主要着眼点是个体适应度之间的大小关系，对个体适应度是否取正值或负值以及个体适应度之间的数值差异程度并无特殊要求。

其主要思想是：对群体中的所有个体按其适应度大小进行排序，基于这个排序来分配各个个体被选中的概率。其具体操作过程是：

1） 对群体中的所有个体按照其适应度大小进行降序排序；

2） 根据具体求解问题，设计一个概率分配表，将各个概率值按上述排序次序分配

给各个个体；

3） 以各个个体所分配到的概率值作为其能够被遗传到下一代的概率，基于这些概

率值所用比例选择的方法来产生下一代群体。

7．随机联赛选择（Stcochastic Tournament Model）

它也是一种基于个体适应度之间大小关系的选择方法。其基本思想是：每次选择

几个个体之间适应度最高的一个个体遗传到下一代全体中。

此方法中，每次进行适应度大小比较的个体数目称为联赛规模。一般情况下，

联赛规模N的取值为2。其具体操作过程是：

1）从群体中随机选择N个个体进行适应度大小的比较，将其中适应度最高的个

体遗传到下一代群体中；

2）将上述过程重复M次，就可以得到下一代群体的M个个体。

四．交叉算子

遗传算法中的交叉运算，是指对两个互相配对的染色体安装某种方式互相交换其

部分基因，从而形成两个新的个体。遗传算法中，在交叉运算之前先对群体中的个体进行配对，最常用的配对策略是随机配对。交叉运算一般要求它即不要太多地破坏个体编码串中表示优良性状的优良模式，又要能够有效地产生出一些较好的新个体模式。另外，交叉算子的设计要和个体编码设计统一考虑。

交叉算子的设计包括一下两方面的内容：

1） 如何确定交叉点的位置？

2） 如何进行部分基因交换？

最常用的交叉算子是单点交叉算子。

1．单点交叉（One－point Crossover）

它是指在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。单点交叉的重要特点是：若邻接基因座之间的关系能提供较好的个体性状和较高的个体适应度的话，则这种单点交叉操作破坏这种个体性状和降低个体适应度的可能性最小。

2．双点交叉与多点交叉（Two-point Crossover）

它是指在个体编码串中随机设置了二个交叉点，然后再进行部分基因交换。其具体操作过程是：

1） 在相互配对的两个个体编码串中随机设置两个交叉点；

2） 交换两个个体在所设定的两个交叉点之间的部分染色体。

将单点交叉和双点交叉的概率加以推广，可以得到多点交叉（multi－point crossover）的概念。

一般来说，不要使用多点交叉算子，它有可能破坏一些号的模式。交叉点越多，

优良模式被破坏的可能性越大。

指两个配对个体的每个基因座上的基因都以相同的交叉概率进行交换，从而形成两个新的个体。均匀交叉实际上可以归属于多点交叉的范围，其具体运算可通过设置一屏蔽字来确定个体的各个基因如何由哪一个父代个体来提供。其具体操作过程如下：

1）随机产生一个与个体编码串长度等长的屏蔽字W=w1w2…wi…wl,其中l为编码串长度；

2）由下述规则从A,B两个父代个体中产生出两个新的子代A’,B’：

若wi＝0，则A’在第i个基因座上的基因值继承A对应基因值，B’在第i个基因座上的基因值继承B的对应的基因值。

4．算术交叉（Arithmetic Crossover）

指由两个个体的线性组合而产生出两个新的个体，通常这类交叉操作的对象是浮

点数编码所表示的个体。XB

假设在两个个体

XA，XB之间进行算术交叉，则交叉运算后所产生出的连歌新个

体是： ttt

式中，a为一参数，它可以是一个常数，此时所进行的交叉运算称为均匀算术交叉；它也可以是一个由进化代数所确定的变量，此时称为非均匀算术交叉。其主要操作过程是：

1） 确定两个个体进行线性组合时的系数a；

2） 依据（3－14）生成两个新的个体。

五．变异算子

所谓变异运算，指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位来替换，从而形成一个新的个体。

交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力；而变异运算只是产生新个体的辅助方法，但是它是必不可少的一个运算步骤，决定了遗传算法的局部搜索能力。

使用变异算子主要有以下两个目的：

1） 改善遗传算法的局部搜索能力；

2） 维持群体的多样性，防止出现早熟现象。

变异算子的设计内容包括如下两个方面的内容：

1） 如何确定变异的位置？

2） 如何进行基因值替换？

最简单的变异算子是基本位变异算子。

1．基本位变异（Simple Mutation）

它是指对个体编码串中以变异概率pm随机指定的某一位或某几位基因座上的基因值作变异运算。

它是指分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。其具体操作过程是：

1） 依次指定个体编码串中的每个基因座为变异点；

2） 对每个变异点，以变异概率p从对应基因的取值范围内取一随机数来替代原有基

因值。

均匀变异操作特别适合应用于遗传算法的初期运行阶段，它使得搜索点可以在整个搜索空间内自由地移动，从而可以增加群体的多样性，使算法处理更多的模式。

3．边界变异（Boundary Mutation）

它是均匀变异操作的一个变形遗传算法，在进行操作时，随机地取基因座的二个对应边界基因值之一去替代原有基因值。

12.14.2003

4．非均匀变异（Non－uniform Mutation）

均匀变异操作取某一范围内均匀分别的随机数来替换原有基因值，可使得个体在搜索空间自由移动。但另一个方面，它却不能够对某一重点区域进行局部搜索。为此，我们对原有基因值作一随机扰动，以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行变异运算后，相当于整个解向量在解空间中作了一个轻微的变得。这种变异操作方法就称为非均匀变异

非均匀变异的具体操作过程与均匀变异类似，但它重点搜索原个体附近的微小区域。 在进行由X=x1x2…xk…xl向X’＝x1x2…x’k…xl的非均匀变异操作时，若变异点xk

处的基因值取值范围为[Ukmin, Ukmax]，则新的基因值x’k由下式确定：

kk式中， ∆(t,y)（y代表Umax−vk和vk−Umin）表示[0,Y]范围内符合非均匀分布的一个随

机数，要求随着进化代数t的增加，∆(t,y)接

近于0的概率也逐渐增加。例如，∆(t,y)可安照下式定义：

六．遗传算法的运行参数

遗传算法中需要选择的运行参数主要有个体编码串长度l，群体大小M，交叉概率pc，变异概率pm，终止代数T，代沟G等。其选取的一般规则是：

1．编码串长度l。 使用二进制编码来表示个体时，编码串长度l的选取与问题所要求的求解精度有关；使用浮点数编码来表示个体时，编码串长度l与决策变量的个数n相等；使用符号编码来表示个体时，编码串长度l由问题的编码方式来确定；另外，也可以使用变长度的编码来表示个体。

2 群体大小M。群体大小M表示群体中所含个体的数量。当M取值较小时，可提高遗传算法的运算速度，但却降低了遗传算法的多样性，有可能会引起早熟现象；而当M取值交大时，又会使得遗传算法的运行效率降低。一般建议的取值范围是20～100。

3 交叉概率pc 。交叉概率一般取值较大。但过大容易破坏群体中的优良模式，若过小产生新个体的速度较慢。一般建议取值范围是0.4~0.99。另外，也可以使用自适应的思想来确定交叉概率。

4 变异概率pm。变异概率较大时，可能破坏较好的模式；太小则不利于产生新个体和抑制早熟现象。一般建议范围是0.0001~0.1。另外也可以使用自适应的思想来确定变异概率。

5 终止代数T。一般建议取值范围是100～1000，它还可以利用某种判定准则，判定出当群体已经进化成熟且不再有进化趋势时就可以终止算法的运行过程。常用的判定准则有下面两种：

1) 连续几代个体平均适应度的差异小于某一个极小的阈值；

2）群体中所有个体的适应度的方差小于某一个极小的阈值。

6．代沟G。代沟G是表示各代群体之间个体重叠程度的一个参数，它表示每一个群体中被替换掉的个体在全部个体中所占的百分率。

七．约束条件的处理方法

实际应用中的优化问题一般都含有一定的约束条件，它们的描述形式各种各样。目前尚无一般化方法，只能是针对具体应用问题及约束条件的特征，再考虑遗传算法中遗传算子的运行能力，选用不同的处理方法。在构造遗传算法时，处理约束条件的常用方法主要有如下三种：搜索空间限定法，可行解变换法，惩罚函数法。

1．搜索空间限定法

其基本思想是：对遗传算法的搜索空间的大小加以限制，使得搜索空间中表示一个个体的点与解空间中表示一个可行解的点有一一对应的关系。

1）用编码方法来保证总是能够产生出在解空间中有对应可行解的染色体。这个实现要求我们设计出一种比较好的个体编码方案。

2）用程序来保证直到产生出解空间中有对应可行解的染色体之前，一直进行交叉运算和变异运算。

2．可行解变换法

其基本思想是：在由个体基因型到个体表现型的变换中，增加使其满足约束条件的处理过程。即寻找出一种个体基因型和个体表现型之间的多对一的变换关系，使进化过程中所产生的个体总能够通过这个变换而转化成解空间中满足约束条件的一个可行解。

3．惩罚函数法

其基本思想是：对在解空间中无对应可行解的个体，计算其适应度时，处以一个惩罚函数，从而降低该个体的适应度，使该个体被遗传到下一代群体中的机会减少。即用下式对个体的适应度进行调整：

F(x,y)=f(x,y)-a•max{0,x2+y2−1}

式子中，F(X)为原适应度，F’（X）为考虑了惩罚函数之后的新适应度，P（X）是惩罚函数。

例如：在处理x2＋y2

F(x,y)=f(x,y)-a•max{0,x2+y2−1}

式中，a>0就是确定惩罚函数作用强度的一个系数。

八．遗传算法的工具箱

第四章 遗传算法的高级实现技术

一． 倒位算子

1．倒位操作（Inverse Operation）

它是指颠倒个体编码串中随机指定的二个基因座之间的基因排列顺序，从而形成一个新的染色体。其具体操作过程是：

1） 在个体编码串中随机指定二个基因值之后的位置为

倒位点；

2） 以倒位概率pi颠倒这二个倒位点之间的基因排列顺序。如下例所示：

要说明的是，倒位算子只是个体编码串重新排序算子的一种，还有其他的一些重新排序算子，将在后面介绍。

2003-12-16

2．倒位算子应用示例

下面我们以栅格空间内的移动机器人路径规划为例，说明倒位算子的作用。

如图4－1所示为一移动机器人的2维规划空间，整个空间依据机器人的尺寸被划分为一块一块的栅格，每个栅格有一标号，图中带有

阴影的栅格表示障碍物，S为机器人行走路线的起点，G为终点。

用遗传算法进行及其人路径规划时，可取机器人移动过程中所经过的栅格之标号的顺序排列来作为一个个体（一条行走线路）的表现形式，如下所示即表示一条行走线路：

PATH：0－3－9－13－29－39 （虚线所示路线）

若在上述行走线路的第二个路径点和第三个路径点之间进行倒位操作，则可得到一条新的行走路线：

PATH：0－9－3－13－29－39 （实线所示路线）

如果以路径长短作为路径优劣的评价标准的话，则新的行走路线比原有行走路线好。

二． 二倍体与显性操作算子

1．二倍体结构的生物基础

二倍体结构中各个基因有显性基因（Dominance Gene）和隐形基因（Recessive Gene）之分。二类基因使个体所呈现出的表现型由下述规则来决定：在每个基因座上，当两个同源染色体其中之一为显性时，则该基因所对应的性状表现为显性；而仅当两个同源染色体中对应基因皆为隐性时，该基因所对应的性状才表现为隐性。

上述性状的特点是：显性基因在纯合子（AA）或杂合子（A或a）情况下均能够被表现出，而隐性基因只能在纯合子（aa）情况下才能被表现出。

二倍体的意思：

1） 二倍体的记忆能力，使得生物能够记忆以前所经历过的环境变化，使得生物的遗传进化过程能够快速地适应环境的变化。

2）显性操作的鲁棒性，它使得即使随机选择了适应度不高的个体，而在显性操作的作用下，能够用其另一同源染色体对其进行校正，从而避免这个有害选择所带来的不利之处。这样能够提高遗传算法的运行效率，维护好的搜索群体。

2． 二倍体结构在遗传算法中的实现方案

Hollstien提出了二倍体与显性操作的双基因座显性映射方法。该方法中，每个二进制基因用两个基因来描述，一个称为函数基因，取通常含义的0或1直；另外一个称为修饰基因，取值为M或m，其中M表示显性基因，m表示隐性基因。对函数基因取值为0的基因，当两个同源染色体中至少有一个修饰基因是M时，则该基因呈显性，否则该基

因呈隐性。这种映射关系如图4－2所示。

3．使用双倍体的遗传算法描述

算法DiploidyGA

1） 初始化，并设置进化代数计数器初值：t=1；

2） 随机产生具有二倍体结构的初始群体P（t）；

3） 对初始群体P（t）进行显性操作；

4） 评价初始群体P（t）中各个个体的适应度；

5） 交叉操作。有每两个随机配对的二倍体个体进行交叉操作时，共可产生四个单倍

体个体；

6） 变异操作。对群体中的各个个体进行变异操作时，需要考虑隐性基因的作用；

7） 对群体进行显性操作；

8） 评价现在群体中的各个个体的适应度；

9） 个体选择，复制操作；

10） 终止条件判断。若不满足终止条件，则跳转到（5）步，继续进化；否则，输

出当前最优个体，算法结束。

2003-12-18

三．变长度染色体遗传算法

1. 变长度染色体遗传算法的编码与解码

将常规遗传算法的染色体编码串中各基因座位置及相应基因组成一个二元组，把这个二元组按一定顺序排列起来，就组成了变长度染色体的一种通用染色体编码方式。一般它可以表示为：

Xm：（i1，v1）（i2，v2）… （ik，vk）… （in，vn）

其中ik是所描述的基因在原常规染色体中的基因座编号，vk为对应的基因值。

对于所求解的问题，若使用常规遗传算法时的染色体长度固定为l，各基因值取自集合V，则有：

1≤ik≤l （k＝1，2，…,n） (4-1)

vk∈V (k=1,2,…,n) (4-2)

m 例如，常规染色体X：100101，表示为X：（1,1）(2,0)(3,0)(4,1)(5,0)(6,1)

2. 切断算子与拼接算子

变长度染色体遗传算法除了使用常规遗传算法中的选择算子合变异算子以外，不再使用交叉算子，而代之为使用下述的切断算子和拼接算子，以它们作为产生新个体的主要遗传算子。

1） 切断算子（Cut Operator）

切断算子以某一预先指定的概率，在变长度染色体中随机选择一个基因座，在该处将个体的基因型切断，使之称为二个个体的基因型。

2） 拼接算子（Splice Operator）

拼接算子以某一预先指定的概率，将二个个体的基因型连接在一起，使它们合并为一个个体的基因型。

3．变长度染色体遗传算法的算法结构

与基本遗传算法类似

四．小生境遗传算法

4．4．1 小生境与遗传算法

让遗传算法的个体在一个特定的生存环境中进化，以找出更多的最优解，从而利于求解出多峰值函数的优化计算问题。

4．4．2 遗传算法中小生境的实现方法

1． 基于预选择（Preselection）的小生境实现方法

其基本思想是：仅当新产生的子代个体的适应度超过其父代个体的适应度时，所产生出的子代个体才能替换其父代个体而遗传到下一代群体中，否则父代个体仍保留在下一代群体中。

2．基于排挤（Crowding）的小生境实现方法

其基本思想是：设置一排挤因子CF，由群体中随机选择的1/CF个个体组成排挤成员，然后依据新产生的个体与排挤成员的相似性来排挤掉一些与排挤成员相类似的个体。这里的个体的相似性可用个体编码串之间的海明距离来度量。

3．基于共享函数（Sharing）的小生境实现方法

其基本思想是：通过反映个体之间相似程度的共享函数来调整群体中各个个体的适应度，从而在这以后的群体进化过程中，算法能够依据这个调整后的新适应度来进行选择运算，以维护群体的多样性，创造出小生境的进化环境。

共享函数（Sharing Function）是表示群体中两个个体之间密切关系程度的一个函数，可记为S（dij），其中dij表示个体i和个体j之间的某种关系。

2003-12-22

4．4．3 小生境遗传算法在多峰值函数全局最优中的应用

基本思想：首先两两比较群体中各个个体之间的距离，若这个距离在预先指定的距离L之内的话，再比较两者之间的适应度的大小，并对其中适应度较低的个体施加一个较强的惩罚函数，极大地降低起竞争能力，这样，对于在预先指定的某一距离L之内的两个个体，其中较差的个体经处理后，其适应度变得更差，它在后面的进化过程中被淘汰的概率就极大。也就是说，在距离L之内将只存在一个优良的个体，从而既维护了群体的多样性，又使得各个个体之间保持一定的距离，并使得个体能够在整个约束空间中分散开来，这样就实现了一种小生境遗传算法。

小生境算法描述如下：

a．设置进化代数计数器t＝1，随机生成M个初始个体组成初始群体P（t），并求出各个个体的适应度F i（i＝1，2，…，M）；

b．根据各个个体的适应度对其进行降序排序，记忆前N个个体（N

c．选择运算。对群体P（t）进行比例选择运算，得到P’（t）；

d．交叉算子。对选择出的个体集合P’（t）做单点交叉运算，得到P’’（t）；

e．变异运算。对P’’（t）做均匀变异运算，得到P’’’(t)；

f．小生境淘汰运算。将e中得到的M个个体和第b步所记忆的N个个体合并在一起，得到一个含有

M＋N个个体的新群体；对这M+N个个体，按照下式求出每两个个体Xi和Xj之间的海明距离：

||Xi−Xj||=M+N−1ij==1,2,...,i+1,...,M+N)

当 ||Xi-Xj||

g．更加这M+N个个体的新适应度对各个个体进行降序排序，记忆前N个个体； h．终止条件判断。若不满足终止条件，则：更新进化代数计数器t＝t＋1，并将第g步排序中的前M个个体作为新的下一代群体P（t），然后转到第c步；若满足终止条件，则：输出计算结果，算法结束。

例：Shubert函数的全局最优化计算。

minf(x1,x2)={∑i•cos[(i+1)x1+i]}*{∑i•cos[(i+1)x2+i]}

i=1i=155

S.T.−10≤xi≤10(i=1,2)

上述函数共有760个局部最优点，其中18个是全局最优点，全局最优点处的目标函数值是fopt（x1，x2）＝－186. 731。

用上述小生境遗传算法求解该例题时，可用下式进行目标函数值到个体适应度的变换处理：

F(x1,x2)={1−0.05f(x1,x2)

1(if(iff(x1,x2)

f(x1,x2)≥0)

运用该算法时所使用的运行参数是：

l＝20×2（二进制编码串长度，其中每个变量用10位二进制编码来表示）

－30 M=50，T=500，pc＝0.8，pm＝0.1，L=0.5 (小生境的距离参数) Penlty＝10（罚函数）

4．5 混合遗传算法

4．5．1 混合遗传算法的思想

遗传算法的主要问题：容易产生早熟现象，局部寻最优能力较差，并且通常其结果比针对问题的启发式算法的求解效率要差，另外，遗传算法也无法避免多次搜索同一个可行解。

混合遗传算法的思想：

a．引入了局部搜索过程。

b. 增加了编码变换操作过程。

混合遗传算法的基本构成原则

a．尽量采用原有算法的编码。

b．利用原有算法的优点。

c. 改进遗传算子。

2003-12-23

4．5．2 模拟退火算法（Simulated Annealing）

模拟退火算法是基于金属退火的机理而建立起的一种全局最优化方法，它能够以随机搜索技术从概率的意义上找出目标函数的全局最小点。模拟退火算法的构成要素如下：

1．搜索空间Ω

搜索空间也称为状态空间，它由可行解的集合所组成，其中的一个状态x就代表一个可行解。

2．能量函数E(x)

能量函数也就是需要进行优化计算的目标函数，其最小点为所求的最优解。

3．状态转移规则P

状态转移是指从一个状态xold（一个可行解）向另一个状态xnew（另一个可行解）的转移概率，它与当前的温度参数T有关。

4．冷却进度表T(t)

冷却进度表是指从某一高温状态T0向低温状态冷却时的降温管理表。

假设时刻t的温度T(t)，则经典的模拟退火算法的降温方式为：

nf(x1,x2,...,xn)=∑ciximax

i=1ns..t∑wixi≤v 

i=1xi∈{0,1}(i=1,2,...,n)

而快速模拟退火算法的降温方式为：

T(t)=T0 1+t

这两种方式都能够使得模拟退火算法收敛于全局最小点。

另外，在实际应用中，为计算简便起见，也可用下式进行温度管理：

T(t)＝k·T（t－1）

式子中，k为略小于1.0的系数。

假设在状态xold时，系统受到某种扰动而可能会使其状态变为xnew。与此相对应，系统的能量也可能会从E(xold)变成E(xnew)。系统由状态xold变成xnew的接受概率可由下面的Meteopolis规则来确定：

1ifE(xnew)

上式的含义是：当新状态使系统的能量函数值减小时，系统一定接受这个新的状态；而当新状态使系统的能量函数值增加时，系统以某一概率接受这个新的状态。

固定温度参数T，反复进行状态转移过程，接受概率p（x）将服从Gibbs分布：

p(x)=1E(x)exp(−) ZT

式中，Z是使得概率值正规划的系数。

模拟退火算法可以描述如下：

4．5．4 遗传模拟退火算法

基本思想：遗传模拟退火算法是将遗传算法与模拟退火算法相结合而构成的一种优化算法。遗传算法的局部搜索能力较差，但把握搜索过程总体的能力较强；而模拟退火算法具有较强的局部搜索能力，并能使搜索过程避免陷入局部最优解，但模拟退火算法却对整个搜索空间的状况了解不多，不便于使搜索过程进入最有希望的搜索区域，从而使得模拟退火算法的运行效率不高。

因而将两者结合，取长补短，可能开发出性能优良的全局搜索算法。

遗传模拟退火算法描述：

另一种构造混合遗传算法的方法是在模拟退火算法中溶入遗传算法的思想。例如，Mathefound所开发的并行组合模拟退火算法PRSA(Parellel Recombination Simulated

Annealing)，其算法描述为：

4．5．5 混合遗传算法在求解背包问题中的应用

背包问题的一般提法是：已知n个物品的重量及其价值分别为wi>0和ci>0（i＝1,2,…n）,背包的容量假设为v>0，如何选择哪些物品装入该背包可使得在背包的容量约束限制之内所装物品的总价值最大？

该问题的模型可表示为下述整数规划模型：

nf(x1,x2,...,xn)=∑ciximax

i=1ns..t∑wixi≤v i=1xi∈{0,1}(i=1,2,...,n)

式中xi为0－1决策变量，xi＝1表示将物品i装入背包中，反之则表示不装入。

背包问题是一个典型的NP完全（Nondeterministic Polynomial Completeness）难题，对该问题的求解可以解决管理中的资源分配, 投资决策, 装载问题等实际问题，采用的方法主要是一些启发式算法（如贪婪算法等），也可以用遗传算法来求解该问题。

采用基于贪婪算法的染色体编码串转换算法的描述如下：

第五章 并行遗传算法

5．1 遗传算法的并行化

5．1．1 遗传算法并行化的目的

主要目的的提高遗传算法的运行速度。

5．1．2 遗传算法的并行性分析

Goldberg对基本遗传算法的归纳

遗传算法可以从下面四种并行性方面着手对其进行改进和发展。

1．并行性I: 个体适应度评价的并行性

2．并行性II： 整个群体中各个个体适应度评价的并行性

3．并行性III：子代群体产生过程的并行性

4．并行性IV：基于群体分组的并行性

5．1．3． 并行遗传算法的实现方法分类

为了提高遗传算法的运算速度，改善其求解性能，对基于上述各种并发机制的发掘和利用，人们在并行计算机或局域网环境下开发出了多种不同的并行遗传算法。概况起来，实现这些并行遗传算法的方法大体上可以分为如下两类：标准型并行方法（Standard Parallel Approach）和分解型并行方法（Decomposition Parallel Approach）。

标准型并行方法并未改变串行遗传算法的基本特点，它在一个总体的环境中实现进化计算，所以它需要实用一个统一的群体，实现时也需要有一个全局存储器，还需要有一个同意的控制机构来协调群体的遗传进化过程及群体之间的通讯过程。

分解型并行方法将整个群体分解为几个子群体，各个子群体被分配在不同的处理机上，它们各自串行运行所在处理机上的基本遗传算法，然后在适当的时候，各处理机之间相互交换一些信息。

遗传算法的并行机制

2003-12-28

5．1．4 并行遗传算法的硬件支持环境及性能评价

加速比

设T1为某算法在串行计算机上的运行时间，Tp是该算法在由p各处理机说构成的并行机上的运行时间，则此算法在该并行计算机上的加速比Sp定义为：

Sp＝T1/Tp

5．2 实现并行遗传算法的标准型并行方法

5．2．1 标准型并行方法的基本思想

这类并行方法不改变简单遗传算法的基本结构特点，即群体的全部个体都在统一的环境中进化。其基本出发点是从局部的角度开发个体进化的并行性。在应用遗传算法方法进行优化计算时，各个个体的适应度评价以及染色体的选择、交叉和变异等操作是可以相互单独进行的。这样，利用具有共享存储器结构的并行机，就可对群体的进化过程进行并行计算以达到提高遗传算法运行速度的目的。这类方法在个体适应度计算量较大的场合比较有效。

5．2．2 算法实例

略

5．3 实现并行遗传算法的分解型并行方法

5．3．1 分解型并行方法的基本思想

这种方法将整个群体划分为几个子群体，各个子群体分配在各自的处理机或局域网工作站上独立地进行简单遗传算法的进化操作，在适当的时候各个子群体之间相互交换一些信息。其基本出发点是从全局的角度开发群体进化的并行性。这种方法改变了简单遗传算法的基本特点，即各子群体独立地进行进化，而不是全部群体采用同一机制进化。

在构造这种并行遗传算法时，需要考虑下述几个主要问题： 1．子群体划分方式。 2．信息交换方式。

1） 参加信息交换的对象（哪几个处理机之间可以相互交换信息？）； 2） 交换信息的内容（是随机交换，还是择优交换？）； 3） 交换时间或频率（何时交换？）； 4） 交换信息量（交换几个个体？）

5．3．2 分解型并行遗传算法的形式化定义与描述

基于群体分组的并行遗传算法的运算过程是：各个处理机运行各自的基本遗传算法，对它自身所带的存储器中的M/p 个个体进行遗传算法操作；当达到一个预先指定的信息交换时间T时，每个处理机pi发送需要交换的信息Z到其信息交换对象X；同时，它也接受

i

来自于X的信息，用该信息来替换本处理机上的某一个或者某一些个体。上述过程不断地迭代进行，直到满足某个终止条件为止。 5．3．3 子群体信息交换模型

实现分解并行遗传算法所采用的群体模型主要有三种： 1．踏脚石群体模型（Stepping－stone Model） 2．岛屿群体模型（Island Model）

3． 邻居群体模型（Neighborhood Model）

i

5．4 伪并行遗传算法

5。4．1 伪并行遗传算法的基本思想

在简单遗传算法中，利用并行遗传算法的思想，将群体划分为一些子群体，各子群

体按一定的模式分别进行独立进化，在适当的时候，某一些子群体之间交换一些信息，这样可以维持群体的多样性，从而达到抑制早熟现象的效果。 5

．4．2 伪遗传算法的应用举例

例1． 六峰值驼背函数（Six－hump Camel Back Function）的全局最小值计算问题：

该函数有六个局部最小点，其中（－0.0898,0.7126

）和（0.0898 –0.71216）为全局最小点,最小值为 –1.031628。

例2． Rosenbrock函数的全局最大值计算问题：

该函数有两个局部最大点（f2.048, -2.048）=3897.7342 和（f-2.048, -2.048）=3905.9262，其中，后者为全局最大点。

第六章 遗传算法的数学理论

6．1 模式定理

6．1．1 模式

【定义6.1 】 模式（Schema）表示一些相似的模块，它描述了在某些位置上具有相似结构特征的个体编码串的一个子集。

以二进制编码方式为例，个体是由二值字符集V＝{0, 1}中的元素组成的一个编码串，而 模式却是由三值字符集V+={0, 1, * } 中的元素说组成的一个编码串，其中的“*”表示通配符，它既可被当作“1”，也可被当作“0”。

例如， 模式 H＝11**1 描述了长度为5，且在位置1、2、5取值为“1”的所有字符串的集合{ 11001，11011，11101，11111}。

遗传算法的本质是对模式所进行的一系列运算，即通过选择算子将当前群体中的优良模式遗传到下一代群体中，通过交叉算子对模式的重组，通过变异算子对模式的突变。通过这些遗传运算，一些较差的模式逐步被淘汰，而一些较好的模式逐步被遗传和进化，最终就可得到问题的最优解。

【定义6.2】 模式H中具有确定基因值的位置数目称为该模式的模式阶（Schema Order），记为o（H）。

当字符串的长度固定时，模式阶越高，能与该模式匹配的字符串数就越少，因而该模式的确定性就越高。

【定义6.3】 模式H中第一个确定基因值的位置和最后一个确定基因值的位置之间的距离称为该模式的模式定义长度（Schema Defining Length），记为δ(H)。

例如，δ（11*0**）=3, δ(0 * * * 1)=4。对于只有一个确定基因值的模式，规定它们的模式长度为1。 6．1．2 模式定理

【模式定理】 遗传算法中，在选择、交叉和变异算子的作用下，具有低价、短的定义长度，并且平均适应度高于群体平均适应度的模式将按指数级增长。

6．2 积木块假设与遗传算法欺骗问题 6．2．1 积木块假设

模式定理说明了具有结构特征的模式在遗传进化过程中其样本将按指数级增长，这种模式就是具有低价、短的定义长度，且平均适应度高于群体平均适应度的模式。这种类型的模式被称为基因块或积木块（Building Block）。

【积木块假设】 个体的基因块通过选择、交叉、变异等遗传算子的作用，能够相互拼接在一起，形成适应度更高的个体编码串。

6．2．2 遗传算法的欺骗问题（GA Deceptive Problem）

优良模式周围存在不良模式包围所导致

6．3 隐含并行性

6．4 遗传算法的收敛性分析

6．5 适应度函数的自相关分析

第七章 遗传算法的应用

7．1 数值函数优化计算

7．1．1 遗传算法与纯数值函数优化计算

7．1．2 评价遗传算法性能的常用测试函数

1． De Jong 函数F1：

这是一个简单的平方和函数，只有一

个极小点f1（0，0，0

）＝0。

2． De Jong 函数F2：

3

． De Jong 函数F3：

一个全局最小值为30。

4． De Jong 函数F4：

一个全局最小值f4（0，0，……，0）＝0。 5． De Jong函数F5：

一个全局最小点f5（－32，－32）＝0.998。

6．Schaffer 函数F6：

该函数有一个全局最小点f6（0，0）＝0。

7．Schaffer 函数F7：

该函数有一个全局极小点f7（0，0）＝0。

8．Goldstein－Price 函数：

该函数有一个全局极小点f（0，－1）＝3。 9. Shubert函数：

多峰值函数，有18个全局最小点，f＝186.731。

10． 六峰值驼背函数

该函数有六个局部极小点，其中（－0.0898,0.7126）和（0.0898,-0.7126）为全局最小点，最小值为－1.031628。

11． 带有复杂约束条件的函数（之一）

全局极小点f（1，1，1，1，1，1，1，1，1，1，1，1，

3，3，3，1）＝－15。

12． 带有复杂约束条件的函数（之二）