第4章(3遗传算法).ppt

第四章，计算智能的仿生技术(3)遗传算法，4.3遗传算法，4.3.1遗传算法原理，4.3.2优化模型的遗传算法求解4.3.3基于遗传学的分类学习系统，4.3.1遗传算法原理，遗传算法是模拟自然环境中生物的遗传和进化过程形成的自适应全局优化搜索算法。它模拟生物的繁殖、交配和变异，并从最初的种群中产生一群更适合环境的后代。1975年，美国密歇根大学的霍兰德教授提出了。德博士。美国人Jong将遗传算法应用于函数优化。戈德堡完成了遗传算法的框架。4.3.1.1遗传算法概述遗传算法是一种基于遗传的搜索优化算法。遗传作为一种指令代码封装在每个染色体(个体)中，并以基因(比特)的形式包含在染色体(个体)中。在遗传算法中，“染色体”对应于数据或数组，通常由一维字符串结构数据表示。字符串上的每个位置对应一个“基因”，每个位置的值对应基因的值。一串基因是一个染色体，或基因型个体。一定数量的个体组成一个群体。遗传算法以某种形式对问题的每一个可能的解进行编码，编码后的解称为染色体(个体)。随机选择N条染色体(个体)形成初始种群，然后根据预定的评价函数计算每条染色体的适应度值，使得性能较好的染色体具有较高的适应度值。选择适应值高的染色体进行复制，通过遗传操作：选择、交叉(重组)和变异，产生一组更适合环境的新染色体，形成新的种群。这一代又一代人继续繁衍和进化，最终收敛到一个最适合环境的个体，以获得问题的最优解。遗传算法处理流程图，4.3.1.2遗传算法的基本要素，遗传算法包含以下五个基本要素：1)问题编码2)初始种群设置3)适应度函数设计4)遗传操作设计5)控制参数设置(主要指种群规模和使用遗传操作的概率等。)这五个要素构成了遗传算法的核心内容。(1)问题编码，如何将问题描述为一个位串，即问题编码。通常，问题中的每个参数都用二进制编码，形成子串，然后将子串拼接在一起，形成“染色体”位串。不同的字符串长度和不同的编码系统会对问题求解的准确性和遗传算法的收敛时间产生很大的影响。目前，还有其他编码方法，如使用向量和规则来表示染色体。(2)对于初始种群的生成，遗传算法是一种种群操作，因此必须为遗传操作准备一个由多个初始解组成的初始种群。初始种群中的每个个体都是通过随机方法产生的。(3)适应度函数的确定，其根据目标函数来确定。适应值总是非负的，无论如何，越大越好。适应度函数的选择非常重要。它直接影响算法的收敛速度，即能否找到最优解。对于函数优化问题，目标函数本身可以直接作为适应度函数。(4)控制参数，如个体编码长度、群体大小M、交叉概率Pc、变异概率Pm、终止代数T等。对遗传算法的运行有很大影响，需要仔细选择。根据每条染色体的适应值，适应值越大，被选择的概率越大，下一代的后代数量越多。选择操作基于对组中个体的适应值的评估。目前，常用的选择算子包括适应值比例法、最佳个体保存法、期望值法等。交叉算子通过染色体重组产生新一代染色体。如果有两个二进制编码的个体a和b .交叉前后：a=a1a2a 3a4a 5a =a1a2a 3B4 b5b=b1b S3B4 b5b =b1b S3a4a 5(父代)(子代)；改变某一位的内容。在二进制编码中，0的一个比特变成1，1变成0。例如，第四位数字110010被突变成110110(父)(子)，4.3.1.4遗传算法的理论基础，1。遗传算法的理论基础是荷兰提出的模式定理。模式是一个相似模板，它描述了一个位串子集，这些位串在总体中的某些确定的位串位置上具有相似性。模式定理是遗传算法的理论基础。这表明具有高适应值、短长度和低阶的模式将至少指数地增加其后代中包含模式H的比特串的数量。原因是遗传使适应值高的模型复制更多的后代。基因块假设高适合度、短长度和低顺序的模式被称为基因块。基因块假说：短长度、低阶和高适应度模式(基因块)通过生殖、交换和突变等遗传操作逐渐进化，形成潜在的高适应度位串。这一假设指出，通过遗传算法可以获得接近全局最优解的能力。4.3.1.5遗传算法的特点，遗传算法是搜索种群。它在群体中搜索多个个体，形成一个进化的群体序列。它能找到全局最优解(比爬山法好)。遗传算法是一种随机搜索方法。这三个操作符都是随机操作，使用概率转移规则。遗传算法的处理对象是由问题参数编码的个体，而不是参数本身。参数被编码成位串个体，并由遗传算子操作。不直接对参数变量进行操作。遗传算法使用无导数或其他辅助信息的自适应值信息。遗传算法使用适应值来评估个体，并使用遗传算子来产生更好的后代。它不需要像神经网络那样由梯度公式来指导。隐式并行性：遗传算法是对n位字符串个体进行操作，它隐含着大量的模式(个体所包含的通配符#)，4.3.2遗传算法优化模型，遗传算法用于优化计算实例，实例1:在上找到f(x)=x2的最大值0，31。首先，初始人口1。编码：X由五位二进制表示，x=000000 x=31111112。初始群体随机产生4个人：13，24，8，193。适应值fi直接使用目标函数作为适应值：fi=xi2，非负；(2)逐步增加4。选择率ps和期望值选择率：ps=fi/fi平均适应值：f=fi/n期望值：fi/f5。实际选择值的期望值是一个整数，并计算初始群体参数。2.遗传，描述：1。在种群中选择(繁殖),如果实际选择值(期望值)高，则进行乘法运算；实际选择值(期望值)越低，再现越少或没有再现。个体在交配池中的繁殖。2.交叉随机选择交配对象(相同的个体不交配)，例如个体1和2、3和4。交叉点被随机选择用于交叉。变异概率pe=0.01意味着每100个人中就有一个变异。新人口的平均值和最大值有了很大提高。平均值为293439，最大值为576729。在新人口的四个人中，两个人有所改善：25，25；两个坏了：12个，16个。如果一个世代再次被继承，并且仅使用交叉而不使用变异，那么多少个世代将不会得到最优解31(11111)。主要原因是第三位的所有个体都是0，因此只能获得27(11011)个次优解。如果在第四个位置选择一个个体从0突变到1，在遗传过程中将获得最优解。例如，旅行推销员问题(TSP)，知道n个城市的地理位置(x，y)，找到穿过所有城市的最短距离，然后返回到起始城市，每个城市只经过一次。这是一个NP完全问题，它的计算量是城市数量的数量级。遗传算法目前被用来解决这个问题。1，编码，每条路径对应一个个体，其形式表示为R=城市_否|城市_否不互相重复n，n是城市的数量。例如，对于n=10的TSP问题，它代表一个人的城市路径：31578910426，2。每个人都代表一条可能的道路。个体n的适应值是：其中n是人口数，Dn是沿着个体标记的城市序列行进的距离：其中ni代表个体中第一个位置的城市号，n11=n1。自适应值是非负的，值越大越好。指示所有个体的路径长度总和。3.十字架。从人群中随机选择两个不同的个体进行杂交，并随机选择一个截面。横截面中两个个体的对应部分通过匹配和换位实现交叉操作。对于个体a和b:a=984 | 567 | 13210 b=871 | 4103 | 2965横截面对于个体a，在横截面中由b转置的数字，例如4、10和3，对于a中相同数量的其他位是相反的，即4变为5，10变为6，3变为7；对于个体B，进行类似的处理，最后获得以下结果：A，=985 | 4103 | 1726b，=831 | 567 | 29104，4。变异。根据变异概率Pe，从种群中随机选择待变异个体，在个体上随机选择两个变异位置，然后交换两个位置上的城市序列号。例如：A=98456713210下划线部分是要突变的两个位置。变化是：a=97456813210，5。遗传算法结果表明，n个城市的最优路径接近一个外环无交叉的环。4.3.3分类学习系统基于遗传学，分类器系统是一种学习字符串规则的学习系统(也称为分类器)，它由三个主要部分组成：规则和消息系统、信任分配系统和遗传算法，其中规则和消息系统是产生系统的一种特殊形式。产生式规则的一般形式是：在分类器系统中，产生式规则的语法受到很大限制，采用固定长度的表示，适合遗传操作。4.3.3.1遗传分类学习系统的基本原理GCLS。我们开发的GCLS遗传分类学习系统是一个字符串规则(分类器)的学习系统。它将规则“条件”和“结论动作”组合成一个消息个体，也称为分类器。适应值被设计为分类器(规则)覆盖的消息数。覆盖的消息越多，规则就越有效。GCLS系统由五部分组成：检测器信息表分类器测试表行动者分类器系统的详细结构框图如下：分类学习系统的工作流程，1。所有预设参数的初始化。2.将环境信息放入消息表中。3.调用初始群体的信任分配算法，并修改规则的适应值。4.合并群体，并将合并的群体设置为群体m。如果群体m已经收敛，则将群体的规则复制到细化分类器，然后跳到步骤(8)。6.调用遗传算法生成新的一代种群L，它与种群M结合并发送到种群F，从而形成新的初始种群。7.返回到步骤(3)。8.调用测试表上的细化分类器规则T生成结论部分。9.将T发送至致动器，并将其转换为实际输出值，以作用于环境。4.3.3.2 GCLS遗传分类器学习系统的应用，这是用于识别脑出血和脑血栓的学习诊断规则的应用实例。为了做出判断，应该考虑以下特征(属性):编码原则，知识的获取，1。编码方法：每个训练示例由12个特征和1个类别组成。将示例编码为二进制字符串：消息是由24位条件和2位结论组成的二进制组。如上面的例子：m=(01001010101