遗传算法第讲幻灯片.ppt

《遗传算法第讲幻灯片.ppt》由会员分享，可在线阅读，更多相关《遗传算法第讲幻灯片.ppt（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、遗传算法第讲第1页，共64页，编辑于2022年，星期三培训大纲一、简介二、原理三、步骤四、样例第2页，共64页，编辑于2022年，星期三2023/4/163什么是遗传算法（Genetic Algorithm）生物进化生命自从在地球上诞生以来，就开始了漫长的生物演化历程，低级、简单的生物类型逐渐发展为高级、复杂的生物类型。这一过程已经由古生物学、胚胎学和比较解剖学等方面的研究工作所证实。生物进化的原因自古至今有着各种不同的解释，其中被人们广泛接受的是达尔文的自然选择学说。定义：模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率算法 最早由美国的J.Holland教授于1975年在

2、他的专著自然界和人工系统的适应性中首先提出。第3页，共64页，编辑于2022年，星期三达尔文18251825年至年至18281828年在爱丁大学学医，后进入剑桥大学学习神学。年在爱丁大学学医，后进入剑桥大学学习神学。18311831年从剑桥大学毕业后，以博物学家的身份乘海军勘探船年从剑桥大学毕业后，以博物学家的身份乘海军勘探船“贝格贝格尔号（尔号（BeagleBeagle）”作历时作历时5 5年（年（1831183118361836）的环球旅行，观察和搜集）的环球旅行，观察和搜集了动物、植物和地质等方面的大量材料，经过归纳整理和综合分析，形成了了动物、植物和地质等方面的大量材料，经过归纳整理和

3、综合分析，形成了生物进化的概念。生物进化的概念。18591859年出版年出版物种起源（物种起源（OnOnthe Origin of Speciesthe Origin of Species）一书，全面提出以自然选择（一书，全面提出以自然选择（Theory of Natural electionTheory of Natural election）为基）为基础的进化学说。该书出版震动当时的学术界，成为生物学史上的一个转折点。础的进化学说。该书出版震动当时的学术界，成为生物学史上的一个转折点。自然选择的进化学说对各种唯心的神造论、目的论和物种不变论提出根本性自然选择的进化学说对各种唯心的神造论、目

4、的论和物种不变论提出根本性的挑战。使当时生物学各领域已经形成的概念和观念发生根本性的改变。的挑战。使当时生物学各领域已经形成的概念和观念发生根本性的改变。达尔文（达尔文（Charles Robert DarwinCharles Robert Darwin，1809180918821882）英国博）英国博物学家，进化论的奠基人。物学家，进化论的奠基人。18091809年年2 2月月1212日，出生于英国日，出生于英国医生家庭。医生家庭。第4页，共64页，编辑于2022年，星期三自然选择学说 自然选择学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物与无机环境之间

5、的斗争三个方面。在生存斗争中，具有有利变异(mutation)的个体容易存活下来，并且有更多的机会将有利变异传给后代，具有不利变异的个体容易被淘汰，产生后代的机会也少得多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存、不适者淘汰的过程叫做自然选择。达尔文的自然选择学说表明，遗传和变异是决定生物进化的内在因素。第5页，共64页，编辑于2022年，星期三遗传学之父 奥地利生物学家Mendel(孟德尔),（1822-7-201884-1-6）出生于奥地利西里西亚，是遗传学的奠基人，被誉为现代遗传学之父。Mendel通过豌豆实验，发现了遗传规律、分离规律以

6、及自由组合规律。Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质。所以，每个基因产生的个体对环境具有某中适应性。基因突变和基因杂交可产生更适应于环境的后代，经过存优劣的自然淘汰，适应性高的基因结构得以保存下来。第6页，共64页，编辑于2022年，星期三遗传算法的起源20世纪60年代中期，美国Michigan（密西根）大学的John Holland提出了位串编码技术，这种编码既适合于变异又适合杂交操作，并且他强调将杂交作为主要的遗传操作。随后，Holland将该算法用于自然和人工系统的自适应行为的研究之

7、中，并于1975年出版其开创性的著作Adaptation in Natural and Artificial Systems。后来，Holland与他的学生们将该算法加以推广并应用到优化及机器学习等问题之中，而且正式定名为遗传算法。遗传算法的通用编码技术及简单有效的遗传操作为其广泛的应用和成功奠定了基础。第7页，共64页，编辑于2022年，星期三遗传算法的搜索机制 遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较

