遗传算法新版本

遗

传

算

法

原

理

与

应

用赵

鹏pzhao@bjtu.ed1一

、

基

本

原

理1.遗

传

算

法

起

源遗传算法是由美国的J.Holland教授于1975年在他的专著《自

然界和人工系统的适应性》中首先提出的，

它是一类借鉴生物

界自然选择和自然遗传机制的随机化搜索算法。2生

物

进

化

循

环

图淘汰的群体种

群竞

争婚

配群

体子

群变

异3生

物

遗

传

概

念遗

传

算

法中的

作

用适者生存在算法停止时

，

最优目标值的解有最大的可能被保留个体(individual)解染色体(chromosome)解的编码

(

字

符串，向量等)基

因(gene)解中每

一

分

量的

特征(如

各

分

量的

值

)适应性(fitness)适

应函

数

值群

体(population)选定的

一

组

解(

其中

解的

个数为

群

体的

规

模

)种

群(reproduction)根

据

适

应函

数

值

选

取的

一

组

解交

配(crossover)通

过

交

配

原

则

产

生

一

组

新

解的

过

程变

异(mutation)编

码的

某

一

个

分

量

发

生

变

化的

过

程4生物遗传概念在遗传算法中的对应关系遗

传

算

法

的

主

要

特

征

：进化发生在解的编码上，

这些编码按生物学的术语称为染色体。

由于对解进行了编码，

优化问题的一切性质都通过编

码来研究。

编码和解码是遗传算法的一个主题。自然选择规律决定哪些染色体产生超过平均数的后代。遗传算法中，通过优化问题的目标而人为地构造适应函数以达

到好的染色体产生超过平均数的后代。当染色体结合时，

双亲的遗传基因的结合使得子女保持父母的特征。当染色体结合后，

随机的变异会造成子代同父代的不同。5遗传算法主要处理步骤首先是对优化问题的解进行编码，称一个解的编码为一个染色

体，组成编码的元素称为基因。编码的目的主要是用于优化问题

解的表现形式和利于之后遗传算法中的计算。第二是适应函数的构造和应用。适应函数基本上依据优化问题

的目标函数而定。

当适应函数确定以后，

自然选择规律是以适应

函数值的大小决定的概率分布来确定哪些染色体适应生存，

哪些

被淘汰。

生存下来的染色体组成种群，

形成一个可以繁衍下一代

的

群

体

。第三是染色体的结合。双亲的遗传基因结合是通过编码之间的

交配达到下一代的产生。新一代的产生是一个生殖过程，

它产生

了一个新解。最后是变异。新解产生过程中可能发生基因变异，

变异使某些

解的编码发生变化，

使解有更大的遍历性。62、

基本

遗

传算

法基本遗传算法(

Simple

Genetic

Algorithms,简称SGA

,又称简单遗传算法或标准遗传算法),是由Goldberg

总结

出的一种最基本的遗传算法，

其遗传进化操作过程简单，容易理解，

是其它一些遗传算法的雏形和基础。基本遗传算法的组成(

1)

编

码

(

产

生

初

始

种

群

)(2)

适应

度

函

数(3)

遗传

算

子

(

选

择

、

交

叉

、

变

异

)(

4

)

运

行

参

数7编

码GA是通过某种编码机制把对象抽象为由特定符号按一定顺

序排成的串。正如研究生物遗传是从染色体着手，

而染色体则是由基因排成的串。SGA使用二进制串进行编码。函数优化示例求下列一元函数的最大值：x

∈[-1,2],求解结果精确到6位小数。8SGA对

于

本

例

的

编

码由于区间长度为3,

求解结果精确到6位小数，因此可将

自变量定义区间划分为3×106等份。又因为221<3×106<222,所

以本例的

二进

制

编

码

长

度

至

少需

要2

2

位，本

例

的

编

码

过程实质上是将区间[-1,2]内对应的实数值转化为一个二进制

串

(b21b20.b0)

。9几

个

术

语

个体

(

染

色体

)基

因

型

：

1

0

0

0

1

0

1

1

1

0

1

1

0

1

0

1

0

0

0

1

1基因解

码

编码表现

型：

0.63719710初始种群SGA

采用随机方法生成若

干

个

个

体的集合，

该集合称为初始

