第三章 经典进化计算-遗传算法-2

3.2遗传算法的应用与特点一、遗传算法应用举例二、遗传算法的特点与优势一、遗传算法应用举例

例1

利用遗传算法求解区间［0,31］上的二次函数y=x2的最大值。

y=x2

31

XY

分析

原问题可转化为在区间［0,31］中搜索能使y取最大值的点a的问题。那么，［0,31］中的点x就是个体,函数值f(x)恰好就可以作为x的适应度，区间［0,31］就是一个(解)空间。这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。

解

(1)

设定种群规模,编码染色体，产生初始种群。将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

(2)定义适应度函数,

取适应度函数：f(x)=x2

(3)计算各代种群中的各个体的适应度,并对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止。

首先计算种群S1中各个体

s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)的适应度f(si)

。容易求得

f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361再计算种群S1中各个体的选择概率。选择概率的计算公式为

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31

赌轮选择示意s40.31s20.49s10.14s30.06●赌轮选择法

在算法中赌轮选择法可用下面的子过程来模拟:①在［0,1］区间内产生一个均匀分布的随机数r。②若r≤q1,则染色体x1被选中。③若qk-1<r≤qk(2≤k≤N),则染色体xk被选中。其中的qi称为染色体xi(i=1,2,…,n)的积累概率,其计算公式为选择-复制

设从区间［0,1］中产生4个随机数如下:

r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503

染色体

适应度选择概率积累概率选中次数s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001于是，经复制得群体：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）交叉

设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1’与s2’配对，s3’与s4’配对。分别交换后两位基因，得新染色体：

s1’’=11001（25）,s2’’=01100（12）

s3’’=11011（27）,s4’’=10000（16）

变异设变异率pm=0.001。这样，群体S1中共有

5×4×0.001=0.02位基因可以变异。

0.02位显然不足1位，所以本轮遗传操作不做变异。

于是，得到第二代种群S2：

s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）

第二代种群S2中各染色体的情况

染色体

适应度选择概率积累概率

估计的选中次数s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.001

假设这一轮选择-复制操作中，种群S2中的4个染色体都被选中，则得到群体：

s1’=11001（25）,s2’=01100（12）

s3’=11011（27）,s4’=10000（16）

做交叉运算，让s1’与s2’，s3’与s4’

分别交换后三位基因，得

s1’’=11100（28）,s2’’=01001（9）

s3’’=11000（24）,s4’’=10011（19）

这一轮仍然不会发生变异。

于是，得第三代种群S3：

s1=11100（28）,s2=01001（9）

s3=11000（24）,s4=10011（19）

第三代种群S3中各染色体的情况

染色体

适应度选择概率积累概率

估计的选中次数s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.001

设这一轮的选择-复制结果为：

s1’=11100（28）,s2’=11100（28）

s3’=11000（24）,s4’=10011（19）

做交叉运算，让s1’与s4’，s2’与s3’

分别交换后两位基因，得

s1’’=11111（31）,s2’’=11100（28）

s3’’=11000（24）,s4’’=10000（16）

这一轮仍然不会发生变异。

于是，得第四代种群S4：

s1=11111（31）,s2=11100（28）

s3=11000（24）,s4=10000（16）

显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。

YYy=x2

8131924

X第一代种群及其适应度y=x2

12162527

XY第二代种群及其适应度y=x2

9192428

XY第三代种群及其适应度y=x2

16242831

X第四代种群及其适应度二、遗传算法的特点与优势

◆遗传算法的主要特点

——遗传算法一般是直接在解空间搜索,而不像图搜索那样一般是在问题空间搜索,最后才找到解。

——遗传算法的搜索随机地始于搜索空间的一个点集,而不像图搜索那样固定地始于搜索空间的初始节点或终止节点,所以遗传算法是一种随机搜索算法。

——遗传算法总是在寻找优解,而不像图搜索那样并非总是要求优解,而一般是设法尽快找到解,所以遗传算法又是一种优化搜索算法。

——遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索,而不像图搜索那样一般是从空间的一个点到另一个点地搜索。因而它实际是一种并行搜索,适合大规模并行计算,而且这种种群到种群的搜索有能力跳出局部最优解。

——遗传算法的适应性强,除需知适应度函数外,几乎不需要其他的先验知识。

——遗传算法长于全局搜索,它不受搜索空间的限制性假设的约束,不要求连续性,能以很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。◆遗传算法的应用函数优化是遗传算法的经典应用领域;组合优化实践证明，遗传算法对于组合优化中的NP完全问题非常有效;自动控制如基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习等;机器人智能控制遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等;组合图像处理和模式识别目前已在图像恢复、图像边缘持征提取、几何形状识别等方面得到了应用;人工生命基于遗传算法的进化模型是研究人工生命现象的重要理论基础，遗传算法已在其进化模型、学习模型、行为模型等方面显示了初步的应用能力；遗传程序设计Koza发展了遗传程序设计的慨念，他使用了以LISP语言所表示的编码方法，基于对一种树型结构所进行的遗传操作自动生成计算机程序;

指导遗传算法的基本理论，是J.H.Holland教授创立的模式理论。该理论揭示遗传算法的基本机理。一、基本概念二、模式定理三、建筑块假说四、隐含并行性3.3—遗传算法的模式理论一、基本概念

1.1问题的引出

例：求maxf(x)=x2x{0,31}[分析]

•当编码的最左边字符为“1”时，其个体适应度较大，如2号个体和4号个体，我们将其记为“1****”；

其中2号个体适应度最大，其编码的左边两位都是1，我们记为“11***”；•当编码的最左边字符为“0”时，其个体适应度较小，如1号和3号个体，我们记为“0****”。

