第6章遗传算法

1、2022-5-1上海工程技术大学机械工程学院1第六章 遗传算法 6.1遗传算法概述 6.2基本遗传算法 6.3遗传算法数学基础 6.4遗传算法的改进2022-5-1上海工程技术大学机械工程学院26.1 遗传算法概述一、简介 遗传算法(Genetic Algorithms, GA)是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法. 遗传算法吸取了自然生物系统“适者生存”的进化理论，将达尔文的进化理论引入人工系统串结构的改造中，使得串结构及其携带的信息发生有组织的而又是随机的变换和组合，并使该过程按物种进化规律来操作运行，设法使物种的优良品质在组合中加以保留，从而不断产

2、生出更佳的个体后代。2022-5-1上海工程技术大学机械工程学院36.1 遗传算法概述二、发展简史 n20世纪50年代，生物学家Fraser试图通过计算的方法来模拟生物界“遗传与选择”的进化过程 。n20世纪60年代，1975年Holland教授出版了遗传算法历史上的经典著作Adaptation in Natural and Artificial Systems，首次提出遗传算法的概念 。n20世纪80年代，迅速发展 ，1989年，Holland的学生Goldberg出版了Genetic Algorithms in Search ,Optimization and Machine Learni

3、ng 一书，为这一领域奠定了坚实的科学基础。n20世纪90年代，随着计算机技术的发展，遗传算法在各个领域得到了广泛的应用。不同领域的专家、学者根据各自的实际问题，构造出了多种能很好地解决行业问题新的遗传算法。 2022-5-1上海工程技术大学机械工程学院46.1 遗传算法概述三、遗传算法的特点 v全局性v并行性和高效性v鲁棒性 v普适性和易扩性 v简明性 2022-5-1上海工程技术大学机械工程学院56.2 基本遗传算法一、基本原理1、基本术语n染色体：遗传物质的主要载体，指多个遗传因子的集合。n个体：指染色体带有特征的实体称个体n种群：染色体带有特征个体的集合称为群体，该集合内的个体书称为群

4、体的大小。n编码：从表现型到遗传子型的映射称为编码n适应度：各个个体对各自适应环境的程度称为适应度。n选择：指决定以一定的概率从群体中选择若干对个体的操作称为选择。n交叉：把两个染色体换组的操作称为交叉，又称重组。n变异：让遗传因子以一定的概率变化的操作称为变异n解码：从遗传子型到表现型的映射称为解码2022-5-1上海工程技术大学机械工程学院66.2 基本遗传算法2、基本原理与流程 2022-5-1上海工程技术大学机械工程学院76.2 基本遗传算法YN简单遗传算法基本流程图 2022-5-1上海工程技术大学机械工程学院83、遗传算法的基本操作n设有函数 ,用遗传算法求其自变量x在区间0，31

5、取整数时最大值2( )f xx6.2 基本遗传算法2022-5-1上海工程技术大学机械工程学院9（1）初始种群6.2 基本遗传算法2022-5-1上海工程技术大学机械工程学院10（2）复制 根据目标函数适应度的计算，从初始种群中挑选适应度高的个体进行复制。通常可把目标函数制定成获得的利益、利润、功效等指标的量度函数。这里，可把目标函数值确定为适应值。 适应值相当于自然界中的一个生物为了生存所具备的各项能力的大小，决定了该染色体被复制还是被淘汰。6.2 基本遗传算法2022-5-1上海工程技术大学机械工程学院116.2 基本遗传算法2022-5-1上海工程技术大学机械工程学院126.2 基本遗传

6、算法2022-5-1上海工程技术大学机械工程学院13 根据上表数据，对应轮盘赌转盘的随机方法，绘制出轮盘赌转盘。6.2 基本遗传算法2022-5-1上海工程技术大学机械工程学院14 旋转4次轮盘，就产生4个染色体，这4个染色体是上一代种群中有选择的复制，有的可能被复制一次或多次，有的则可能被淘汰。6.2 基本遗传算法2022-5-1上海工程技术大学机械工程学院15（3）交叉 不但复制出优秀的染色体，而且还要创造出新的染色体。交叉操作模拟生物进化过程的繁殖现象，通过两个染色体的交换组合，从而产生新的优良品种。 交叉步骤：（1）将复制产生的染色体随机两两匹配，称之为双亲的染色体；（2）将双亲的染色