种群。初始种群中个体的数量称为种群规模。适

应

度

函

数遗传算法对

一个个体(解)的好坏用适应度函数值来评价，适应度函数值越大，

解的质量越好。适应度函数是遗传算法

进化过程的驱动力，

也是进行自然选择的唯一标准，

它的设计应结合求解问题本身的要求而定。11选

择

算

子遗传算法使用选择运算来实现对群体中的个体进行优胜劣

汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，

被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，

遗传到下一代群体。

SGA中选择算子采用轮盘赌选择方法。12S40.31/s₃0.06●轮

盘

赌

选

择

法轮

盘

赌

选

择

示

意S10.14S20.4913轮

盘

赌

选

择

方

法轮盘赌选择又称比例选

择

算

子，它

的基本思想是

：

各个

个体被选中的概率与其适应度函数值大小成正比。设群体大

小为n,个体i

的适应度为

F,则个体i

被选中遗传到下一代群体的概率为：14轮盘赌选择

方

法的实现步

骤(1)

计算群体中所有个体的适应度函数值(需要解码);(2)利用比例选择算子的公式，

计算每个个体被选中遗传到下

一

代

群

体的

概

率

；(3)采用模拟赌盘操作(即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配)来确定各个个体

是否遗传到下一代群体中。15交

叉

算

子所谓交叉运算，

是指对两个相互配对的染色体依据交

叉概率Pc按某种方式相互交换其部分基因，从而形成两个

新的个体。交叉运算是遗传算法区别于其他进化算法的重要

特征，它在遗传算法中起关键作用，

是产生新个体的主要方

法。SGA中

交叉算子采用单点交叉算子。16单点交叉运算

交

叉

前

：

交叉点

O0000|04TOOO000001000011100|00000111111000101交

叉

后

：O0000|0000011111100010111100|0111000000001000017变

异

算

子所谓变异运算，是指依据变异概率

Pm

将个体编码串中

的某些基因值用其它基因值来替换，从而形成一个新的个体

。遗传算法中的变异运算是产生新个体的辅助方法，它决定

了遗传算法的局部搜索能力，

同时保持种群的多样性。交叉

运算和变异运算的相互配合，

共同完成对搜索空间的全局搜

索和局部搜索。

SGA

中变异算子采用基本位变异算子。18基

本

位

变

异

算

子基本位变异算子是指对个体编码串随机指定的某一位或某

几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0,则变异操作将其变为1;反之，若原有基因

值为1,则变异操作将其变为0。19变

异

前

：000001110000000010000变

异

后

：000001110001000010000基本位

变异

算

子的执行

过

程

变异点

20运

行

参

数(1)M

:

种

群

规

模(2)T:

遗传运算的终止进化代数(3)Pc:

交叉概率(4)Pm:变异概率21GA

OperatorsMutationCrossoverReproductionEvaluationFitnessvalueEvolution

EnvironmentGenetic

Algorithm

Evolution

Flow初始种群Cost遗

传

算

法

应

用

举

例利用遗

传算

法

求

解区间

[0,31]上的二次函数y=x²的最大值。23分

析原问题可转化为在区

间

[0,3

1]

中搜索能使

y

取最大值

的

点a

的

问题

。那么

,[0,31]

中

的点x就是个体，函数值f(x)恰好就可以作为x的

适应度，

区间[0,31]就是一个(解)空间。这

样，只要能给出个体x的适当染色体编码，该问

题就可以用遗传算法来解决。24解(1)设定种群规模，编码染色体，产生初始种

群

。将种群规模设定为4;用5位二进制数编码

染色体；取下列个体组成初始种群S₁:s₁=13

(01101),s₂=24(11000)s₃=8(01000),

s₄=19(10011)(2)定义适应度函数，取适应度函数：f(x)=x²25(3)计算各代种群中的各个体的适应度，并对其染色体进行遗传操作，直到适应度最高的个

体(即31(11111))出现为止。26首先计算种群S₁中各个体s₁=13(01101),

s₂=24(11000)

s₃=8(01000),

s₄=19(10011)的适应度f(s;)。容易求得f(s₁)=f(13)=13²=169f(s₂)=f(24)=242=576f(s₃)=f(8)=8²=64f(s₄)=f(19)=192=36127再计