8、优的个体，利用遗传算子标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。直到满足某种收敛指标为止。从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能第8页，共64页，编辑于2022年，星期三遗传算法的步骤(1)确定编码方案(2)确定适应度函数(3)选择策略的确定(4)遗传算子的设计(5)确定算法的终止准则(6)控制参数的选取(7)编程上机运行2023/4/16

9、9特点：随机地随机地、迭代地迭代地、不厌其烦地去寻找最优解！第9页，共64页，编辑于2022年，星期三遗传算法流程图开始随机初始化初始化种群P(0),t0计算计算P(0)中每个个体的适应值适应值终止?杂交杂交计算计算P(t)中每个个体的适应值适应值变异变异择优生成新种群（选择选择）tt+1输出t代优良品种输出最优个体结束第10页，共64页，编辑于2022年，星期三培训大纲一、简介二、原理三、步骤四、样例第11页，共64页，编辑于2022年，星期三遗传学相关概念 遗传学遗传算法数学1个体个体要处理的基本对象、结构要处理的基本对象、结构也就是可行解也就是可行解2群体群体个体的集合个体的集合被选定的

10、一组可行解被选定的一组可行解3染色体染色体个体的表现形式个体的表现形式可行解的编码可行解的编码4基因基因染色体中的元素染色体中的元素编码中的元素编码中的元素5基因位基因位某一基因在染色体中的位置某一基因在染色体中的位置元素在编码中的位置元素在编码中的位置6适应值适应值个体对于环境的适应程度，或在个体对于环境的适应程度，或在环境压力下的生存能力环境压力下的生存能力可行解所对应的适应函可行解所对应的适应函数值数值7种群种群被选定的一组染色体或个体被选定的一组染色体或个体根据入选概率定出的一根据入选概率定出的一组可行解组可行解8选择选择从群体中选择优胜的个体，淘汰从群体中选择优胜的个体，淘汰劣质个体

11、的操作劣质个体的操作保留或复制适应值大的保留或复制适应值大的可行解，去掉小的可行可行解，去掉小的可行解解第12页，共64页，编辑于2022年，星期三遗传学相关概念 遗传学遗传算法数学9交叉交叉一组染色体上对应基因段的交一组染色体上对应基因段的交换换根据交叉原则产生的一根据交叉原则产生的一组新解组新解10交叉概率交叉概率染色体对应基因段交换的概率染色体对应基因段交换的概率（可能性大小）（可能性大小）闭区间闭区间0,1上的一个值，上的一个值，一般为一般为0.650.9011变异变异染色体水平上基因变化染色体水平上基因变化编码的某些元素被改变编码的某些元素被改变12变异概率变异概率染色体上基因变化的

12、概率（可染色体上基因变化的概率（可能性大小）能性大小）开区间开区间(0,1)内的一个值内的一个值,一般为一般为0.0010.0113进化、进化、适者生存适者生存个体进行优胜劣汰的进化，一个体进行优胜劣汰的进化，一代又一代地优化代又一代地优化目标函数取到最大值，目标函数取到最大值，最优的可行解最优的可行解第13页，共64页，编辑于2022年，星期三生物的进化是以集团的形式共同进行的，这样的一个团体称为群体(Population)，或称为种群。组成群体的单个生物称为个体(Individual)，每一个个体对其生存环境都有不同的适应能力，这种适应能力称为个体的适应度(Fitness)。个体：就是模拟

13、生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。种群：就是模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。第14页，共64页，编辑于2022年，星期三 适应度(fitness)：就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。适应度函数(fitness function)：就是问题中的全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）

14、。例如：个体 染色体 9 -1001 （2，5，6）-010 101 110 等位基因：0,1第15页，共64页，编辑于2022年，星期三q基本思想：遗传算法基本原理u基于模仿生物界遗传学的遗传过程，把问题的参数用基因来表示，把问题的解用染色体来表示代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体。u 这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代，后代随机化地继承父代的最好特征，并也在生存环境的控制支配下继续这一过程。u 群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优解。第16页，共64页，编辑于2

15、022年，星期三遗传算法的步骤 q遗传算法基本步骤：u把这些可行解置于问题的“环境”中，按适者生存的原则，选取较适应环境的“染色体”进行复制，并通过交叉、变异过程产生更适应环境的新一代“染色体”群u 把问题的解表示成“染色体”，在算法中就是以二进制编码的串，给出一群“染色体”，也就是假设的可行解u经过这样的一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解第17页，共64页，编辑于2022年，星期三遗传算法具体步骤 选择编码策略，把参数集合（可行解集合）转换染色体结构空间；定义适应函数，便于计算适应值；确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉

