遗传算法与蚁群算法简介.ppt

遗传算法与群智能优化算法简介 主要内容 智能优化算法简介问题的NP 完全特性常用的智能优化算法遗传算法 GeneticAlgorithm群智能优化算法蚁群优化算法 AntColonyOptimization粒子群优化算法 ParticleSwarmOptimization 北京交通大学计算机与信息技术学院 2 2020 3 26 智能优化算法简介 20世纪80年代以来 一些优化算法得到发展GA EP ACO PSO SA TS ANN及混合的优化策略等基本思想 模拟或揭示某些自然现象或过程为用传统的优化方法难以解决的NP 完全问题提供了有效的解决途径由于算法构造的直观性与自然机理 因而通常被称作智能优化算法 intelligentoptimizationalgorithms 或现代启发式算法 meta heuristicalgorithms 智能优化算法及其应用 王凌 清华大学出版社 2001 北京交通大学计算机与信息技术学院 3 2020 3 26 智能优化算法简介 问题的NP 完全特性 求解n个城市的TSP问题 典型的组合优化问题 是NP 完全的要准确求解该问题只能用枚举类的办法要枚举的解的个数为 n 1 例 n 24 则要枚举的解的个数为 23 25 852 016 738 884 976 640 000 北京交通大学计算机与信息技术学院 4 2020 3 26 1s 24s 10m 4 3h 4 9d 136 5d 10 8y 325y 北京交通大学计算机与信息技术学院 5 2020 3 26 北京交通大学计算机与信息技术学院 6 2020 3 26 北京交通大学计算机与信息技术学院 7 2020 3 26 智能优化算法简介 常用的智能优化算法 遗传算法 GeneticAlgorithm GA 演化规划 EvolutionaryProgramming EP 蚁群优化算法 AntColonyOptimization ACO 粒子群优化算法 ParticleSwarmOptimization PSO 模拟退火算法 SimulatedAnnealing SA 禁忌搜索算法 TabuSearch TS 人工神经网络 ArtificialNeuralNetwork ANN 北京交通大学计算机与信息技术学院 8 2020 3 26 主要内容 智能优化算法简介问题的NP 完全特性常用的智能优化算法遗传算法 GeneticAlgorithm群智能优化算法蚁群优化算法 AntColonyOptimization粒子群优化算法 ParticleSwarmOptimization 北京交通大学计算机与信息技术学院 9 2020 3 26 遗传算法 GeneticAlgorithm 1975年 Holland出版了著名的 AdaptationinNaturalandArtificialSystems 标志着遗传算法的诞生 在一定程度上解决了传统的基于符号处理机制的人工智能方法在知识表示 信息处理和解决组合爆炸等方面所遇到的困难基于 适者生存 原则 是并行优化算法 其自组织 自适应 自学习及群体进化的能力适合大规模复杂优化问题将问题求解表示为 染色体 通过选择 selection 交叉 crossover 和变异 mutation 操作的迭代 实现种群的演化 最后终收敛到 最适应环境 的个体 从而求得问题的最优解 满意解 北京交通大学计算机与信息技术学院 10 2020 3 26 遗传算法 简单遗传算法 简单遗传算法 SimpleGeneticAlgorithms SGA 又称基本遗传算法 标准遗传算法基于二进制编码 是最基本的遗传算法 其遗传进化操作过程简单 容易理解 是其他遗传算法的雏形和基础三种基本操作选择 通常用比例选择 即选择概率正比于个体的适配值 使适配值高的个体在下一代中被选中的概率大 提高种群平均适配值交叉 交换两父代个体的部分信息构成后代个体 使得后代继承父代的有效模式 有助于产生优良个体变异 随机改变个体中的某些基因 有助于增加种群多样性 避免早熟收敛 北京交通大学计算机与信息技术学院 11 2020 3 26 北京交通大学计算机与信息技术学院 12 2020 3 26 随机产生N个个体构成初始种群P 0 令k 0 对种群P k 中各个体进行评价 终止 令m 0 从种群中选择两个体 rand pc 将所选个体作为临时个体 对临时个体以概率pm执行变异操作 产生两个新个体并放入P k 1 中 令m m 2 对选中个体执行交叉操作生成两个临时个体 输出优化结果 m N y n y n y n 遗传算法 选择 适者生存 适应值高的个体的生存概率大 即被选中用来繁殖下一代的概率大 常用的选择方法有 比例选择 轮盘选择 基于排名的选择 由好到坏排序 然后以一定方式给每一个体分配选择概率 线性 非线性等方式 要求好的个体被选择的概率大 所有个体所分配的概率之和为1 锦标赛选择 在父代个体随机选k个 然后选最好的 北京交通大学计算机与信息技术学院 13 2020 3 26 适应值 第i个个体的选择概率 产生随机数 选择满足下式的第i个个体 遗传算法 交叉 用于组合出新的个体 在解空间中进行有效搜索 同时降低对有效模式的破坏概率二进制编码的GA通常采用单点交叉和多点交叉 单点交叉 随机选定一个交叉位置 然后对换交叉点后的子串 多点交叉 随机选择多个位置 然后对换相应子串 两点交叉 北京交通大学计算机与信息技术学院 14 2020 3 26 1011 0010 001 110 1011 0010 001 110 10 01 110 00 10 101 10 01 110 00 10 101 遗传算法 交叉 续 实数编码的GA通常采用算术交叉 双个体算术交叉 x1 x2为父代个体 0 1 为随机数x1 x1 1 x2x2 x2 1 x1多个体算术交叉 x1 x2为父代个体 i 0 1 且 i 1x 1x1 2x2 nxn组合优化中的置换编码GA通常采用部分映射交叉 partiallymappingcrossover PMX 随机选择两个交叉点 交换交叉点之间的片段 对于其他基因 若它不与换过来的片段冲突则保留 若冲突则通过部分映射来确定最后的基因p1 264 7358 91 p1 234 1876 95 p2 452 1876 93 p2 412 7358 96 北京交通大学计算机与信息技术学院 15 2020 3 26 遗传算法 交叉 续 Non ABEL交叉 p1 i p1 p2 i p2 i p2 p1 i p1 264735891 p1 736298514 p2 452187693 p2 571628934 Non ABEL群置换操作产生后代方式简单 过分打乱了父串 不利于保留有效模式次序交叉 OX 首先随机确定两个交叉位置 并交换交叉点之间的片段 并从第2交叉位置起在原先父代个体中删除将从另一父代个体交换过来的基因 然后从第2交叉位置后开始填入剩余基因 p1 264 7358 91 p2 452 1876 93 北京交通大学计算机与信息技术学院 16 2020 3 26 264 7358 91 452 1876 93 p1 435 1876 92 p2 216 7358 94 遗传算法 交叉 续 单位置次序交叉 C1 类似于OX 选择一个交叉位置 保留父代个体p1交叉位置前的基因 并在另一父代个体p2中删除p1中保留的基因 将剩余基因填入p1的交叉位置后来产生后代个体p1 如父代个体同前 交叉位置为4 则后代个体为p1 2647 51893 p2 4521 67389 线性次序交叉 LOX 与OX相比 仅填入基因起始位置不同 首先随机确定两个交叉位置 并交换交叉点之间的片段 在原先父代中删除将从另一父代个体交换过来的基因 然后从第1个基因位置起依次在两个交叉位置外填入剩余基因 如父代个体和交叉点同前 则片段 7358 和 1876 将交换 在p1中删除 1876 后剩余 24359 然后将其填入p1 得到 243 1876 59 相应地p2 421 7358 69 北京交通大学计算机与信息技术学院 17 2020 3 26 遗传算法 交叉 续 基于位置的交叉 PX 与OX类似 只是它不再选取连续的基因片段 而是随机选取一些位置 然后交换被选中位置上的基因 并在原先父代个体中删除从另一父代个体交换过来的基因 接着从第一个基因位置起依次在未选中位置填入剩余基因 如父代个体同前 假设随机选取的位置点为2 3 6 8 则后代为p1 652437891 p2 264185793 循环交叉 CX 北京交通大学计算机与信息技术学院 18 2020 3 26 遗传算法 变异 二进制或十进制用另一种基因替换某一位置或某些位置上的基因实数编码采用扰动的方式 x x 其中 为扰动幅度 为扰动变量组合优化互换 逆序 插入等 北京交通大学计算机与信息技术学院 19 2020 3 26 遗传算法 函数优化示例 求整数函数f x x2在区间 0 31 上取最大值的点用基本遗传算法求解问题是求最大值点 目标函数可取为x2 用5位的二进制位串表示个体 对应区间 0 31 上的32个整数 随机地选取4个位串作为初始种群 位串与对应的整数如下 011011311000240100081001119 北京交通大学计算机与信息技术学院 20 2020 3 26 根据目标函数 对每个位串计算适值为每个位串指定一个与其适应值成正比的繁殖概率根据遗传操作生成下一代种群假设选择的两对父代个体分别为1和2 2和4 北京交通大学计算机与信息技术学院 21 2020 3 26 交叉过程 假设使用单点交叉 交叉概率pc 0 95 位串1 2 011 01011 00110 00110 01位串2 4 110 00110 11100 11100 00变异过程 假设变异概率pm 0 05 且此处无变异 评价第二代种群 北京交通大学计算机与信息技术学院 22 2020 3 26 遗传算法 数学解释 Holland为解释基于二进制编码的基本遗传算法建立了模式定理和隐含并行性定理模式定理的含义 在SGA中 阶次低 定义长度短且适配值超过平均适配值的模式在种群中的数目的期望值以指数级递增 遗传算法存在找到全局最优解的可能性 隐含并行性定理 遗传算法所处理的有效模式的总数约与群体规模的三次方成正比积木块假设的含义 通过短定义距 低阶及高平均适应度的模式 积木块 在遗传操作下相互结合 最终接近全局最优解 说明在遗传算子的作用下能生成全局最优解 北京交通大学计算机与信息技术学院 23 2020 3 26 遗传算法 改进 编码方式的改进二进制编码使得个体串很长 特别是精度要求较高的时候 根据需要采用格雷编码 浮点数编码 自然数编码等对遗传操作的改进改进选择策略 交叉算子 变异算子对控制参数的自适应调整 如自适应调整交叉概率和变异概率等对执行策略的改进混合遗传算法 小生境技术 免疫遗传算法 单亲遗传算法 并行遗传算法 北京交通大学计算机与信息技术学院 24 2020 3 26 遗传算法 欺骗问题 完全欺骗问题一致欺骗问题序列欺骗问题基本欺骗问题具体请参考 李敏强 寇纪淞 遗传算法的模式欺骗性分析 中国科学 E辑 2002 32 1 95 102 北京交通大学计算机与信息技术学院 25 2020 3 26 遗传算法 欺骗问题举例 设编码空间 0 1 3上的最优解位串为 11l 若模式适应值满足 f 0 f 1 f 00 f 11 f 01 f 10 f 0 f 1 f 0 0 f 1 1 f 0 1 f 1 0 f 0 f 1 f 00 f 11 f 01 f 10 即竞争力强的低阶模式的有效基因位为 0 那么该类模式在群体中的数量将按指数增长 包含 0 的1 2阶模式使GA搜索偏离最优解 就形成了3阶模式欺骗问题 北京交通大学计算机与信息技术学院 26 2020 3 26 遗传算法 主要特点 处理参数集合的编码 而不是参数本身始终保持整个种群而不是个体的进化 即使某个体在某时刻丢失了有用的特性 这种特性也会被其它个体保留并发展下去只需要知道问题本身所具有的目标函数的信息 且不受连续 可微等条件的约束 因而具有广泛的适用性启发式搜索 可适用于有噪声和多峰值的复杂空间 北京交通大学计算机与信息技术学院 27 2020 3 26 主要内容 智能优化算法简介问题的NP 完全特性常用的智能优化算法遗传算法 GeneticAlgorithm群智能优化算法蚁群优化算法 AntColonyOptimization粒子群优化算法 ParticleSwarmOptimization 北京交通大学计算机与信息技术学院 28 2020 3 26 群智能优化算法 群智能优化算法是一种近年来新兴的优化方法 其模拟社会性动物的各种群体行为 利用群体中个体间的信息交互和合作来实现寻优目的群智能优化算法包括很多算法 如人工蜂群算法和人工鱼群算法等 不过研究比较深入 应用比较广泛的是蚁群优化算法和粒子群优化算法 也有人将遗传算法和差分演化算法 DifferentialEvolutionAlgorithm 归入群智能优化算法中 北京交通大学计算机与信息技术学院 29 2020 3 26 与基于梯度的优化算法不同 群智能优化算法依靠的是概率搜索 其优点是 无集中控制约束 不会因个别个体而影响整个问题的求解 确保了系统的鲁棒性以非直接的信息交流方式确保了系统的扩展性并行分布式算法模型对问题定义的连续性无特殊要求算法实现简单 北京交通大学计算机与信息技术学院 30 2020 3 26 主要内容 智能优化算法简介问题的NP 完全特性常用的智能优化算法遗传算法 GeneticAlgorithm群智能优化算法蚁群优化算法 AntColonyOptimization粒子群优化算法 ParticleSwarmOptimization 北京交通大学计算机与信息技术学院 31 2020 3 26 蚁群优化算法 AntColonyOptimization 蚁群优化算法 蚂蚁算法 是一种分布式智能模拟算法由M Dorigo于1992年在他的博士论文中提出 其灵感来源于蚂蚁在寻找食物过程中发现路径的行为基本思想是模拟蚂蚁依赖信息素进行通信而显示出的社会行为是一种随机的通用试探法 可用于求解各种不同的组合优化问题初始的蚁群优化算法是基于图的蚁群系统 过程如下 以求解对称的TSP问题为例 北京交通大学计算机与信息技术学院 32 2020 3 26 问题的描述 n个城市N 1 2 n 任两城市的边A i j i j N 城市间的距离为D dij n n设有m只蚂蚁 其出发城市可随机确定路径的构造为TSP图中的每一条弧 i j 赋信息素初值 ij 0 通常的做法是随机生成一个解 设其目标值为f0 则 ij 0 1 f0设置城市间的启发式信息 ij 通常 ij 1 dij设第k只蚂蚁在城市i 则其根据下面的概率选择下一个城市 其中另外 每一蚂蚁有一个表list 用于记录其访问过的城市 当访问了所有的城市后 就可以在其经过的路径上更新信息素 北京交通大学计算机与信息技术学院 33 2020 3 26 与 表示信息素与启发式信息的相对重要程度 通常 1或2 2或3 表示蚂蚁k可选的城市集合 即其还未访问过的城市集合 信息素更新策略 局部更新 所有蚂蚁周游完成后更新信息素 首先以一定的比例 1 减少每条边上的信息素 表示信息素的挥发 然后更新各自路径上的信息素 即更新信息素的方式为其中信息素的挥发机制可以避免信息素大量积累 也体现了生物界的 遗忘 现象 表示蚂蚁k在边 i j 上留下的信息素 如果蚂蚁没有经过该边 则其留下的信息素为0 即其中 表示蚂蚁k构造的路径的长度 Q是一常数 比如1 此机制体现了 构造的路径越短 蚂蚁留下的信息素越多 某边经过的蚂蚁越多 其上积累的信息素也就越多 北京交通大学计算机与信息技术学院 34 2020 3 26 全局更新 对于一次迭代中最好的那只蚂蚁 单独更新其经过路径上的信息素上面的蚁群优化算法的不足信息素的累积造成 停滞 现象 蚂蚁基本上走同一条路径要得到更好的优化能力往往需要与局部搜索算法结合 对最好的路径执行局部搜索蚁群算法的改进精英策略 对已发现的最好路径给予额外的增强 从而增大较好路径的选择概率负反馈机制 蚂蚁走过一条边时 立即减少该边上的信息素 以减少该边再次被选中的概率Max Min蚂蚁系统 将信息素的浓度限制在 min max 的范围内 避免搜索停滞 T Stutzle H Hoos MAX MINAntSystem FGCS 2000 16 889 914 北京交通大学计算机与信息技术学院 35 2020 3 26 蚁群优化算法 较成功的算法 北京交通大学计算机与信息技术学院 36 2020 3 26 蚁群优化算法 较成功的应用 北京交通大学计算机与信息技术学院 37 2020 3 26 蚁群优化算法 较成功的应用 续 北京交通大学计算机与信息技术学院 38 2020 3 26 M Dorigo T Stutzle著 张军等译 蚁群优化 清华大学出版社 2007 主要内容 智能优化算法简介问题的NP 完全特性常用的智能优化算法遗传算法 GeneticAlgorithm群智能优化算法蚁群优化算法 AntColonyOptimization粒子群优化算法 ParticleSwarmOptimization 北京交通大学计算机与信息技术学院 39 2020 3 26 粒子群优化算法 ParticleSwarmOptimization 粒子群优化算法 ParticleSwarmOptimization PSO 也称为微粒群优化算法 是由Kennedy和Eberhart于1995年提出来的所谓粒子是指不考虑群体中的成员的质量和体积 只考虑速度和加速状态 北京交通大学计算机与信息技术学院 40 2020 3 26 设第i个粒子表示为Xi xi1 xi2 xiD 有最好适应值的位置记为Pi pi1 pi2 piD 也称为Pbest 设符号g表示群体中所有粒子经历过的最好位置 也称为gb