算

种

群S₁中

各

个

体的

选

择

概

率

。选

择

概

率的

计

算

公

式

为P(s₁)=P(13)=0.14P(s₂)=P(24)=0.49P(s₃)=P(8)=0.06P(s₄)=P(19)=0.31由

此

可

求

得28S40.31/s₃0.06●赌

轮

选

择

法赌

轮

选

择

示

意S10.14S20.4929在算法中赌轮选择

法

可

用下

面的子过

程

来

模拟

：①在

[0,

1]

区

间

内产

生

一

个

均

匀

分

布

的

随

机数

r。②

若r≤q₁,则染色体x₁被选中。③若qk-₁<r≤qμ(2≤k≤N),

则染色体x被选中。其中的q;称为染色体x;(i=1,2,

...,n)的积累概率，

其计算公

式

为30染色体适应度选择概率积累概率选中次数S₁=011011690.140.141S₂=110005760.490.632S₃=01000640.060.69OS₄=100113610.311.001选择-复制设从区间[0,1]中产生4个随机数如下：r₁=0.450126,r₂=0.110347r₃=0.572496,r₄=0.9850331于是，

经复

制

得

群

体

：s₁

′=11000(24),s₂

′=01101(13)s₃

′=11000(24),s₄

′=10011(19)32交

叉设交叉率p=100%,

即S₁中的全体染色体都参

加

交

叉

运

算

。设s₁'与s₂

'配对，

s₃

'与s₄'配对。分别交换后两

位

基因，得

新

染

色

体

：S₁

′'=11001(25),s₂

′′=01100(12)s₃

′'=11011(27),s₄

′'=10000(16)33变

异设变异率pm=0.001。这样，群体S₁中共有5×4×0.001=0.02位

基因可以

变

异

。0

.

0

2

位

显

然

不

足1

位

，

所

以本轮遗传操作不做

变

异

。34于是，得到第二代种群S₂:S₁=11001(25),S₂=01100(12)S₃=11011(27),S₄=10000(16)35染色体适应度选择概率积累概率估计的选中次数S₁=110016250.360.361S₂=011001440.080.441S₃=110117290.410.851S₄=100002560.151.001第二代种群S₂中各染色体的情况36假设这一轮选择-

复制操作中，种群S₂中

的4个染色体都被选中，则得到群体：S₁′=11001(25),s₂′=01100(12)S₃'=11011(27),s₄'=10000(16)做交叉运算，让s₁’与s₂’,s₃’

与s₄’分别交换后三位基因，

得S₁”=11100(28),s₂”=01001(9)s₃”=11000(24),s₄”=10011(19)这一轮仍然不

会发生

变

异

。37于是，得第三

代

种

群S3:S₁=11100(

28

),S₂

=01001(9)S₃=11000(24),S₄=10011(19)38染色体适应度选择概率积累概率估计的选中次数S₁=111007840.440.442S₂=01001810.040.48OS₃=110005760.320.801S4=100113610.201.001第三代种群S₃中各染色体的情况39设这一轮的选择-复制结果为：s₁'=11100(28),s₂

'=11100(28)S₃

′=11000(24),s₄

′=10011(19)做交叉运算，让s₁

’与s₄

’,s₂

’与s₃

’分别交换后两

位

基因，

得S₁

′'=11111(31),s₂

′'=11100(28)s₃

′'=11000(24),s₄

′′=10000(16)这一

轮仍

然

不

会

发

生

变

异

。40于是，得第四代种群S₄:S₁=11111(31),S₂=11100(28)S₃=11000(24),S₄=10000(16)41显然，

在

这

一

代

种

群

中

已

经

出

现

了

适

应

度

最高的染色体s₁=11111。

于是，遗传操作终止，

将

染

色

体

“1

1

1

1

1

”

作

为

最

终

结

果

输

出

。然后，

将

染

色

体

“

1

1

1

1

1”

解

码

为

表

现

型

，

即得

所

求

的

最

优

解

：

31。将31代入函数y=x²中，即得原问题的解，

即

函数y=x²的最大值为961。42第三

代

种

群

及

其

适

应

度第四代种群

及

其

适

应

度第一

代种

群

及

其

适

应

度第二

代种

群

及

其

适

应

度43遗传