16、概率、变异概率等遗传参数；随机产生初始化群体；计算群体中的个体或染色体解码后的适应值；按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；判断群体性能是否满足某一指标，或者已完成预定的迭代次数，不满足则返回第五步，或者修改遗传策略再返回第六步第18页，共64页，编辑于2022年，星期三培训大纲一、简介二、原理三、步骤四、样例第19页，共64页，编辑于2022年，星期三基本遗传算法 基本遗传算法（基本遗传算法（Simple Genetic AlgorithmsSimple Genetic Algorithms，简称，简称SGASGA，又称简单遗传算法或标准遗传算法），是由又称简单遗

17、传算法或标准遗传算法），是由GoldbergGoldberg总结出的总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。是其它一些遗传算法的雏形和基础。基本遗传算法的组成（1 1）编码（产生初始种群）编码（产生初始种群）（2 2）适应度函数）适应度函数（3 3）遗传算子（选择、交叉、变异）遗传算子（选择、交叉、变异）选择：选择：轮盘赌选择法轮盘赌选择法 交叉：交叉：单点交叉单点交叉 变异：变异：小概率变异小概率变异（4 4）运行参数）运行参数第20页，共64页，编辑于2022年，星期三 编码 G

18、A GA是通过某种编码机制把对象抽象为由特定符号是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。手，而染色体则是由基因排成的串。SGASGA使用二进制使用二进制串进行编码。串进行编码。第21页，共64页，编辑于2022年，星期三确定编码方案 变量作为实数，可以视为演化算法的表现型形式。从表现型到基因型的映射称为编码。我们这里采用二进制编码，将某个变量值代表的个体表示为一个0,1二进制串。串长取决于求解的精度。如果确定在-1,1区间内，求解精度到3位小数，由于区间长度为1-(-

19、1)=2，必须将区间-1，1分为2 103等份。因为 10242102103211=2048 所以编码的二进制串长至少需要11位。二进制串转化为十进制：例如s=x=560 x=-0.453 与表示区间的两个端点-1和1。第22页，共64页，编辑于2022年，星期三原则：1 低阶，短定义精度（易于生成适应度较高的个体）2 最小字符集（在确定规模的种群中能处理最多的模式）二进制编码方法：最常用，使用由二进制符号0和1组成的二值符号集0,1，所构成的个体基因型是一个二进制编码符号串。假定某参数取值范围U1,U2,用长度为l的二进制符号串来表示：000.0000=0 U1 111.1111=-1 U2

20、精度：解码：染色体编码方法第23页，共64页，编辑于2022年，星期三二进制编码对于一些连续函数的优化问题，由于随机性使其局部搜索能力差；精度和编码串长度问题。格雷码：连续的两个整数所对应的编码值之间仅有一个码位不同。十进制数十进制数二进制码二进制码格雷码格雷码000000000100010001200100011300110010401000110501010111染色体编码方法第24页，共64页，编辑于2022年，星期三转换转换：二进制编码 格雷码：二进制到格雷：格雷到二进制：其他编码方法其他编码方法：浮点数编码方法，符号编码方法 十进制编码方法 染色体编码方法第25页，共64页，编辑于2

21、022年，星期三（1）编码和产生初始群体）编码和产生初始群体u确定编码的策略，也就是说如何把 a,b 区间内的数用计算机语言表示出来。编码就是从表现型到基因型的映射，编码时要注意以下三个原则：n 完全性：分布在所有问题域的解都可能被构造出来；n 封闭性：每个基因编码对应一个可接受的个体,不产生无效的个体；n 可扩展性：对于具体问题,要考虑编码形式与大小影响下的解码时间n复杂性:是指整体考虑基因型的结构复杂性、解码复杂性、计算复杂性等。第26页，共64页，编辑于2022年，星期三函数优化示例 求下列一元函数的最大值：求下列一元函数的最大值：x x-1,2 -1,2 ，求解结果精确到，求解结果精确

