全局最优化(基于递归深度群体搜索的新方法)

本书介绍全局优化算法的基本理论和研究进展，特别聚焦于最近几年提出的基于递归深度群体搜索的一类新方法，并详细介绍递归深度群体搜索技术在确定性全局优化和智能优化算法中的具体应用。在确定性全局优化中，以DIRECT算法为例，深入介绍了递归深度群体搜索的设计原则与技巧；在智能优化中，以粒子群优化算法为例，介绍了递归深度搜索和群体搜索的融合方法及性能提升。本书提供了全局优化算法从入门到精通的各种材料，包括基本概念、基本理论、算法设计原则与技巧、国际通用的测试函数库、主流的测试数据分析方法和技术。因此，本书适合于对全局优化算法有兴趣的高年级本科生、研究生、研究人员以及工程技术人员。

刘群锋，理学博士，东莞理工学院教授，分别于1999年、2002年在华中科技大学数学系获学士、硕士学位，于2011年在湖南大学数学学院获博士学位。主要从事全局优化、计算智能与机器学习等领域的理论与方法研究。主持国家自然科学基金面上项目、教育部人文社科基金青年项目、广东省自然科学基金面上项目等科研项目5项，累计研究经费超400万。在相关领域的主流期刊上发表论文50余篇。

第1部分 全局最优化问题、算法与递归深度群体搜索技术 第1章 全局最优化问题与算法简介 3 1.1 最优化问题 3 1.1.1 最优化模型 3 1.1.2 最优化问题的基本理论 4 1.1.3 最优化算法简介 6 1.2 全局最优化问题 8 1.2.1 全局最优化问题的理论困境: 全局最优性条件的缺失 9 1.2.2 全局最优化问题的数值困境: 计算复杂度的挑战 9 1.2.3 全局最优化问题的数值困境: 问题维数的诅咒 11 1.3 全局最优化算法简介 12 1.3.1 确定性全局优化算法 12 1.3.2 随机性全局最优化算法 14 第2章 递归深度群体搜索技术 18 2.1 全局最优化的渐近无效现象 18 2.1.1 渐近无效的一个实例 18 2.1.2 渐近无效的普遍性 20 2.2 递归深度群体搜索技术 22 2.2.1 递归深度的技术渊源: 数值代数中的多重网格法 23 2.2.2 全局最优化中的群体搜索技术 27 2.2.3 递归深度群体搜索的实现方法 29 2.3 本书后续内容安排 32 第2部分 递归深度群体搜索技术在确定性全局最优化算法中的应用 第3章 稳健DIRECT算法 37 3.1 DIRECT 算法 37 3.1.1 Lipschitz 优化与Lipschitz 常数 37 3.1.2 抽样与分割 39 3.1.3 区域选择 41 3.1.4 DIRECT 算法的全局收敛性 43 3.1.5 DIRECT 算法的代码获取 45 3.2 DIRECT 算法的一些变化 45 3.2.1 区域大小 45 3.2.2 分割方式 45 3.2.3 动态平衡参数 46 3.3 DIRECT 算法对目标函数线性校正的敏感性 46 3.3.1 敏感性的理论证据 46 3.3.2 敏感性的数值证据 48 3.4 稳健DIRECT 算法 48 3.4.1 对潜最优区域的重新定义 48 3.4.2 稳健性的证明 49 3.5 数值实验 50 第4章 基于递归深度群体搜索的稳健DIRECT算法 54 4.1 DIRECT 算法的渐近无效行为 54 4.1.1 强最优超矩形 55 4.1.2 渐近无效性的证据与分析 55 4.2 引进两水平深度搜索策略 56 4.2.1 两重网格方法 57 4.2.2 两水平深度搜索策略 58 4.2.3 RDIRECT-b 算法 60 4.3 数值实验（一） 61 4.3.1 对问题（4.1）的测试结果 62 4.3.2 对Jones 测试集的测试结果 62 4.3.3 RDIRECT-b 算法的参数灵敏度分析 64 4.3.4 在Hedar 测试集上的测试结果 67 4.4 引进递归深度技术产生多水平搜索 69 4.4.1 多重网格方法 69 4.4.2 MrDIRECT算法 71 4.5 数值实验（二） 72 4.5.1 对问题（4.1）的测试结果 72 4.5.2 对Hedar 测试集的测试结果 73 4.5.3 MrDIRECT 算法的参数灵敏度分析 75 4.5.4 GKLS 测试集上的数值结果 78 4.6 结论 81 第5章 DIRECT 算法渐近无效现象的消除 82 5.1 DIRECT 算法渐近无效的两大内因 82 5.1.1 再探DIRECT 算法的渐近无效现象 83 5.1.2 第一个内因: 平衡机制 84 5.1.3 第二个内因: 参数? 84 5.2 MrDIRECT 算法与渐近无效行为的第一个内因 85 5.2.1 在问题（4.1）上的测试 86 5.2.2 Shubert 型测试集的测试 87 5.2.3 数据结果的解释 88 5.3 MrDIRECT 算法的改进与渐近无效行为的第二个内因 90 5.3.1 问题（4.1）中的测试结果 90 5.3.2 Shubert 型测试集上的测试结果 91 5.3.3 整个Hedar 测试集上的比较 92 5.4 改进MrDIRECT 算法的数值实验 93 5.4.1 Hedar 测试集的测试 93 5.4.2 再看Shubert 问题 94 5.4.3 GKLS 测试集和CEC 测试集上的数值比较 95 5.5 总结 99 第6章 递归深度群体搜索技术的更一般应用与探讨 101 6.1 基于分割的全局优化算法 101 6.1.1 PGO 算法框架 101 6.1.2 PGO 算法的收敛性 103 6.2 基于递归深度群体搜索的一般分割式全局优化算法 105 6.2.1 基于两水平分割的GOMP-T 算法 105 6.2.2 基于多水平分割的GOMP 算法 106 6.2.3 GOMP 算法的收敛性 108 6.3 递归深度搜索与深度学习 110 6.3.1 深度学习简介 110 6.3.2 深度搜索与深度学习的联系与区别 111 6.4 搜索深度对算法的影响 113 6.5 数值结果分析 115 第3部分 递归深度群体搜索技术在智能优化算法中的应用 第7章 粒子群优化算法 119 7.1 粒子群优化算法 119 7.1.1 群体智能优化简介 119 7.1.2 原始粒子群优化算法 119 7.1.3 经典粒子群优化算法 121 7.2 粒子群优化算法的研究进展简介 121 7.2.1 动态方程的变化 121 7.2.2 拓扑选择与优化 122 7.2.3 理论研究进展 124 第8章 粒子群优化算法的稳定性分析 126 8.1 稳定性分析的一个综述 126 8.2 弱停滞性假设 129 8.2.1 粒子分类和知识传播 129 8.2.2 占优粒子的领导行为 130 8.3 二阶稳定性分析 132 8.3.1 稳定性定义 132 8.3.2 计算E[R2(t)] 134 8.3.3 参数的稳定域 136 8.4 比较和讨论 137 8.5 数值实验 139 8.5.1 算法配置和测试问题 139 8.5.2 数据分析技术 141 8.5.3 稳定性和效率 143 8.5.4 “最佳” 参数设置 146 8.5.5 测试问题的影响 146 8.6 总结与展望 149 第9章 粒子群优化算法的拓扑优化分析 150 9.1 拓扑优化研究回顾 151 9.1.1 静态拓扑优化的现有工作 151 9.1.2 结论 152 9.2 基于正则图的粒子群优化及其拓扑优化 153 9.2.1 正则拓扑的生成 153 9.2.2 平均路径长度和平均聚类系数 154 9.2.3 正则拓扑的参数优化 160 9.3 数值实验 162 9.3.1 实验设置 162 9.3.2 数据分析技术 164 9.3.3 给定粒子数情况下的最优度数 165 9.3.4 最优粒子数 171 9.3.5 讨论 173 9.4 结论 173 第10章 基于递归深度群体搜索的粒子群优化算法 174 10.1 算法框架 174 10.2 基于RDSS 技术的两水平粒子群优化算法 176 10.2.1 算法实现与参数设置 176 10.2.2 数值实验 176 10.3 基于RDSS 技术的三水平粒子群优化算法 178 10.3.1 算法实现与参数设置 178 10.3.2 数值实验 179 10.4 结论与展望 181 10.4.1 渐近无效现象的普遍性 181 10.4.2 递归深度群体搜索技术的作用 181 10.4.3 未来的研究方向 182 第4部分 附录 附录A 带残差校正的多重网格法的收敛性分析 185 A.1 引言 185 A.2 扰动两重网格方法 .186 A.3 带残差校正的多重网格法的收敛性分析 188 A.3.1 在最细一层进行残差校正的收敛性分析 189 A.3.2 在任意k (1≤k≤L) 层进行残差校正的收敛性分析 190 A.3.3 ??> 2 时的收敛性分析 192 A.4 数值实验 193 A.5 小结 196 附录B 全局优化算法的数值比较简介 197 B.1 全局优化测试函数库简介 197 B.1.1 Hedar 测试函数库 197 B.1.2 GKLS 测试函数库 199 B.1.3 CEC 测试函数库系列 200 B.1.4 BBOB 测试函数库系列 201 B.1.5 更多测试函数库 202 B.2 全局优化算法的比较方法 202 B.2.1 用表格呈现数据 202 B.2.2 L 型曲线法 203 B.2.3 performance profile 技术 203 B.2.4 data profile 技术 204 参考文献 206