基于合作协同演化的微粒群计算及其应用.pdf

湖南省管理科学与工程重点实验室课题出版资金立项出版 基于合作协同演化的微粒群 计算及其应用 伍大清 著 南华大学专著出版资金立项出版 内 容 简 介 本书围绕粒子群优化算法在优化领域存在的不足，并结合具体工业生产过程的实际应用，对粒子群优化算法进行了改进和应用研究。本书基于合作协同算法框架，将各种局部优化、全局优化、自适应等策略融入到微粒群优化算法，以克服传统微粒群算法某些方面的缺陷，较大幅度地改进了算法性能，构建了面向大规模复杂优化问题的微粒群智能计算框架体系，并利用通用的组合优化和实数优化问题对算法进行了验证，将其应用于函数优化、柔性车间调度、环境经济调度、带时间窗的车辆路径优化及低碳供应链选址-路径-库存集成优化等实际管理工程复杂问题，在应用过程中体现了合作协同微粒群计算的有效性和实用性，为求解大规模复杂问题提供理论基础与方法支持。本书可作为计算机、电气自动化技术、管理科学与工程等相关专业高年级本科生或研究生智能计算方法课程的教材，也可作为计算机、电气自动化技术、管理科学与工程等相关行业研究和开发的参考书。未经许可，不得以任何方式复制或抄袭本书之部分或全部内容。版权所有，侵权必究。图书在版编目（CIP）数据 基于合作协同演化的微粒群计算及其应用/伍大清著.北京：电子工业出版社，2015.9 ISBN 978-7-121-27258-5.基 .伍 .电子计算机算法理论.TP301.6 中国版本图书馆 CIP 数据核字（2015）第 227383 号 策划编辑：章海涛 戴晨辰 责任编辑：郝黎明 印 刷：装 订：出版发行：电子工业出版社 北京市海淀区万寿路 173 信箱 邮编 100036 开 本：7871 092 1/16 印张：8.75 字数：224 千字 版 次：2015 年 9 月第 1 版 印 次：2015 年 9 月第 1 次印刷 定 价：39.00 元 凡所购买电子工业出版社图书有缺损问题，请向购买书店调换。若书店售缺，请与本社发行部联系，联系及邮购电话：（010）88254888。质量投诉请发邮件至 ，盗版侵权举报请发邮件至 。服务热线：（010）88258888。前 言 受自然现象或生物进化启发的群智能算法被广泛用于求解科学研究和工程应用领域中的优化问题。面临优化问题不断增加的复杂性，许多群智能算法难以满足大规模复杂优化问题求解的需求，将合作协同演化理论引入到群智能算法中已成为求解大规模复杂优化问题的有效途径之一。基于合作协同演化的群智能算法通过多元集成、协同进化等方式，根据实际求解问题灵活构造抽象的算法模型，从而达到有效改善算法优化质量、效率和鲁棒性的目的。微粒群优化（Particle Swarm Optimization，PSO）算法是一种可靠、通用的元启发式优化算法，在各类优化问题中展现了令人瞩目的性能。然而，微粒群优化算法存在容易陷入局部停滞、早熟收敛或优化精度不高等缺陷。为了提高微粒群优化算法的性能，本书系统地分析了微粒群优化算法的基本原理和算法要点，从多角度入手，将合作协同演化理论引入到微粒群优化算法中，提出了基于合作协同演化的微粒群计算模型，并将其应用到实际管理优化问题中。该研究拓展了大规模复杂优化问题和群智能优化算法的研究范畴，为求解大规模复杂优化问题提供了有效的新方法。本书主要创新性工作概括如下。（1）为了适应各类复杂问题的求解，提高微粒群算法的普适性和鲁棒性，根据协同免费午餐理论，本书提出了基于自适应学习的多策略并行微粒群算法。融合快速收敛、跳出局部极值、深度搜索、广度开发 4 种变异策略，本书引入了自适应学习机制，根据问题复杂程度选择出合适的策略来完成全局寻优。仿真实验验证了算法在优化效率、优化性能和鲁棒性方面均有很大改善，并具有较强的普适性。（2）通过对协同演化策略和群智能算法特性的反思，将协同演化模式和并行进化机制引入到微粒群算法和蜂群算法中，建立了一种多阶段动态群智能算法。该算法结合动态种群的微粒群算法与开发能力较强的协同蜂群算法的各自优势，实现了全局寻优。该算法将整个搜索过程分成 3 个阶段，为了保持种群的多样性，首先，利用微粒群局部模型进行粗搜索；其次，采用个体间反馈能力强的协同蜂群算法搜索空间的广度及深度；再次，利用微粒群全局模型提高寻优速度，从而完成整个问题的全局寻优。通过函数优化测试及柔性车间作业调度问题的求解，验证了提出的算法具有收敛速度快、全局搜索能力强、稳定性好、求解精度高的特点。（3）受空间自适应划分和动态拓扑结构启发，将多目标优化问题分解成多个单目标问题进行求解，提出一种基于空间自适应划分的动态种群多目标优化算法，并引入年龄观测器及精英学习策略，防止帕雷托（Pareto）最优解集陷入局部最优，对国际多目标测试函数及环境经济调度问题进行仿真测试，提出算法能对解空间进行更加全面、充分的探索，从而快速找到一组分布具有尽可能好的逼近性、宽广性和均匀性的最优解集合。（4）以管理优化中具有代表性的带时间窗车辆路径优化问题为研究对象，采用基于集 合的编码方式，引入插入启发式与前推启发式信息初始化方法及局部搜索算子，设计了一种解决多目标组合优化问题的微粒群算法，通过对国际标准测试算例带时间窗车辆路径优化问题仿真实验，验证了提出算法比许多启发式算法搜索精度高。运用算例仿真实验结果表明该算法能有效降低物流配送成本，提高配送效率，具有较好的实用价值。（5）对涉及生产商、潜在配送中心及分销商的低碳化多源选址路径库存集成问题进行研究。在考虑碳排放的基础上，对产品从生产商经过潜在配送中心再到最终分销商的整个流程中有关配送中心选址、库存要求及路径选择等问题进行优化设计，构建低碳供应链多级网络选址路径库存多目标优化模型，以整条供应量成本及碳排放成本最低为目标；设计了两个阶段的协同多目标微粒群优化算法；通过仿真实验对算例进行了分析，并对模型进行了求解，得出了相应的结论。本书技术路线如图 1-1 所示，各章节的内容组织安排如下。第 1 章，绪论。本章阐述了本书的选题背景及研究意义，分别对合作协同演化算法、微粒群优化算法及其实际应用领域等进行了简要的描述，重点介绍了本书的研究内容和创新点。第 2 章，相关理论。本章概要地介绍了书中涉及的单目标及多目标优化理论，合作协同演化算法理论，以及智能优化算法，包括微粒群优化算法、蜂群优化算法的基本概念、基本原理与基本操作。第 3 章，基于自适应学习的并行协同微粒群算法及理论研究。本章针对目前很多特定的微粒群算法其鲁棒性和普适性均不强等问题，融合 4 种不同进化策略，在自适应学习机制下完成寻优。仿真实验验证了新算法显著提高了微粒群优化算法的性能，在优化效率、优化性能和鲁棒性方面均有很大改善，并具有较强的普适性。理论分析证明了自适应学习多策略并行微粒群算法的收敛性和计算复杂度等。第 4 章，基于多阶段协同微粒群智能优化算法。本章针对微粒群和协作型人工蜂群优化算法各自的优缺点，基于“阶段混合”思想，提出一种基于微粒群和人工蜂群的多阶段混合智能优化算法。仿真实验验证了新算法的整体寻优能力。第 5 章，基于空间自适应划分的动态种群多目标优化算法。本章提出了一种基于动态划分的多种群协同演化的多目标优化算法，通过在一种新的局部和全局最优粒子的引导下，快速靠近帕雷托最优前沿面，使用年龄观测器来保持种群多样性，设计差分演化变异操作来防止帕雷托最优解陷入局部最优，仿真结果表明，新算法能够在保持帕雷托最优解多样性的同时具有较好的收敛性能。第 6 章，基于集合编码的车辆路径多目标优化模型及算法。本章以最小化所需运输车辆数目和车辆行驶距离为目标，提出了一种基于集合编码的多目标离散微粒群优化算法，通过对国际标准算例测试验证了新算法比许多启发式算法搜索精度和效率更高。第 7 章，低碳供应链选址路径库存集成优化模型及算法。本章建立了一个考虑碳排放的多级供应链网络选址路径库存集成优化多目标模型，然后利用两阶段协同多目标微粒群优化算法对模型进行求解，并对算例进行讨论分析。第 8 章，总结与展望。本章总结了本书的研究工作，提出下一步的研究方向。V 目 录 第 1 章 绪论 1 1.1 研究背景与意义 1 1.2 国内外研究进展 2 1.2.1 合作协同演化算法研究进展 2 1.2.2 微粒群优化算法研究进展 4 1.2.3 微粒群优化计算典型应用 8 1.3 研究目的 10 1.4 研究内容 10 1.5 创新点 11 第 2 章 相关理论 13 2.1 引言 13 2.2 最优化理论 13 2.2.1 单目标优化问题 14 2.2.2 多目标优化问题 16 2.3 合作协同演化理论 18 2.4 智能计算方法 19 2.4.1 微粒群优化算法 19 2.4.2 蜂群优化算法 22 2.5 小结 25 第 3 章 基于自适应学习的并行协同微粒群算法及理论研究 26 3.1 引言 26 3.2 基于自适应学习的并行 PSO 算法 26 3.2.1 并行协同演化策略 27 3.2.2 自适应学习机制 28 3.2.3 HLPSO 算法步骤 28 3.2.4 HLPSO 算法实现 29 3.3 自适应学习的并行 PSO 算法理论基础 30 3.3.1 HLPSO 算法收敛性分析 30 VI 3.3.2 HLPSO 算法复杂度分析 32 3.4 HLPSO 在函数优化中的应用 33 3.4.1 测试函数 33 3.4.2 均值方差对比 35 3.4.3 双侧 T-检验 36 3.5 小结 36 第 4 章 基于多阶段协同微粒群智能优化算法 37 4.1 引言 37 4.2 多阶段协同微粒群智能优化算法 37 4.2.1 DMPSOABC 算法思想 37 4.2.2 DMPSOABC 算法模型 38 4.2.3 DMPSOABC 算法描述 40 4.2.4 DMPSOABC 算法实现 41 4.3 DMPSOABC 算法时间复杂度分析 42 4.4 DMPSOABC 算法在函数优化中的应用 42 4.4.1 测试函数 42 4.4.2 实验目的 44 4.4.3 实验环境 44 4.4.4 参数设置 45 4.4.5 实验结果 46 4.5 基于多阶段协同的柔性作业车间智能调度 51 4.5.1 柔性作业车间调度问题数学模型 51 4.5.2 柔性作业车间调度算法描述 52 4.5.3 实例验证 56 4.6 小结 61 第 5 章 基于空间自适应划分的动态种群多目标优化算法 62 5.1 引言 62 5.2 基于空间自适应划分的动态多目标优化算法 62 5.2.1 ECMPSO 算法思想 62 5.2.2 ECMPSO 算法模型 66 5.2.3 ECMPSO 算法描述 67 5.3 ECMPSO 算法时间复杂度分析 68 5.4 实验测试 68 5.4.1 测试函数及参数设置 68 5.4.2 参数敏感性分析 70 5.4.3 测试结果 74 5.5 ECMPSO 在解决环境经济调度问题中的应用 80 5.5.1 环境经济调度的数学模型 80 VII 5.5.2 环境经济调度算法描述 81 5.5.3 仿真实验与分析 82 5.6 小结 84 第 6 章 基于集合编码的车辆路径多目标优化模型及算法 86 6.1 引言 86 6.2 带时间窗车辆路径多目标优化模型 86 6.3 基于集合编码的带时间窗车辆路径多目标优化算法 88 6.3.1 算法思想 88 6.3.2 种群编码 88 6.3.3 初始化种群 89 6.3.4 粒子更新 90 6.3.5 局部搜索策略 93 6.3.6 算法描述 93 6.4 实验仿真与结果分析 94 6.4.1 测试问题 94 6.4.2 性能评价指标 94 6.4.3 实验结果 95 6.4.4 实例分析 99 6.5 小结 100 第 7 章 低碳供应链选址路径库存集成优化模型及算法 101 7.1 引言 101 7.2 考虑碳排放的 CLIRP 模型 103 7.2.1 问题描述及假设 103 7.2.2 模型构建 104 7.3 基于两阶段协同