遗传算法及其在路径规划中的应用

1、2020/7/20，北京科技大学自动化学院控制科学与工程系，1。遗传算法及其在路径规划中的应用，2020/7/20，2。参考文献：2020/7/20，北京科技大学自动化学院控制科学与工程系，美国、德国等国的一些科学家开始模仿生物和人类进化的方法来解决复杂的优化问题，从而形成了一种模拟进化的优化方法，其代表方法有遗传算法、进化规划和进化策略。本次讲座将主要详细介绍遗传算法。传统的数学优化技术基于梯度优化技术，计算速度快，但要求优化问题是可微的，通常只能得到局部最优解，而模拟进化方法是不可微的，适用于任何优化问题，特别是求解组合优化问题和具有不可微目标函数或复杂约束的非线性优化问题。由于采用了随机

2、优化技术，他们将很有可能得到全局最优解。由于计算机软硬件技术的快速发展，高计算成本的问题不再是一个制约因素。1遗传算法的背景，2020年7月20日，北京科技大学自动化学院控制科学与工程系，4，1.1遗传算法的基本概念，1.1.1进化的基本理论，(1)达尔文的生物进化理论，(2)孟德尔的自然遗传理论，1.1.2遗传算法术语介绍，(1)个体(染色体)首先，要优化的问题的参数被编码(一般用二进制代码串表示)，从而得到一个字符串，称为个体或染色体(2)人口：所有个体的人口。(3)人口规模：人口中的个体数量称为人口规模。(4)基因：每个个体被称为一个基因。(5)适应度函数：一种可以评估个体对环境适应性的

3、适应度函数。2020/7/20，北京科技大学自动化学院控制科学与工程系，5月1.1.3遗传算法应用示例，例如：求最大值。解决方法：(1)确定编码方式，用五位二进制码表示变量x。(2)初始种群的生成，假设种群规模为N=4，初始种群的随机生成如表1所示。2020年7月20日，北京科技大学自动化学院控制科学与工程系，6，(3)适应度函数值的计算，取适应度函数为f (x)=x2，四个样本的适应度值如下表所示。2020/7/20，北京科技大学自动化学院控制科学与工程系，7，(4)复制，使用赌博轮法计算每个人的复制次数。2020/7/20，北京科技大学自动化学院控制科学与工程系，8，(5)交叉，随机交叉匹

4、配和单点交叉。2020/7/20，北京科技大学自动化学院控制科学与工程系，9，(6)突变，使用单点随机突变。2020年7月20日，北京科技大学自动化学院控制科学与工程系，10，1.2遗传算法的基本步骤，1.2.1遗传算法的流程，2020年7月20日，北京科技大学自动化学院控制科学与工程系，11，1.2.2遗传算法的实现，(1)编码方法的选择，因此，如何用合适的字符串编码来表示问题的解，成为遗传算法应用中的首要问题。目前使用的字符串编码方法主要包括二进制、实数(浮点数)和符号。(1)二进制编码，多位数字和详细描述，扩大了搜索范围；然而，交叉操作的计算量很大，并且因为大量的具体问题是十进制的，所以

5、有必要对实际参数进行编码和解码，这增加了额外的计算时间。(2)使用实数(浮点数)编码，交叉操作的计算量小，但变异过程困难。(3)符号编码通常用于一些特殊的应用。2020/7/20，北京科技大学自动化学院控制科学与工程系，北京，12。(2)对应于问题的初始解的初始种群的生成通常以两种方式生成：完全随机方式(字符串的每个比特都是随机生成的)；由随机数生成器生成(整个字符串由随机数生成器一次生成)。此外，如果有一些关于优化问题的先验知识，可以将其转化为一组必须满足的约束，然后从满足这些约束的解中随机选择个体来形成初始种群。(3)适应度函数的确定，它是遗传算法与实际优化问题的接口。在遗传算法中，适应度