7、体进行交叉繁殖。6.2 基本遗传算法2022-5-1上海工程技术大学机械工程学院166.2 基本遗传算法2022-5-1上海工程技术大学机械工程学院176.2 基本遗传算法2022-5-1上海工程技术大学机械工程学院186.2 基本遗传算法2022-5-1上海工程技术大学机械工程学院19（4）变异 以很小的概率随机地改变遗传基因的值，模拟生物在自然环境中，由于某种偶然因素引起的基因突变。假设只有复制和交叉，没有变异操作，就无法在初始基因族组以外的空间进行搜索，可能使进化过程较早陷入局部解而失去某种特殊的进化途径。 对于二进制编码表示的染色体数字符串中，随机地将染色体的某一个基因，即染色体的数字

8、符串的某一位的数值由1变成0，或由0变成1。6.2 基本遗传算法2022-5-1上海工程技术大学机械工程学院20 变异的概率比较小，通常取千分之一二，但变异操作增加了基因类型的多样性，使搜索能在尽可能大的空间进行，得到更优化的解。 假设变异概率为0.001，则对于种群总共有20个基因位，期望的变异串位数为20X0.001=0.02位，所以这里没有基因位数值的改变。6.2 基本遗传算法2022-5-1上海工程技术大学机械工程学院216.2 基本遗传算法二、遗传算法的设计与实现 1、编码 利用遗传算法进行问题求解时,首先确定问题的目标函数和变量,然后对其进行编码。这样做主要是因为在遗传算法中,问题

9、的解是用数字串来表示的，而遗传操作算子也是直接对串进行操作的。编码方式常用的有二进制编码和浮点数编码 。2022-5-1上海工程技术大学机械工程学院226.2 基本遗传算法2、适应度函数 在生物的遗传和进化过程中，对生物环境适应程度较高的物种将有更多的繁殖机会。遗传算法中也使用这个概念来度量群体中各个个体在优化计算中有可能达到或有助于找到最佳解的寻优过程。适应度较高的个体遗传到下一代的概率就较大，而适应度较低的个体遗传到下一代的概率就相对小一些。度量个体适应度的函数称为适应度函数（Fitness Function）。 2022-5-1上海工程技术大学机械工程学院236.2 基本遗传算法适应度函

10、数设计方法（1）目标函数映射成适应度函数2022-5-1上海工程技术大学机械工程学院246.2 基本遗传算法（2）适应度函数调整 应用遗传算法时(尤其用它处理小规模群体时)常常会出现一些不利于优化的现象或结果。在进化的初期，通常会出现一些异常的个体，若按照轮盘选择策略，这些异常个体有可能在群体中占据很大的比例，这是我们所不期望出现的现象。因为这样可能导致未成熟收敛现象。这些异常个体竞争力太突出，它们会控制选择过程，影响算法的全局优化性能。调整方式主要有:2022-5-1上海工程技术大学机械工程学院256.2 基本遗传算法1)线性调整 2022-5-1上海工程技术大学机械工程学院266.2 基本

11、遗传算法2)幂调整2022-5-1上海工程技术大学机械工程学院276.2 基本遗传算法3. 遗传算子(1) 选择运算(selection) 选择是从群体中挑选优良个体并淘汰劣质个体的操作过程。它建立在适应度评估的基础上，个体适应度越大，被选中的可能性就越大，它的子代保留到配对库(mating pool)中的个数就越多。常用选择方法:轮盘赌方法 、 排序选择法 、最佳个体保存法 。 2022-5-1上海工程技术大学机械工程学院286.2 基本遗传算法轮盘赌方法 (roulette wheel model) 2022-5-1上海工程技术大学机械工程学院296.2 基本遗传算法2022-5-1上海工

