演化计算方法及应用.pdf

演化计算方法及应用 演化计算方法及应用 窦全胜 陈姝颖 著 演化计算方法及应用 内 容 简 介 本书全面概括了用演化方法求解优化问题的一些新方法，重点介绍了进化规划、粒子群优化、微分演化、文化算法和蚁群算法，并阐述了几种新的改进算法，例如，群体启发进化规划方法、模拟退火粒子群优化算法及有分工策略的粒子群优化等，同时就所涉及的算法进行了系统的实验和比较，讨论了不同算法对不同环境的适应能力。本书可作为从事群体智能、演化计算等领域的研究人员的参考书，对于解决优化问题有一定的参考和应用价值。未经许可，不得以任何方式复制或抄袭本书之部分或全部内容。版权所有，侵权必究。图书在版编目（CIP）数据 演化计算方法及应用/窦全胜,陈姝颖 著.北京：电子工业出版社，2016.1 ISBN 978-7-121-26482-5 .演.窦 陈.人工神经网络与计算 .TP183 中国版本图书馆 CIP 数据核字（2015）第 117530 号 责任编辑：李 敏 特约编辑：刘广钦 印 刷：装 订：出版发行：电子工业出版社 北京市海淀区万寿路 173 信箱 邮编：100036 开 本：7201000 1/16 印张：11.25 字数：178 千字 版 次：2016 年 1 月第 1 版 印 次：2016 年 1 月第 1 次印刷 定 价：38.00 元 凡所购买电子工业出版社图书有缺损问题，请向购买书店调换。若书店售缺，请与本社发行部联系，联系及邮购电话：（010）88254888。质量投诉请发邮件至 ，盗版侵权举报请发邮件至 。服务热线：（010）88258888。演化计算方法及应用 前言前言 最优化问题是一门既古老又年轻的学科，特别是随着科学技术的发展，许多更加复杂的大规模优化问题不断涌现出来。本书详细阐述了基于演化计算方法的最优化问题求解，主要内容包括：基于遗传算法的优化问题求解；进化规划和群体启发进化规划；粒子群优化算法和算法改进；微分演化方法；基于文化算法的约束优化问题求解；蚁群算法；演化算法的应用示例。本书共 8 章：第 1 章绪论，介绍本书的研究背景，对求解优化问题的数学方法和演化计算方法进行了简要的概括和比较；第 2 章对基于遗传算法的最优化问题求解过程进行了阐述，对以往的一些处理技巧进行了论述；第 3 章对标准进化规划进行了分析，阐述了群体启发进化规划方法，并把它应用于求解高维优化问题；第 4 章介绍了 PSO 算法，并进一步阐述了关于 PSO 方法的两种改进方法；第 5 章介绍了微分演化方法的执行过程；第 6 章概括了用演化计算方法求解约束优化问题的几个策略，着重介绍了几种不可行个体的处理方式，讨论了基于约束与群体的分离策略的文化算法；第 7 章对蚁群算法和蚁群聚类进行介绍；第 8 章列举了几个演化计算方法在实际问题中的应用示例。演化计算方法及应用 IV 本书的工作得到了国家自然基金（61272244、60970088、61175053、61173173）等项目和山东省高校智能信息处理重点实验室（山东工商学院）的资助，在此表示感谢。此外，还要特别感谢吉林大学的周春光教授，山东工商学院的范辉教授、原达教授、谢青松教授、刘培强教授，感谢他们为本书写作提供的帮助与支持。由于水平有限，书中难免有疏漏和不足之处，敬请读者指正。作者的联系方式为：。作者 2015 年 2 月 目录目录 第 1 章 绪论.1 1.1 最优化问题.2 1.2 求解优化问题的数学方法.4 1.3 求解优化问题的演化计算方法.5 第 2 章 遗传算法.9 2.1 标准遗传算法.10 2.2 编码.12 2.2.1 二进制编码.12 2.2.2 值编码（Value Encoding）.12 2.2.3 互换编码（Permutation Encoding）.13 2.3 遗传算子.14 2.3.1 交叉.14 2.3.2 变异.15 2.3.3 选择.17 2.4 参数控制.18 2.5 模式定理和隐并行性定理.19 2.6 收缩映射原理.21 2.7 小结.24 演化计算方法及应用 VI 第 3 章 进化规划.25 3.1 标准进化规划方法.26 3.2 进化策略.28 3.3 概率分析.29 3.4 群体启发进化规划.33 3.4.1 群体启发进化规划算法.33 3.4.2 PHEP 算法验证.35 3.5 用群体启发进化规划求解高维优化问题.40 3.5.1 高维优化.40 3.5.2 实验结果.41 3.6 小结.44 第 4 章 粒子群优化.45 4.1 标准粒子群优化方法.47 4.2 二进制粒子群优化算法.49 4.3 参数设置.56 4.4 粒子轨迹的确定性分析.59 4.5 粒子的分布特征.62 4.6 粒子的聚度.63 4.7 模拟退火粒子群优化方法.66 4.7.1 模拟退火.67 4.7.2 模拟退火粒子群优化.68 4.8 有分工策略的粒子群优化方法.70 4.9 算法测试.73 4.10 动态优化.76 4.10.1 线性模型.76 4.10.2 环形模型.77 4.10.3 随机模型.77 4.10.4 动态优化仿真.78 4.11 小结.83 目 录 VII 第 5 章 微分演化.85 5.1 微分演化方法描述.86 5.2 DE 参数的设置.89 5.3 算法仿真.90 5.3.1 低维条件下的仿真结果.90 5.3.2 高维条件下的仿真结果.91 5.4 微分演化粒子群优化.92 5.5 用 DE 确定 PSO 的最佳参数.95 5.6 小结.98 第 6 章 文化算法.99 6.1 约束的处理.101 6.1.1 可行解和不可行解.101 6.1.2 可行个体评价函数 evalf的设计.102 6.1.3 不可行个体的处理.103 6.2 文化算法简介.108 6.2.1 文化算法框架.108 6.2.2 信仰空间的约束表达和信仰空间的更新.109 6.2.3 群体空间的演化.113 6.3 算法测试.113 6.4 小结.114 第 7 章 蚁群优化.116 7.1 蚁群优化算法.117 7.2 蚁群聚类.120 7.3 小结.123 演化计算方法及应用 VIII 第 8 章 应用举例.125 8.1 属性约简.126 8.1.1 信息系统与属性约简.126 8.1.2 常用的属性约简方法.126 8.1.3 基于遗传算法的属性约简.129 8.2 电力负荷关联规则提取.132 8.2.1 问题概述.132 8.2.2 关联规则.133 8.2.3 频繁项集挖掘.136 8.2.4 基于 DPSO 方法负荷规则萃取.138 8.3 神经网络训练.142 8.3.1 神经元模型.143 8.3.2 神经网络.144 8.3.3 神经网络的学习.145 8.3.4 前向神经网络.146 8.4 小结.149 附录 A 无约束优化问题.150 附录 B 约束优化问题.157 参考文献.162 第第 1 章章 绪论绪论 演化计算方法及应用 -2-1.1 最优化问题 最优化是一个重要的数学分支，也是一门应用相当广泛的学科。最优化的目的是对于给出的实际问题，从众多方案中选择出最优方案。例如，工程设计中怎样选择设计参数，使得设计方案既满足设计要求又能降低成本；资源分配中，怎样分配有限的资源，使得分配方案既能满足各方面的基本要求，又能获得好的经济效益。在人类活动的各个领域中，诸如此类，不胜枚举。应用案例应用案例 1：某城市有大型超市 8 个，在“农超对接”对接模式下，8 个超市的某些品种蔬菜全部由该市县级农产品物流中心进行统一配送。其中，县级农产品物流中心位置为 O，8 个超市间距离不同，如表 1-1 所示。配送车辆从 O 出发，选择一个最短的行程对 8 个超市进行农产品配送，最后回到物流中心 O，问如何选择配送路线，使其配送成本最低？表 1-1 某市 8 个超市间距离 单位（km）O A B C D E F G H O 0 25 16 28 19 10 24 20 22 A 25 0 15 9 7 6 23 12 15 B 16 15 0 9.7 4 15 10 13 5.7 C 28 9 9.7 0 12 5.7 6.2 9 12 D 19 7 4 12 0 18 6 16 10 E 10 6 15 5.7 18 0 12 9 15 F 24 23 10 6.2 6 12 0 21 17 G 20 12 13 9 16 9 21 0 12 H 22 15 5.7 12 10 15 17 12 0 应用案例应用案例 2：某工厂生产甲、乙、丙、丁共 4 种产品，需要用到 A、B、C 共 3 种原料，每种产品需要使用的各种原料的数量及其可能获得的利润如表 1-2 所示。另外，A、B 两种原料供应量有限，单位生产周期内只能提供一定的数量，而 C 种原料一经开包使用就必须用足一定量后才可停止使用，且不能单独使用。现有关数据均见表 1-2，问应如何安排生产，才能使该厂所获利润达到最大值?第1章 绪论 -3-表 1-2 加工产品所需原料及可能获得的利润 加工每件产品所需原料 原料 甲 乙 丙 丁 单位周期内原料的供应量或必须使用量 A 1.0 1.2 1.4 1.5 2100 B 0.5 0.6 0.6 0.8 1000 C 0.7 0.7 0.8 0.8 1300 每件利润 12 15 8 10 类似这样的优化问题在生产生活中大量存在，其研究历史可以追溯到十分古老的极值问题。早在 17 世纪，英国伟大科学家牛顿发明微积分的时代，已经提出极值问题，后来又出现 Lagrangian 乘数法。1847 年，法国数学家 Cauchy 研究了函数沿什么方向下降最快的问题，提出了最速下降法。1939 年，前苏联数学家.提出了解决下料问题和运输问题这两种线性规划问题的求解方法。人们关于最优化问题的研究工作，随着历史的发展不断深入。但是，任何学科的进步，都受到历史条件的限制，直至20 世纪 30 年代，最优化这个古老的课题还未形成独立的学科。在最近的二三十年中，伴随着计算机技术的高速发展和优化计算方法的进步，各种优化问题的理论研究发展迅速，新方法不断出现，实际应用日益广泛。在计算机的推动下，一些超大规模的优化问题得以实现，最优化理论与方法在经济规划、工程设计、生产管理、交通运输等方面得到了广泛应用，成为一门十分活跃的学科。最优化问题的一般形式为1 ()Mins.t.f xxX （1-1）其中，nxR是决策变量，()f x为目标函数，nXR为约束集或可行域。特别地，如果约束集nXR=，则最优化问题（1-1）称为无约束最优化问题。在本书中，若X为nR中的超立方体，也近似地把问题（1-1）看成无约束最优化问题。优化问题通常带有一些约束条件，称为约束最优化问题，表述为()()()Mins.t.0,0,ijf xcxiEcxjI=（1-2）演化计算方法及应用 -4-这里，E 和 I 分别是等式约束指标集和不等式约束指标集，()icx是约束函数。当目标函数和约束函数均为线性函数时，问题称为线性规划；当目标函数和约束函数中至少有一个是变量x的非线性函数时，问题称为非线性规划。此外，根据决策变量、目标函数和要求的不同，最优化还可以分为整数规划、动态规划、网络规划、非光滑规划、随机规划、几何规划、多目标规划等若干分支。1.2 求解优化问题的数学方法 求解最优化问题通常采用迭代方法，其基本思想如下：给定一个初值点0nxR，按照某一迭代规则产生一个序列 kx，使得当 kx为有穷点列时，其最后一个点是最优化问题的最优解。当 kx为无穷列时，它有极限点，且其极限点是最优化问题的最优解。一个好的算法应该具备如下特征：迭代点能够稳定地接近局部极小点*x的邻域，然后迅速收敛于*x。迭代方法的基本结构如下1。步骤 1 给定初始点0 x，确定搜索方向kd。步骤 2 确定步长因子k。步骤 3 令1kkkkxxd+=+。（1-3）步骤 4 若1kx+满足某种终止条件，则停止迭代，得到近似最优解。否则，