6、函数值必须是非负的，在任何情况下，值越大越好；然而，实际优化问题的目标函数不一定满足这个条件，其中一些是正的，一些可能是负的，甚至可能是复值。因此，对于任何优化问题，数学形式都应表示为遗传算法适合求解的形式，同时应保证它们在数学优化水平上是等价的。这个过程叫做体能转换。2020/7/20，北京科技大学自动化学院控制科学与工程系，北京，13。在适应度变换中，首先要保证适应度值不为负，其次目标函数的优化方向要与适应度值的增加方向一致。如果实际优化问题的目标函数是J(x)，遗传算法的适应度函数是f(x)，那么有：适应度函数可以表示为实际优化问题的目标函数的线性形式，即有，其中a和b是系数，可以根据具

7、体问题的特点和期望适应度的离散程度来确定。对于极小化问题，一般采用以下变换形式，其中cmax可以是迄今为止所有进化世代中目标函数J(x)的最大值(此时，cmax将随进化而变化)，也可以根据经验人为设置。2020/7/20，北京科技大学自动化学院控制科学与工程系，14。对于最大化问题(如有必要)，一般采用以下变换形式，其中cmin可以是当前代目标函数J(x)的最小值，也可以根据经验人为设置。指数函数如下：当问题最大化时，c一般取1.618或2；当最小化问题时，c可以取为0.618。这样，适应值就不会为负，适应值的增加方向与目标函数的优化方向一致。2020年7月20日，北京科技大学自动化学院控制科

8、学与工程系，15，(4)再生产或选择，它基于适者生存理论，是指种群中的每个个体根据适应度函数进入匹配池的过程。适应值高于群体平均适应值的个体在下一代有更多机会繁殖一个或多个后代，而适应值低于平均适应值的个体可能被淘汰。复制的目的是确保适应性强的优秀个体在进化中生存，而复制不会产生新的个体。常用的复制方法如下：(1)博奕轮法和成对竞争法，从种群中随机选择两个个体，将适应度较大的个体视为复制个体；如果两个人的健康状况相同，可以随意选择一个。排序方法，首先，根据目标函数值的大小，对个体进行排序，并根据具体问题，应用个体的排序数来分配它们进入匹配池的概率。适应度可以根据序列号线性变化，也可以根据某种非

9、线性关系变化。2020年7月20日，控制科学与工程系，一点杂交(One Point Crossing)，对于每对配对个体，根据设定的杂交概率pc，在它们的杂交点交换两个亲代个体的一些染色体，从而产生两个新个体，如下图所示。2020年7月20日，北京科技大学自动化学院控制科学与工程系，17，两点交叉，根据交叉概率随机设置两个交叉点，然后在两个交叉点之间交换双亲的基因。统一交叉，其操作过程是：首先选择两个父个体，然后根据交叉概率pc生成一个与父个体长度相同的二进制字符串，这里称为模板。如果模板中的某个位为0，则两个父个体的对应位不交换；相反，当模板之一为1时，两个亲本相应位置的基因被交换。2020

10、年7月20日，北京科技大学自动化学院控制科学与工程系，18，算术交叉。算术交叉的运算对象一般是由浮点代码表示的个体，它通过两个父个体的线性组合产生两个新的个体。假设在两个父个体之间有一个算术交叉，交叉操作后产生的两个新个体是一个参数，如果它是一个常数，此时的交叉操作称为均匀算术交叉；它也可以是由进化代数决定的变量，交叉操作称为非均匀算术交叉。2020年7月20日，北京科技大学自动化学院控制科学与工程系，19，(6)突变，一般的突变操作只对具有二进制代码的单个个体起作用，这否定了具有一定突变概率pm的个体的某些位。正如基因突变在自然界很少发生一样，突变概率pm通常相对较小。突变的目的是增加个体的

11、多样性，防止一些有用的遗传模型的丢失。在简单的遗传算法中，变异是否定个体中某一位的值。2020年7月20日，北京科技大学自动化学院控制科学与工程系，20，(7)收敛准则，传统优化方法有数学上严格的收敛准则，而遗传算法的收敛准则通常是启发式的。由于遗传算法不使用梯度信息，很难从数学上构造严格的收敛准则。常用的收敛准则如下：(1)根据计算时间和所用计算机的性能确定收敛准则：(2)一般采用指定最大迭代次数的方法；该标准由解的质量决定：如果几代(或几十代)中的最优解没有改变，则认为算法收敛；或者，当群体中最佳个体的适应度与平均适应度之差以及平均适应度之比小于给定值时，也可以认为算法已经收敛。2020/

