遗传GA算法课件

关于遗传GA算法第1页，讲稿共54页，2023年5月2日，星期三遗传算法起源

遗传算法是由美国的J.Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。遗传算法介绍第2页，讲稿共54页，2023年5月2日，星期三1、智能优化算法智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。遗传算法介绍第3页，讲稿共54页，2023年5月2日，星期三常用的智能优化算法

（1）遗传算法（GeneticAlgorithm，简称GA）（2）模拟退火算法（SimulatedAnnealing，简称SA）（3）禁忌搜索算法（TabuSearch，简称TS）

……遗传算法介绍第4页，讲稿共54页，2023年5月2日，星期三传统的优化方法（局部优化）（1）共轭梯度法（ConjugateGradient，简称CG）（2）拟牛顿法（Quasi-Newton，简称QN）（3）单纯形方法（SimplexMethod）

……遗传算法介绍第5页，讲稿共54页，2023年5月2日，星期三遗传算法介绍比较：传统的优化方法

1）依赖于初始条件。

2）与求解空间有紧密关系，促使较快地收敛到局部解，但同时对解域有约束，如可微或连续。利用这些约束，收敛快。

3）有些方法，如Davison-Fletcher-Powell直接依赖于至少一阶导数；共轭梯度法隐含地依赖于梯度。第6页，讲稿共54页，2023年5月2日，星期三全局优化方法1）不依赖于初始条件；2）不与求解空间有紧密关系，对解域，无可微或连续的要求。求解稳健，但收敛速度慢。能获得全局最优。适合于求解空间不知的情况遗传算法介绍第7页，讲稿共54页，2023年5月2日，星期三⑴选择运算⑵交换操作⑶变异遗传算法的基本运算遗传算法原理

模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量——染色体，向量的每个元素称为基因。通过不断计算各染色体的适应值，选择最好的染色体，获得最优解。第8页，讲稿共54页，2023年5月2日，星期三●选择运算——从旧的种群中选择适应度高的染色体，放入匹配集（缓冲区），为以后染色体交换、变异，产生新的染色体作准备。选择方法——适应度比例法（转轮法）按各染色体适应度大小比例来决定其被选择数目的多少。某染色体被选的概率：Pcxi为种群中第i个染色体，第9页，讲稿共54页，2023年5月2日，星期三具体步骤1）计算各染色体适应度值2）累计所有染色体适应度值，记录中间累加值S-mid和最后累加值sum=∑f(xi)3）产生一个随机数N，0〈N〈sum4）选择对应中间累加值S-mid的第一个染色体进入交换集

5）重复（3）和（4），直到获得足够的染色体。举例：⒈具有6个染色体的二进制编码、适应度值、Pc累计值。第10页，讲稿共54页，2023年5月2日，星期三染色体的适应度和所占的比例用转轮方法进行选择第11页，讲稿共54页，2023年5月2日，星期三染色体编号12345678910适应度8217721211737被选概率0.10.020.220.090.020.160.140.090.030.09适应度累计8

10

273436

48

59

666976随机数2349761312757所选染色体号码37103137染色体被选的概率被选的染色体个数例2、10个染色体种群按比例的选择过程第12页，讲稿共54页，2023年5月2日，星期三●交换操作

方法:随机选择二个染色体(双亲染色体),随机指定一点或多点,进行交换,可得二个新的染色体(子辈染色体).新的子辈染色体:A’11010001B’01011110模拟生物在自然界环境变化,引起基因的突变.在染色体二进制编码中,1变成0;或0变成1.突变产生染色体的多样性,避免进化中早期成熟,陷入局部极值点,突变的概率很低.●变异复制不能创新,交换解决染色体的创新第13页，讲稿共54页，2023年5月2日，星期三GA的流程第14页，讲稿共54页，2023年5月2日，星期三简单遗传算法（GA）的基本参数①种群规模P:参与进化的染色体总数.②代沟G:二代之间不相同的染色体数目,无重叠G=1;

