简明遗传算法课件.ppt

遗传算法及其应用GeneticAlgorithm itsAplication 吴耀武华中科技大学电气与电子工程学院 遗传算法的概念 遗传算法及其应用 遗传算法与传统优化方法的比较 遗传算法的应用 群体智能优化方法简介 1遗传算法的概念 1 1遗传算法的起源自然进化化石记录表明 复杂结构生命是在相对短的时间内进化而来的 进化理论的一般特性进化过程是发生在染色体上 而不是在它们所编码的生物体上 自然选择把染色体以及由它们所译成的结构的表现联系起来 那些适应性好的个体的染色体经常比差的个体的染色体有更多的繁殖机会 繁殖过程是进化发生的那一刻 变异可以使生物体子代染色体不同于它们父代染色体 通过结合两个父代染色体中的物质 重组 杂交 交叉 过程可以在子代中产生有很大差异的染色体 生物进化没有记忆 有关产生个体的信息包含在个体所携带的染色体的集合以及染色体编码的结构之中 这些个体会很好地适应它们的环境 大多数生物体是通过自然选择和有性繁殖进行演化的 自然选择决定群体中那些个体能够存活并繁殖 有性繁殖保证了后代基因中的混合和重组 自然选择原则 达尔文进化论适者生存 优胜劣汰 1遗传算法的概念 遗传算法的起源是一族通过模拟自然进化过程搜索最优解的方法 1940年代 生物模拟已成为计算科学的组成部分 1960年代 美国Michigan大学JohnHolland在从事自适应系统研究时 注意到学习也可以通过一个群体的许多代进化适应发生 1960年代中期 Holland开发了一种编程技术 遗传算法 其基本思想是利用类似于自然选择的方式来设计计算机程序1975年Holland出版了专著AdaptationinNaturalandArtificialSystems 遗传算法逐渐为人所知 1遗传算法的概念 1 2遗传算法描述基本遗传算法框图主要步骤确定表示方案染色体串 映射 搜索空间确定适应值度量确定控制算法的参数和变量种群规模Mc 最大进化代数MEra pc pm pc pm 保留个体数等 4 确定指定结果的方法和停止运行准则 1遗传算法的概念 染色体编码y f x x x x x为0 1 二进制编码x为整数 二进制 十进制编码x为实数 二进制 十进制 实数编码编码原则 完备性 问题空间中所有点 侯选解 都能用遗传算法空间中的点 染色体 表现 健全性 遗传算法空间中的染色体都能对应问题空间中的所有侯选解 非冗余性 染色体和侯选解一一对应 1遗传算法的概念 生成初始种群根据染色体编码 随机确定染色体中的各段基因值 也可根据研究问题空间特点指定部分基因段 适应度函数的确定作用 评价种群中个体的优劣 基于适应度函数值的选择 求极小值问题 求极大值问题 1遗传算法的概念 遗传操作 选择 复制 选择算子根据是每个个体对应的优化问题目标函数转换成的适应度函数值的大小进行复制 体现了自然界中适者生存法则 是遗传算法的关键 适应度函数值比例法 赌轮法 个体被选取的概率适应值的比例变换法期望值法 个体不多时 排位次法 个体适应度相近时 1遗传算法的概念 遗传操作 杂交 交叉 GA的根本所在 通过模拟生物界中的有性繁殖 能把注意力集中到搜索空间中期望值最高的部分 方法 一点杂交 二点杂交和多点杂交遗传操作 变异模拟生物进化过程中偶然的基因突变现象 能保持群体的多样性 避免陷于局部最优 并可以在当前解的附近找到更好的解 杂交前A1 11000A2 10011杂交后A 1 11011A 2 10000 变异前A1 11001变异后A 1 11011 1遗传算法的概念 遗传操作 保留使得遗传算法能以概率1收敛到全局最优解 对种群进行简单的选择 复制 杂交和变异操作是遗传算法的精髓 停止运行准则 最大困难所在 1 达到最大进化代数2 连续多代没有改进时 1遗传算法的概念 1 3遗传算法的基本定理模式定理在考虑选择 交叉和变异作用下 一个特定模式H在下一代中期望产生的数目可近似表示为其中 H 为模式定义长度 指模式H中第一个常数位置与最后一个常数位置之间的距离 O H 为模式的阶 指出现在模式H中常数位置的个数 模式定义长度短 低阶且适应值在群体平均适应值以上的模式 在遗传算法迭代过程中将按指数增长率被采样 1遗传算法的概念 1 3遗传算法的基本定理隐含并行性串长为L 规模为N的二进制群体中 包含有2L到N 2L个模式 模式数是按二项式分布的 由于杂交算子会破坏那些定义长度相对较长的模式 因此 按有效方式被处理的模式数目与群体规模的立方成正比 即Ns O N3 此即 每一代中除了仅对N个染色体处理外 遗传算法实际上处理大约O N3 个模式 从而每代只执行与群体规模成比例的计算量 就可以同时收到并行地对大约O N3 个模式进行有效处理的目的 并且无须额外的存储 Holland称之为遗传算法的隐含并行性 2遗传算法与传统优化方法的比较 2 1传统数学优化方法线性规划 LP LinearProgramming 在满足一组线性约束条件下 寻求多变量线性目标函数的极大 小值 求解方法 单纯形法 线性混合整数规划法 分枝定界法 割平面法 隐枚举法 和内点法 非线性规划 NP NonlinearProgramming 目标函数或约束条件 一个或多个非线性函数 求解方法 微分法 拉格朗日乘子法 牛顿法 梯度法 变尺度法以及基于变分法的优化方法等 要求函数连续 甚至可导 2遗传算法与传统优化方法的比较 2 1传统数学优化方法动态规划 DP DynamicProgramming 运筹学的重要分支 由美国数学家贝尔曼 R Bellman 等人在1950年代提出 是研究多阶段决策过程最优化的一种有效方法 动态规划将整个优化问题转化为一个多阶段优化序列来处理 通过合理选择各个阶段决策的集合 使整个过程总体达到最优 要求所求解的问题具有明显的阶段性 它对目标函数的形态没有特殊的要求 理论上可以真正获得全局最优解 缺点是容易出现 维数灾 和 后效 问题 2遗传算法与传统优化方法的比较 2 2遗传算法的特点不是直接作用于参变量集上 而是利用参变量的某种编码 通用性强 采用群体搜索策略 同时对多个解进行评估 因而具有全局优化和隐含并行性 不用搜索空间的知识或其它辅助信息 仅用适应度函数值来评价个体 适应度函数无连续可导限制 定义域任意 特别适用于求解非连续变量结构优化问题 采用概率转移规则指导搜索方向 概率选择 概率交叉 概率变异 而非确定性规则 鲁棒性强 逐代进化 易于通过基因干预提高收敛速度 可同时获得最优解和若干次优解 便于决策分析 3遗传算法的应用 3 1遗传算法的应用领域自适应系统自适应下棋程序模式识别函数优化管道优化医学图像变换囚犯困境游戏分类系统喷气发动机涡轮设计 100 10387 导航 躲避和跟踪 主要应用领域搜索优化机器学习电力系统中 规划设计 建设施工和运行控制各环节 3遗传算法的应用 3 2GA在电力系统电源规划中的应用3 2 1何谓是电源规划 核心 4W问题 即 When Where What How 典型的组合排序问题特点高维数 m个待优选电站 m 组合方案m 38 m 38 5 23 1044 约1 66 1037年 非线性 目标函数 约束条件是非线性的整数性 变量是整数型的不确定性 基础数据 负荷 燃料 设备价格 水电风电出力 贴现率等 不确定 3遗传算法的应用 电源规划 为什么要进行电源规划 按英国1997年装机水平 1 18kW 13 6亿 16亿kW 3遗传算法的应用 电源规划 3 2 2GA电源规划模型 目标函数 约束条件待建电站建设施工约束系统可靠性约束系统 分区电力电量平衡约束电站运行约束 3遗传算法的应用 电源规划 3 2 2GA电源规划模型 总体框图 3遗传算法的应用 电源规划 3 2 3整数向量染色体编码与初始种群的生成染色体编码 电源规划方案 整数向量m电源规划方案可以编码为长度为N的整数向量m m1 m2 mN 其中 mk表示向量m的第k个元 顺序第k位投建的待优选电站序号 电源规划初始方案集 初始种群MC 生成 动态模板整数向量染色体编码法 3遗传算法的应用 电源规划 3 2 4适应度函数值的计算种群中方案i的适应度函数值AFi 3 2 5遗传操作选择算子 适应度函数值比例法 赌轮法 3遗传算法的应用 电源规划 3 2 5遗传操作杂交算子1 次序杂交 OC OrderingCrossover 例 mF1 9 2 13 4 6 12 3 8 1 10 15 5 14 7 11 mF2 4 6 9 11 5 2 14 1 7 3 13 15 10 12 8 杂交位置 0 0 0 0 0 0 0 0 0 0 0 mS1 9 2 13 4 6 12 11 8 1 10 15 5 14 7 3 mS2 13 6 9 11 5 2 14 1 7 3 4 15 8 12 10 2 位置杂交 LC LocatingCrossover 例 mF1 9 2 13 4 6 12 3 8 1 10 15 5 14 7 11 mF2 4 6 9 11 5 2 14 1 7 3 13 15 10 12 8 杂交位置 0 0 0 0 0 0 0 0 0 0 0 mS1 2 13 9 11 4 6 12 1 8 3 10 15 5 14 7 mS2 6 9 13 4 11 5 2 8 14 10 1 7 3 15 12 3遗传算法的应用 电源规划 3 2 5遗传操作杂交算子3 映射杂交 MC MappingCrossover 例 mF1 9 2 13 4 6 12 3 8 1 10 15 5 14 7 11 mF2 4 6 9 11 5 2 14 1 7 3 13 15 10 12 8 杂交位置 0 0 0 0 0 0 0 0 0 0 0 mS1 9 12 13 4 5 2 14 1 8 10 15 6 3 7 11 mS2 4 5 9 11 6 12 3 8 7 14 13 15 10 2 1 4 循环杂交 CC CyclingCrossover 例 mF1 9 2 13 4 6 12 3 8 1 10 11 5 14 7 15 mF2 4 6 9 11 5 2 14 1 7 3 13 15 10 12 8 mS1 4 2 9 11 6 12 3 8 1 10 13 5 14 7 15 mS2 9 6 13 4 5 2 14 1 7 3 11 15 10 12 8 3遗传算法的应用 电源规划 3 2 5遗传操作变异算子作用 在群体中提供和保持多样性以使其它的算子可以继续起作用 本身也可以使遗传算法具有局部随机搜索能力 1 位置变异 随机选择染色体向量上的两个元 然后将第二个元放在第一个元之前 2 次序变异 随机选择染色体向量上的两个元 然后交换其位置 3 打乱变异 随机选择染色体向量上的两个元一段 然后打乱在这个段内元的次序 GA电源规划模型中直接采用位置变异算子 3遗传算法的应用 电源规划 3 2 6算例及其结果原始数据 3遗传算法的应用 电源规划 3 2 6算例及其结果原始数据 3遗传算法的应用 电源规划 3 2 6算例及其结果优化结果 优化结果表明 能够获得全局最优解 计算的基本参数 种群规模 MC 30最大遗传进化代数 NEra max 2000保留算子 Nopt 3杂交率 pc 0 8变异率 pm 0 05 3遗传算法的应用 电源规划 3 2 6算例及其结果结果分析 3遗传算法的应用 电源规划 收敛特性 遗传算法的全局优化性和隐含并行性使得遗传算法具有非常高收敛速度 能够快速定位于电源规划问题的全局最优解的邻域附近 遗传算法的随机搜索过程使得遗传算法还具有局部搜索能力弱的特点 混合遗传算法 3遗传算法的应用 电源规划 收敛特性 4群体智能优化方法简介 专家系统 ES ExpertSystem 在启发式推理中引入专家知识 将专家知识与计算机计算结合 根据某种规则进行决策和推理 是一种很好的启发式推理工具 其效率很大程度上决定于知识库的建立 模糊集理论 FS FuzzySetTheory 用隶属度函数将输入模糊化 输入和输出关系用模糊规则描述 输出的模糊变量用隶属度函数反模糊化 变为现实世界的决策 模拟退火算法 SA SimulatedAnnealing 模拟热力学中液体凝结与结晶 金属熔液冷却与退火过程的随机搜索技术 其执行过程是一系列的 产生新解 判断 接受 舍弃 迭代过程 理论上是一个全局最优算法 4群体智能优化方法简介 禁忌搜索算法 TS TabuSearch 一种扩展邻域的启发式搜索技术 通过记录 Tabu表 搜索历史 从中获得知识并用来指导后续搜索方向以避开局部最优解 原理 产生一个初始解 采用一组 移动 操作从当前解的邻域中随机产生一系列试验解 选择最好的解作为当前解 重复迭代 直到满足一定的终止准则 目前还不能从数学上证明一定能收敛于全局最优解 但大量的应用研究表明它能有效地获得非常好的次优解 它还具有局部搜索能力强的特点 神经网络 ANN ArtificialNeuralNetworks 模拟生物神经网络构造的 由一些简单的节点及其大规模并行连接构造的网络 它致力于按照生物神经系统同样的方式处理真实世界的客观事物 已被证明通过适当的训练 可用于模式识别 预测 分类和组合优化问题 4群体智能优化方法简介 免疫算法 IA ImmuneAlgorithm 免疫系统是生物体的一个高度进化 复杂的功能系统 它可以自适应地识别和排除侵入机体的抗原性异物 并具有学习 记忆 自适应调节能力 维护体内环境的稳定 免疫系统的这一特有的进化特性被用于各类组合优化问题求解 思维进化算法 MEA MindEvolutionAlgorithm 基于人类思维进化过程的优化算法 把整个群体划分为若干个子群体 采用趋同 Similartaxis 和异化 Dissmilation 进化操作代替GA的交叉和变异算子 通过个体之间有效信息的交换实现种群的快速进化 4群体智能优化方法简介 粒子群算法 PSO ParticleSwarmOptimization 模拟鸟群觅食过程中的迁徙和群集行为时提出的一种基于群体智能的演化计