22、到6 6位小数。位小数。SGA对于本例的编码 由于区间长度为由于区间长度为3 3，求解结果精确到，求解结果精确到6 6位小数，因此可将自变量定义区间划位小数，因此可将自变量定义区间划分为分为3103106 6等份。又因为等份。又因为2 22121 310 3106 6 2 22222 ，所以本例的二进制编码长度，所以本例的二进制编码长度至少需要至少需要2222位，本例的编码过程实质上是将区间位，本例的编码过程实质上是将区间-1-1，22内对应的实数内对应的实数值转化为一个二进制串（值转化为一个二进制串（b21b20b0b21b20b0）。）。第27页，共64页，编辑于2022年，星期三几个术语

23、 基因型：1000101110110101000111 表现型：表现型：0.637197编码解码个体（染色体）基因第28页，共64页，编辑于2022年，星期三初始种群 在遗传算法处理流程中，继编码设计后的任务是初始群体在遗传算法处理流程中，继编码设计后的任务是初始群体的生成，并以此为起点一代代进化直到满足某种进化停止准则的生成，并以此为起点一代代进化直到满足某种进化停止准则终止进化进程，初始群体也称为进化的初始代，即第一代。终止进化进程，初始群体也称为进化的初始代，即第一代。SGA SGA采用随机方法生成若干个个体的集合，该集合称为初采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种

24、群中个体的数量称为种群规模。始种群。初始种群中个体的数量称为种群规模。适应度函数 遗传算法对一个个体（解）的好坏用适应度函数值来评价，遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。结合求解问题本身的要求而定。第29页，共64页，编辑于2022年，星期三适应度不能为负；函数值最大，最小。适应度尺度变换适应度尺度变换：在遗传算法运行的初级阶段，群体中可

25、能会有少数几个个体的适应度相对其他个体来说非常高。若用比例选择算子来确定个体的遗传数量时，这几个相对较好的个体将在下一代中有很高的比例，当群体规模较小时，新的群体可能完全由这样的少数几个个体所组成。这时就会导致交叉算子起不了什么作用，这样就会使群体的多样性降低，容易导致遗传算法发生早熟现象，使遗传算法所求到的解停留在某一局部最优点上。在遗传算法运行的后期阶段群体中所有个体的平均适应度可能会接近群体中个体的最佳适应度，使得进化过程无竞争可言，从而影响遗传算法的运行效率。为了克服这种现象，需在遗传算法运行初期阶段对适应度较高的个体做缩小变换，对适应度较低的个体做扩大变换，进而维护群体的多样性。适应

26、度函数第30页，共64页，编辑于2022年，星期三适应度尺度变换较常用的方法是线性尺度变换。现行尺度变换的公式如下：F=aF+b，式中F-原适应度；F-变换后的适应度；a和b是系数。系数a、b直接影响到这个尺度变换的大小一般希望它们满足两个条件：条件一：尺度变换后全部个体的新适应度的平均值Favg要等于其原适应度平均值Favg，即：Favg=Favg。这条要求是为了保证群体中适应度接近于平均适应度的个体能够有期待的数量被遗传到下一代中。条件二：尺度变换后群体中新的最大适应度Fmax要等于其原平均适应度Favg的指定倍数，即：Fmax=C*Favg.式中C为最佳个体的期望复制数量，对于群体大小为

27、50100的情况，一般取C=1.22。这条要求是为了保证群体中最好的个体能够期望复制C倍到新一代群体。FmaxFavgFminFminFavgFmax适应度函数第31页，共64页，编辑于2022年，星期三适应度函数 定义适应函数和适应值由于目标函数 f(x)在-1,2 内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下基础。n 定义适应函数：为了便于计算，这里的 Fmin 采用了一个特定的输入值 例：例：如果取如果取Fmin=-1，则，则f(x)=1对应的适应值为对应的适应值为g

28、(x)=2第32页，共64页，编辑于2022年，星期三适应度函数（评估函数）适应度函数设计是模拟自然选择，进行遗传进化操作的基础，它的评估是遗传操作的依据。适应度函数值即适应度。由于下面定义的选择概率以适应度为基础，因此适应度是非负的。几种常见的适应度定义为：对f(x),取Cmin,Cmax使Cminmaxf(x),Cmax0 (1)求f(x)最大值问题：如果对应解x的个体为X,可以定义个体X的适应度为 (2)求f(x)最小值问题：可以定义个体X的适应度为第33页，共64页，编辑于2022年，星期三选择标准 确定选择标准 用适应值比例来作为入选概率。设给定的规模为 n 的群体 pop=a1,a

