智能控制第10章 1

第十章遗传算法，10.1遗传算法的基本原理。遗传算法是由密歇根大学的霍兰德教授于1962年提出的一种并行随机搜索优化方法，它模拟了自然和生物进化的遗传机制。遗传算法基于达尔文的自然选择理论。自然选择理论包括以下三个方面：(1)遗传：这是生物学的一个普遍特征。父母给他们的后代生物信息，他们的后代总是有相同或相似的特征。有了这个特性，物种可以稳定地生存。(2)变异：父母和孩子之间以及孩子不同个体之间的差异称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。(3)适者生存的斗争：具有适应性变异的个体被保留，而没有适应性变异的个体被淘汰。通过一代又一代对生存环境的选择，性状逐渐不同于祖先，进化成新的物种。遗传算法将“适者生存、适者生存”的生物进化原理引入到由优化参数组成的编码串联种群中，根据选择的适应度函数，通过遗传中的复制、交叉和变异来筛选个体，使适应度高的个体得以保留并形成新的种群，新的种群不仅继承了上一代的信息，而且优于上一代。这样，团队中的个人体能会不断提高，直到满足某些条件。遗传算法算法简单，可以并行处理，并能达到全局最优解。遗传算法的基本操作是：(1)繁殖算子繁殖是从旧种群中选择一个生命力强的个体比特串来产生新种群的过程。适应度高的位串更有可能在下一代产生一个或多个后代。复制操作可以通过随机方法实现。首先，生成均匀分布在0和1之间的随机数。如果一个字符串的复制概率为40%，当生成的随机数在0.40和1.0之间时，该字符串将被复制，否则将被消除。(2)交叉操作者复制可以从旧群体中选择最好的，但不能产生新的染色体。交叉模拟生物进化过程中的繁殖现象，通过两条染色体的交换和组合产生新的优良品种。交叉过程如下：从匹配池中选择两条染色体，随机选择一个或多个交换点；通过交换亲代染色体交换点的右边部分，可以获得两个新的染色体数目。这个交集体现了信息交换的本质。有小交叉、多点交叉、一致交叉、顺序交叉和周期性交叉。一点相交是最基本的方法，应用广泛。(3)突变操作器突变操作用于模拟生物体自然遗传环境中各种偶然因素引起的基因突变。它以很小的概率随机改变遗传基因的值(代表染色体符号串的某一位)。在染色体以二进制编码的系统中，它随机地将染色体的一个基因从1变为0，或者从0变为1。如果只有选择和交叉而没有变异，就不可能在初始基因组合以外的空间进行搜索，导致进化过程陷入局部解并在早期进入终止过程，从而影响解的质量。为了在尽可能大的空间内获得高质量的最优解，必须采用变异操作。10.2遗传算法的特点(1)遗传算法对参数进行编码，而不是对参数本身进行编码，这使得我们有可能从生物学中的染色体和基因的概念中学习，并在优化计算过程中模拟自然界生物的遗传和进化机制。(2)遗传算法同时利用多个搜索点的搜索信息。传统的优化方法通常从解空间的一个初始点开始迭代搜索最优解。单个搜索点提供的信息很少，搜索效率不高。有时搜索过程甚至仅限于loc遗传算法从由许多个体组成的初始组开始搜索最优解的过程，而不是从单个个体开始搜索，这是遗传算法独有的隐含并行性，因此遗传算法的搜索效率更高。(3)遗传算法直接将目标函数作为搜索信息。传统的优化算法不仅需要使用目标函数值，还需要目标函数值等辅助信息来确定搜索方向。然而，遗传算法可以仅通过使用由目标函数值转换的适应度函数值来确定进一步的搜索方向和搜索范围，而不需要诸如目标函数的导数之类的其他辅助信息。遗传算法可应用于目标函数找不到导数或导数不存在的函数优化问题，以及组合优化问题。(4)遗传算法采用概率搜索技术。遗传算法的选择、交叉、变异等操作都是以概率的方式进行的，因此遗传算法的搜索过程具有很好的灵活性。随着进化的进行，新的遗传算法群体将产生许多新的优秀个体。(5)遗传算法在解空间进行有效的启发式搜索，而不是盲目的穷举或完全随机搜索；(6)遗传算法对要优化的函数没有限制。它既不要求函数的连续性，也不要求函数的可微性。它可以是由数学解析表达式表达的显式函数，也可以是映射矩阵的隐式函数，甚至是神经网络。因此，它有着广泛的应用。(7)遗传算法具有并行计算的特点，可以通过大规模并行计算提高计算速度，适用于大规模复杂问题的优化。10.3遗传算法的应用领域(1)函数优化。函数优化是遗传算法的经典应用领域，也是遗传算法性能评价的常见例子。特别是对于非线性、多模型和多目标函数优化问题，其他优化方法更难求解，而遗传算法可以得到更好的结果。(2)组合优化。随着问题的增多，组合优化问题的搜索空间也急剧扩大。传统的优化方法很难得到最优解。遗传算法是找到这个满意解的最佳工具。例如，遗传算法已经成功地应用于解决旅行商问题、背包问题、包装问题和图划分问题。(3)在许多情况下，很难通过建立数学模型来精确地解决生产调度问题。在实际生产中，更多的经验用于调度。遗传算法是解决复杂调度问题的有效工具。遗传算法已有效应用于单件生产车间调度、装配线生产车间调度、生产计划、任务分配等方面。(4)自动控制。在自动控制领域，有许多与优化相关的问题需要解决，遗传算法已经初步应用于其中。例如，用遗传算法优化控制器参数，学习基于遗传算法的模糊控制规则，基于遗传算法的参数辨识，基于遗传算法和权重学习的神经网络结构优化等。(5)以机器人为例，研究了遗传算法并将其应用于移动机器人路径规划、关节机器人运动轨迹规划、机器人结构优化和行为协调。(6)图像处理的遗传算法可用于图像处理中扫描、特征提取和图像分割的优化计算。目前，遗传算法已经应用于模式识别、图像恢复、图像边缘特征提取等领域。10.4.1遗传算法的要素(1)染色体编码方法基本遗传算法使用固定长度的二进制符号来表示群体中的个体，它们的等位基因由二进制符号集0，1组成。初始个体基因值可以由均匀分布的随机值产生，例如，它可以代表染色体长度为18的个体。(2)个体适应度评价：基本遗传算法与个体适应度成正比的概率确定因此，必须首先确定从目标函数值J到个体适应度F的转换规则。(3)遗传算子：基本遗传算法使用以下三种遗传算子：选择操作：使用比例选择算子；(2)交叉操作：使用单点交叉算子；(3)变异操作：使用基本位变异算子或一致变异算子。(4)需要预先设置基本遗传算法的以下四个操作参数：m:种群规模，即种群中包含的个体数，一般为20 100个；g:遗传算法的终止进化代数，一般取100 500；Pc:交叉概率，一般为0.4 0.99；Pm:变异概率，一般为0.00010.1。对于需要优化的实际问题，遗传算法一般可以按照以下步骤构造：步骤1:确定决策变量和各种约束，即确定问题的个体表型x和解空间；第二步是建立优化模型，即确定目标函数的类型、数学描述形式或定量方法；10.4.2遗传算法应用步骤，步骤3:确定代表可行解的染色体编码方法，即确定遗传算法的个体基因型x和搜索空间；第四步是确定解码方法，即确定个体基因型X到个体表型X的对应关系或转换方法；第五步：确定个体适应度的量化评价方法，即确定目标函数值向个体适应度的转化规律；第六步：设计遗传算子，即确定遗传算子的具体操作方法，如选择操作、交叉操作和变异操作。步骤7:确定遗传算法的相关操作参数，即M、G、Pc、Pm和其他参数。上述操作过程如图10-1所示。图10-1遗传算法流程图，用遗传算法寻找罗森布鲁克函数的最大值，用10.5遗传算法寻找函数的最大值，用10.5.1二进制编码遗传算法寻找函数的最大值来解决遗传算法的构造过程中的这个问题：(1)确定决策变量和约束条件；(2)建立优化模型；(3)确定编码方法，使用长度为10位的二进制编码串分别代表两个决策变量X1和X2。10位二进制代码串可以表示从0到1023的1024个不同的数字，因此x1和x2的域被离散成1023个相等的区域，1024个不同的离散点包括两个端点。从离散点-2.048到离散点2.048分别对应于从00000000000000 (0)到111111111(1023)的二进制代码。由x1和x2表示的两个10位长的二进制代码串连接在一起形成一个20位长的二进制代码串，这构成了用于该函数优化问题的染色体编码方法。使用这种编码方法，遗传算法的解空间和搜索空间是一一对应的。例如，它表示个体的基因型，其中前10位代表x1，后10位代表x2。(4)确定解码方法：解码时，需要将20位长的二进制码串切割成两个10位长的二进制码串，然后分别转换成相应的十进制整数码，分别记为y1和y2。根据个体编码方法和域的离散化方法，用于将代码y转换成变量x的解码公式是，例如，对于个体，它由两个代码组成。在解码两个代码之后，可以获得两个实际值(5)来确定个体评估方法：由于Rosenbrock函数的范围总是非负的，并且优化目标是找到函数的最大值，所以个体的适应度可以直接作为相应的目标函数值，即选择个体适应度的倒数作为目标函数(6)来设计遗传算子：选择操作使用比例选择算子，交叉操作使用单点交叉算子，变异操作使用基本位变异算子。(7)确定遗传算法的操作参数：种群规模M=80，终止进化代数G=100，交叉概率Pc=0.60，变异概率Pm=0.10。以上七个步骤构成了基本的遗传算法从仿真结果可以看出，随着进化过程的进行，群体中一些适应度较低的个体逐渐被淘汰，而一些适应度较高的个体越来越多，他们都集中在期望问题的最佳点附近，从而寻找问题的最优解。10.5.2实数编码遗传算法寻找函数最大值遗传算法的构造过程解决了这个问题：(1)确定决策变量和约束；(2)建立优化模型；(3)确定编码方法：用2个实数分别表示2个决策变量，将域离散化为离散点-2.048到离散点2.048的大小实数。(4)确定个体评价方法：将个体适应度直接作为相应的目标函数值，即选择个体适应度的倒数作为目标函数；(5)设计遗传算子：选择操作采用比例选择算子，交叉操作采用单点交叉算子，变异操作采用基本位变异算子。(6)确定遗传算法的运行参数：种群规模M=500，终止进化代数G=200，交叉概率Pc=0.90。适应性变异概率，即变异概率与适应度有关，适应度越小，变异概率越大。上述六个步骤构成了一个真正的编码遗传算法，用于优化计算罗森布鲁克的最大值。十进制编码用于寻找罗森布鲁克函数的最大值。仿真程序见第10_2章。模拟程序要经过200步的迭代，最好的例子是，函数的最大值为3880.3。10.6基于遗传算法优化的径向基函数网络逼近，10.6.1遗传算法优化原理在径向基函数网络逼近算法第7.3节中，网络权值、高斯函数中心向量和基宽度向量的初始值难以确定，如果这些参数选择不当，逼近精度将下降，甚至径向基函数网络将发散。径向基函数网络参数的优化可以通过遗传算法来实现。为了获得满意的逼近精度，误差的绝对值指标被用作参数选择的最小目标函数。在公式中，逼近的总步长是第一步中径向基函数网络的逼近误差。在遗传算法的应用中，为了避免参数选择范围过大，可以先根据经验选择一组参数，然后用遗传算法围绕这组参数进行设计，从而大大减少了初始优化的盲目性，节省了计算量。10.6.2仿真示例使用径向基函数网络来逼近以下对象：在径向基函数网络中，网络输入信号为2，即网络的初始权重和高斯函数参数的初始值之和，通过遗传算法进行优化。遗传算法优化程序是第10 _ 3A章。采取总的近似步骤，每个步骤的近似误差由第10 _ 3B章获得。使用二进制编码，向量B、C和W中的每个值由10位二进制编码串表示。在遗传算法优化中，样本数为Size=30，交叉概率为Pc=0.60，采用自适应变异概率，即适应度越小，变异概率越大。以变异概率为优化所用的径向基函数网络结构为2-3-1，网络权值wj的取值范围为-1，1，高斯函数基宽向量的取值范围为0.1，3.0，