智能控制系统-遗传算法

null第四章 遗传算法第四章 遗传算法4.2 遗传算法的基本操作4.1 遗传算法的研究现状4.3 遗传算法的实现遗传算法的研究现状遗传算法的研究现状遗传算法的研究新动向： 1、基于遗传算法的机器学习：把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。 2、遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合， 3、并行处理的遗传算法的研究十分活跃。 4.1遗传算法的研究现状遗传算法的研究现状遗传算法的研究新动向： 4、遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用， 5、遗传算法和进化规划（Evolution rogramming,EP）以及进化策略（Evolution Strategy,ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化的智能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。 4.1遗传算法的研究现状遗传算法的研究现状遗传算法的发展情况： 1、1975年美Michigan大学J.Holland教授提出。特点是群体搜索策略和群体中个体之间的信息交换。 2、1991年D.Whitey在他的中提出了基于领域交叉的交叉算子（Adjacency based crossover），这个算子是特别针对用序号示基因的个体的交叉，并将其应用到了TSP问题中，通过实验对其进行了验证。 3、D.H.Ackley等提出了随即迭代遗传爬山法（Stochastic Iterated Genetic Hill-climbing，SIGH）采用了一种复杂的概率选举机制，此机制中由m个“投票者”来共同决定新个体的值（m表示群体的大小）。实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力。 4.1遗传算法的研究现状遗传算法的研究现状遗传算法的发展情况： 4、H.Bersini和G.Seront将遗传算法与单一方法（simplex method）结合起来，形成了一种叫单一操作的多亲交叉算子（simplex crossover），该算子在根据两个母体以及一个额外的个体产生新个体，事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。同时，文献还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三者交叉算子比其余两个有更好的性能。 4.1遗传算法的研究现状遗传算法的研究现状遗传算法的发展情况： 1、国内也有不少的专家和学者对遗传算法的交叉算子进行改进。2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题 2、2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法（Building-block Coded Parallel GA，BCPGA）。该方法以粗粒度并行遗传算法为基本框架，在染色体群体中识别出可能的基因块，然后用基因块作为新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编码的染色体群体作为下一轮以相同方式演化的初始群体。 3、2005年，江雷等针对并行遗传算法求解TSP问题,探讨了使用弹性策略来维持群体的多样性,使得算法跨过局部收敛的障碍,向全局最优解方向进化。 4.1遗传算法的基本原理遗传算法的基本原理 遗传算法是一种基于自然选择和基因遗传学原理的优化搜索方法。 全局优化问题：在搜索空间至少找到一个使目标函数最大化的点。 主要考虑两类搜索空间： 1）伪布尔优化问题：S在离散空间B,所有长度为L且取值为0或1的二进制位串的集合 2）连续参数优化问题：取S为伪n维实数空间R中有界集合，相应的具有连续变量的优化问题4.1遗传算法的基本原理遗传算法的基本原理 “优胜劣汰，适者生存”生物进化原理引入待优化参数形式的编码串群体中，按照一定的适配值函数及一系列遗传操作对个体进行筛选，从而使适配值高的个体被保留下来，组成新的群体，新群体包含上一代的大量信息，并且引入了新的优于上一代的个体。 遗传算法的研究目的： 1)抽象和严谨地解释自然界的适应过程； 2)为了将自然生物系统的重要机理运用到工程系统、计算机系统或商业系统等人工系统的设计中。4.1遗传算法的特点遗传算法的特点1)是对参数的编码进行操作，而非对参数本身。 2)遗传算法是从许多点开始进行并行操作，而非局限于一点，因而可以有效地防止搜索过程收敛于局部最优解。 3)遗传算法通过目标函数来计算适配值，而不需要其他推导和附加信息，从而对问题的依赖性小。 4)寻优规则是由概率决定的，而非确定性的。 5）遗传算法是在解空间进行高效启发性搜索，而非盲目地穷举或完全随机搜索；遗传算法的特点遗传算法的特点6）遗传算法对于待寻优的函数基本无限制，它不要求函数连续，也不要求函数可微。可以是数学解析式所表达的显函数，又可映射矩阵甚至是神经网络等隐函数。 7）具有并行计算的特点，可通过大规模并行计算来提高计算速度； 8）适合大规模复杂问题的优化； 9）计算简单，功能强。遗传算法的基本操作遗传算法的基本操作一、遗传算法的基本流程4.2遗传算法的基本操作遗传算法的基本操作遗传算法涉及六大基本要素 1、参数编码 2、初始群体的设定 3、适应度函数的设计 4、遗传操作的设计 5、控制参数的设定 6、迭代终止条件4.2遗传算法的基本操作遗传算法的基本操作二、遗传编码 1、由问题空间向GA编码空间的映射称为编码。 2、问题编码一般满足三个原则： 1）完备性 问题空间所有点→GA空间的点 2）健全性：染色体位串→ 问题空间某潜在解 3）非冗余性4.2遗传算法的基本操作遗传算法的基本操作二、遗传编码 3、常用的编码方式 1）二进制编码 2）大字符集编码 3）序列编码 4）实数编码 5）树编码 6）自适应编码 7）乱序编码4.2二进制编码二进制编码假设某一参数的取值范围是[umin , umax]，用长度为l的二进制编码符号串来表示该参数，则它总共能够产生 2l种不同的编码，参数编码时的对应关系如下： 00000000…00000000＝0 umin 00000000…00000001＝1 umin +  00000000…00000010＝2 umin + 2 …… 11111111…11111111=2l–1 umax 其中， 为二进制编码的编码精度，其公式为：null解码 假设某一个体的编码是： x： bl bl-1 bl-2……b2b1 则对应的解码公式为： null[例] 设 -3.0 ≤ x ≤ 12.1 , 精度要求 =1/10000，由公式： 即： 217 < 151001 < 218 x需要18位 {0/1} 符号表示。 如：010001001011010000 解码：得：三、遗传算子三、遗传算子生物的发展进化主要有三个原因：遗传、变异和选择。 遗传：是生物进化的基础，子代总是和亲代相似。遗传性是一切生物所共有的特性，使得生物能够把它的特性、性状态传给后代。 变异：指子代和亲代有某些不相似的现象，它是一切生物所具有的共同特征，是生物个体之间相互区别的基础。引起变异的原因主要是生活环境的影响、器官的使用的不同及杂交。生物的变异性为生物的进化和发展创造了条件。 选择：是指具有精选的能力。它决定了生物进化的方向。自然选择是指生物在自然界的生存环境中适者生存，不适者被淘汰的过程。通过不断地自然选择，有利于生存的变异就会遗传，积累起来，使变异越来越大，逐步产生新的物种。 4.2复 制（选择）复 制（选择）1、复制：从一个旧种群中选择生命力强的个体位串（字符串）产生新种群的过程。 复制是个体位串根据目标函数f（适配值函数）拷贝自己的过程。 适配值在自然群体中是由一个生物为继续生存而捕食、预防时疫、在生长和繁殖后代过程中克服障碍的能力决定的。 在复制过程中，目标函数（适配值）是该位串被复制或被淘汰的决定因素。 复 制（选择）复 制（选择）2、复制算法 1)适应度比例法（转轮法）：每个个体被选择的期望数量与其适应度值和群体平均适应度值的比例有关 2）Boltzmann选择 3）排序选择：将群体中个体按适应度值由大到小排序，将事先设计好的序列概率分配给每个个体。 4）联赛选择：群体中随机选择一定数量的个体，将其中适应度最大的个体放入配对池中 5）精英选择 6）稳态选择 复 制复 制3、复制操作 复制的初始种群（旧种群）的产生是随机的。 例：求函数f=x2在[0，31]上取得最大者的点。 1）在[0，31]上的x可用5位二进制编码表示。 2）通过投硬币可产生初始种群如下（1正面，0背面） 将其编成四个位串： 01101 11000 01000 10011 位串解码为十进制数： 位串1：23＋22+ 1＝13 位串3： 8 位串2：24 ＋ 23＝24 位串8：19 取目标函数或适配值f（x）＝x2。复 制复 制复 制复 制 复制时，简单转动按权重划分的转盘4次，从而产生4个下一代的种群。适配值高的，被复制的概率大，适配值低的复制概率低，有可能被淘汰。 null交叉交叉 交叉分两步实现： 在由等待配对的位串构成的匹配池中，将新复制的产生位串个体随机两两配对； 随机选择交叉点，对匹配的位串进行交叉繁殖，产生新的位串。 交叉交叉 设位串的字符长度为l，在[1,l-1]的范围内，随机选取一个整数值k作为交叉点，将两个配对串从位置k后的所有字符进行交换，从而产生新的位串。 例如图：位串长度5，将定在1－4之间随机选取一个数k＝4，则两个串前面4个位保持不变，第5个位交换，产生新的 位串：null遗传算法的有效性来自于复制和交叉操作。变异变异 遗传算法中复制和交叉是第一位的，但不能保证不会遗漏一些重要遗传信息。在人工遗传系统中，变异用来防止不可弥补的遗漏。 变异在遗传算法中的作用必不可少。变异操作可以起到恢复位串字符多样化的作用，并能适当提高遗传算法的搜索效率。 根据经验研究，为了取得好的效果，变异的概率位每一个千位的传送中，只变异一位，即变异的概率为0.001。变异变异 变异是某个字符串某一位的值偶然（概率很小）随机的改变，即某些特定位置上简单地把1变为0，或反之。 例如：求使函数fx＝x2在[0，31]上取得最大值的点x0。 null1、在区间上整参数x可用一个5位的二进制位串进行编码，x的值直接对应二进制位串的数值： X＝0 00000 x＝31 11111 2、用抛硬币方法产生一个由4个 位串组成的初始种群，适配 值及选择率 复制和交叉null3、变异。 取变异概率Pm＝0.001，则平均每1000位中才 有一位变异，由4个位串组成的种群共有20 位，则变异的期望值为20*0.001=0.02位。null2.6 算法流程图null基本遗传算法应用举例 [例] Rosenbrock函数的全局最大值计算。 max f(x1,x2) = 100 (x12-x22)2 + (1-x1)2 s.t. -2.048 ≤ xi ≤ 2.048 (xi=1,2)如图所示： 该函数有两个局部极大点， 分别是: f(2.048, -2048)=3897.7342 和 f(-2.048,-2.0048)=3905.9262 其中后者为全局最大点。null下面介绍求解该问题的遗传算法的构造过程： 第一步：确定决策变量及其约束条件。 s.t. -2.048 ≤ xi ≤ 2.048 (xi=1,2) 第二步：建立优化模型。 max f(x1,x2) = 100 (x12-x22)2 + (1-x1)2 第三步；确定编码方法。 用长度为l0位的二进制编码串来分别表示二个决策变量x1,x2。 lO位二进制编码串可以表示从0到1023之间的1024个不同的数，故将x1,x2的定义域离散化为1023个均等的区域，包括两个端点在内共有1024个不同的离散点。从离散点-2.048到离散点2.048，依次让它们分别对应于从0000000000(0)到1111111111(1023)之间的二进制编码。再将分别表示x1和x2的二个10位长的二进制编码串连接在一起，组成一个20位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。例如 X：0000110111 11011 10001 就表示一个个体的基因型。null第四步：确定解码方法。 解码时先将20位长的二进制编码串切断为二个10位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为y1和y2。 依据前述个体编码方法相对定义域的离散化方法可知，将代码yi转换为变量xi的解码公式为：例如，对前述个体 X： 0000110111 11011 10001 它由这样的两个代码所组成： y1= 55 y2 = 881 经上式的解码处理后，得到： x1= -1.828 x2= 1.476 null 第五步：确定个体评价方法。 由式 f(x1,x2) = 100 (x12-x22)2 + (1-x1)2 可知， Rosenbrock函数的值域总是非负的，并且优化目标是求函数的最大值，故这里可将个体的适应度直接取为对应的目标函数值，并且不再对它作其他变换处理，即有： F(x) = f(x1,x2) 第六步：设计遗传算子。 选择运算使用比例选择算子； 交叉运算使用单点交叉算子； 变异运算使用基本位变异算子。 第七步：确定遗传算法的运行参数。 对于本例，设定基本遗传算法的运行参数如下： 群体大小: M＝80 终止代数: T＝200 交叉概率：pc＝0.6 变异概率：pm＝0.001 遗传算法与常规优化区别遗传算法与常规优化区别1、遗传算法只对参数集的编码操作，不对参数本身操作 2、遗传算法从许多初始点开始并行操作，而不是在一个单点上进行寻优；可以有效防止搜索过程收敛于局部最优； 3、遗传算法通过目标函数计算适配值，不需要其他的推导和附属信息，从而对问题的依赖性小； 4、遗传算法使用随机转换规则而不是确定性规则工作遗传算法的应用遗传算法的应用4.31、 函数优化 　函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。遗传算法的应用遗传算法的应用4.32、 组合优化 　随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、 背包问题、装箱问题、图形划分问题等方面得到成功的应用。 3、GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。 遗传算法的一般算法遗传算法的一般算法4.31、创建一个随机的初始状态 　　初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样，在那里问题的初始状态已经给定了。 2、评估适应度 　　对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。不要把这些“解”与问题的“答案”混为一谈，可以把它理解成为要得到答案，系统可能需要利用的那些特性。　遗传算法的一般算法遗传算法的一般算法4.33、繁殖(包括子代突变) 　　带有较高适应度值的那些染色体更可能产生后代(后代产生后也将发生突变)。后代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。 4、下一代 　如果新的一代包含一个解，能产生一个充分接近或等于期望答案的输出，那么问题就已经解决了。如果情况并非如此，新的一代将重复他们父母所进行的繁衍过程，一代一代演化下去，直到达到期望的解为止。遗传算法的计算机实现遗传算法的计算机实现4.3遗传算法实现中的一些基本问题在遗传算法中，除了复制、交叉、变异基本操作外，还应该考虑目标函数到个体适配值的映射、适配值调整、编码原则和多参数编码映射方法等基本问题。 1、目标函数值到适配值形式的映射 适配值是非负的，任何情况下希望越大越好，而目标函数值有正，负，甚至可能是复数值。并且目标函数和适配值之间的关系是多样的，如求最大值对应点时，目标函数和适配值变化方向相同；求最小值对应点，变化方向相反；目标函数值越小的点，适配值越大。 首先应保证映射后适配值非负，其次目标函数的优化方向对应于适配值的增大方向。 遗传算法实现中的一些基本问题遗传算法实现中的一些基本问题2、适配值调整 遗传算法的运行分为开始、中间和结束三个阶段。 在开始阶段，规模不大的种群内有少数非凡的个体（适配值很高的位串），按通常的选择方法，这些个体会被大量复制，在种群中占有大的比重，这样会减少种群的多样性，从而可能丢失一些有意义的搜索点或最优点，而进入局部最优。 在结束阶段，即使种群内保持了很大的多样性，但若所有或大多数个体都有很高的适配值，从而种群平均适配值和最大适配值相差无几，这样个体选中的机会相同，适配值的作用就会消失，从而搜索性能得不到明显改进，因此有必要对种群内各位串的适配值进行有效调整，既不能相差太大，又要拉开档次，强化位串之间的竞争性。遗传算法实现中的一些基本问题遗传算法实现中的一些基本问题遗传算法实现中的一些基本问题3、编码原则 深层意义上的建筑块原则和最小字母表原则，而后 者是一种应用广泛的实用原则。 最小字母表原则：选择一个使问题得以自然表达的 最小字母进行编码。如二进制编码。 4、多参数级联定点映射编码 多个实数参数的函数优化：采用多参数级联定 点映射编码。 将无符号整数线性映射到待定区间上，仔细控制一 些决定性变量的变化范围和精度。 为了设计多参数编码，把相互关联的参数按要求简 化成若干单一参数代码。 遗传算法的改进遗传算法的改进 在遗传算法进化过程中，有时会产生一些超常的个体，这些个体因竞争力太突出而控制了选择运算过程，从而影响算法的全局优化性能，导致算法获得某个局部最优解。 改进途径： （1）对编码方式的改进 （2）对遗传算子 的改进 （3）对控制参数的改进 （4）对执行策略的改进 对编码方式的改进对编码方式的改进 二进制编码优点在于编码、解码操作简单，交叉、变异等操作便于实现，缺点在于精度要求较高时，个体编码串较长，使算法的搜索空间急剧扩大，遗传算法的性能降低。格雷编码克服了二进制编码的不连续问题 ，浮点数编码改善了遗传算法的计算复杂性 。 对遗传算子 的改进对遗传算子 的改进排序选择 均匀交叉 逆序变异（1） 对群体中的所有个体按其适应度大小进行降序排序； （2） 根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次序分配给各个个体； （3） 以各个个体所分配到的概率值作为其遗传到下一代的概率，基于这些概率用赌盘选择法来产生下一代群体。 对遗传算子 的改进对遗传算子 的改进排序选择 均匀交叉 逆序变异（1） 随机产生一个与个体编码长度相同的二进制屏蔽字P = W1W2…Wn ； （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 对控制参数的改进对控制参数的改进 Schaffer建议的最优参数范围是： M = 20-100 //群体规模 T = 100-500 //最大迭代代数 Pc = 0.4-0.9 //交叉概率 Pm = 0.001-0.01 //变异概率 对控制参数的改进对控制参数的改进 Srinvivas等人提出自适应遗传算法，即PC和Pm能够随适应度自动改变，当种群的各个个体适应度趋于一致或趋于局部最优时，使二者增加，而当种群适应度比较分散时，使二者减小，同时对适应值高于群体平均适应值的个体，采用较低的PC和Pm，使性能优良的个体进入下一代，而低于平均适应值的个体，采用较高的PC和Pm，使性能较差的个体被淘汰 。作业作业说明遗传算法的基本思想和算法流程 利用遗传算法编程求出下面函数的极小值： z=2-exp[-(x2+y2)], x,y[-5,+5]