29、2,.,an，个体 ai 的适应值为 g(ai)，则其入选概率为第34页，共64页，编辑于2022年，星期三选择算子 遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。代群体。SGASGA中选择算子采用轮盘赌选择方法。

30、中选择算子采用轮盘赌选择方法。第35页，共64页，编辑于2022年，星期三 选择算子比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i的适应度为Fi，则个体i被选中遗传到下一代群体的概率为：轮盘赌选择方法的实现步骤：（1）计算群体中所有个体的适应度函数值（需要解码）；（2）利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；（3）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。第36页，共64页，编辑于2022年，星期三 确定式采样选择1 计算个体在下一代群

31、体中的期望生存数目Ni：i=（1,2，M）2用Ni的整数部分 确定各个对应个体在下一代群体中的生存数目。由此可确定下一代群体中的 个个体。3按照Ni的小数部分对个体进行降序排序，顺序取前M-个个体加入到下一代群体中。可保证适应度较大的个体一定能被保留在下一代群体中，且操作简单。此外，还有排序选择，联赛选择等选择算子第37页，共64页，编辑于2022年，星期三轮盘赌选择方法 轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为中的概率与其适应度函数值大小成正比。设群体大小为n n，个体，个

32、体i i 的适的适应度为应度为 F Fi i，则个体，则个体i i 被选中遗传到下一代群体的概率为：被选中遗传到下一代群体的概率为：轮盘赌选择方法的实现步骤（1 1）计算群体中所有个体的适应度函数值（需要解码）；计算群体中所有个体的适应度函数值（需要解码）；（2 2）利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；（3 3）采用模拟赌盘操作（即生成采用模拟赌盘操作（即生成0 0到到1 1之间的随机数与每个个体遗传到之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体下一代群体

33、的概率进行匹配）来确定各个个体是否遗传到下一代群体中。中。第38页，共64页，编辑于2022年，星期三选择策略的内在原理选择-轮盘赌2023/4/1639演化算法的选择是一个类似于赌博的过程演化算法的选择是一个类似于赌博的过程第39页，共64页，编辑于2022年，星期三交叉算子交叉：对两个相互配对的染色体依据交叉概率Pc按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。例如,设染色体 s1=01001011,s2=10010101,交换其后4位基因,即单点交叉，均匀交叉，双点交叉，多点交叉（随交

34、叉点数增多，个体的结构被破坏的可能性增大，难于保存较好模式）第40页，共64页，编辑于2022年，星期三交叉算子算术交叉 算术交叉是针对浮点数编码的一种交叉方法，是由指两个个体的线性组合而产生出两个新的个体。假设在两个个体 之间进行算术交叉，则交叉运算后所产生出的两个新个体是：式中，为一个参数，它可以是一个常数，此时所进行的交叉运算称为均匀算术交叉；它也可以是一个由进化代数所决定的变量，此时所进行的交叉运算称为非均匀算术交叉。第41页，共64页，编辑于2022年，星期三单点交叉运算 单点交叉单点交叉又叫简单交叉。具体操作是：在个体基因串中又叫简单交叉。具体操作是：在个体基因串中随机设定一个交叉

35、点。实行交叉时，该点前或后的两个个体随机设定一个交叉点。实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体。当基因链码的长的部分结构进行互换，并生成两个新个体。当基因链码的长度为度为n n时，可能有时，可能有n-1n-1个交叉点位置。个交叉点位置。交叉前：交叉前：00000|0111000000001000000000|0111000000001000011100|0000011111100010111100|00000111111000101交叉后：交叉后：00000|0000011111100010100000|0000011111100010111100|0111000

36、000001000011100|01110000000010000交叉点交叉点第42页，共64页，编辑于2022年，星期三两点交叉 与单点交叉类似，只是需设置两个交叉点，然后两个染色体相互交换两点之间的部分，从而生成两个新染色体。一个两点交叉的示例如下：父辈个体:aaa|aaaa|aaa aaa|bbbb|aaa 父辈个体:bbb|bbbb|bbb bbb|aaaa|bbb 对于两点交叉，若染色体长为n,则可能有(n-1)(n-2)/2种交叉点的设置。第43页，共64页，编辑于2022年，星期三均匀交叉 均匀交叉则是依概率交换两个父辈个体基因串的每一位。其过程是：先随机的产生一个与父辈个体基因

