论文总字数：19957字

目录

中文摘要．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．1

英文摘要．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．2

引言．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．3

1 CMA-ES算法原理介绍 4

1.1 基本方程：采样 4

1.2 选择和重组：移动平均值（均值的更新） 4

1.3 协方差矩阵的更新 5

1.3.1 更新 6

1.3.2 更新 7

2 算法性能测试 9

2.1 一些标准测试问题 10

2.2 函数测试结果 11

3 策略参数对算法性能的影响 11

3.1 对算法性能的影响 11

3.1.1 实验设置 11

3.1.2 数值结果及比较 13

3.2 对算法性能的影响 16

参考文献 19

致谢 20

一类基于正态分布采样的全局优化算法研究

杜彬

，China

Abstract: Compared to classical evolutionary algorithm, normal distribution sampling algorithm has good global search capability, but convergence efficiency is not ideal. A mixed strategy is an effective decrease effective solution to this problem. In this paper, we studied accelerated strategies of normal sampling algorithm. And we focused on covariance matrix adaptive evolutionary strategy algorithm (CMA-ES), gave CMA-ES algorithm flow chart, and we got the results that CMA-ES algorithm has good overall performance, high efficiency characteristics optimization through multi-peak test functions.

This article through a large number of digital simulation experiments, solve some test problems which are simple or complex, and the result is true and reliable, and may have a certain reference value to the practical application.

KEY WORDS: CMA-ES; Adaptability; Overall performance; Optimization efficiency

引言

结构复杂的优化问题维度高、峰值多、非线性、非连续，对此传统优化方法难以获得全局最优解；而利用仿生优化方法能够获得全局最优解，但是函数评价次数高，计算效率较低。因此，如何在获得全局最优解的前提下，进一步提高复杂结构问题的优化效率（减少函数评价次数），已经成为专家和学者普遍关心的问题。

基于概率分布估计方法是当前流行的一种优化算法，其中基于正态分布的算法是这类方法中的研究热点。相比于经典的进化算法，基于正态分布采样算法能够在整体很好的搜寻，但是收敛效率不够理想。我们认为混合有效的下降策略是一种可行的解决方法。我们打算对基于正态分布采样算法的加速策略进行了研究，以自适应协方差矩阵进化策略算法（CMA-ES）为重点，给出CMA-ES算法的算法流程，通过对多个单峰值和多峰值测试函数的测试得出CMA-ES算法具有全局性能好、寻优效率高的特点；在分析各种标准测试问题的代表特征的基础上，针对不同测试问题的特点，改变CMA-ES算法中策略参数的大小，达到对测试函数最佳的优化效果。

本文对一些单峰值测、非线性试函数的代表特征进行了分析，并且利用CMA-ES算法对这些测试问题进行数值实验测试；根据实验结果一致发现CMA-ES算法在解决非凸，非线性问题时具有全局性能好、寻优效率高的特点。

CMA-ES算法数值实验流程的第一步即是策略参数的设置.需要设置的参数一般有种群大小，父代个体数，重组权值以及自适应调整时所需的常量等策略参数的取值对算法的性能具有重要的影响.文献[1]中对上述参数进行了详细的讨论，并给出了各个参数的建议值；本文主要着眼于种群大小和父代个体数的不同取值对算法性能的影响展开讨论，针对不同问题探究策略参数对算法性能的影响.

首先，我们在分析单峰值测试函数和多峰值函数代表性特征的基础上，通过测试在达到收敛条件的情况下的函数评价次数，对比迭代最后一步的最优解的精度并分析寻优效率图，我们得到CMA-ES算法具有良好的全局寻优性能的结论。其中，单峰值函数集来自于文献[8]，多峰值函数集来自于文献[9].

接着，我们以达到收敛条件的平均函数评价次数（M-FES）和迭代最后一步的平均最优值（M-Best）为判断依据，通过改变种群大小λ和样本大小μ时M-FES的变化，寻找策略参数λ和μ对算法性能影响，并给出了测试函数集的算法策略参数的优化结果。

最后，我们对一些常见的多峰值函数做了测试并进行了策略参数的优化，得到了一些关于CMA-ES算法在解决多峰值问题过程中参数λ如何取值的结论。

本文通过大量的数字模拟实验，解决了一些简单和复杂特征的测试问题，结果真实可靠，对实际应用有一定的参考价值。

CMA-ES算法原理介绍

进化策略的一般算法可以描述如下：

问题为寻找实值n维矢量x，使得函数F(x): Rⁿ→R取极值。不失一般性，设此程序为极小化过程。
从各维的可行范围内随机选取亲本x_i，i = 1, … , p的始值。初始试验的分布一般是均匀分布。
通过对于x的每个分量增加零均值和预先选定的标准差的高斯随机变量，从每个亲本x_i产生子代x_i’。
通过将适应度F(x_i)和F(x_i’)，i＝1，…，P进行排序，选择并决定那些矢量保留。具有最小适应度的P个矢量变成下一代的新亲本。

进行新试验，选择具有最小方差的新子代，一直到获得充分解，或者直到满足某个终止条件。

自适应协方差矩阵进化策略（Covariance Matrix Adaption Evolution Strategy,short for CMA-ES）是在进化策略的基础上发展起来的一种高效的全局优化算法，它将进化算法的可靠性、全局性与自适应协方差矩阵的高引导性结合起来，对解决非线性、非凸优化问题具有较强的适应性.

CMA-ES算法包含突变、选择、重组等进化过程.CMA-ES算法从给定或随机产生的一个初始搜索点出发，以该初始点为中心，按一定的概率密度随机生成第一代种群（能够执行时间空间运算的群体），突变产生新一代种群的方程为：

（1-1）