【人工智能_人工智能原理与应用】第七章遗传算法

第 7章 遗传算法 7.1 遗传算法简介 7.2 基本遗传算法 7.3 函数优化 7.4 旅行商问题 7.1 遗传算法简介 7.1.1 遗传算法的起源 n 自然界所提供的答案是经过漫长的自适应 遗传 过程获得的结果。 n 我们也可以利用这一过程本身去解决一些复杂的问 题。 n 遗传算法的研究主要集中在以下几个方面：函数优 化、组合优化生产调度、自动控制、机器人学、图 像处理、人工生命、演化编程和机器学习。 7.1.2 设计遗传算法的基本原则 n 适应性原则 n 可靠性原则 n 收敛性原则 n 稳定性原则 n 生物类比原则 7.1.3 设计遗传算法的基本步骤 n 确定编码方案 n 选择何种编码表示有时对算法的性能、效率等产生很大的 影响。 n 确定适应函数 n 解的适应值是演化过程中进行选择的唯一依据。 n 选择策略的确定 n 优胜劣汰的选择机制使得适应值大的解有较高的存活率， 这是遗传算法与一般搜索算法的主要区别之一。 n 控制参数的选取 n 遗传算子的设计 n 主要包括繁殖、杂交、变异以及其它高级操作。 7.1.3 设计遗传算法的基本步骤 procedure genetic program begin initialize /种群初始化 evaluate /评价种群 while ( not termination-condition) do begin select from /选择个体到下一种群 alter /对种群进行遗传操作 evaluate end end 7.1.4 遗传算法的主要特点 n 智能性 n 遗传算法具有自组织、自适应和自学习等特性。 n 灵活的个体编码 n 灵活的个体编码使遗传算法可直接对结构对象进行描述和 操作。 n 多点搜索能力 n 遗传算法是同时对多个解进行处理、评估，并行地爬多个 峰。这一特点使遗传算法具有较好的全局搜索能力，减少 了陷于局部优解的风险。 7.1.4 遗传算法的主要特点 n 并行性 n 遗传算法是内在并行的。演化计算适合在并行机或分布式 系统中做大规模的并行处理。 n 遗传算法是内含并行性的。由于遗传算法采用种群的方式 组织搜索，从而可同时搜索空间内的多个区域，并相互交 流信息 . 7.1.5 遗传算法的研究内容和应用前景 n 算法的理论模型研究 n 优化求解方法的研究 n 学习系统的遗传算法研究 n 新的进化模型 n 遗传算法的并行分布式处理 n 遗传算法的应用系统 n 演化硬件 7.2 基本遗传算法 7.2.1 编码表示 n 位串编码 二进制编码即是将原问题的解空间映射到位串空 间 上，然后在位串空间上进行遗传操作。 l 优点 l 算法易于用生物遗传理论来解释并使得遗传操作（如杂 交、变异等）很容易实现 l 采用二进制编码时，算法处理的模式数最多 l 缺点 l 相邻整数的二进制编码可能具有较大的 Hamming距离 l 二进制编码时，一般要先给出求解的精度以确定串长 l 在求解高维优化问题时，二进制编码串将非常之长 7.2.1 编码表示 n 实数编码 l 对于问题的变量是实向量的情形，可以直接采用实进制进 行编码。这样，便可直接在解的表现型上进行遗传操作。 从而便于引入与问题领域相关的启发信息以增加遗传算法 的搜索能力。 n 有序串编码 l 目标函数的值不仅与表示解的字符串中各字符的值有关， 而且与其所在字符串的位置有关。这样的问题称为有序问 题。 l 需要针对具体问题专门设计有效且能保证后代合法的遗传 算子。 l 这类编码方案较多地使用在组合优化问题之中。 7.2.1 编码表示 n 结构式编码 l 将问题的解表示树或图的形式的编码称为结构式编码。 l 因为遗传算子是直接在解的表现型上进行操作，这样使得 我们比较容易加入与领域有关的知识和一些启发式的信息 。 7.2.2 适应性的度量 个体的适应值即是它繁殖的能力，它将直接关 系到其后代的数量，在遗传算法中，适应函数是用 来区分群体中个体好坏的标准，是算法演化过程的 驱动力，同时也是进行自然选择的唯一依据。 n 原始适应函数 l 原始适应函数是问题求解目标的直接表示，通常采用问题 的目标函数作为个体的适应度量 。 l 定义原始适应函数的方法可能不止一种，选择时要尽量反 映问题本身整体特性，而不能只追求片面的目标 。 7.2.2 适应性的度量 n 标准适应函数 l 适应值会出现两种情形，一是极小情形即原始适应值越小 个体性能越好；另一种是极大化情形即原始适应值越大个 体性能越好 。 l 遗传算法中的某些选择策略则要求适应函数是非负的，而 且适应值越大表明个体的性能越好。 l 对于极小化情形，标准适应值可定义为 ： n 适应值的调节 l 存在问题：过早收敛、停滞现象 l 改变算法性能的方法之一是对适应值进行调节，即通过变 换，改变原适应值的比例关系。 7.2.3 选择策略 n 不同的选择策略将导致不同的选择压力，即下一代 中父代个体的复制数目的不同分配关系。 n 转盘式选择 l 转盘式选择是基于适应值比例的选择中比较重要的选择策 略。 l 先计算个体的相对适应值 ，即 l 根据选择概率 把一个圆盘分成 N份 l 生成一个内的随机数 r，若 ， 则选择个 体 i 7.2.3 选择策略 n 基于排名的选择 l 首先根据个体 的适应值在群体中的排名来分配其选择 概率 。 l 根据这个概率使用转盘选择 l 线性排名选择 l 线性排名选择方法是按适应值大小从好到坏依次排列为 ，然后根据一个线性函数分配选择概率 。 7.2.3 选择策略 n 非线性排名选择 l 首先按适应值从好到坏依次排列群体成员，并按非线性函 数分配选择概率 。 7.2.4 遗传算子的设计 n 杂交算子 l 杂交运算是指对两个相互配对的染色体按某种方式相互交 换其部分基因，从而形成两个新的个体。 l 单点杂交 单点杂交又称为简单杂交，它是指在个体编码串 中只随机设计一个杂交点，然后在该点相互交换两个 配对个体的部分染色体。 7.2.4 遗传算子的设计 n 双点杂交与多点杂交 n 双点杂交是指在个体编码串中设置了二个杂交点，然 后再进行部分基因交换。 7.2.4 遗传算子的设计 n 均匀杂交 l 均匀杂交是指两个配对个体每一个基因座上的基因都 以相同的杂交概率进行交换，从而形成两个新的个体 。 l 均匀杂交实际上可归属于多点杂交的范围 . l 算术杂交 l 算术杂交是由两个个体的线性组合而产生出两个新的 个体。 l 为了能够进行线性组合运算，算术杂交的操作对象一 般是浮点数所表示的个体。 7.2.4 遗传算子的设计 n 变异算子 l 变异运算是指将个体染色体编码串中的某些基因座上的基 因值用该基因座的其它等为基因来替换，从而形成一个新 的个体。 l 遗传算法中使用变异算子主要有以下两个目的： l 1）改善遗传算法的局部搜索能力。 l 2）维持群体的多样性，防止出现早熟现象。 7.2.4 遗传算子的设计 n 基本位变异 l 对个体的每一个基因座，依变异概率 指定其为变 异点。 l 对每一个指定的变异点，对其基因值做取反运算或用 其他等位基因值来代替，从而产生出一个新的个体。 l 均匀变异 n 依次指定个体编码串中的每个基因座为变异点。 n 对每一个变异点，以变异概率 从对应基因的取值 范围内取一随机数来替代原有基因值。 7.2.4 遗传算子的设计 n 非均匀变异 l 非均匀变异的具体操作过程与均匀变异相类似，但它重点 搜索原个体附近的微小区域。 7.3 函数优化 n 优化技术是一种以数学为基础，用于求解各种工程 问题优化解的应用技术 . n 最优化问题可分为函数优化问题和组合优化问题两 大类，其中函数优化的对象是一定区间内的连续变 量，而组合优化的对象则是解空间中的离散状态。 n 所有的搜索、优化都是对目标函数的 “函数 ”优化。 n 近年来，遗传算法作为一种全新的优化方法，其巨 大的潜力受到越来越多学者的重视。 7.3.1 问题描述 n 全局最大化 : 对于 ，寻求点 ，都 有 n 全局最小化：对于 ，寻求点 ，都 有 n 不论待求解问题是求最大值还是求最小值问题，我们可将待 求解的问题一律看成求解最大值问题。 n 转化方法如下：如果优化问题是就函数 的最小值，它等同 与求函数 的最大值，其中 ，即 7.3.1 问题描述 n 目标函数 在其值域里只取正值，若为负，可通 过加入某个正数 C 使之为正，即 7.3.2 种群的初始化 n 对于函数优化来说，在初始化过程中需在上、下限 区间内产生随机数，并将这个随机数赋给变量 。 7.3.3 选择策略 n 在选择策略上，本例采用基于概率的轮转盘选择策 略。计算出群体的总适应值 n 对每个个体 ，选择概率 ，显然 。 n 每个个体 的累积概率 ，我们 可得知 且 。 7.3.4 遗传算子 n 杂交算子 n 对新群体中的每个个体产生一个在 0,1区间内产生随机 浮点数； n 如果 ，随机地选择个体配对，然后进行杂交操作 。若个体中有 n个分量，在 1,n区间中产生随机整数 pos ， pos表示杂交点的位置。 n 若两个个体分别为： 在 pos点杂交后产生子代 7.3.4 遗传算子 n 算法的程序描述如下： /在 0,1区间产生随机数 /判断随机数是否小于杂交概率 /进行杂交操作 7.3.4 遗传算子 /杂交点，即第几个分量进行相互交换 /在 n个分量中，随机确定第 pos个分量 进行相互交换 /前 pos个分量进行相互交换 7.3.4 遗传算子 n 变异算子 l 变异就是以很小的概率 随机地改变群体中个体 (染色体 ) 的某些基因的值。 l 具体算法的描述如下： /在 0,1区 间产生随机数 /判断随机数是否小于变异概率 /为第 i个个体的 j变量进行变异 操作 7.4 旅行商问题 7.4.1 旅行商问题的描述 n 已知 n个城市之间的距离，现有一推销员必须访问这 n个城市，并且每个城市只能访问一次，最后必须返 回出发城市。如何安排他对这些城市的访问次序， 可使其旅行路线的总长最短。 n 旅行商问题可分为对称旅行商问题和非对称旅行商 问题。 n TSP问题求解的研究工作主要集中在以下几个方面 ： n 采用适当的表示方法表示个体的编码； n 设计可用的遗传算子，以爆出父代的特性避免新个体的不 可行性； n 防止算法过早的收敛。 7.4.2 个体的编码表示 n TSP问题的个体编码表示方法大致可分为两大类： n 在巡回旅行路线所经过的城市序列； n 各城市在巡回旅行路线中的邻接关系。 n 近邻表示 n 近邻表示方法将路径表示成 n个城市的一个排列，若排列 中的第 i位为城市，当且仅当路径中从城市 i所到达的下一 个城市为 j。 n 次序表示 l 表示方法为：先取城市集合 C的顺序排列如 C=（ 1 2 3 4 5 6 7 8 9）作为次序排列的一个参照点，然后按路径中 城市处在 C的位置确定表示串中的点，且每确定一个则从 C中删除相应的城市。 7.4.2 个体的编码表示 n 路径表示 l 路径表示可能是 TSP问题最自然、最直接的表示方式。它 直接采用城市在路径中的相对位置来进行表示。 l 例如，路径 51786293 4直接表示成（ 5 1 7 8 6 2 9 3 4） 7.4.3 杂交算子 n 部分映射杂交 l 首先随机地在父体中选取两个杂交点，并交换相应的段， 再根据该段内的城市确定部分映射。在每个父体上先填入 无冲突的城市，而对有冲突的城市依照映射关系选择候选 的城市，直到找到无冲突的城市填入，按此方法获得了杂 交后的两个后代。 l 次序杂交 l 首先随机地在父体中选择两个杂交点，再交换杂交段，其 它位置根据保持父体中城市的相对次序来确定。 7.4.3 杂交算子 n 循环杂交 n 循环杂交的步骤如下： n 根据双亲相对应的城市位置设计出一个循环链； n 把一个双亲的已在循环上的城市复制到一个后代上； n 删去另一个双亲已在循环链上的城市，剩下的城市组成一 序列； n 将 3）步的序列从左到右依次填满后代空缺的位置。 7.4.3 杂交算子 n 基于位置的杂交 n 步骤 : n从一个双亲上随机选取一些杂交点； n将第一个双亲的这些杂交点复制到一个空字符串的相 应位置，产生一个后代； n删去第二个双亲上已有的城市，剩下的城市构成了一 个新的序列； n将 3）步中所得到的新序列，从左到右依次插入到后代 空缺的位置上 7.4.4 变异算子 n 倒置变异 l 利用简单的倒置操作来进行变异。即首先在父体中随机地 选择两个截断点，然后将