进化计算.ppt

1进化算法概述 为什么 进化算法框架基本步骤特点应用 为什么 进化算法框架 基本步骤 1 进化计算是基于自然选择和自然遗传等生物进化机制的一种搜索算法 与普通的搜索方法一样 进化计算也是一种迭代算法 不同的是进化计算在最优解的搜索过程中 一般是从原问题的一组解出发改进到另一组较好的解 再从这组改进的解出发进一步改进 而且在进化问题中 要求当原问题的优化模型建立后 还必须对原问题的解进行编码 进化计算在搜索过程中利用结构化和随机性的信息 使最满足目标的决策获得最大的生存可能 是一种概率型的算法 一般来说 进化计算的求解包括以下几个步骤 给定一组初始解 评价当前这组解的性能 从当前这组解中选择一定数量的解作为迭代后的解的基础 再对其进行操作 得到迭代后的解 若这些解满足要求则停止 否则将这些迭代得到的解作为当前解重新操作 以遗传算法为例 其工作步骤可概括为 基本步骤 2 1 对工作对象 字符串用二进制的0 1字符编码 2 根据字符串的长度L 随即产生L个0 1字符组成初始个体 3 计算适应度 适应度是衡量个体优劣的标志 通常是所研究问题的目标函数 4 通过复制 将优良个体插入下一代新群体中 体现 优胜劣汰 的原则 5 交换字符 产生新个体 交换点的位置是随机决定的 6 对某个字符进行补运算 将字符1变为0 或将0变为1 这是产生新个体的另一种方法 突变字符的位置也是随机决定的 7 遗传算法是一个反复迭代的过程 每次迭代期间 要执行适应度计算 复制 交换 突变等操作 直至满足终止条件 基本步骤 3 伪代码 将其用形式化语言表达 则为 假设 I记为个体 I记为个体空间 适应度函数记为 I R 在第t代 群体P t a1 t a2 t an t 经过复制r reproduction 交换c crossover 及突变m mutation 转换成下一代群体 这里r c m均指宏算子 把旧群体变换为新群体 L I True Flase 记为终止准则 利用上述符号 遗传算法可描述为 t 0initializeP 0 a1 0 a2 0 an 0 while l P t True doevaluateP t a1 t a2 t an t reproduction P t r P t crossover P t c P t mutation P t 1 m P t t t 1 end 2 特点 进化计算是一种具有鲁棒性的方法 能适应不同的环境不同的问题 而且在大多数情况下都能得到比较满意的有效解 对问题的整个参数空间给出一种编码方案 而不是直接对问题的具体参数进行处理不是从某个单一的初始点开始搜索 而是从一组初始点搜索 搜索中用到的是目标函数值的信息 可以不必用到目标函数的导数信息或与具体问题有关的特殊知识 因而进化算法具有广泛的应用性 高度的非线性 易修改性和可并行性 应用 传统最优化进化计算 进化编程 进化学习优化神经网络图像处理 仪器参数优化 工程设计 搜索 规划 等 应用举例 卫星通信星座优化设计VMCK 甚小线性调频键控 调制波形优化基于匹配追踪法的导波检测信号处理信号盲源分离 卫星通信星座优化设计 星座由一群卫星组成 理论上 卫星可以位于任何轨道上 卫星星座设计具有多种优化的目标 例如覆盖率最大化 优化的参数包括有 长半轴 轨道倾角 偏心率 星座轨道面个数 近地点幅角 各轨道面的卫星数 等 VMCK 甚小线性调频键控 调制波形优化 根据VMCK波形及功率谱估计发现 其调制因子与解调性能具有一定的关联度 例如当其等于0 4时 频谱能量更集中一些 且边带抑制性更好 通过选择合适的调制因子 可以在信号解调性能和频带利用率间进行很好的平衡 基于匹配追踪法的导波检测信号处理 匹配追踪法的主要思想是信号的稀疏分解 其是一个迭代过程 每次匹配时从过完备原子库D中选择一个最佳的匹配原子 然后从信号中减去该匹配原子在信号中的占有成分得到剩余量 对剩余量重复进行此过程 直到满足要求时停止 由于原子库的原子数量较大 若采用遍历搜索的方式 其运算速度不能满足应用要求 信号盲源分离 独立分量分析 ICA 是解决盲信号分离的主要方法之一 其基本目标是设置一分离矩阵W 使得观测信号X t 经分离矩阵W输出列向量Y t y1 t y2 t yM t 变换后的Yi t 尽可能的统计独立 2遗传算法 主要发展历史生物学的基本概念和术语基本思想特点应用基本流程有效性适应度及调整有关的几个问题模式定理改进理论研究应用举例 2 1主要发展历史 20世纪50年代和60年代 人工进化系统 研究20世纪60年代初期 I Rechenberg在物体形状的参数优化随后 L J Fogel等在有限态自动机设计中提出了进化规划60年代中期 Holland等提出了位串编码技术 交叉作为主要遗传操作 DeJong将其用于最优化问题1989年 Goldberg著第一本全面分析著作1992年 Mkhalewiez出版了另外一本关于遗传算法与数据结构的著作 2 2生物学的基本概念和术语 染色体个体脱氧核糖核酸种群核糖核酸进化遗传因子适应度遗传子型选择表现型复制基因座交叉变异编码解码 2 3基本思想 100111001110 100011011101 101111001010 110101001110 100101000110 100111011101 100011001110 100110011101 遗传算法的流程图 产生初始种群 计算适应度 是否满足优化准则 最佳个体 结束 开始 选择 交叉 变异 2 4特点 自组织 自适应和自学习性 智能性 本质并行性不需要求导或其它辅助知识 而只需要影响搜索方向的目标函数和相应的适应度函数强调概率转换规则 而不是确定的转换规则可以更加直接的应用对给定问题 可以产生许多的潜在解 最终选择可以由使用者确定 在某些特殊情况下 如多目标优化问题不止一个解存在 则有一组最优解 这种遗传算法对于确认可替代解集而言是特别合适的 2 5应用 函数优化组合优化生产调度自动控制机器人智能控制图像处理和模式识别人工生命遗传程序设计机器学习 2 6基本流程 初始化种群遗传操作选择交叉变异结束条件 终止条件 起始 随机生成初始种群 评价 结束条件 结束 GA操作 选择 交叉 变异 评价 Y N 2 6 1初始化 二进制编码随机数的生成字符串长度的计算十进制编码二进制和十进制的转换 2 6 2选择 轮盘赌法期待值法两两竞争法保留最优个体法 轮盘赌 fi为个体的适应度 fsum为种群的总适应度 pi为个体i的选择概率 1 2 3 4 5 6 7 8 轮盘赌选择的步骤 在第t代 设种群为P1 由前式分别求pi与fsum 产生 0 1 的随机数rand 求s rand fsum求中最小的k 则k个个体被选中 进行N次步骤 2 3 的操作 得到N个个体 成为第t t 1代的种群P2 期待值法 轮盘赌法变形 将期待值vi四舍五入 得到个体i被选择的次数ni 从而种群由P1成为P2 期待值法 举例 两两竞争法 每次随机地在种群P1中取两个个体 选择适应度大的个体 若两者相同 只取一 直到选出的个体数为N 得到种群P2 竞争法 推广 网状和环状 保留最优个体法 精英保留 保留最优个体法是将一代适应度f高的个体不进行交叉 变异操作 直接保留到下一代中 2 6 3交叉 是将选择后的种群P2中的个体放入交配池配对 按照选定的交叉方式及确定的交叉概率pc 把成对个体的基因部分的交换 形成一对子代 可见交叉后会生成新的个体 分类 一点交叉 多点交叉 均匀交叉 一点交叉 实例 00011101 10010010 00010010 10011101 一点交叉 29 146 18 157 多点交叉 将一对父代个体的基因链随机地多点切断 二者位置相同 部分交换重组后产生一对新个体 成为子代 均匀交叉 变异 突然变异单点变异与多点变异动态与静态变异 2 6 4突然变异 100111011101 100110011101 100111011101 101110011101 2 7有效性 交叉能继承父代优良的品质变异能摆脱交叉无法跳出的超平面群体搜索策略比一点搜索寻优好 它突破了邻域搜索的限制 可以在整个解空间上采集信息并搜索解 100110011101 100110011101 100110011101 100110111101 2 8适应度及调整 适应度变换适应度调整 适应度变换 1 对于极小值问题 式中 Cmax或是输入的参数 或是理论上z x 的最大值 但一般理论上z x 的最大值是未知的 适应度变换 2 对于极大值问题 式中 Cmin或是输入的参数 或是理论上z x 的最大值 但一般理论上z x 的最大值是未知的 适应度调整 1 线性调整式中a b为常系数 适应度调整 2 预处理 适应度调整 3 乘幂调整 2 9几个问题 SGA的参数编码原则约束问题终止条件GA的特点SGA的不足 SGA的参数 种群规模 N 20 150交叉概率 pc 0 5 1变异概率 pm 0 001 0 05串长度 L 由待求解问题要求解的精度确定迭代结束的代数 T 与以上参数 编码方式等有关 编码原则 选择使问题得以自然表达的符号串进行编码 也就是要与求解问题的特征有关 应使确定规模的种群中包括尽可能多的模式 约束问题 当前主要有3种方法 1 编码时考虑约束 使个体译码后的解始终是可行解2 编码时不考虑约束 运算过程中保留可行解 去除不可行解 3 惩罚方法 即对于不可行解 使其适应度减小作为惩罚 进入种群后 随着迭代运算 不可行解逐渐减少 以求得最优解 终止条件 起初是由设置的迭代终了的代数T为终止条件 改进方法是设定某种判别标准 常用的是使连续几代种群的平均适应度不超过某一阈值等 GA的特点 1 不是一点搜索 而是在群体中一代一代搜索 取得最优解或准最优解 2 是对积木块操作 是在群体中并行进行的 这就是其内在的并行性 3 运用随机搜索技术 对所需求解的问题无连续性和可微性要求 4 迭代过程模拟了生物的遗传和进化过程 与达尔文生物进化论所述 适者生存 优胜劣汰 是一致的 SGA的不足 1 早期收敛2 变异虽可以使陷入某一超平面的个体得以解脱 但由于是随机的 因此不能有效的保证这一问题的解决 3 微调能力差 4 GA参数的选择问题 5 模式定理是SGA的理论基础 但只适用于 0 1 二进制编码 2 10模式定理 模式也称积木块 buildingblock 是描述位串子集的相似性模板 表示基因串中某些特征位相同的结构 如以下位串及适应度 2 10 1模式 模式在 0 1 上定义 其中 可为 0 或 1 设H表示模式 其表达式为 H 10 00 设O H 表示模式的位数 是H中有定义的非 位的个数 称为H模式的阶 表示模式的定义长度 是H中最两端有定义的基因座之间的距离 称为模式H的距 它们是分析位串的相似性 SGA的3个基本算子对模式影像的基本手段 举例 某位串A 101001 长度L 6 列出其中包含的3个模式及其阶与距 模式H1 01 1001 10 模式H的阶342模式H的距531对于长度为L的位串 所含的模式数是个 若种群规模为N 则具有的模式数在之间 具体取决于位串的多样性 2 10 2基本算子对模式的影响 选择交叉变异 选择 交叉 变异 模式定理 在3个遗传算子 选择 交叉 变异 作用下 定义长度短的 确定位数少的 平均适应度高的模式的数量 将随着迭代次数的增加呈指数增长 可见 GA是通过在种群中迭代运算 使高质量的模式得以组合 从而求得高质量的个体的 这就是GA高效搜索的原因 2 11改进 交叉 变异概率的自适应调整高级算子并行GA可变长个体与MessyGA基于小生境技术的GA混合GA导入年龄结构的GA基于基因分布评价的适应度调整GA相关理论研究 2 11 1交叉 变异概率的自适应调整 2 11 2高级算子 逆算子对等交叉法静态繁殖本地算子 逆算子 也称倒位算子 其操作是在一个个体的长度方向上选两个切断点 两点之间的基因倒位后再接起来 成为新的个体 经常将逆算子与交叉相结合进行操作 下图为在4567号基因座上倒位 10010101 10001011 逆算子 对等交叉法 两个个体上的基因完全对等时 才可进行交叉 例如 有3个个体A B和C A 11001 B 00110 C 10011由于A B的基因完全对等 因此可进行交叉 而A C和B C都不能 静态繁殖 SGA是用子代取代父代 静态繁殖 steadystatereproduction 是在迭代过程中用部分优质子串来更新部分父串 这需要合理确定更新的数量 本地算子 自然界中相距遥远的 种类相似的生物并非一起繁殖 本地的才有机会 为了维持多样性 本地算子采取了两项措施 1 采用一种共享机制 限制一些个体快速扩张 2 为了维持一些个体的存在 应有选择地进行交配 即交叉受限 2 11 3并行GA 岛模型近旁模型 岛模型 属于PGA ParallelGA 模型的一种 是把种群分成多个子群 在多台计算机上进行并行且独立的GA操作 同时 不同部分的子群之间可进行个体交换 将其称为迁移 若任意子群均可有个体迁移 则称为飞石模型 stepping stonemodel 岛模型的迁移 需确定如下几个问题 1 哪些子群间可以迁移 2 迁移个体的选择及迁移的个体数 3 经几代可迁移 近旁模型 属PGA型 是指在种群内的各个个体仅与限定的近旁的个体相互作用 进行GA操作 因此操作是并行的 且是局域的 在种群内 每一个个体定义其近旁 此模型中 由于近旁的定义不同 而有多种形式 用近旁模型 由于GA操作的局域性 在种群中即使某个个体的适应度f很高 其影响只能通过近旁间渐渐地波及到整个群体 因此个体适应度的急剧增加被抑制 也就起到了抑制早期收敛的作用 并行GA的一些拓扑结构 1 并行GA的一些拓扑结构 2 2 11 4可变长个体与MessyGA 可变长个体MessyGA 可变长个体 若个体的位串长度L不变 个体可用二元组 基因座与其值 表示为A i1 v1 i2 v2 i3 v3 iL vL 例如 A 011001 可表示为A 1 0 2 1 3 1 4 0 5 0 6 1 因此 当可变长个体长度L是可变的 个体也可用二元组表示 此时 例如 4 0 5 0 3 1 4 0 3 1 4 0 2 1 5 0 6 1 1 0 切断与接合算子 切断 cut 以某概率在个体长度上随机选择位置 将基因链切断 接合 splice 以某概率将两个基因链接合 MessyGA 设置最大长度 初始化 评价 两两竞争选择 种群规模 N 切断 接合 选择 评价 结束条件 结束 Y N Y N 2 11 5基于小生境技术的GA 该算法是用共享函数来调整种群中各个个体的适应度 使种群在进化过程中能依据调整后的适应度进行选择 以维护种群的多样性 构造出小生境的进化环境 共享函数 共享函数是表示两个个体之间关系密切程度的函数 设有n个个体的种群的A a1 a2 an 两个个体ai与aj之间的共享函数sh dij 一般描述为个体ai在 同一小生境内 种群中的共享度mi是它与种群中其它个体间共享函数值之和 描述为 设个体ai的共享适应度如下 2 11 6混合GA 局部搜索结合全局搜索 梯度 GA模拟退火 GA智能体 GA 2 11 7导入年龄结构的GA 给个体赋予年龄 达到死亡年龄的个体也被淘汰 增设死亡率参数 2 11 8GA的理论研究 编码与收敛问题参数的优化GA欺骗问题在GA搜索过程中 将妨碍适应度高的个体生成而影响GA的工作 使搜索方向偏离全局最优解的问题 A 标准遗传算法的马氏链模型 B 遗传算法收敛性的一般理论 遗传算法收敛的定义及性质概率强弱收敛 遗传算法收敛的定义及性质 概率强弱收敛 2 11 9应用举例 函数优化系统辨识神经控制 1 函数优化 函数最优化问题如下 应用GA 结合最优化问题的要求 求解步骤如下 1 设定解空间2 确定目标函数及适应度之间的变换3 确定GA算子4 初始种群 编码5 求适应度值6 评价7 重复以上遗传操作 举例1 本例是二参数优化问题 其特点是有一个最优解 z x y 3906 2 048 2 048 有一个次优解 z x y 3898 2 048 2 048 求解步骤 求解步骤 举例2 本例是两参数优化问题 其特点是有4个最优解 z x y 52 43 5 12 5 12 求解步骤 2 系统辨识 GA用于系统辨识 也是求解最优化问题 本节讨论在假设系统 或环节 模型结构已知的情况下 由GA优化模型的参数 使准则函数最小 将GA用于系统辨识的步骤与将GA用于函数最优化的步骤类似 不同的是对于系统辨识 GA空间S的个体位串表示的是被辨识系统模型参数估计 候补解或解 的编码 GA用于系统辨识流程图 相关问题 举例1 求解步骤 3 神经控制 GA训练网络权系数W Project1最小化问题动态寻优 要求 提供源程序 matlab代码 提供相应的报告 报告内容包括 源代码 作图 程序流程 寻优结果 收敛曲线 作图 算法流程 流程图 收敛曲线 主要参数记录 3粒子群算法 主要发展历史基本原理带惯性权重的粒子群算法改进实验设计与参数选择应用举例 3 1主要发展历史 1997年 Kennedy和eberhart提出了二进制微粒群算法1998年 shi和erberhart在微粒群算法的速度项中引入惯性权重w1999年 clerc在进化方程中引入了收缩因子以保证算法的收敛性 1999年 angeline引入进化计算中的选择概念 随后 lovbjerg等人进一步将进化计算机制应用于微粒群算法 如复制 交叉等 2001年 lovbjerg等人将遗传算法中的子群体概念引入微粒群算法中 同时引入繁殖算子以进行子群体的信息交流 3 2基本原理 算法原理流程社会行为分析特点 3 2 1算法原理 也采用群体与进化的概念 同样也是依据个体 微粒 粒子 的适应度大小进行操作 所不同的是 微粒群算法不像其它进化算法那样对于个体使用进化算子 而是将每个个体看作是在n维搜索空间中的一个没有质量和体积的微粒 并在搜索空间中以一定的速度飞行 该飞行速度由个体的飞行经验和群体的飞行经验进行动态调整 原理 从上述微粒进化方程可以看出 c1调节微粒飞向自身最好位置方向的步长 c2调节微粒向全局最好位置飞行的步长 为了减少在进化过程中微粒离开搜索空间的可能性 vij通常限定于一定范围内 即vij vmax vmax 如果问题