《第七章遗传算法简介.ppt》由会员分享,可在线阅读,更多相关《第七章遗传算法简介.ppt(111页珍藏版)》请在三一文库上搜索。
1、第七章 遗传算法与控制简介,模拟进化计算(Simulated Evolutionary Computation)是近十几年来信息科学、人工智能与计算机科学的一大研究领域,由此所派生的求解优化问题的仿生类算法(遗传算法、演化策略、进化程序),由于其鲜明的生物背景、新颖的设计原理、独特的分析方法和成功的应用实践,正日益形成全局搜索与多目标优化理论的一个崭新分支。 遗传算法(Genetic Algorithm,简称GA)是通过模拟生物进化过程来完成优化搜索的。,科学研究、工程实际与国民经济发展的众多问题可归结为“最大效益、最小代价”这类典型的优化模型。求解这类模型导致寻求某个目标函数(有解析表达式或
2、无解析表达式)在特定区域上的最优解,传统的建立在梯度计算基础上的非线性规划类方法,当目标函数仅具有单极点时,通常表现出较高的计算效率,但当目标函数具有多极值点时,由于其本身固有的局部优化性及不稳健等缺陷,而被广泛认为不适于全局优化问题的求解。近二十年来,人们相继发展了许多求解全局优化问题的方法,一般可分为确定型与非确定型(如随机搜索)算法。Monto-Carlo方法及模拟退火算法都归属后者。当目标函数具有为数不多的极值点时,确定型算法常表现出较高的计算效率,但同时也暴露出算法复杂、对目标函数的性质要求高、可靠性差等缺点。相比而言,随机搜索方法具有较强的鲁棒性,算法容易实现,但常有计算效率低的缺
3、点。,仿生类算法是近十几年来才发展起来的一类新型全局优化搜索技术,它们通过向自然界学习,借鉴生物进化机制求解问题。这类算法的主要优点在于其本质上的并行性、广泛的可适用性(如对目标函数的性态无特殊要求,特别可以没有明确的表达式)和较强的鲁棒性、简明性与全局优化性能。虽然从基本思想的产生至今已有二、三十年的历史,但广泛用于求解优化问题还是近十几年的事。初步研究及广泛的应用实践已显示出它们作为可靠、有效的全局优化算法的巨大潜力和诱人前景。 仿生类算法,就其目前发展而言,可分为仿生过程算法与仿生结构算法两大类,前者以模拟进化算法为代表,后者以神经网络为典型。,遗传算法的生物学背景,适者生存:最适合自然
4、环境的群体往往产生了更大的后代群体。 生物进化的基本过程:,染色体(chromosome):生物的遗传物质的主要载体。 基因(gene):扩展生物性状的遗传物质的功能单元和结构单位。 基因座(locus):染色体中基因的位置。 等位基因(alleles):基因所取的值。,遗传算法的基本思想: 在求解问题时从多个解开始,然后通过一定的法则进行逐步迭代以产生新的解。,遗传算法的发展历史,1962年,Fraser提出了自然遗传算法。 1965年,Holland首次提出了人工遗传操作的重要性。 1967年,Bagley首次提出了遗传算法这一术语。 1970年,Cavicchio把遗传算法应用于模式识别
5、中。 1971年,Hollstien在论文计算机控制系统中人工遗传自适应方法中阐述了遗传算法用于数字反馈控制的方法。 1975年,美国J. Holland出版了自然系统和人工系统的适配;DeJong完成了重要论文遗传自适应系统的行为分析。 20世纪80年代以后,遗传算法进入兴盛发展时期。,设计遗传算法的基本原则与内容,设计的基本原则:,设计的基本内容:,设计遗传算法的基本原则与内容,遗传算法的搜索机制,遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象,在每次迭代中都保留一组候选解,并按某种指标从解群中选取较优的个体,利用遗传算子(选择、交叉和变异)对这些个体进行组合,产生新一
6、代的候选解群,重复此过程,直到满足某种收敛指标为止。,基本遗传算法,基本遗传算法(Simple Genetic Algorithms,简称SGA,又称简单遗传算法或标准遗传算法),是由Goldberg总结出的一种最基本的遗传算法,其遗传进化操作过程简单,容易理解,是其它一些遗传算法的雏形和基础。,基本遗传算法的组成,遗传算法的五个基本要素: 参数编码 初始群体的设定 适应度函数的设计 遗传操作设计 控制参数设定,编码,位串编码,一维染色体编码方法:将问题空间的参数编码为一维排列的染色体的方法。,二进制编码:用若干二进制数表示一个个体,将原问题的解空间映射到位串空间 B=0,1上,然后在位串空间
7、上进行遗传操作。,(1) 二进制编码,编码,(1) 二进制编码(续),优点: 类似于生物染色体的组成,算法易于用生物遗传理论解释,遗传操作如交叉、变异等易实现;算法处理的模式数最多。,缺点: 相邻整数的二进制编码可能具有较大的Hamming距离,降低了遗传算子的搜索效率。 15:01111 16: 10000 要先给出求解的精度。 求解高维优化问题的二进制编码串长,算法的搜索效率低。,编码,(2) Gray 编码,Gray编码:将二进制编码通过一个变换进行转换得到的编码。,编码,2. 实数编码,采用实数表达法不必进行数制转换,可直接在解的表现型上进行遗传操作。 多参数映射编码的基本思想:把每个
8、参数先进行二进制编码得到子串,再把这些子串连成一个完整的染色体。 多参数映射编码中的每个子串对应各自的编码参数,所以,可以有不同的串长度和参数的取值范围。,编码,3. 有序串编码,有序问题:目标函数的值不仅与表示解的字符串的值有关,而且与其所在字符串的位置有关。,4结构式编码,Goldberg等提出MessyGA(mGA)的遗传算法编码方法。,初始种群的产生,群体设定,(1)根据问题固有知识,把握最优解所占空间在整个问题空间中的分布范围,然后,在此分布范围内设定初始群体。 (2)随机产生一定数目的个体,从中挑选最好的个体加到初始群体中。这种过程不断迭代,直到初始群体中个体数目达到了预先确定的规
9、模。,2. 种群规模的确定,群体设定,模式定理表明:若群体规模为M,则遗传操作可从这M 个个体中生成和检测 个模式,并在此基础上能够不断形成和优化积木块,直到找到最优解。,群体规模太小,遗传算法的优化性能不太好,易陷入局部最优解。 群体规模太大,计算复杂。,将目标函数映射成适应度函数的方法,适应度函数,若目标函数为最大化问题,则 若目标函数为最小化问题,则,将目标函数转换为求最大值的形式,且保证函数值非负!,若目标函数为最大化问题,则 若目标函数为最小化问题,则,将目标函数映射成适应度函数的方法(续),适应度函数,存在界限值预选估计困难或者不能精确估计的问题!,若目标函数为最大化问题,则 若目
10、标函数为最小化问题,则 :目标函数界限的保守估计值。,适应度函数的尺度变换,在遗传算法中,将所有妨碍适应度值高的个体产生,从而影响遗传算法正常工作的问题统称为欺骗问题(deceptive problem)。,过早收敛:缩小这些个体的适应度,以降低这些超级个体的竞争力。,停滞现象:改变原始适应值的比例关系,以提高个体之间的竞争力。,适应度函数的尺度变换(fitness scaling)或者定标:对适应度函数值域的某种映射变换。,适应度函数,适应度函数的尺度变换(续),(1)线性变换:,满足,适应度函数,适应度函数的尺度变换(续),(2)幂函数变换法:,(3)指数变换法:,适应度函数,选择,个体选
11、择概率分配方法 选择操作也称为复制(reproduction)操作:从当前群体中按照一定概率选出优良的个体,使它们有机会作为父代繁殖下一代子孙。 判断个体优良与否的准则是各个个体的适应度值:个体适应度越高,其被选择的机会就越多。,个体选择概率分配方法 (1)适应度比例方法(fitness proportional model)或蒙特卡罗法(Monte Carlo),各个个体被选择的概率和其适应度值成比例。,个体 被选择的概率为:,选择,1. 个体选择概率分配方法 (2) 排序方法 (rank-based model), 线性排序:J. E. Baker,群体成员按适应值大小从好到坏依次排列:
12、个体 按转盘式选择的方式选择父体,选择,1. 个体选择概率分配方法 (2) 排序方法 (rank-based model), 非线性排序: Z. Michalewicz,将群体成员按适应值从好到坏依次排列,并按下式分配选择概率:,选择,1.个体选择概率分配方法 (2) 排序方法 (rank-based model),可用其他非线性函数来分配选择概率,只要满足以下条件:,选择,2. 选择个体方法 (1)转盘赌选择(roulette wheel selection),按个体的选择概率产生一个轮盘,轮盘每个区的角度与个体的选择概率成比例。 产生一个随机数,它落入转盘的哪个区域就选择相应的个体交叉。,
13、第1轮产生一个随机数:0.81,第2轮产生一个随机数:0.32,选择,2. 选择个体方法 (2)锦标赛选择方法(tournament selection model),锦标赛选择方法:从群体中随机选择个个体,将其中适应度最高的个体保存到下一代。这一过程反复执行,直到保存到下一代的个体数达到预先设定的数量为止。,随机竞争方法(stochastic tournament):每次按赌轮选择方法选取一对个体,然后让这两个个体进行竞争,适应度高者获胜。如此反复,直到选满为止。,选择,2. 选择个体方法 (3) 和 选择,从规模为 的群体中随机选取个体通过重组和变异生成 个后代, 再选取 个最优的后代作为
14、新一代种群。,从 个后代与其父体共 中选取 个最优的后代。,选择,2. 选择个体方法 (4)Boltzmann锦标赛选择,最佳个体(elitist model)保存方法:把群体中适应度最高的个体不进行交叉而直接复制到下一代中,保证遗传算法终止时得到的最后结果一定是历代出现过的最高适应度的个体。,(5)最佳个体保存方法,随机选取两个个体 ,若 则选择适应值好的作为胜者,否则计算概率 ,若 ,选择差解,否则选择好解。,选择,交叉,1. 基本的交叉算子 (1)一点交叉(single-point crossover),一点交叉:在个体串中随机设定一个交叉点,实行交叉时,该点前或后的两个个体的部分结构进
15、行互换,并生成两个新的个体。,二点交叉:随机设置两个交叉点,将两个交叉点之间的码串相互交换。,(2)二点交叉 (two-point crossover),交叉,基本的交叉算子(续),均匀交叉:按照均匀概率抽取一些位,每一位是否被选取都是随机的,并且独立于其他位。然后将两个个体被抽取位互换组成两个新个体。,(3)均匀交叉(uniform crossover)或一致交叉,交叉,2. 修正的交叉方法 (1)部分匹配交叉PMX:Goldberg D. E.和R. Lingle(1985),2. 修正的交叉方法(续) (2)顺序交叉OX:Davis L. (1985),(3) 循环交叉CX:Smith
16、D. (1985),交叉,3. 实数编码的交叉方法 (1)离散交叉(discrete crossover),部分离散交叉:在父解向量中选择一部分分量,然后交换这些分量。 二进制的点式交叉,整体离散交叉:以0.5的概率交换父体 的所有分量。 二进制编码的均匀性交叉,交叉,3. 实数编码的交叉方法(续) (2)算术交叉(arithmetical crossover),部分算术:先在父解向量中选择一部分分量,如第 个分量以后的所有分量,然后生成 个0,1区间的随机数,并将两个后代定义为:,交叉,3. 实数编码的交叉方法(续) (2)算术交叉(arithmetical crossover),整体算术交
17、叉:先生成 n 个区间的随机数,则后代分别定义为:,交叉,1. 整数编码的变异方法 (1)位点变异:群体中的个体码串,随机挑选一个或多个基因座,并对这些基因座的基因值以变异概率作变动。,(2)逆转变异:在个体码串中随机选择两点(逆转点),然后将两点之间的基因值以逆向排序插入到原位置中。,(3)插入变异:在个体码串中随机选择一个码,然后将此码插入随机选择的插入点中间。,变异,变异,1. 整数编码的变异方法(续) (4)互换变异:随机选取染色体的两个基因进行简单互换。 (5)移动变异:随机选取一个基因,向左或者向右移动一个随机位数。 (6)自适应变异:类似于位点变异,但变异概率随群体中个体的多样性
18、程度而自适应调整。,2. 实数编码的变异方法 (1)均匀性变异,均匀性变异:在父解向量中随机地选择一个分量(第 个),然后在 中以均匀概率随机选择 代替 以得到 ,即,变异,2. 实数编码的变异方法(续) (2)正态性变异(normal distributed mutation),变异,2. 实数编码的变异方法(续) (3)非一致性变异,Z. Michalewicz首先提出将变异算子的结果与演化代数联系起来。 在演化初期,变异范围相对较大,而随着演化的推进,变异范围越来越小,起着一种对演化系统的微调作用。,变异,2. 实数编码的变异方法(续) (4)自适应变异,自适应变异方式与非一致性变异算子
19、相同,只是将其中的演化代数 改为 ,函数表达式变为:,变异,遗传算法的一般步骤,遗传算法的简单实例,简单实例 产生初始种群 计算适应度,0001100000 0101111001 0000000101 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011,(8) (5) (2) (10) (7) (12) (5) (19) (10) (14),遗传算法的简单实例,简单实例 选择,0.086957,0.054348,0.021739 0.108696 0.076087 0.130435 0.054
20、348 0.206522 0.108696 0.152174,遗传算法的简单实例,简单实例 选择,0.086957,0.054348,0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.108696 0.152174,0.086957,0.141304,0.163043,0.271739 0.347826 0.478261 0.532609 0.739130 0.847826 1.000000,遗传算法的简单实例,简单实例 选择 在01之间产生一个 随机数:,0.086957,0.054348,0.021739 0.108696 0.
21、076087 0.130435 0.054348 0.206522 0.108696 0.152174,0.086957,0.141304,0.163043,0.271739 0.347826 0.478261 0.532609 0.739130 0.847826 1.000000,0.070221,0.545929,0.784567,0.446930,0.507893,0.291198,0.716340,0.270901,0.371435,0.854641,遗传算法的简单实例,遗传算法的简单实例,遗传算法的简单实例,简单实例 至下一代,适应度计算选择交叉变异,直至满足终止条件。,函数优化示例
22、,求下列一元函数的最大值:,x-1,2 ,求解结果精确到6位小数。,SGA对于本例的编码,由于区间长度为3,求解结果精确到6位小数,因此可将自变量定义区间划分为3106等份。又因为221 3106 222 ,所以本例的二进制编码长度至少需要22位,本例的编码过程实质上是将区间-1,2内对应的实数值转化为一个二进制串(b21b20b0)。,几个术语,基因型:1000101110110101000111,表现型:0.637197,编码,解码,个体(染色体),基因,初始种群,SGA采用随机方法生成若干个个体的集合,该集合称为初始种群。初始种群中个体的数量称为种群规模。,适应度函数,遗传算法对一个个体
23、(解)的好坏用适应度函数值来评价,适应度函数值越大,解的质量越好。适应度函数是遗传算法进化过程的驱动力,也是进行自然选择的唯一标准,它的设计应结合求解问题本身的要求而定。,选择算子,遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作:适应度高的个体被遗传到下一代群体中的概率大;适应度低的个体,被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体,遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。,轮盘赌选择方法,轮盘赌选择又称比例选择算子,它的基本思想是:各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n ,个体i 的适应度为 Fi,则个体i
24、 被选中遗传到下一代群体的概率为:,轮盘赌选择方法的实现步骤,(1) 计算群体中所有个体的适应度函数值(需要解码); (2) 利用比例选择算子的公式,计算每个个体被选中遗传到下一代群体的概率; (3) 采用模拟赌盘操作(即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配)来确定各个个体是否遗传到下一代群体中。,交叉算子,所谓交叉运算,是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因,从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征,它在遗传算法中起关键作用,是产生新个体的主要方法。 SGA中交叉算子采用单点交叉算子。,单点交叉运算,交
25、叉前: 00000|01110000000010000 11100|00000111111000101 交叉后: 00000|00000111111000101 11100|01110000000010000,交叉点,变异算子,所谓变异运算,是指依据变异概率 Pm 将个体编码串中的某些基因值用其它基因值来替换,从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法,它决定了遗传算法的局部搜索能力,同时保持种群的多样性。交叉运算和变异运算的相互配合,共同完成对搜索空间的全局搜索和局部搜索。 SGA中变异算子采用基本位变异算子。,基本位变异算子,基本位变异算子是指对个体编码串随机指定的某
26、一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体,若需要进行变异操作的某一基因座上的原有基因值为0,则变异操作将其变为1;反之,若原有基因值为1,则变异操作将其变为0 。,基本位变异算子的执行过程,变异前: 000001110000000010000 变异后: 000001110001000010000,变异点,运行参数,(1)M : 种群规模 (2)T : 遗传运算的终止进化代数 (3)Pc : 交叉概率 (4)Pm : 变异概率,SGA的框图,遗传算法的特点,(1)群体搜索,易于并行化处理; (2)不是盲目穷举,而是启发式搜索; (3)适应度函数不受连续、可微等
27、条件的约束,适 用范围很广。,遗传算法原理,1、遗传算法的数学基础 2、遗传算法的收敛性分析 3、遗传算法的改进,遗传算法的数学基础,(1)模式定理 (2)积木块假设,模式,模式是指种群个体基因串中的相似样板,它用来描述基因串中某些特征位相同的结构。在二进制编码中,模式是基于三个字符集(0,1,*)的字符串,符号*代表任意字符,即 0 或者 1。 模式示例:10*1,两个定义,定义1:模式 H 中确定位置的个数称为模式 H 的阶,记作O(H)。例如O(10*1)=3 。 定义2:模式 H 中第一个确定位置和最后一个确定位置之间的距离称为模式 H 的定义距,记作(H)。例如(10*1)=4 。,
28、模式的阶和定义距的含义,模式阶用来反映不同模式间确定性的差异,模式阶数越高,模式的确定性就越高,所匹配的样本数就越少。在遗传操作中,即使阶数相同的模式,也会有不同的性质,而模式的定义距就反映了这种性质的差异。,模式定理,模式定理:具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。 模式定理保证了较优的模式(遗传算法的较优解)的数目呈指数增长,为解释遗传算法机理提供了数学基础。,模式定理,从模式定理可看出,有高平均适应度、短定义距、低阶的模式,在连续的后代里获得至少以指数增长的串数目,这主要是因为选择使最好的模式有更多的复制,交叉算子不容易破坏高频率出现的、短定义长的模
29、式,而一般突变概率又相当小,因而它对这些重要的模式几乎没有影响。,积木块假设,积木块假设:遗传算法通过短定义距、低阶以及高平均适应度的模式(积木块),在遗传操作下相互结合,最终接近全局最优解。 模式定理保证了较优模式的样本数呈指数增长,从而使遗传算法找到全局最优解的可能性存在;而积木块假设则指出了在遗传算子的作用下,能生成全局最优解。,遗传算法的收敛性分析,遗传算法要实现全局收敛,首先要求任意初始种群经有限步都能到达全局最优解,其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。,种群规模对收敛性的影响,通常,种群太小则不能提供足够的
30、采样点,以致算法性能很差;种群太大,尽管可以增加优化信息,阻止早熟收敛的发生,但无疑会增加计算量,造成收敛时间太长,表现为收敛速度缓慢。,选择操作对收敛性的影响,选择操作使高适应度个体能够以更大的概率生存,从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略,即将父代群体中最佳个体保留下来,不参加交叉和变异操作,使之直接进入下一代,最终可使遗传算法以概率1收敛于全局最优解。,交叉概率对收敛性的影响,交叉操作用于个体对,产生新的个体,实质上是在解空间中进行有效搜索。交叉概率太大时,种群中个体更新很快,会造成高适应度值的个体很快被破坏掉;概率太小时,交叉操作很少进行,从而会使搜索停滞不前,
31、造成算法的不收敛。,变异概率对收敛性的影响,变异操作是对种群模式的扰动,有利于增加种群的多样性 。但是,变异概率太小则很难产生新模式,变异概率太大则会使遗传算法成为随机搜索算法。,遗传算法的本质,遗传算法本质上是对染色体模式所进行的一系列运算,即通过选择算子将当前种群中的优良模式遗传到下一代种群中,利用交叉算子进行模式重组,利用变异算子进行模式突变。通过这些遗传操作,模式逐步向较好的方向进化,最终得到问题的最优解。,遗传算法的改进,遗传欺骗问题:在遗传算法进化过程中,有时会产生一些超常的个体,这些个体因竞争力太突出而控制了选择运算过程,从而影响算法的全局优化性能,导致算法获得某个局部最优解。,
32、遗传算法的改进途径,(1)对编码方式的改进 (2)对遗传算子 的改进 (3)对控制参数的改进 (4)对执行策略的改进,对编码方式的改进,二进制编码优点在于编码、解码操作简单,交叉、变异等操作便于实现,缺点在于精度要求较高时,个体编码串较长,使算法的搜索空间急剧扩大,遗传算法的性能降低。格雷编码克服了二进制编码的不连续问题 ,浮点数编码改善了遗传算法的计算复杂性 。,对遗传算子 的改进,排序选择 均匀交叉 逆序变异,(1) 对群体中的所有个体按其适应度大小进行降序排序; (2) 根据具体求解问题,设计一个概率分配表,将各个概率值按上述排列次序分配给各个个体; (3) 以各个个体所分配到的概率值作
33、为其遗传到下一代的概率,基于这些概率用赌盘选择法来产生下一代群体。,对遗传算子 的改进,排序选择 均匀交叉 逆序变异,(1) 随机产生一个与个体编码长度相同的二进制屏蔽字P = W1W2Wn ; (2) 按下列规则从A、B两个父代个体中产生两个新个体X、Y:若Wi = 0,则X的第i个基因继承A的对应基因,Y的第i个基因继承B的对应基因;若Wi = 1,则A、B的第i个基因相互交换,从而生成X、Y的第i个基因。,对遗传算子 的改进,排序选择 均匀交叉 逆序变异,变异前: 3 4 8 | 7 9 6 5 | 2 1 变异前: 3 4 8 | 5 6 9 7 | 2 1,对控制参数的改进,Scha
34、ffer建议的最优参数范围是: M = 20-100, T = 100-500, Pc = 0.4-0.9, Pm = 0.001-0.01。,对控制参数的改进,Srinvivas等人提出自适应遗传算法,即PC和Pm能够随适应度自动改变,当种群的各个个体适应度趋于一致或趋于局部最优时,使二者增加,而当种群适应度比较分散时,使二者减小,同时对适应值高于群体平均适应值的个体,采用较低的PC和Pm,使性能优良的个体进入下一代,而低于平均适应值的个体,采用较高的PC和Pm,使性能较差的个体被淘汰 。,对执行策略的改进,混合遗传算法 免疫遗传算法 小生境遗传算法 单亲遗传算法 并行遗传算法,遗传算法的应
35、用,1、遗传算法的应用领域 2、遗传算法的应用示例,遗传算法的应用领域,(1)组合优化 (2)函数优化 (3)自动控制 (4)生产调度 (5)图像处理 (6)机器学习 (7)人工生命 (8)数据挖掘,遗传算法的应用示例,例设有函数 ,求其在0,31区间的最大 值。 (1)确定适当的编码,把问题的可能解表示为染色体数字串。 因为有一个决策变量,其取值范围为0,31,25=32,使用5位 无符号二进制数组成的染色体数字串,即可表达变量x,以及问 题的解答方案。 (2)选择初始种群。通过随机的方法产生由4个染色体的数字 串组成的初始种群。,遗传算法的应用示例,(3)计算适应度值及选择概率。 此问题中
36、染色体的适应度取为函数自身 ,为计算每 个染色体的适应度,先将染色体解码,求出其二进制数字串等 价的十进制数,即x值。再由x值计算目标函数的值 。 在此基础上计算选择概率 和适应度期望值 ,计算结果如上表所示。,遗传算法的应用示例,(4)选择进入交换集的染色体。 按适应度比例法,选择进入交换集的染色体,如上表所示,染 色体1和4均被选择了1次;染色体2被选择了2次;染色体3没有 被选择。也就是说染色体3被淘汰了。所选择的4个染色体被送 到交换集,准备参加交换。,遗传算法的应用示例,(5)交换染色体。 首先对进入交换集的染色体进行随机配对,此例中是染色体2和 1配对,染色体4和3配对。接着随机确
37、定交换位置,结果是第1 对染色体交换位置是4,第2对染色体交换位置为2。经交换操作 后得到的新种群如下表所示。 (6)变异。此例中变异概率取为0.001。由于种群中4个染色体 总共有20位代码,变异的期望次数为20*0.001=0.02位,这意味 着本群体不进行变异操作。,遗传算法的应用示例,从上表可以看出,虽然仅进行了一代遗传操作,但种群适应度 的平均值及最大值却比初始种群有了很大的提高,平均由293变 到439,最大值由576变到729。这说明随着遗传运算的进行,种 群正向着优化的方向发展。,基于遗传算法的PID控制简介,遗传算法(Genetic Algorithm,以下简称GA)是一种基
38、于自然选择和基因遗传原理的迭代自适应概率性搜索算法。基本思想就是将待求解问题转换成由个体组成的演化群体和对该群体进行操作的一组遗传算子,包括3个基本操作:复制(reproduction)、交叉(cross- over)、变异(mutation)。其基本流程如图所示。基于遗传算法的PID具有以下特点: (1) 把时域指标同频域指标做了紧密结合,鲁棒性和时域性能都得到良好保证; (2) 采用了新型自适应遗传算法,收敛速度和全局优化能力大大提高; (3) 具有较强的直观性和适应性; (4)较为科学地解决了确定参数搜索空间的问题,克服了人为主观设定的盲目性。,基于遗传算法的PID控制简介,基于遗传算法
39、的PID控制简介,1、基于遗传算法的PID参数优化设计 基于遗传算法的自适应PID控制的原理框图如图所示,图中省略了遗传算法的具体操作过程。其思想就是将控制器参数构成基因型,将性能指标构成相应的适应度,便可利用遗传算法来整定控制器的最佳参数,并且不要求系统是否为连续可微的,能否以显式表示。,基于遗传算法的PID控制简介,(1) 当遗传算法用于PID控制参数寻优时的操作流程 参数编码、种群初始化; 适应度函数的确定; 通过复制、交叉、变异等算子更新种群; 结束进化过程。,基于遗传算法的PID控制简介,(2) 采用遗传算法进行PID三个参数的整定时具有的优点 与单纯形相比,遗传算法同样具有良好的寻
40、优特性,且它克服了单纯形参数初值的敏感性。在初始条件选择不当的情况下,遗传算法在不需要给出调节器初始参数的情况下,仍能寻找到合适的参数,使控制目标满足要求。同时单纯形法难以解决多值函数问题以及在多参数寻优中,容易造成寻优失败或时间过长,而遗传算法的特性决定了它能很好地克服以上问题。 与专家整定法相比,它具有操作方便、速度会地优点,不需要复杂地规则,只通过字串进行简单地复制、交叉、变异,便可达到寻优。避免了专家整定法中前期大量地知识库整理工作及大量地仿真实验。 遗传算法是从许多点开始并行操作,在解空间进行高效启发式搜索,克服了从单点出发的弊端以及搜索的盲目性,从而使寻优速度更快,避免了过早陷入局
41、部最优解。 遗传算法不仅适用于单目标寻优,而且也适用于多目标寻优。根据不同的控制系统,针对一个或多个目标,遗传算法均能在规定的范围内寻找到合适的参数。 遗传算法作为一种全局优化算法,得到了越来越广泛的应用。近年来,在控制上的应用也越来越多。,基于遗传算法的PID控制简介,2 、基于遗传算法的预测自整定PID控制器 基于遗传算法的预测自整定PID控制系统结构如图所示。,基于遗传算法的PID控制简介,这种算法利用预测技术克服时滞,利用遗传算法优化PID控制器参数。对工业过程中典型的大时滞被控过程鲁棒性强,响应速度快,抗干扰能力强,可构成较实用的工程控制器。 按PID控制的增量式算式,Kp,Ki,Kd便是控制器要寻优的参数,在遗传算法中其初始值随机产生。PID控制器的输入是最优预测形成的反馈偏差,在控制过程中,被控过程未来的最优状态来控制其当前行为,提高控制决策的智能性及控制系统的动态品质,减小时滞对系统稳定性的影响。,谢谢!,
链接地址:https://www.31doc.com/p-2996037.html