12、程技术大学机械工程学院306.2 基本遗传算法(2) 交叉运算(crossover) 在遗传操作中的，交叉操作因其全局搜索能力而成为主要算子，其作用在于它不仅使原种群中优良个体的特性能够在一定程度上保持，而且其探索新的基因空间的能力使得种群中的个体具有多样性。它是GA获取新优良个体的最重要手段。交叉是指把两个父串个体的部分结构加以替换重组而生成新个体的操作。交叉运算分为两类，一类为二进制交叉，另一类为浮点数交叉。 2022-5-1上海工程技术大学机械工程学院316.2 基本遗传算法（a）二进制交叉运算 交叉操作是按一定概率Pc在配对库中随机地选取两个个体进行的。交叉的位置也是随机确定的。其二进

13、制编码操作又可分为单点交叉、两点交叉和多点交叉等。n一点交叉：是在个体中随机地选定一个交叉点，两个个体在该点前后进行部分互换，以产生新的个体。父辈个体1 A A A A A A |A A A A A A B B B B B B | A A A A A A父辈个体2 B B B B B B | B B B B B B A A A A A A | B B B B B Bn两点交叉：该交叉操作与单点交叉类似，只是随机设置两个交叉点进行部分互换，以产生新的个体。父辈个体1 A A A A | A A A A |A A A A A A A A | B B B B | A A A A父辈个体2 B B B

14、 B | B B B B | B B B B B B B B | A A A A | B B B B n多点交叉：该交叉操作即前述两中交叉方法的推广，多点交叉有时又被叫做广义交叉。若用参数c表示交叉数，则当c1或c2时即为单点交叉和两点交叉。 2022-5-1上海工程技术大学机械工程学院326.2 基本遗传算法（b）浮点数编码的交叉运算2022-5-1上海工程技术大学机械工程学院336.2 基本遗传算法(3) 变异运算(mutation) 遗传算法中使用变异算子使得遗传算法具有局部的随机搜索能力,能找到更精确的值.并配合交叉操作以维持种群的多样性，防止出现过早收敛。两类变异运算：二进制变异运算

15、，浮点数的变异运算。（a）二进制变异运算 以很小的概率Pm随机地改变群体中染色体某些基因的值。变异操作的基本过程是，变异算子随机地将某个基因值取反，即“0”变成“1”或“1”变为“0”。 01000101000101011010 01010101000101001010 2022-5-1上海工程技术大学机械工程学院346.2 基本遗传算法（b）浮点数变异运算2022-5-1上海工程技术大学机械工程学院356.2 基本遗传算法三、遗传算法运行参数的选择 1、种群规模 种群规模过小，容易使算法陷入局部最优解；种群规模过大，增加了算法的计算量，从而减缓了算法的进化速度。一般来说对种群的大小是针对一个

16、具体的问题而言的，种群的规模与以下影响因素有关：(1) 问题的内在规律。如果在问题空间内目标函数的极值点越多，所要求的种群规模越大；如果问题空间内目标函数的变化越平滑，所要求的种群规模越小。(2) 问题空间的范围。问题空问的取值范围越大，要求的种群规模也越大。(3) 交叉率、变异率的选择。交叉率和变异率较大时，要求的种群规模较小；反之，较大。 2022-5-1上海工程技术大学机械工程学院366.2 基本遗传算法2、交叉率 交叉率是最主要的遗传运算，遗传算法的性能在很大程度上取决于所采用的交叉算子的性能和交叉率的大小。交叉率是指各代中交叉产生的后代数与种群规模之比。交叉运算产生新个体，不断拓展搜

17、索空间，较高的交叉率可以搜索更大的解空间，从而降低停在非优解的机会；但是交叉率太高，会因搜索不必要的解空间而耗费大量的计算时间。常用的交叉率的取值范围为0.40.6。2022-5-1上海工程技术大学机械工程学院376.2 基本遗传算法3、 变异率 变异率也是遗传操作中的重要参数，它直接影响到算法的收敛性和最终解的性能。变异率是指种群中变异的基因数占总基因数的百分比。变异率控制了新基因引入的比例。在实际操作的过程中，算法常用变异率的数量级范围为0.10.001。或者在进化初期选择一个较大的值，而在进化后期变异概率随之减小。 2022-5-1上海工程技术大学机械工程学院386.2 基本遗传算法4.