37、串同样长度的二进制串，其中0表示不交换，1表示交换。这个二进制串称为交叉模版；然后根据该模版对两个父辈基因串进行交叉，得到的两个新基因串即为后代新个体。例如：父辈个体 1:110010111000 父辈个体 2:101011101011 模版 001101011100 后代个体 1:111011101000 后代个体 2:100010111011 由于均匀交叉在交换位时并不考虑其所在位置，破坏模式的可能性较大。但另一方面它能搜索到一些前面基于点的交叉方法无法搜索到的模式。第44页，共64页，编辑于2022年，星期三基于实向量算术运算的交叉设两向量x1,x2,则有凸交叉：x1=1x1+2x2 x

38、2=1x2+2x1 1=2=0.5仿射交叉：x1=1x1+2x2 x2=1x2+2x1 1=1.5 2=-0.5线性交叉：x1=1x1+2x2 x2=1x2+2x1 1+20,20第45页，共64页，编辑于2022年，星期三变异算子 所谓变异运算，是指依据变异概率所谓变异运算，是指依据变异概率 P Pm m 将个体编码串中的某些基因值用将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持产生新个体的辅助方法，它决定了遗传算法的局部搜索

39、能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。的全局搜索和局部搜索。SGA SGA中变异算子采用基本位变异算子。中变异算子采用基本位变异算子。第46页，共64页，编辑于2022年，星期三变异算子1 1）、基本变异）、基本变异 基本变异算子是针对二值基因链而言。其具体操作是：对群体基本变异算子是针对二值基因链而言。其具体操作是：对群体中基因链码随机筛选中基因链码随机筛选C C个基因位置并对这些基因位置的基因值以变个基因位置并对这些基因位置的基因值以变异概率异概率P P取反，即取反，即

40、0 0变成变成1 1，1 1变成变成0 0。当。当C=1C=1时，表示一个基因值取反。时，表示一个基因值取反。2 2）、均匀变异）、均匀变异 该变异方法是针对实数编码方式的该变异方法是针对实数编码方式的.为叙述方便为叙述方便,设设v=(v1,v2,vm)v=(v1,v2,vm)是群体中的一个个体是群体中的一个个体,z=(z1,z2,zm),z=(z1,z2,zm)是变异产是变异产生的后代。均匀性变异则是先在个体生的后代。均匀性变异则是先在个体v v中随机的选择一个分量中随机的选择一个分量vk,vk,然然后，在一个定义的区间后，在一个定义的区间ak,bkak,bk中均匀随机的取一个数中均匀随机的

41、取一个数vklvkl代替代替vkvk以以得到得到z,z,即即z=(v1,vkl,vm)z=(v1,vkl,vm)3 3）、自适应变异算子）、自适应变异算子 该算子与基本变异算子的操作相似，两者之间的区别就是使该算子与基本变异算子的操作相似，两者之间的区别就是使用自适应变异算子时变异率不是固定不变，而是随着群体中个体用自适应变异算子时变异率不是固定不变，而是随着群体中个体多样性的程度自适应调整多样性的程度自适应调整。第47页，共64页，编辑于2022年，星期三基本位变异算子的执行过程 变异前：变异前：00000111000000001110000 0000010000000010000变异后：变

42、异后：00000111000000001110001 1000010000000010000变异点变异点第48页，共64页，编辑于2022年，星期三运行参数（1）M：种群规模（2）T：遗传运算的终止进化代数（3）Pc：交叉概率（4）Pm：变异概率 Schaffer建议的最优参数范围是：M=20-100，T=100-500，Pc=0.4-0.9，Pm=0.0001-0.01。确定算法的终止准则代数（迭代次数）采用设定最大（遗传）代数的方法，一般可设定为 50代，此时就可能得出最优解此种方法简单易行，但可能不是很精确b.最好个体在若干代内无改变 根据个体的差异来判断，通过计算种群中基因多样性测度，

43、即所有基因位相似程度来进行控制运行参数和终止准则第49页，共64页，编辑于2022年，星期三SGA的框图 产生初始群体产生初始群体是否满足停止准则是否满足停止准则是是输出结果并结束输出结果并结束计算个体适应度值计算个体适应度值比例选择运算比例选择运算单点交叉运算单点交叉运算基本位变异运算基本位变异运算否否产生新一代群体产生新一代群体执行执行M/2M/2次次第50页，共64页，编辑于2022年，星期三 遗传算法基本流程框图生成初始种群计算适应度选择-复制交叉变异生成新一代种群终止?终止?生成初始种群计算适应度选择-复制交叉变异生成初始种群计算适应度结束结束伪代码描述：Procedure SGAb