12、7/20，北京科技大学自动化学院控制科学与工程系，21，(8)约束的处理，遗传算法在求解约束优化问题时应处理约束。处理方法如下：这直接体现在字符串的编码上。对于优化问题中变量的上限和下限，用字符串表示的最大值和最小值可以分别对应于实际约束变量的上限和下限。让待优化变量的变化范围为XMIN和XMAX。如果用1位二进制字符串Y表示，则X和Y之间的关系如下：(1)确定废弃方法。在遗传算法的运算过程中，检查字符串对应的解是否是可行解。如果是，则将其添加到下一代人口中；否则，丢弃它。罚函数法，如果一个解违反了一个约束，它将根据违反的程度进行惩罚，使其具有较小的适应度。限制越严格，适合度越小。2020/7

13、/20，北京科技大学自动化学院控制科学与工程系，22，1.3遗传算法的特点，目前有三种常规优化方法：解析法，枚举法直接法是通过沿着梯度信息的最陡方向逐渐移动来寻找局部极值的方法；间接规则是通过使目标函数的梯度为零，然后求解一组非线性方程来寻找局部极值的方法。(1)分析方法，分析方法的主要问题是：(1)目标函数要求连续、光滑和可微；(2)一般来说，只能找到局部极值，而不能找到全局极值，因此，对于具有多峰极值的优化问题，有时显得无能为力。2020/7/20，北京科技大学自动化学院控制科学与工程系，23。随机方法可以克服上述两种方法的缺陷。它在搜索空间中随机漫游，记录找到的最佳结果，并在搜索达到一定

14、程度时终止。当然，它发现的结果往往不是最佳解决方案。事实上，随机方法也是枚举方法之一。(2)枚举法可以克服解析法的两个缺点，可以找到全局极值，并且不需要目标函数的连续光滑性。然而，它的致命缺点是计算效率太低。对于许多实际问题，由于搜索空间太大，通常不可能逐个搜索所有情况。(3)随机方法，北京科技大学自动化学院控制科学与工程系，2020年7月20日，24。遗传算法是一种基于自然选择和遗传遗传学原理的搜索方法。它将“适者生存、适者生存”的生物进化原理引入到待优化参数构成的编码串种群中，并根据一定的适应度函数和一系列遗传操作对每个个体进行筛选，从而选择适应度值较高的个体。这样，种群中每个个体的适应度

15、不断提高，直到满足某些收敛条件。最后，将种群中适应值最高的个体作为待优化参数的最优解。(4)遗传算法也采用随机搜索技术，通过对参数空间进行随机编码，并以适应度函数为工具，将搜索过程引向更有效的方向，不同于传统的随机方法。2020/7/20，北京科技大学自动化学院控制科学与工程系，25。与传统优化方法相比，遗传算法具有更好的鲁棒性。它的主要特点如下：遗传算法对参数进行编码，而不是对参数本身进行编码；遗传算法从多个初始点开始，而不是从某一点开始，这在很大程度上避免了搜索过程过早收敛到局部极值，因此更容易找到全局极值；遗传算法通过目标函数计算适应度，不需要其他求导操作和附加信息，因此对问题的依赖性很小；遗传算法使用概率运算规则代替确定性规则；遗传算法在解空间中采用启发式搜索，而不是盲目枚举或完全随机搜索，因此搜索效率较高；遗传算法对要优化的问题没有限制，可以是用数学解析公式表示的显式函数，也可以是用映射矩阵或神经网络表示的隐式函数，并且不要求要优化的函数是连续的和可微的；2020/7/20，北京科技大学自动化学院控制科学与工程系，26，遗传算法具有隐式并行的特点，这使得通过大规模并行搜索来提高计算速度成为可能；遗传算法适用于复杂和高度非线性问题的优化。1.4遗传算法的研究热点，(1)编码方式的确定；(2)特殊遗传算子的设计；