18、 进化终止条件 化计算的终止可以从两方面进行控制：预先设定进化代数或者以种群的进化程度进行控制。种群的进化程度是指种群的当前代最大适应值与种群的平均适应值的比例关系。 2022-5-1上海工程技术大学机械工程学院396.2 基本遗传算法四、函数寻优实例 2022-5-1上海工程技术大学机械工程学院406.2 基本遗传算法1、染色体编码2022-5-1上海工程技术大学机械工程学院416.2 基本遗传算法2022-5-1上海工程技术大学机械工程学院426.2 基本遗传算法2、适应度计算2022-5-1上海工程技术大学机械工程学院436.2 基本遗传算法3、染色体的选择 2022-5-1上海工程技术

19、大学机械工程学院446.2 基本遗传算法2022-5-1上海工程技术大学机械工程学院456.2 基本遗传算法2022-5-1上海工程技术大学机械工程学院466.2 基本遗传算法4、交叉运算 2022-5-1上海工程技术大学机械工程学院476.2 基本遗传算法2022-5-1上海工程技术大学机械工程学院486.2 基本遗传算法5、变异运算 2022-5-1上海工程技术大学机械工程学院496.2 基本遗传算法2022-5-1上海工程技术大学机械工程学院506.2 基本遗传算法6、循环 2022-5-1上海工程技术大学机械工程学院516.3遗传算法的数学基础 一、模式定理 1、模式的定义 由编码串的

20、结构形式变化表明，模式是一个字符串集在某些位置上的相似性。对于二进制编码方式，个体是由二值编码串集0,1所组成，由此产生了常见的0,1编码串，再加入一个通配符“*”，其含义即可表示为0也可表示为1。这样就将二值字符串扩展成了三值字符串0,1,*，由此可以产生00110、01*11、*01*等编码串。n模式 ：描述基因串集中相似类基因串的模板，该类基因串中某些特征位结构相同，称为“模式”。 通俗地讲，基于三值字符集0,1,*所产生的一类能够描述在某些位置上具有结构相似性的0，1编码串集的编码，称为模式。2022-5-1上海工程技术大学机械工程学院526.3遗传算法的数学基础n模式阶(schema

21、 order)：模式H中确定位置的个数,称为该模式的阶，记作O(H)。 例如，在二进制编码中，一个模式的阶就是所有0和1的数目。模式H=*1*0*的阶数为2，记为O(H)2；，模式H=1*10*的阶数为3，记为O(H)3；显然一个模式的阶越高，其样本数就越少，其确定性也越高。n定义长度(Defining Length)：模式H中第一个确定位和最后一个确定位置的距离称作该模式的定义长度，记作。 例如：模式H=*1*0*的定义长度为2，记为(H)=2，这是因为第一个确定位置为3，最后一个确定位置为5，他们之间的距离(H)=5-3=2。若模式H=1*仅有一个确定位置，根据概念该模式的定义长度为0。2

22、022-5-1上海工程技术大学机械工程学院536.3遗传算法的数学基础2、选择对模式的影响 选择操作能使模式的数量以指数形式增减，但由于选择操作只能将某些高适应度的个体复制，低适应度的个体淘汰，它并不能产生新的模式结构，因而选择操作对性能的改进是有限的。 2022-5-1上海工程技术大学机械工程学院546.3遗传算法的数学基础3、交叉对模式的影响 交叉操作是基因串之间的有组织而又是随机的信息交换，它在创造新结构的同时，应尽可能少的破坏复制过程所选择的高适应度模式。 在选择和交叉操作共同作用下，模式数量的增长或减少，取决于其模式的平均适应度的高低和定义长度的长短，平均适应度越大，定义长度越小，则