[结论]从这个例子可以看比，我们在分析编码字符串时，常常只关心某一位或某几位字符，而对其他字符不关心。换句话讲．我们只关心字符的某些特定形式，如1****，11***，0****。这种特定的形式就叫模式。

1.2模式、模式阶及模式定义长度

模式(Schema)——指编码的字符串中具有类似特征的子集。以五位二进制字符串为例，模式

*111*可代表4个个体：01110，01111，11110，11111；模式*0000则代表2个个体：10000，00000。

•

个体是由二值字符集V={0,1}中的元素所组成的一个编码串;

•而模式却是由三值字符集V={0,1,*}中的元素所组成的一个编码串，其中“*

”表示通配符，它既可被当作“1”也可被当作“0”。模式阶(SchemaOrder)

——指模式中已有明确含意(二进制字符时指0或1)的字符个数，记做o(s)，式中s代表模式。例如，模式(011*1**)含有4个明确含意的字符，其阶次是4，记作o(011*1**)=4;模式(0******)的阶次是1，记作o(0******)=1。

•阶次越低，模式的概括性越强，所代表的编码串个体数也越多，反之亦然；

•当模式阶次为零时，它没有明确含义的字符，其概括性最强。模式的定义长度(SchemaDefiningLength)——指模式中第一个和最后一个具有明确含意的字符之间的距离，记作(s)。例如，模式(011*l**)的第一个字符为0，最后一个字符为l，中间有3个字符，其定义长度为4，记作(011*l**)=4；模式(0******)的长度是0，记作(0******)=0；

•一般地，有式子

(s)＝b–a式中b—模式s中最后一个明确字符的位置;a—模式s中最前一个明确字符的位置。

•模式的长度代表该模式在今后遗传操作(交叉、变异)中被破坏的可能性：模式长度越短，被破坏的可能性越小，长度为0的模式最难被破坏。1.3编码字符串的模式数目

(1)模式总数

•二进制字符串假设字符的长度为l，字符串中每一个字符可取(0,1,*)三个符号中任意一个，可能组成的模式数目最多为：333…3=(2+1)l

•一般情况下，假设字符串长度为l，字符的取值为k种，字符串组成的模式数目n1最多为：n1=(k+1)l(2)编码字符串（一个个体编码串）所含模式总数

•二进制字符串对于长度为l的某二进制字符串，它含有的模式总数最多为：222…2=2l

[注意]这个数目是指字符串已确定为0或1，每个字符只能在已定值(0/1)或*中选取；前面所述的n1指字符串未确定，每个字符可在{0,1,*}三者中选取。

•一般情况下长度为l、取值有k种的某一字符串，它可能含有的模式数目最多为：n2=kl

(3)群体所含模式数

在长度为l，规模为M的二进制编码字符串群体中，一般包含有2l~M·2l个模式。二、模式定理

由前面的叙述我们可以知道，在引入模式的概念之后，遗传算法的实质可看作是对模式的一种运算。对基本遗传算法(GA)而言，也就是某一模式s的各个样本经过选择运算、交义运算、变异运算之后，得到一些新的样本和新的模式。

[模式定理]

适应度高于群体平均适应度的，长度较短，低阶的模式在遗传算法的迭代过程中将按指数规律增长。模式定理深刻地阐明了遗传算法中发生“优胜劣汰”的原因。在遗传过程中能存活的模式都是定义长度短、阶次低、平均适应度高于群体平均适应度的优良模式。遗传算法正是利用这些优良模式逐步进化到最优解。2.5模式定理示例例：求maxf(x)=x2x{0,31}个体变化叉叉S1S2S3叉三、建筑块假说3.1模式对搜索空间的划分

[举例]

以maxf(x)=x2x{0,31}为例，图中：横坐标表示x，纵坐标代表适应度f(x)=x2，用千分数表示，弧线表示适应度曲线，网点区代表所有符合此模式的个体集合。模式1：1****模式2：10***模式3：**1*1[结论]

模式能够划分搜索空间，而且模式的阶越高，对搜索空间的划分越细致。3.2分配搜索次数

模式定理告诉我们：

GA根据模式的适应度、长度和阶次为模式分配搜索次数。为那些适应度较高，长度较短，阶次较低的模式分配的搜索次数按指数率增长；为那些适应度较低，长度较长，阶次较高的模式分配的搜索次数按指数率衰减。3.3建筑块假说

前面我们已经介绍了GA如何划分搜索空间和在各个子空间中分配搜索次数，

那么GA如何利用搜索过程中的积累信息加快搜索速度呢？Holland和Goldberg在模式定理的基础上提出了“建筑块假说”。

[建筑块（或称积木块）(BulidingBlock)]——短定义长度、低阶、高适应度的模式。

之所以称之为建筑块（积木块），是由于遗传算法的求解过程并不是在搜索空间中逐一地测试各个基因的枚举组合，而是通过一些较好的模式，像搭积木一样、将它们拼接在一起，从而逐渐地构造出适应度越来越高的个体编码串。

[建筑块假说]GA在搜索过程中将不同的“建筑块”通过遗传算子（如交叉算子）的作用结合在一起，形成适应度更高的新模式。这样将大大缩小GA的搜索范围。[建筑块混合]——建筑块通过遗传算子的作用集合在一起的过程称为“建筑块混合”。当那些构成最优点（或近似最优点）的“建筑块”结合在一起时，就得到了最优点。[建筑块混合的例子]

•问题的最优用三个建筑块BB1,BB2,BB3表示；

•群体中有8个个体。

•初始群体中个体1，个体2包含建筑块BB1，个体3包含BB3,个体5包含BB2。P1P2P3P4P5P6P7P8BB