有重叠0<G<1③选择方法:转轮法,精英选择法,竞争法.④交换率:Pc一般为60~100%.⑤变异率:Pm一般为0.1~10%举例:变异概率取0.001第15页，讲稿共54页，2023年5月2日，星期三初始种群和它的适应度值染色体的交换操纵第16页，讲稿共54页，2023年5月2日，星期三举例：函数图第17页，讲稿共54页，2023年5月2日，星期三步骤1）编码：确定二进制的位数；组成个体（染色体）步骤2）选择种群数P和初始个体，计算适应度值，

P=50；步骤3）确定选择方法；交换率PC；变异率Pm。选择方法用竞争法；PC=0.25,Pm=0.01第18页，讲稿共54页，2023年5月2日，星期三第19页，讲稿共54页，2023年5月2日，星期三遗传算法数学基础（1）模式定理（2）积木块假设第20页，讲稿共54页，2023年5月2日，星期三模式

模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三个字符集(0,1,*)的字符串，符号*代表任意字符，即0或者1。

模式示例：10**1第21页，讲稿共54页，2023年5月2日，星期三两个定义定义1：模式H中确定位置的个数称为模式H的阶，记作O(H)。定义2：模式H中第一个确定位置和最后一个确定位置之间的距离称为模式H的定义距，记作δ(H)。第22页，讲稿共54页，2023年5月2日，星期三模式的描述：第23页，讲稿共54页，2023年5月2日，星期三模式的阶和定义距的含义

模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。第24页，讲稿共54页，2023年5月2日，星期三模式定理模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗传算法机理提供了数学基础。模式定理：在选择、交换、变异的作用下，阶次低、定义长度短、适应度高的图式（模块）将按指数增长的规律，一代一代地增长。第25页，讲稿共54页，2023年5月2日，星期三模式定理的推导①模式式在选择过程中的增加.第26页，讲稿共54页，2023年5月2日，星期三经过选择，在t+1代，模式H的数量m(H,t+1)为:

第27页，讲稿共54页，2023年5月2日，星期三②模式在交换中的破坏③模式在变异中的破坏经过选择、交换、变异后在t+1中，模式H的数量：第28页，讲稿共54页，2023年5月2日，星期三模式定理从模式定理可看出，有高平均适应度、短定义距、低阶的模式，在连续的后代里获得至少以指数增长的串数目，这主要是因为选择使最好的模式有更多的复制，交叉算子不容易破坏高频率出现的、短定义长的模式，而一般突变概率又相当小，因而它对这些重要的模式几乎没有影响。第29页，讲稿共54页，2023年5月2日，星期三积木块假设积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解。模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的作用下，能生成全局最优解。第30页，讲稿共54页，2023年5月2日，星期三2、遗传算法的收敛性分析

遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。第31页，讲稿共54页，2023年5月2日，星期三种群规模对收敛性的影响

通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。第32页，讲稿共54页，2023年5月2日，星期三选择操作对收敛性的影响选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率1收敛于全局最优解。第33页，讲稿共54页，2023年5月2日，星期三交叉概率对收敛性的影响

交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。第34页，讲稿共54页，2023年5月2日，星期三变异概率对收敛性的影响

变异操作是对种群模式的扰动，有利于增加种群的多样性。但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。第35页，讲稿共54页，2023年5月2日，星期三Schaffer建议的最优参数范围是：

Population=20-100，

Generation=100-500，

Pc=0.4-0.9，