44、egin initialize P(0);t=0;while(t=T)do for i=1 to M do Evaluate fitness of P(t);end for for i=1 to M do Select operarion of P(t);end for for i=1 to M/2 do Crossover operarion of P(t);end for for i=1 to M do Mutation operarion of P(t);end for for i=1 to M do P(t+1)=P(t);end for t=t+1;end whileend第51页，

45、共64页，编辑于2022年，星期三遗传算法的循环过程2023/4/1652第52页，共64页，编辑于2022年，星期三遗传算法优点遗传算法优点1.群体搜索，易于并行化处理；2.对求解问题的本身可以一无所知，如对搜索空间没有特殊要求(如连续、凸性等)，对目标函数也不要求连续、可微、单峰值等假设，它所需要的仅是对算法所产生的每一个染色体能用适应度函数进行评价，这一特性使它的应用范围更加宽广；3.良好的全局优化性能和稳健性，遗传算法是多点搜索，而不是单点，从而避免陷入局部最优，逐步逼近全局最优解；4.良好的可操作性与简单性，遗传算法的处理对象不是参变量本身，而是参变量编码后的称为人工染色体的二进制串

46、，使得遗传算法可直接对集合、队列、矩阵、图表等结构对象进行操作。第53页，共64页，编辑于2022年，星期三遗传算法缺点遗传算法缺点1.全局搜索能力强而局部搜索能力不足；2.出现早熟收敛和随机漫游现象；3.结构计算的工作量过大而导致搜索速度较慢等。4.求得的解为近似的数值解5.对于经典数学可以解决的问题，效率较低第54页，共64页，编辑于2022年，星期三培训大纲一、简介二、原理三、步骤四、样例第55页，共64页，编辑于2022年，星期三遗传算法的手工模拟计算示例遗传算法的手工模拟计算示例遗传算法的手工模拟计算示例遗传算法的手工模拟计算示例为更好地理解遗传算法的运算过程，下面用手工计算来简单地

47、模拟遗传算法的各为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各个主要执行步骤。个主要执行步骤。例：求下述二元函数的最大值：例：求下述二元函数的最大值：maxf(x1,x2)=x12+x22s.t.x1 1,2,3,4,5,6,7x2 1,2,3,4,5,6,7(1)(1)个体编码个体编码个体编码个体编码遗传算法的运算对象是表示个体的符号串，所以必须把变量遗传算法的运算对象是表示个体的符号串，所以必须把变量x1,x2编码为一种符号串。本编码为一种符号串。本题中，用无符号二进制整数来表示。题中，用无符号二进制整数来表示。因因x1,x2为为07之间的整数，所以分别用之间的整数

48、，所以分别用3位无符号二进制整数来表示，将它位无符号二进制整数来表示，将它们连接在一起所组成的们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可位无符号二进制数就形成了个体的基因型，表示一个可行解。行解。例如，基因型例如，基因型X101110所对应的表现型是：所对应的表现型是：x5，6。个体的表现型个体的表现型x和基因型和基因型X之间可通过编码和解码程序相互转换。之间可通过编码和解码程序相互转换。第56页，共64页，编辑于2022年，星期三(2)(2)初始群体的产生初始群体的产生初始群体的产生初始群体的产生遗传算法是对群体进行的进化操作，遗传算法是对群体进行的进化操作，需要

49、需要给其淮备一些表示起始搜索点的初始给其淮备一些表示起始搜索点的初始群体数据。群体数据。本例中，群体规模的大小取为本例中，群体规模的大小取为4，即群体由，即群体由4个个体组成，每个个体可通过随机个个体组成，每个个体可通过随机方法产生。方法产生。如：如：011101，101011，011100，111001(3)(3)适应度汁算适应度汁算适应度汁算适应度汁算遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会的大小。机会的大小。本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接本例中，目标函

50、数总取非负值，并且是以求函数最大值为优化目标，故可直接利用目标函数值作为个体的适应度。利用目标函数值作为个体的适应度。(4)(4)选择运算选择运算选择运算选择运算选择运算选择运算(或称为复制运算或称为复制运算)把当前群体中适应度较高的个体按某种规则或模型遗传到下一把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代群体中。群体中。第57页，共64页，编辑于2022年，星期三本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中本例中，我们采用与适应度成正比的概