23、H的数量就越多。 2022-5-1上海工程技术大学机械工程学院556.3遗传算法的数学基础4、变异对模式的影响 2022-5-1上海工程技术大学机械工程学院566.3遗传算法的数学基础5、模式定理 在遗传算子选择、交叉和变异的作用下，具有低阶、短定义长度以及平均适应度高于群体平均适应度的模式，将在子代中呈指数级地增长。 模式定理是遗传算法的理论基础，适用于二进制编码，对其他编码方式未必成立。 2022-5-1上海工程技术大学机械工程学院576.3遗传算法的数学基础二、积木块假设 由模式定理可知，具有低阶、短定义长度以及平均适应度高于群体平均适应度的模式，在子代中将呈指数级增长。这类模式在遗传算

24、法中非常重要，称之为积木块(Building Block)。 积木块假设(Building Block Hypothesis)：低阶、短定义长度、高平均适应度的模式在遗传算子作用下，相互结合，能生成高阶、长定义长度、高平均适应度的模式，可最终生成全局最优解。 2022-5-1上海工程技术大学机械工程学院586.4 遗传算法的改进一、早熟现象 在遗传算法进化的过程中，在某些时候会出现以下情况:(1）当群体中出现个别或极少数适应度值相当高的个体时,由于选择机制就有可能导致这些个体在群体中迅速繁殖，经过少数几次迭代后就占满了群体的位置, 这样GA的求解过程就结束了，但这样很有可能是收敛到局部最优解，

25、即遗传算法的不成熟收敛；（2）当群体中个体适应度彼此非常接近时，便失去了种群的多样性，这些个体进行交配的机会相等，而且交叉后得到的新个体也不会有多大变化，这样搜索过程也不能有效地进行，从而使进化过程陷于停顿的状态,。这两种情况统称“早熟”现象。2022-5-1上海工程技术大学机械工程学院596.4 遗传算法的改进二、自适应遗传算法 自适应遗传算法是指个体的交叉和变异率由个体在当前种群中的优良程度来自适应决定，并随遗传代数的变化而变化。动态自适应技术在进化过程中通过调整遗传控制参数可以克服早熟现象，在进化早期，群体中个体的差异较大，所以选择操作和交叉操作的作用比较明显，进化速度也较快；但在进化的

26、后期，由于选择问题和固定交叉、变异的问题使得种群中个体的近亲繁殖而造成的种群失去了多样性，其适应度值也比较接近，产生早熟现象。 2022-5-1上海工程技术大学机械工程学院606.4 遗传算法的改进1指数形式实现交叉和变异 指数形式的交叉和变异是指在进化过程中，交叉率和变异率随指数形式变化。 交叉率对遗传代数影响较大，这是因为在迭代初期，交换率选择得大一些可以造成足够的扰动，从而增强遗传算法的搜索能力，而在迭代后期，交换率选得小一些可以避免破坏优良基因，从而加快收敛速度。考虑到交换率随遗传代数变化下降的关系，可将算式可表示为 2022-5-1上海工程技术大学机械工程学院616.4 遗传算法的改

27、进2022-5-1上海工程技术大学机械工程学院626.4 遗传算法的改进2022-5-1上海工程技术大学机械工程学院636.4 遗传算法的改进2平均适应度形式实现交叉和变异 以平均适应度形式的交叉和变异是指在进化过程中，交叉率和变异率随该带的平均适应度变化而变化。 平均适应度在一定意义上反映整个种群的变化趋势，因此可以平均适应度形式判定种群中的交叉和变异率，即系统自适应产生的交叉和变异率必须同这一代的平均适应度相关联，如下式所示2022-5-1上海工程技术大学机械工程学院646.4 遗传算法的改进2022-5-1上海工程技术大学机械工程学院656.4 遗传算法的改进2022-5-1上海工程技术大学机械工程学院666.4 遗传算法的改进2022-5-1上海工程技术大学机械工程学院676.4 遗传算法的改进三、小生境技术 在遗传进化过程中，尤其是对于一些多峰值函数的优化计算时，在寻优过程中往往都会找一些局部最优解并徘徊其中，很难跳出。使得进化后期大量个体收敛于该局部优化解从而陷入早熟的现象。为此，小生境技术的引入也是为了实现寻优过程的全局最优。几种小生境策略： 2022-5-1上海工程技术大学机械工程学院