人工智能第七章遗传算法ppt下载

PPT内容

这是人工智能第七章遗传算法ppt，包括了遗传算法简介，基本遗传算法，函数优化，旅行商问题等内容，欢迎点击下载。

第7章  遗传算法 7.1    遗传算法简介 7.2    基本遗传算法 7.3    函数优化 7.4    旅行商问题 7.1   遗传算法简介 染色体（Chromosome）：染色体是指对个体进行编码后所得到的编码串。染色体中的每1位称为基因，染色体上由若干个基因构成的一个有效信息段称为基因组。 适应度（Fitness）函数：适应度函数是一种用来对种群中各个个体的环境适应性进行度量的函数。其函数值是遗传算法实现优胜劣汰的主要依据 遗传操作（Genetic Operator）：遗传操作是指作用于种群而产生新的种群的操作。标准的遗传操作包括以下3种基本形式： 选择（Selection） 杂交（Crosssover） 变异（Mutation） 7.1.3  设计遗传算法的基本步骤 procedure genetic program    begin initialize                              //种群初始化         evaluate                              //评价种群        while ( not termination-condition) do         begin select       from                  //选择个体到下一种群              alter                                  //对种群进行遗传操作          evaluate        end end 7.2    基本遗传算法 遗传算法的基本步骤 7.2.2   适应性的度量 个体的适应值即是它繁殖的能力，它将直接关系到其后代的数量，在遗传算法中，适应函数是用来区分群体中个体好坏的标准，是算法演化过程的驱动力，同时也是进行自然选择的唯一依据。 原始适应函数 原始适应函数是问题求解目标的直接表示，通常采用问题的目标函数作为个体的适应度量 。 定义原始适应函数的方法可能不止一种，选择时要尽量反映问题本身整体特性，而不能只追求片面的目标 。 标准适应函数 适应值会出现两种情形，一是极小情形即原始适应值越小个体性能越好；另一种是极大化情形即原始适应值越大个体性能越好  。 遗传算法中的某些选择策略则要求适应函数是非负的，而且适应值越大表明个体的性能越好。 对于极小化情形，标准适应值可定义为 ： 适应值的调节 存在问题：过早收敛、停滞现象  改变算法性能的方法之一是对适应值进行调节，即通过变换，改变原适应值的比例关系。 7.2.3  选择策略 不同的选择策略将导致不同的选择压力，即下一代中父代个体的复制数目的不同分配关系。 转盘式选择 转盘式选择是基于适应值比例的选择中比较重要的选择策略。 先计算个体的相对适应值       =  根据选择概率      把一个圆盘分成N份  生成一个内的随机数 r(0≤r≤1)，若                         ，则选择个体 i 0 1 1 0 1 => x=13 => f(x) = 169 1 1 0 0 0 => x=24 => f(x) = 576 0 1 0 0 0 => x=8   => f(x) = 64 1 0 0 1 1 => x=19 => f(x) = 361 169+576+64+361=1170 用轮盘赌选择个体时，各个个体的被选择的概率为：0.1444，0.4923，0.0547，0.3085； 制作转盘：0-0.1444；0.1445-0.6367；0.6368-0.6914；0.6915-1； 7.2.3  选择策略 基于排名的选择 首先根据个体     的适应值在群体中的排名来分配其选择概率        。 根据这个概率使用转盘选择 线性排名选择 线性排名选择方法是按适应值大小从好到坏依次排列为                                ，然后根据一个线性函数分配选择概率        。 7.2.4   遗传算子的设计 杂交算子 杂交运算是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。 单点杂交：称为简单杂交，它是指在个体编码串中只随机设计一个杂交点，然后在该点相互交换两个配对个体的部分染色体。 7.2.4   遗传算子的设计 双点杂交与多点杂交 双点杂交是指在个体编码串中设置了二个杂交点，然后再进行部分基因交换。 7.2.4   遗传算子的设计 均匀杂交 均匀杂交是指两个配对个体每一个基因座上的基因都以相同的杂交概率进行交换，从而形成两个新的个体。 均匀杂交实际上可归属于多点杂交的范围 . 算术杂交 算术杂交是由两个个体的线性组合而产生出两个新的个体。 为了能够进行线性组合运算，算术杂交的操作对象一般是浮点数所表示的个体。 7.2.4   遗传算子的设计 变异算子 变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其它等为基因来替换，从而形成一个新的个体。 遗传算法中使用变异算子主要有以下两个目的： 1）改善遗传算法的局部搜索能力。 2）维持群体的多样性，防止出现早熟现象。 7.2.4   遗传算子的设计 基本位变异 对个体的每一个基因座，依变异概率     指定其为变异点。 对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新的个体。 均匀变异 依次指定个体编码串中的每个基因座为变异点。 对每一个变异点，以变异概率     从对应基因的取值范围内取一随机数来替代原有基因值。 7.2.4   遗传算子的设计 非均匀变异 非均匀变异的具体操作过程与均匀变异相类似，但它重点搜索原个体附近的微小区域。 当个体形态很接近时，杂交算子会失去作用；此时变异算子有助于算法跳出局部最优，从而搜索到全局最优解； 7.3   函数优化 优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术 . 最优化问题可分为函数优化问题和组合优化问题两大类，其中函数优化的对象是一定区间内的连续变量，而组合优化的对象则是解空间中的离散状态。 所有的搜索、优化都是对目标函数的“函数”优化。 近年来，遗传算法作为一种全新的优化方法，其巨大的潜力受到越来越多学者的重视。 7.3.1  问题描述 全局最大化 :  对于             ，寻求点             ，都有 全局最小化：对于              ，寻求点             ，都有 不论待求解问题是求最大值还是求最小值问题，我们可将待求解的问题一律看成求解最大值问题。 转化方法如下：如果优化问题是就函数   的最小值，它等同与求函数    的最大值，其中                        ，即 7.3.1  问题描述 目标函数      在其值域里只取正值，若为负，可通过加入某个正数  C 使之为正，即 7.3.2  种群的初始化 对于函数优化来说，在初始化过程中需在上、下限区间内产生随机数，并将这个随机数赋给变量 。 7.3.3   选择策略 在选择策略上，本例采用基于概率的轮转盘选择策略。计算出群体的总适应值 对每个个体                     ，选择概率                    ，显然                   。 每个个体                    的累积概率                ，我们可得知                且                       。 7.3.4   遗传算子 杂交算子 对新群体中的每个个体产生一个在[0,1]区间内产生随机浮点数； 如果           ，随机地选择个体配对，然后进行杂交操作。若个体中有n个分量，在[1,n]区间中产生随机整数 pos，pos表示杂交点的位置。 若两个个体分别为： 在pos点杂交后产生子代    7.3.4   遗传算子 算法的程序描述如下： 7.3.4   遗传算子 7.3.4   遗传算子 变异算子 变异就是以很小的概率 随机地改变群体中个体(染色体)的某些基因的值。 具体算法的描述如下：  7.4  旅行商问题 7.4.1  旅行商问题的描述 已知n个城市之间的距离，现有一推销员必须访问这n个城市，并且每个城市只能访问一次，最后必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长最短。 旅行商问题可分为对称旅行商问题和非对称旅行商问题。 TSP问题求解的研究工作主要集中在以下几个方面： 采用适当的表示方法表示个体的编码； 设计可用的遗传算子，以保持父代的特性避免新个体的不可行性； 防止算法过早的收敛。 7.4.2 个体的编码表示 TSP问题的个体编码表示方法大致可分为两大类： 在巡回旅行路线所经过的城市序列； 各城市在巡回旅行路线中的邻接关系。 近邻表示 近邻表示方法将路径表示成n个城市的一个排列，若排列中的第i位为城市，当且仅当路径中从城市i所到达的下一个城市为j。 （2 4 8 3 9 7 1 5 6）表示 1-2-4-3-8-5-9-6-7 有不合法的表示：(2 4 8 1 9 3 5 7 6)包含回路：1-2-4-1； 杂交算子将产生非法路径；需要修正； 次序表示 表示方法为：先取城市集合C的顺序排列如C=（1 2 3 4 5 6 7 8 9）作为次序排列的一个参照点，然后按路径中城市处在C的位置确定表示串中的点，且每确定一个则从C中删除相应的城市。 (1 1 2 1 4 1 3 1 1)表示 1-2-4-3-8-5-9-6-7 可以采用传统的杂交算子； 7.4.2 个体的编码表示 路径表示 路径表示可能是TSP问题最自然、最直接的表示方式。它直接采用城市在路径中的相对位置来进行表示。 例如，路径5——1——7——8——6——2——9——3——4直接表示成（5 1 7 8 6 2 9 3 4）  7.4.3   杂交算子 部分映射杂交 首先随机地在父体中选取两个杂交点，并交换相应的段，再根据该段内的城市确定部分映射。在每个父体上先填入无冲突的城市，而对有冲突的城市依照映射关系选择候选的城市，直到找到无冲突的城市填入，按此方法获得了杂交后的两个后代。 实例：如两父串及匹配区域为     A＝9 8 4 | 5 6 7 | 1 3 2 0     B＝8 7 1 | 2 3 0 | 9 5 4 6 首先交换A和B的两个匹配区域，得到     A’＝9 8 4 | 2 3 0 | l 3 2 0     B’＝8 7 1 | 5 6 7 | 9 5 4 6  对于A’、B’两子串中匹配区域以外出现的遍历重复，依据匹配区域内的位置映射关系，逐一进行交换。对于A’有2到5，3到6，0到7的位置符号映射，对A’的匹配区以外的2，3，0分别以5，6，7替换，则得     A”＝9 8 4 | 2 3 0 | 1 6 5 7  同理可得：     B”＝8 0 1 | 5 6 7 | 9 2 4 3  这样，每个子串的次序部分地由其父串确定。 次序杂交 首先随机地在父体中选择两个杂交点，再交换杂交段，其它位置根据保持父体中城市的相对次序来确定。 再移动匹配区至起点位置，且在其后预留相等于匹配区域的空间(H数目)，然后将其余的码按其相对次序排列在预留区后面，得到     A”＝5 6 7 H H H 1 9 8 4     B”＝2 3 0 H H H 9 4 8 1  最后将父串A，B的匹配区域相互交换，并放置到A”，B”的预留区内，即可得到两个子代：     A”’＝5 6 7 | 2 3 0 | 1 9 8 4     B”’＝2 3 0 | 5 6 7 | 9 4 8 1  虽然，部分映射杂交与次序杂交非常相似，但它们处理相似特性的手段却不同。部分映射杂交趋向于所期望的绝对城市位置，而次序杂交法却趋向于期望的相对城市位置。 7.4.3   杂交算子 循环杂交 循环杂交的步骤如下： 根据双亲相对应的城市位置设计出一个循环链； 把一个双亲的已在循环上的城市复制到一个后代上； 删去另一个双亲已在循环链上的城市，剩下的城市组成一序列； 将3）步的序列从左到右依次填满后代空缺的位置。  设两个父串为     C＝9 8 2 1 7 4 5 0 6 3     D＝1 2 3 4 5 6 7 8 9 0 不同于选择交叉位置，我们从左边开始选择一个城市     C’＝9一一一一一一一一     D’＝1一一一一一一一一 再从另一父串中的相应位置，寻找下一个城市：     C’＝9一一1一一一一一一一     D’＝1一一一一一一一一9一 再轮流选择下去，最后可得     C’＝9 2 3 1 5 4 7 8 6 0     D’＝1 8 2 4 7 6 5 0 9 3 7.4.4   变异算子 倒置变异 利用简单的倒置操作来进行变异。即首先在父体中随机地选择两个截断点，然后将该两点内的子串中的城市进行反序操作。 A ＝1 2 3 | 4 5 6 | 7 8 9 0 A’＝1 2 3 | 6 5 4 | 7 8 9 0 2.插入变异 插入算子就是随机选择一个城市，并将它插入到一个随机位置中去。    A ＝1 2 3 4 5 6 7 8 9    A’＝1 2 5 3 4 6 7 8 9 3. 移位变异 移位算子是选择一个子路径巡回，然后把它插入一个随机的位置  4. 互换变异 互换变异也被称作基于次序的变异（order-based mutation），操作方法是：随机的选择两个城市，并交换其所处的位置 对于串A A ＝1 2 3 4 | 5 6 7 | 8 9 若对换点为4，7，则经对换后，A’为 A’＝1 2 3 7 | 5 6 4 | 8 9 选择方式和种群构成 选择机制和群体构成 从群体规模来看，有变化规模的方式，也有恒定规模的群体构成方式等。 在遗传算法中，最常见的选择机制是依据适应度的比例概率选择机制；在有限规模的群体中，适应度较高的个体有较大的机会繁殖后代，即生物进化论上的适者生存规则。 在新一代群体构成方法方面存在： N方式：全部替换上一代群体的全刷新代际更新方式。 E方式：保留一个最好的父串的最佳保留（elitist）群体构造方式。 G方式：按一定比例更新群体中的部分个体的部分更新方式（或称代沟方法，这种情况的极端是每代仅删去一个最不适的个体的最劣死亡方式）。 B方式：从产生的子代和父代中挑选最好的若干个个体的群体构成形式。 一般讲，N方式的全局搜索性能最好，但收敛速度最慢；B方式收敛速度最快，但全局搜索性能最差；E方式和G方式的性能介于N方式和B方式之间。在求解货郎担问题的应用中，多选用E方式。 旅行商问题的拓展 自动导航仪的路线规划 物流路线的规划 城市道路撒盐问题 红绿灯设置问题 公交车路线规划问题 城市规划问题 网络构建问题 电路布线问题 装箱问题 ----总体来说，遗传算法在规划、管理等组合优化问题上已经取得不少成功应用的案例 其余的应用 在饲料配方设计中的应用：成本、营养； 艺术设计中的应用：基于交互式遗传算法； 图像恢复中的应用：对模糊的运动图像进行还原； 智能交通系统简介 智能交通系统 ITS —Intelligent Transportation System 最先进的电子信息技术 实现人员（包括驾驶员和管理者）、公路和车辆三者的密切结合和和谐统一新公路交通系统。 优点： 减少交通拥挤， 加强对车辆 的集中管理和调度， 为驾驶员提供足够的交通、公安、娱乐等信息 提高交通运输效率 保障交通安全 增强行车的舒适性 改善环保质量 提高能源的利用率。 智能交通系统分类 先进的交通管理系统 (ATMS) 控制中心接收到各种交通信息（如车辆检测、交通信号、告警和求助信号）并经过迅速处理后，通过调节交通信号，向驾驶员和管理人员提供实时信息，从而使交通流始终处于最佳状态 信息检测系统 -信息传输系统 -信息处理系统 -信息发布系统 先进的车辆控制系统（AVCS） 辅助在以至替代驾驶员实行控制 先进的驾驶员信息系统（ADIS） 向驾驶员提供路况信息，自动路径规划、导航系统 营运车辆调度管理系统（CVO） 为运输企业提高盈利而开发的智能型营运管理技术 先进的大众运输系统（APTS） 通过个人计算机、闭路电视等向公众就出行的时间和方式、路线以及车次选择等提供咨询，在公共车站通过显示器向乘客提供车辆的实时运行信息等 从2000年到2011年，美国在洛杉矶等地开发了ITS 在洛杉矶市的自动交通检测和控制中心(AXSAC) 计算机系统监控全市的交通状况和系统自身性能;道路上埋设的感应线圈可检测车辆的车速，车流量及道路占用情况，并可在一秒钟内实时修改数据; ATSAC系统的运行平均减少出行者12%的出行时间，32%的交叉路口耽误和30%的不必要停车。 遗传算法在智能交通中的应用 目的：减少一段时间内每辆到达车辆的平均等待时间 手段：参考历史信息和当前路口上下游路口的拥塞来动态地调整路口交通灯的延长时间 实现方法： 调度算法 模糊控制 遗传编程 系统主要通过模糊控制和调度算法来实现对交通的控制 遗传算法的功能就是通过进化生成上面的模糊控制规则表 遗传算法实现的关键技术 染色体的编码方法 一个现有的模糊控制规则表，是一个N×N的矩阵，N为车流模糊量的隶属度，在我们的系统中设置为7，VF(很少)、F(少)、FP(较少)、C(中)、MP(较多)、M(多)、VM(很多) ，对应的等待时间编码为0、1、2、3、4、5、6，这样一个7×7的矩阵就可以转化成一个编码序列。 具体例子如下： 遗传算法在系统中的应用 上面的表格编码所得的结果为：0123456 0123456 0123455 0123345 0123344 0112234 0011223。编码长度为7 ×7 = 49 位。 遗传算法在系统中的应用 适应度函数的确定－平均等待时间   在路口的模型中，假设有8个车道。每个车道要分别计算，需要假设各个车道的流出速率。  对于某个车道，如果是绿灯结束的情况： a若上次剩下的车全部离开，又因为是以匀速离开，则在本次绿灯时间内的的等待时间为：上次剩下的车辆数×离开时间÷2。【新来的车可以不考虑】 b 若上次剩下的车没有走完，则在本次绿灯时间内的等待时间为：离开的车辆数×本次绿灯时间÷2＋（新来的车辆＋没有走的车辆）×本次绿灯时间。  遗传算法在系统中的应用 对于某个车道，如果是红灯结束的情况：  在本次红灯时间内的等待时间为：（红灯开始时候已经在等待的车辆＋红灯时间内到来的车辆）×本次红灯时间。 注意点： 左转的车道和直行的车道拥有不一样的流出速度，一般来说直行的车要比左转的快一些。 遗传算法在系统中的应用 遗传算法的参数设置 初始种群的产生　初始化种群时，为了保证每个基因都存在于第一代的个体中，人为地制定一条染色体m_genes[i] = i / 7，其余的popnum-1条染色体由随机产生，必须保证满足每个基因的基因型在0到6之间。 交叉　个体按照交叉概率Pc=80%进行杂交。交叉采用均匀杂交，随机产生与染色体等长的二进制杂交模板，0 表示对应位不交换，1 表示交换。然后根据模板对两个父代施行杂交，产生两个后代。均匀杂交能搜索到点式杂交无法搜索到的模式，比较适合用于较小的群体规模。而点式交叉搜索到的模式比较少，在群体规模较小时，其搜索能力将受到一定的影响。 遗传算法在系统中的应用 变异　个体按照变异概率Pm=20％进行变异，而被选中的个体的每位基因又按照5％的概率进行变异。 变异时候需要注意不能超出编码的范围。 新一代个体的产生　在对一代个体进行交叉和变异操作之后，生成一个数目比初始种群数目大的种群。对于该种群每条染色体计算其适应度，并按照适应度大小将所有染色体排列，并取最大的种群数目个作为下一代的种群。 遗传算法在系统中的应用 其他参数的设置  主要影响遗传算法的运行时间。 种群规模popNum; 进化代数generationNum; 计算适应度函数时的模拟运行时间 totalTime; 计算适应度函数时的模拟运行次数 runTime; 交叉概率crossRate; 变异概率mutateRate; 个体基因的变异概率Genome.m_mutationrate; 染色体长度genomeLength; 每个基因的取值范围genomeRange; 相关测试 遗传算法的主要特点 智能性 遗传算法具有自组织、自适应和自学习等特性。 灵活的个体编码 灵活的个体编码使遗传算法可直接对结构对象进行描述和操作。 多点搜索能力 遗传算法是同时对多个解进行处理、评估，并行地爬多个峰。这一特点使遗传算法具有较好的全局搜索能力，减少了陷于局部优解的风险。 并行性 遗传算法是内在并行的。演化计算适合在并行机或分布式系统中做大规模的并行处理。 遗传算法是内含并行性的。由于遗传算法采用种群的方式组织搜索，从而可同时搜索空间内的多个区域，并相互交流信息 . 常见启发式算法 禁忌搜索（tabu search） 模拟退火（simulated annealing） 遗传算法（genetic algorithms） 蚂蚁算法（Ant Algorithm） 粒子群算法(Particle Swarm Optimization) 群智能算法研究背景 蚁群算法原理 自然蚁群与人工蚁群算法 粒子群优化 粒子群优化(Particle Swarm Optimization, PSO) PSO算法是由Kennedy和Eberhart博士于1995年提出 PSO算法起源于对鸟群、鱼群的模拟 PSO算法也借鉴了社会交互的概念，并将其应用于问题的解决  

相关PPT