Pm=0.001-0.01。第36页，讲稿共54页，2023年5月2日，星期三遗传算法的应用（1）优化A、函数优化B、组合优化：确定与问题相关的某些项的排列（如资源约束的项目调度问题、车辆路径和调度问题等）确定某些项的组合（如集覆盖问题和群体问题等）确定某些项的排列和组合（如并行机器调度问题等）任何带有约束的上述类型第37页，讲稿共54页，2023年5月2日，星期三遗传算法的应用1、总体方案设计方面机械现代设计目标要求为功能-质量-成本的系统化，它包括方案选择、材料选择、结构优化、工艺规划、可靠性分析及成本分析等众多因素与综合知识，将遗传算法与CAD技术结合解决系统的优化问题。2、系列化标准件选取方面应用遗传算法的组合优化来解决机械系统中多种系列化标准的组合选取问题。通常主要靠经验的选取，用这类组合优化来解决，使组合系列化，选取更科学化。第38页，讲稿共54页，2023年5月2日，星期三遗传算法的应用3、反求工程方面若要建立原设计产品的数学模型,因一些设计参数和工艺参数往往不易确定,可用遗传算法和计算机仿真技术,把这些参数作为参变量进行编码,在使原设计产品的性能和数学模型的仿真性能之间差异最小的目标下,获得最符合原设计的设计与工艺参数。与此同时,利用遗传算法的优化设计将所建立的原设计的数学模型改进,从而改进原产品设计。4、可靠性分析方面为了使机械系统获得最高可靠性,可以用遗传算法进行系统可靠度分配；在机械维修期望损失最小的前提下，用遗传算法确定机械系统最优维修策略；在原始统计数据基础上,把失效分布模型及其参数作为参变量进行编码，可用遗传算法建立更符合实际的失效分布模型。第39页，讲稿共54页，2023年5月2日，星期三遗传算法的应用5、节能设计方面对于汽车、机床等设备的电机类型、电气控制参数、机械传动方案与参数等,以这些参数为参变量编码，把能耗降低到最小目标，在满足功能要求的约束下,利用遗传优化算法进行节能设计,使设备达到最佳效果。6、FMS(柔性制造系统)调度方面使待加工的零件在FMS系统的制造时间最短，将该零件加工次序进行编码，用遗传优化运算实现最短时间加工；针对一个需多工序加工的零件，为确定每道工序所合理分配设备,对每道工序分配设备号编码,在各台设备的负荷可能相等的前提下,用遗传算法实现机床设备的最优分配。第40页，讲稿共54页，2023年5月2日，星期三遗传算法的应用7、数控加工误差自适应预报控制方面在获得误差实时检测(或序后测量)数据后,对误差模型结构和参数进行编码，用遗传算法建立最优的误差模型。再根据误差预报的误差修改数控加工次程序,实现加工误差和自适应控制。第41页，讲稿共54页，2023年5月2日，星期三遗传算法的应用实例实例1、用衬垫密封的压力容器同盖之间的联接属于紧固螺栓联接第42页，讲稿共54页，2023年5月2日，星期三遗传算法的应用实例已知：E和H、D0和p。选择螺栓的直径和个数，使成本更低适应度函数：第43页，讲稿共54页，2023年5月2日，星期三遗传算法的应用实例迭代到第30代时最优解为D=17，N=6，参照35号钢。采用正火处理的螺栓许用载荷取整为D=18，N=6。达到设计要求。第44页，讲稿共54页，2023年5月2日，星期三遗传算法的应用对大规模控制系统进行综合设计并建立数学模型，在对数学模型的优化上，遗传算法具有其它进化算法无法比拟的优点，已取得一定成绩。例如用遗传算法对自动控制系统数学模型寻优、用遗传算法优化PID控制系统、遗传算法在加工过程智能最优自适应控制的应用、基于遗传算法的模糊控制器的优化设计等。（2）自动控制第45页，讲稿共54页，2023年5月2日，星期三遗传算法的应用实例实例2、甘肃工业大学所研制的径向变量柱塞泵控制系统其中G(s)是广义对象，K为控制器；信号w代表所有的外部输入，包括外部扰动、传感器噪声和参考输入量；输出量z为误差信号；Y为可测变量；U为控制变量第46页，讲稿共54页，2023年5月2日，星期三遗传算法的应用实例第47页，讲稿共54页，2023