算

法的描

述Step1选择问题的一个编码；给出一个有N个染色体的初始群体

pop(1),t:=1;Step2

对群体pop(t)中的每一个染色体pop;(t)计算它的适应函数

f=fitness(pop;(t));Step3若停止规则满足，则算法停止；否则，计算概率P₁=f/Zfi,i=1,2,,,N并以概率从pop(t)中随机选一些染色体构成一个新的种群Newpop(t+1)={pop(t)[j=1,2,...,N};Step4

通过交配，交配概率为p.,得到一个有N个染色体的

crosspop(t+1);Step5

以较小概率pm,

使得一个染色体的基因发生变异，形成

mutpop(t+1);t:=t+1,一个新的体群pop(t)=mutpop(t);返回step2.443、

遗

传

算

法

的

特

点(1)群体搜索，

易于并行化处理；(2)不是盲目穷举，而是启发式搜索；(3)适应度函数不受连续、可微等条件的约束，

适用

范

围

很广。45二

、

理

论

基

础1、

遗传算法的数学基础2、

遗传算法的收敛性分析3、

遗传算法

的改进461、

遗传算

法的数学基

础(

1)模式定理(2)

积

木

块

假设模

式模式是指种群个体基因串中的相似样板，它用来描述基

因串中某些特征位相同的结构。在二进制编码中，

模式是基于三个字符集(0,1,*)的字符串，符号*代表任意字符，

即0或

者1。模式示例：1

0**147两个定义一定义1:

模

式H中

确定位置的个数称为

模

式

H

的

阶

，

记作

O(H)。例

如O(10**1)=3。一定义2:

模

式H中第一个确定位置

和

最

后

一

个

确定

位

置

之

间

的距离称为

模

式

H的

定

义距，

记

作δ(H)

。

例如δ(10**1)=4

。模式的阶和

定

义

距的

含

义模式阶用来

反映

不同

模式间

确

定

性的差

异，

模式阶数越高,

模式的确定性就越高，

所匹配的样本

数

就

越

少。在

遗

传

操

作中，

即使阶数相同的模式，也会有不同的性质，

而模式

的

定义

距

就

反映了这

种

性

质的

差

异

。48模式定理模式定理：

具有低阶、短定义距以

及平均适应度高于种群

平均适应度的模式在子代中呈指数增长。模式定理保证了较优的模式(遗传算法的较优解)的数目呈指数增长，为解释遗传算法机理提供了数学基础。从模式定理可看出，

有高平均适应度、短定义距、低阶的

模式，在连续的后代里获得至少以指数增长的串数目，

这主要

是因为选择使最好的模式有更多的复制，交叉算子不容易破坏

高频率出现的、短定义距的模式，

而一般突变概率又相当小，

因而它对这些重要的模式几乎没有影响。49积

木

块

假

设积木块假设：

遗传算法通

过

短

定

义距

、

低

阶

以

及

高

平

均

适

应

度的模式(积木块),在遗传操作下相互结合，

最终接近全局

最优解。模式定理保证了较优模式的样本数呈指数增长，

从而使遗传算

法找到全局最优解的可能性存在；

而积木块假设则指出了在遗

传算子的作用下，

能生成全局最优解。定理若参数满足：变异概率0

<pm<1,交配概率O≤Pc≤1,则简单遗传算法不收敛于全局最优解。50定理

如果改进简单遗传算法按交配、变异、种群选取之后更新当前最优染色体的进化循环过程，则收敛于全局最优解。改进遗传算法：

进化的每一代中，记录前面各代最优解并

存放在群体的第一位，

这个染色

体

不参与

遗

传

运

算

。2、

遗传算法

的收敛

性

分

析遗传算法要实现全局收敛，

首先要求任意初始种群经有限步都能到达全局最优解，

其次算法必须由保优操作来防止最优解

的遗失。与算法收敛性有关的因素主要包括种群规模、选择操

作、交叉概率和变异概率。51种群规模对收敛性的影响通常，种群太小则不能提供足够的采样点，

以致算法性能

很差；种群太大，

尽管可以增加优化信息，

阻止早熟收敛的发生，但无疑会增加计算量，

造成收敛时间太长，

表现为收敛速

度

缓

慢

。选择操作对收敛性的影响选

择

操

作

使

高

适

应

度

个

体

能

够

以

更

大

的

概

率

生

存

，

从

而

提

高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，

使之直接进入下一代，

最终可使遗传算法以概率1收

敛于全局最优解。52交叉概

率

对收

敛性的影响交叉操作用于个体对，产生新的个体，

实质上是在解空间中进行有效搜索。交叉概率太大时，

种群中个体更新很快，会造

成高适应度值的个体很快被破坏掉；

概率太小时，交叉操作很少进行，从而会使搜索停滞不前，

造成算法的不收敛。变异概

率

对收

敛

性的影响变异操作是对种群模式的扰动，有利于增加种群的多样性。但是，变异概率太小则很难产生新模式，变异概率太大则会使

遗传算法成为随机搜索算法。53遗

传

算

法

的

本

质遗传算法本质上是对染色体模式所进行的一系列运算，

即通过选择算子

将当前种

群中的优

良模式遗

传到下一

代

种

群中,

利用交叉算子进行模式重组，

利用变异算子进行模式突变。通过这些遗传操作，模式逐步向较好的方向进化，

最终得

到问题的最优解。54GA的

局

限

性在

于GA在进化搜索过程中，

每代总要维持一定规模的群体，

若群体规模太小，

含有的信息量也少，不能使算法得到充分发挥

,若群体规模大，包含的信息量也大，但计算次数会激剧增加，

因而限制了算法的使用。GA的另一个不足之处是“早熟”。造成这种成熟前收敛的原因，

一方面是

GA中最重要的遗传算子——交叉算子使群体中的

染色体具有局部相似性，父代染色体的信息交换量小，从而使搜

索停滞不前；

另一方面是变异概率又太小，

以至于不能使搜索转

向其它的解空间进行搜索。GA的爬山能力差，

也是由于变异概率低造成的。553、

遗

传

算

法

的

改

进遗传欺骗问题：

在遗传算法进化过程中，

有时会产生一些

超常的个体，

这些个体因竞争力太突出而控制了选择运算过

程，

从而影响算法的全局优化性能，

导致算法获得某个局部最

优

解

。56遗

传

算

法

的

改

进

途

径(

1)对

编码

方

式

的

改

进

(2)对遗传算子的改进

(3)对控制参数的改进

(4)对执行策略的改进57对

编

码

方

式

的

改

进二进制编码优点在于编码、

解码操作简单，

交叉、

变异等操作便于实现，

缺

点在

于

精

度

要

求

较

高

时

，个

体

编

码

串

较

长

,

使算法的搜索空间急剧扩大，遗传算法的性能降低。格雷

编码克服了二进制编码的不连续问题，浮点数编码改善了遗传算法的计算复杂性。58(1)编码自然数编码，

i₁izig……in

(2)适应度函数f;:

巡回路长度的倒数

(3)选择操作①繁殖池；

②赌轮选择

(4)杂交算子例，基于位置的杂交父代1:

1

2

3

4

5父

代

2

:

5

9

2

4

6所选位置

子

代

1

:

1

9

2

36子代

2

:

9

2

3

4

5(5)变异算子*

*

*例，基于位置的变异、基于次序的变异、打乱变异TSP

问

题

的

基

本

遗

传

算

法108107938107105187★7864659(1)

对群体中的所有个体按其

适应度大小进行降序排序；(2)

根据具体求解问题，设计

一个概率分配表，将各个概率值

按上述排列次序分配给各个个体(3)

以各个个体所分配到的概

率值作为其遗传到下一代的概率

,基于这些概率用赌盘选择法来产生下一代群体。对

遗

传

算

子

的

改

进排序选探

均

匀

交

叉逆

序

变

异60(1)

随机产生一个与个体

编码长度相同的二进制屏蔽

字P

=W₁W₂…Wn;(2)按

下

列

规

则

从A、

B

两

个父代个体中产生两个新个体

X、Y:

若

W;=0,

则

X

的第i个基因继承A的对应基因

,Y

的第i个基因继承B

的对应

基因；若W;=1,

则A、B的

第i个基因相互交换，从而生

成X、Y

的第i个基因。对遗传算子

的

改

进排序选择均

匀

交

叉逆

序

变

异61排序选择均匀交叉

逆

序