本文重点讨论的是进化算法的随机过程模型, 不失一般性, 研究连续搜索空间的最优化问题, 数学描述如下:

min f(x),

s.t. x∈ S⊆Rn^,

其中, f(x)表示目标函数, S表示搜索空间, n表示问题的规模.S中每个元素表示问题的一个解, 对应算法中的每个个体, 这些个体组成种群.记进化策略第t代种群

${{\xi }^{t}}=\{\xi _{1}^{t}, \xi _{2}^{t}, \ldots , \xi _{\lambda }^{t}\}\in S, $

其中λ 表示种群规模.一个典型ES求解最优化问题算法流程如算法1^[25]所示.

算法1 ES流程^[25]

输入 初始化种群

输出 包含目前为止找到满意解

令t=0;

随机生成λ 个个体种群ξ ₀={ ξ10, ξ20, …, ξλ0};

计算每个个体适应值, 评估当代种群中个体优劣; while not stop do

for i=1∶ λ do

通过交叉和变异产生新的种群;

end for

计算每个个体适应值, 评估当代种群中个体优劣;

从λ 个个体中选择ξ '_t个体作为下一代的种群;

t=t+1;

end while

输出到目前为止找到的满意解.

算法1包括使用交叉、变异和选择, 未对交叉和变异做任何限制.选择是采取非精英保存, 即每代维持一个父代个体, 通过变异产生λ 个子代个体.再从λ 个子代个体中选择个体作为下一代的种群.然而, 本文给出的主要结果(即定理3)与这样的具体实现无关, 几乎可以用于任何随机算法.

为了建立非负随机过程, 本文假设在进化策略运行过程中, 第t代种群中至少存在一个个体的适应值优于第t-1代种群个体的适应值.

由于算法很难找到最优解, 当算法找到满意解

${{d}_{min}}(\xi_{opt}^{\text{t}})=min(d(\xi_{opt}^{0}), d(\xi_{opt}^{1}), \ldots )=\varepsilon $

时, 即

$d(\xi_{opt}^{\text{t}})< \varepsilon $

时, 算法终止.

根据随机过程理论, 设(Ω , H, P)为概率空间,

H_t=σ (d(ξ ₀), Y₁, Y₂, …, Y_t)⊂H

为σ -代数流, H包含由信息d(ξ ₀), Y₁, Y₂, …, Y_t生成的所有事件.鞅这个概念最初起源于公平赌博数学模型, 后引入概率论中.鞅就是在掌握从初始到现在累积信息d(ξ ₀), Y₁, Y₂, …, Y_t条件下预测未来与现在相同.

设$\{{{X}_{t}}\}_{\text{t}=0}^{\infty }$和$\{{{H}_{t}}\}_{\text{t}=0}^{\infty }$为随机过程, X_t为$\{{{H}_{t}}\}_{\text{t}=0}^{\infty }$的可测函数, 对∀ t≥ 0, 有

E(X_t+1|H_t)≥ X_t,

称$\{{{X}_{t}}\}_{\text{t}=0}^{\infty }$是关于$\{{{H}_{t}}\}_{\text{t}=0}^{\infty }$的下鞅.若

E(X_t+1|H_t)≤ X_t,

称$\{{{X}_{t}}\}_{\text{t}=0}^{\infty }$是关于$\{{{H}_{t}}\}_{\text{t}=0}^{\infty }$的上鞅.从概率论的角度来看, 下鞅就是在已知d(ξ ₀), Y₁, Y₂, …, Y_t的条件下, X_t+1的条件期望优于现在X_t; 上鞅就是在已知d(ξ ₀), Y₁, Y₂, …, Y_t的条件下, X_t+1的条件期望劣于现在X_t.为了度量当代个体到最优个体之间距离, 给出如下定义1.

定义1 适应值差函数 设函数d在S→ R满足

$d(\xi_{opt}^{\text{t}})=f(\xi_{opt}^{\text{t}})-{{f}_{opt}}$,

则称d为适应值差函数, 其中, ξoptt表示第t代最优个体, f_opt表示目标适应值.当t=0时,

$d(\xi_{opt}^{0})=d({{\xi }_{0}})=f({{\xi }_{0}})$.

令${{d}_{max}}(\xi_{opt}^{\text{t}})$表示ES在第t代之前取得最大适应值差, 即

${{d}_{max}}(\xi_{opt}^{\text{t}})=max(d(\xi_{opt}^{0}), d(\xi_{opt}^{1}), \ldots , d(\xi_{opt}^{\text{t}}))=d(\xi_{opt}^{\text{0}})$.

定义2 增长率^[26] 在ES运行过程中, 增长率表示 t-1代到t代种群之间到最优距离的减少量, 即

${{X}_{t}}=d(\xi_{opt}^{\text{t}-1})-d(\xi_{opt}^{\text{t}}), t=1, 2, \ldots $.

质量增益表示父代与子代之间的适应值减少量^[27].

增长率大小反映ES收敛速度的快慢.增长率越大, 与最优解的距离减少量改变越快, 收敛速度越快; 增长率越小, 与最优解的距离减少量改变越慢, 收敛速度相对越慢.由于是最小化问题, $\{{{X}_{t}}\}_{\text{t}=0}^{\infty }$为非负随机过程, 由此得出如下定义3.

定义3 增长率更新过程 设$\{{{X}_{t}}\}_{\text{t}=0}^{\infty }$为非负随机过程, Y_t为非负随机变量.若对∀ t=1, 2, …, 有

${{Y}_{t}}=\overset{\text{t}}{\mathop{\underset{\text{n}=1}{\mathop \sum }\, }}\, {{X}_{n}}=d({{\xi }_{0}})-d(\xi_{opt}^{\text{t}})$,

则称Y_t为进化策略在第t代增长率更新过程.

在随机算法中, 研究者们通常感兴趣的是算法首次找到满意解时, 算法对适应度函数的迭代次数^[4], 即父代与子代之间到最优距离的减少量之和

Y_t=d(ξ ₀)-ε .

首达时间可使用停时描述, 下面给出停时的定义.

定义4 更新过程停时 设$\{{{X}_{t}}\}_{\text{t}=0}^{\infty }$为非负随机过程, τ 为一个非负随机变量, 若满足

${{T}_{\tau }}=\left\{ \tau |\overset{\tau-1}{\mathop{\underset{\text{k}=1}{\mathop \sum }\, }}\, {{X}_{k}}< d({{\xi }_{0}})-\varepsilon , \overset{\infty }{\mathop{\underset{\text{k}=\tau}{\mathop \sum }\, }}\, {{X}_{k}}\ge d({{\xi }_{0}})-\varepsilon \right\}$,

则称τ 为X_t的一个更新过程停时.

本节主要分析(1, λ )ES带均匀变异算子在倾斜平面问题上的平均首达时间分析.倾斜平面问题是一个连续搜索空间的优化问题, 为了降低计算量, 本节主要讨论二维倾斜平面问题:

f(y₁, y₂)=y₂,

(y_1, y₂)⊂S=[-c, c]× [0, c].

由此可知, y₂=b时, 二维倾斜平面取得最大值.由于本文考虑最小值问题, 因此, 讨论的二维倾斜平面问题转化为

f=min f(y₁, y₂)=-y₂,

(y_1, y₂)⊂S=[-c, c]× [0, c].

可见, y₂=-c时二维倾斜平面取得最小值, 即目标适应值f^* =-c.由于二维倾斜平面问题只在y₂上有分量, 可以归结为一元问题.定义

$d(\xi _{k}^{t-1})=f(\xi _{k}^{t-1})-{{f}^{* }}$

为第t-1次迭代到最优解的适应值差, 第t-1代到第t代的增长率为:

${{\delta }_{t}}={{X}_{t}}=d(\xi _{k}^{t-1})-d(\xi _{k}^{t})=f(\xi _{k}^{t-1})-f(\xi _{k}^{t})$.

(1, λ )ES的平均首达时间关键是推导增长率的概率密度函数, 下面将推导带均匀变异(1, λ )ES的增长率分布函数.

定理4 对于(1, λ )ES, 如果变异算子服从U(-1, 1), 增长率δ _t-1的分布函数为:

$F\left( \gamma \right)=P\left( \delta \le \gamma \right)=\left\{ \begin{array}{*{35}{l}} 0, & \gamma ＜0 \\ \left( \frac{1}{2} \right){^{\lambda }}, & \gamma =0 \\ \left( \frac{1}{2}+\frac{\gamma }{2} \right){^{\lambda }}, & 0＜\gamma \le 1 \\ 1, & \gamma >1 \\ \end{array} \right.$

证明 由算法2可知, 父代y₂分量个体ξ '_t-1通过均匀变异U_k(k=1, 2, …, λ )产生λ 个子代个体

ξ '_{t, k}=(ξ '₁, ξ '₂, …, ξ '_{λ -1}, ξ '_λ ), k=1, 2, …, λ ,

其个体之间相互独立, 则

ξt'=minξt, λ', maxξt, λ'< ξt-1'ξt-1', minξt, λ'> ξt-1'

根据增长率定义, 得

δt=maxUk, minUk≥00, maxUk< 0

进而增长率δ _t的分布函数F(γ )表示如下.

1)当γ < 0时,

F(γ )=P(δ _t< γ )=0.

2)当γ =0时,

$F(\gamma )=P({{\delta }_{t}}< \gamma )=P({{\delta }_{t}}=0)=P\{\max {{U}_{k}}< 0\}={{\left( \frac{1}{2} \right)}^{\lambda }}$^.

3)当0< γ ≤ 1时,

$\begin{align} & F(\gamma )=P({{\delta }_{t}}< \gamma )=P(max{{U}_{k}}< \gamma )= \\ & {{(P({{\delta }_{t}}< 0)+P({{\delta }_{t}}=0)+P(0< \gamma < 1))}^{\lambda }}= \\ & {{\left( 0+\frac{1}{2}+\underset{0}{\overset{\gamma }{\mathop \int }}\, \frac{1}{2}d\gamma \right)}^{\lambda }}={{\left( \frac{1}{2}+\frac{\gamma }{2} \right)}^{\lambda }} \\ \end{align}$.

4)当 γ > 1时,

F(γ )=1.

因此

$F\left( \gamma \right)=\left\{ \begin{array}{* {35}{l}} 0, & \gamma < 0 \\ \left( \frac{1}{2} \right){{~}^{\lambda }}, & \gamma =0 \\ \left( \frac{1}{2}+\frac{\gamma }{2} \right){{~}^{\lambda }}, & 0< \gamma \le 1 \\ 1, & \gamma > 1 \\ \end{array} \right.$

证毕.

定理5 在(1, λ )ES求解倾斜平面问题中, 对于平均首达时间T_τ , 有

$\begin{align} & \frac{\left( \lambda +1 \right)\left( d\left( {{\xi }_{0}} \right)-{{d}_{\text{min}}}\left( \xi _{\text{opt}}^{t} \right) \right)}{\lambda +1+{{\left( 2 \right)}^{-\lambda }}}-\frac{\lambda +1}{\lambda +1+{{\left( 2 \right)}^{-\lambda }}}\le \\ & E({{T}_{\tau }}|d({{\xi }_{0}}))\le 1+\frac{\left( \lambda +1 \right)\left( d\left( {{\xi }_{0}} \right)-{{d}_{\text{min}}}\left( \xi _{\text{opt}}^{t} \right) \right)}{\lambda -1} \\ \end{align}$

成立.

证明 根据定理4, 可得

$\begin{align} & E({{\delta }_{t}}|{{H}_{t}})=\underset{-\infty }{\overset{+\infty }{\mathop \int }}\, \gamma dF(\gamma )=\underset{-\infty }{\overset{0}{\mathop \int }}\, \gamma dF(\gamma )+\underset{0}{\overset{1}{\mathop \int }}\, \gamma dF(\gamma )+\underset{1}{\overset{+\infty }{\mathop \int }}\, \gamma dF(\gamma )= \\ & 0+\underset{0}{\overset{1}{\mathop \int }}\, \gamma dF(\gamma )+0=\frac{\lambda }{2}\underset{0}{\overset{1}{\mathop \int }}\, \gamma {{\left( \frac{1}{2}+\frac{\gamma }{2} \right)}^{\lambda -1}}\text{d}\gamma \text{=}\left[ \gamma {{\left( \frac{1}{2}+\frac{\gamma }{2} \right)}^{\lambda }} \right]_{0}^{1}- \\ & \underset{0}{\overset{1}{\mathop \int }}\, {{\left( \frac{1}{2}+\frac{\gamma }{2} \right)}^{\lambda }}\text{d}\gamma \text{=}1-\frac{2}{\lambda +1}\left[ {{\left( \frac{1}{2}+\frac{\gamma }{2} \right)}^{\lambda +1}} \right]_{0}^{1}\text{=}1-\frac{2}{\lambda +1}\left( 1-{{\left( \frac{1}{2} \right)}^{\lambda +1}} \right) \\ \end{align}$

又因为

$E({{\delta }_{t}}|{{H}_{t}})=1-\frac{2}{\lambda +1}\left( 1-{{\left( \frac{1}{2} \right)}^{\lambda }}^{+1} \right)\ge 1-\frac{2}{\lambda +1}=\frac{\lambda -1}{\lambda +1}$,

$\begin{align} & E({{\delta }_{t}}|{{H}_{t}})=1-\frac{2}{\lambda +1}~(1-{{(2)}^{-\lambda -1}})\le \\ & 1-\frac{1}{\lambda +1}+\frac{1}{\lambda +1}~{{(2)}^{-\lambda -1}}=\frac{\lambda +{{\left( 2 \right)}^{-\lambda -1}}}{\lambda +1} \\ \end{align},$

所以可得出算法平均增长率:

$\frac{\lambda -1}{\lambda +1}\le E({{\delta }_{t}}|{{H}_{t}})\le \frac{\lambda +{{\left( 2 \right)}^{-\lambda }}}{\lambda +1}$.

根据定理3, 对于

${{d}_{\min }}(\xi _{\text{opt}}^{t})> 0$,

可得

$\begin{align} & \underset{{{d}_{\text{min}}}\ \left( \xi _{\text{opt}}^{t} \ \ \right)}{\overset{d\left( {{\xi }_{0}} \right)}{\mathop \int }}\, \frac{\lambda +1}{\lambda +{{\left( 2 \right)}^{-\lambda -1}}}dt-\frac{\lambda +1}{\lambda +{{\left( 2 \right)}^{-\lambda -1}}}\le \\ & E({{T}_{\tau }}|d({{\xi }_{0}}))\le 1+\underset{{{d}_{\text{min}}}\ \ \left( \xi _{\text{opt}}^{t} \right)}{\overset{d\left( {{\xi }_{0}} \right)}{\mathop \int }}\, \frac{\lambda +1}{\lambda -1}dt \\ \end{align}$,

$\begin{align} & E({{T}_{\tau }}|d({{\xi }_{0}}))\ge \underset{{{d}_{\text{min}}}\ \left( \xi _{\text{opt}}^{t}\ \right)}{\overset{d\left( {{\xi }_{0}} \right)}{\mathop \int }}\, \frac{\lambda +1}{\lambda +{{\left( 2 \right)}^{-\lambda -1}}}\text{d}t-\frac{\lambda +1}{\lambda +{{\left( 2 \right)}^{-\lambda -1}}}\text{=} \\ & \frac{\left( \lambda +1 \right)\left( d\left( {{\xi }_{0}} \right)-{{d}_{\text{min}}}\ \left( \xi _{\text{opt}}^{t} \ \ \right) \right)}{\lambda +{{\left( 2 \right)}^{-\lambda -1}}} \\ \end{align}$,

即

$\begin{align} & E({{T}_{\tau }}|d({{\xi }_{0}}))\le 1+\underset{{{d}_{\text{min}}}\ \ \left( \xi _{\text{opt}}^{t} \ \ \right)}{\overset{d\left( {{\xi }_{0}} \right)}{\mathop \int }}\, \frac{\lambda +1}{\lambda -1}dt= \\ & 1+\frac{\left( \lambda +1 \right)\left( d\left( {{\xi }_{0}} \right)-{{d}_{\text{min}}}\ \ \left( \xi _{\text{opt}}^{t} \ \ \right) \right)}{\lambda -1} \\ \end{align}$.

因此, 估计平均首达时间的上下界:

$\begin{align} & \frac{\left( \lambda +1 \right)\left( d\left( {{\xi }_{0}} \right)-{{d}_{\text{min}}}\ \ \left( \xi _{\text{opt}}^{t} \ \ \right) \right)}{\lambda +1+{{\left( 2 \right)}^{-\lambda }}}-\frac{\lambda +1}{\lambda +1+{{\left( 2 \right)}^{-\lambda }}}\le \\ & E({{T}_{\tau }}|d({{\xi }_{0}}))\le 1+\frac{\left( \lambda +1 \right)\left( d\left( {{\xi }_{0}} \right)-{{d}_{\text{min}}}\ \left( \xi _{\text{opt}}^{t}\ \right) \right)}{\lambda -1} \\ \end{align}$.

证毕.

本节分析(1, λ )ES带均匀算子在超平面上的平均首达时间.

如果球函数的对称性在一个方向上被破坏, 这就是RIDGE问题, 相应的RIDGE函数表达式如下:

${{F}_{RIDGE}}(x)={{x}_{0}}-d{{\left( \overset{n-1}{\mathop{\underset{i=1}{\mathop \sum }\, }}\, x_{i}^{2} \right)}^{{{~}^{\frac{\theta }{2}}}}}, \theta \in R, d\in {{R}^{+}}$.

不失一般性, 本节主要研究超平面问题, 这是RIDGE函数中θ =0时的简化形式^{[31, 32]}.相应的函数表达式为

$f(x)={{a}_{0}}+\overset{n}{\mathop{\underset{i=1}{\mathop \sum }\, }}\, {{a}_{i}}{{x}_{i}}$,

${{a}_{0}}\in R, {{a}_{i}}\in {{R}^{+}}, {{x}_{i}}\subset S=[-b, b]$,

其中x=(x₁, x₂, …, x_n), 考虑当x=(0, 0, …, 0), f(x)=a₀为理想最小值.

定义

$d(\xi _{k}^{t-1})=f(\xi _{k}^{t-1})-{{f}^{* }}=({{a}_{0}}+{{a}_{1}}{{x}_{1}}+{{a}_{2}}{{x}_{2}}+\ldots +{{a}_{n}}{{x}_{n}})-{{a}_{0}}$

为第t-1次迭代到最优解的适应值差.那么第t-1代到第t代的增长率为:

$\begin{align} & {{\delta }_{t}}={{X}_{t}}=d(\xi _{k}^{t-1})-d(\xi _{k}^{t})=f(\xi _{k}^{t-1})-f(\xi _{k}^{t})= \\ & \left[ {{a}_{1}}(x_{1}^{t-1}-x_{1}^{t})+\cdots +{{a}_{n}}(x_{n}^{t-1}-x_{n}^{t}) \right] \\ \end{align}$.

虽然独立同分布的均匀分布具有可加性, 但是计算量较复杂, 积分不易计算.为了减少冗余的复杂计算, 下面主要考虑n=5的情形, 结合列维-林德伯格中心极限定理进行分析.增长率δ _t由变异算子及问题规模决定, 因此增长率δ _t是一个随机变量, 分布函数计算如定理6.

定理6 设n=5时, 对于(1, λ )ES, 如果变异算子U服从U(-1, 1), 那么增长率δ _t的分布函数为:

$F(\gamma )=P({{\delta }_{t}}\le \gamma )=\left\{ \begin{array}{* {35}{l}} 0, & \gamma< 0 \\ {{\left( \frac{1}{2} \right)}^{\lambda }}, & \gamma=0 \\ {{\left( \sqrt{\frac{3}{2\pi\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}}\underset{-\infty }{\overset{\gamma }{\mathop \int }}\, \text{exp}\left( -\frac{3{{t}^{2}}\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}{2} \right)\text{d}t \right)}^{\lambda }}, & \gamma > 0 \\ \end{array} \right.$

证明 随机变量 x1t-1-x1t, x2t-1-x2t, …, x5t-1-x5t的期望和方差如下:

$E(x_{k}^{t-1}-x_{k}^{t})=0$,

$D(x_{k}^{t-1}-x_{k}^{t})=\frac{1}{3}, k=1, 2, \ldots , 5$.

则随机变量

$\overset{5}{\mathop{\underset{k=1}{\mathop \sum }\, }}\, {{a}_{k}}(x_{k}^{t-1}-x_{k}^{t})\tilde{\ }N\left( 0, \frac{1}{3}(a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2}) \right)$.

其中~表示近似等于.

1)当γ < 0时, 即f(ξ '_t)> f(ξ '_t-1), 则

F(γ )=0.

2)当γ =0时, 即

$f(\xi _{t}^{'})=f(\xi _{t-1}^{'}), \underset{k=1, 2, \ldots , \lambda }{\mathop{\text{max}}}\, (f(\xi _{t, k}^{'})-f(\xi _{t-1}^{'}))=0$,

则

$F(\gamma )={{\left( \frac{1}{2} \right)}^{\lambda }}$.

3)当γ > 0, 即f(ξ '_t)< f(ξ '_t-1)等价于

$\underset{k=1, 2, \ldots , \lambda }{\mathop{\text{max}}}\, ~(f(\xi _{t, k}^{'})-f(\xi _{t-1}^{'}))$

时, 则

$\begin{align}& F(\gamma )=\underset{k=1, 2, \ldots , \lambda }{\mathop{\text{max}}}\, ~(f(\xi _{t, k}^{'})-f(\xi _{t-1}^{'}))=\overset{\lambda }{\mathop{\underset{k=1}{\mathop \prod }\, }}\, ~(f(\xi _{t, k}^{'})-f(\xi _{t-1}^{'}))= \\& {{\left( \sqrt{\frac{3}{2\pi\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}}\underset{-\infty }{\overset{\gamma }{\mathop \int }}\, \exp \left( \frac{3{{t}^{2}}\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}{2} \right)dt \right)}^{\lambda }} \\ \end{align}$.

因此

F(γ)=0, γ< 0(12)λ, γ=0(12+32π(a12+a22+…+a52)∫0γexp(-3t2(a12+a22+…+a52)2)dt)λ, γ> 0

证毕.

不妨假定进化策略在初始化种群时, 初始化种群到满意解的距离为d(ξ ₀), 即有如下定理7成立.

定理7 在(1, λ )ES求解超平面问题中, 对于${{d}_{\min }}(\xi _{\text{opt}}^{t})> {{a}_{0}}$, 估计首达时间T_τ , 则有

$\begin{align} & \sqrt{\frac{6\pi}{{{\lambda }^{2}}\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}}~(d({{\xi }_{0}})-{{d}_{min}}(\xi _{\text{opt}}^{t})-1)\le E({{T}_{\tau }}|d({{\xi }_{0}}))\le \\ & 1+\sqrt{\frac{24\pi}{{{\lambda }^{2}}\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}}(d(\xi 0)-{{d}_{\min }}(\xi _{\text{opt}}^{t})) \\ \end{align}$

成立.

证明 根据定理4, 可得

$\begin{align} & E({{\delta }_{t}}|{{H}_{t}})=\underset{-\infty }{\overset{+\infty }{\mathop \int }}\, \gamma dF(\gamma )=\underset{-\infty }{\overset{0}{\mathop \int }}\, \gamma dF(\gamma )+\underset{0}{\overset{+\infty }{\mathop \int }}\, \gamma dF(\gamma )= \\ & \underset{0}{\overset{+\infty }{\mathop \int }}\, \gamma d{{\left( \frac{1}{2}+\sqrt{\frac{3}{2\pi\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}}\underset{0}{\overset{\gamma }{\mathop \int }}\, \exp \left( -\frac{3{{t}^{2}}\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}{2} \right)dt \right)}^{\lambda }}= \\ & \underset{0}{\overset{+\infty }{\mathop \int }}\, \gamma \lambda {{\left( \frac{1}{2}+\sqrt{\frac{3}{2\pi\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}}\underset{0}{\overset{\gamma }{\mathop \int }}\, \exp \left( -\frac{3{{t}^{2}}\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}{2} \right)dt \right)}^{\lambda -1}}\cdot \\ & \sqrt{\frac{3}{2\pi\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}}\exp \left( -\frac{3{{\gamma }^{2}}\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}{2} \right)dt. \\ \end{align}$.

由于在算法运行过程中, 随机变量$f(\xi _{t, k}^{'})-f(\xi _{t-1}^{'})\ge 0$且服从均匀分布U(-1, 1), 故$\frac{1}{2}\le F(\gamma )\le 1$.而

$\underset{0}{\overset{+\infty }{\mathop \int }}\, \gamma \sqrt{\frac{3}{2\pi\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}}\exp \left( -\frac{3{{t}^{2}}\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}{2} \right)dt=\sqrt{\frac{a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2}}{6\pi}}$,

因此

$\frac{\lambda }{2}\sqrt{\frac{a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2}}{6\pi}}\le E({{\delta }_{t}}|{{H}_{t}})\le \lambda \sqrt{\frac{a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2}}{6\pi}}$.

假定算法初始化从原点出发, 根据定理4, 推导的首达时间T_τ 下界

$\begin{align} & E({{T}_{\tau }}|d({{\xi }_{0}}))\ge \underset{{{d}_{\text{min}}}\ \ \left( \xi _{\text{opt}}^{t} \ \ \right)}{\overset{d\left( {{\xi }_{0}} \right)}{\mathop \int }}\, \sqrt{\frac{6\pi}{{{\lambda }^{2}}\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}}dt-\sqrt{\frac{6\pi}{{{\lambda }^{2}}\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}}= \\ & \sqrt{\frac{6\pi}{{{\lambda }^{2}}\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}}(d({{\xi }_{0}})-{{d}_{\min }}(\xi _{\text{opt}}^{t}))-\sqrt{\frac{6\pi}{{{\lambda }^{2}}\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}}= \\ & \sqrt{\frac{6\pi}{{{\lambda }^{2}}\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}}(d({{\xi }_{0}})-{{d}_{\min }}(\xi _{\text{opt}}^{t})-1) \\ \end{align}$,

上界

$\begin{align} & E({{T}_{\tau }}|d({{\xi }_{0}}))\le 1+\underset{{{d}_{\text{min}}}\ \left( \xi _{\text{opt}}^{t} \ \right)}{\overset{d\left( {{\xi }_{0}} \right)}{\mathop \int }}\, \sqrt{\frac{24\pi}{{{\lambda }^{2}}\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}}dt= \\ & 1+\sqrt{\frac{24\pi}{{{\lambda }^{2}}\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}}(d({{\xi }_{0}})-{{d}_{\min }}(\xi _{\text{opt}}^{t})) \\ \end{align}$.

证毕.

由定理5和定理7可得, (1, λ )ES在满足均匀分布变异算子时, 理论分析可得到倾斜平面和超平面的首达时间的上下界.

定理5给出二维倾斜平面的平均首达时间上下界的闭合表达式, 下面通过实验方式验证此理论结果.实验中设置如下实验参数:

${{\xi }_{0}}=(x_{1}^{0}, x_{2}^{0})=(0, 0), c=3, d({{\xi }_{0}})=3$,

固定误差

${{d}_{\min }}(\xi _{\text{opt}}^{t})=0.01$.

对于每个种群大小λ , 将算法2在二维倾斜平面上运行100轮.定义$T_{{{d}_{\min \ \left( \xi _{\text{opt}}^{t} \ \right)}}}^{i}$ 表示算法2中第i轮在${{d}_{\min }}(\xi _{\text{opt}}^{t})$去心邻域的首达时间, 实际运行平均首达时间

$E\left( \bar{T}_{{{d}_{\min \ \left( \xi _{\text{opt}}^{t} \ \right)}}}^{i} \ \ \ \ |d({{\xi }_{0}})~ \right)=\frac{1}{100}\overset{100}{\mathop{\underset{i=1}{\mathop \sum }\, }}\, T_{{{d}_{\min \ \left( \xi _{\text{opt}}^{t} \ \right)}}}^{i}$.

记理论分析下界

$E_{\text{low}}^{1}~({{T}_{\tau }}|d({{\xi }_{0}}))=\frac{\left( \lambda +1 \right)\left( d\left( {{\xi }_{0}} \right)-{{d}_{\text{min}}}\ \left( \xi _{\text{opt}}^{t} \ \right) \right)}{\lambda +{{\left( 2 \right)}^{-\lambda -1}}}$,

理论分析上界

$E_{\text{up}}^{1}~({{T}_{\tau }}|d({{\xi }_{0}}))=1+\frac{\left( \lambda +1 \right)\left( d\left( {{\xi }_{0}} \right)-{{d}_{\text{min}}}\ \left( \xi _{\text{opt}}^{t} \ \right) \right)}{\lambda -1}$.

表1给出(1, λ )ES在二维倾斜平面上实际平均首达时间与理论上的时间上界和下界.从表中可以看出, 在选择种群小于λ =13时, 随着种群规模的不断增大, 平均首达时间不断减小, 与理论分析时间的上下界一致.然而当种群大于λ =13时, 随着种群的不断增大, 平均首达时间和理论分析时间的上下界的结果并未减小, 反而趋于一个稳定值.此结果表明种群规模与平均首达时间之间并非负相关.

表1

Table 1

表1(Table 1)

表1 二维倾斜平面上理论与实际平均首达时间对比 Table 1 Comparison of theoretical and actual first hitting time on a two-dimensional inclined plane λ $E_{low}^{1}~({{T}_{\tau }}|d({{\xi }_{0}}))$ $E\left( \bar{T}~_{{{d}_{\text{min}}}\ \ \left( \xi _{opt}^{t} \ \ \right)}^{i}|d({{\xi }_{0}}) \ \ \right)$ $E_{up}^{1}({{T}_{\tau }}|d({{\xi }_{0}}))$ 3 2.60 6.92 6.98 5 2.40 4.77 5.50 7 2.28 3.34 5.00 9 2.22 2.84 4.75 11 2.18 2.82 4.60 13 2.15 2.47 4.50 15 2.13 2.46 4.43 17 2.11 2.31 4.37 19 2.10 2.33 4.32

表1 二维倾斜平面上理论与实际平均首达时间对比 Table 1 Comparison of theoretical and actual first hitting time on a two-dimensional inclined plane

文献[24]引入鞅论和勒贝格控制收敛定理, 分析平均首达时间的上界, 得到紧致的闭合表达式, 但是勒贝格控制收敛定理要求存在控制函数, 这是一个很强的条件, 而本文模型无需要求存在控制函数, 削弱条件后得到更一般结果的时间上下界.文献[23]只给出一个渐近的表达式结果, 而本文模型考虑种群规模对首达时间的影响, 得出更紧的时间下界.

定理7给出超平面的平均首达时间的上下界的闭合表达式, 下面验证此理论结果.实验中设置如下实验参数:

${{\xi }_{0}}=(x_{1}^{0}, x_{2}^{0}, \ldots , x_{5}^{0})=(3, 3, \ldots , 3)$,

$b=3, {{a}_{i}}=\sqrt{2}, i=0, 1, \ldots , 5$,

$d({{\xi }_{0}})\text{=}15\sqrt{2}$,

固定误差

${{d}_{\min }}(\xi _{\text{opt}}^{t})=0.01$.

对于每个种群λ , 将算法2在超平面上运行100轮.定义 Tdmin(ξoptt)i表示算法2中第i轮在d_min( ξoptt)去心邻域的首达时间, 平均首达时间为:

$E\left( \bar{T}~_{{{d}_{\text{min}}}\ \left( \xi _{\text{opt}}^{t} \ \right)}^{i}|d({{\xi }_{0}}) \right)=\frac{1}{100}\overset{100}{\mathop{\underset{i=1}{\mathop \sum }\, }}\, T~_{{{d}_{\text{min}}}\ \left( \xi _{\text{opt}}^{t} \ \right)}^{i}$.

记理论分析下界为:

$E_{\text{low}}^{2}({{T}_{\tau }}|d({{\xi }_{0}}))=\sqrt{\frac{6\pi}{{{\lambda }^{2}}\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}}~(d({{\xi }_{0}})-{{d}_{\min }}(\xi _{\text{opt}}^{t})-1)$,

理论分析上界为:

$E_{\text{up}}^{2}~({{T}_{\tau }}|d({{\xi }_{0}}))=1+\sqrt{\frac{24\pi}{{{\lambda }^{2}}\left( a_{1}^{2}+a_{2}^{2}+\ldots +a_{5}^{2} \right)}}~(d({{\xi }_{0}})-{{d}_{\min }}(\xi _{\text{opt}}^{t}))$.

表2给出(1, λ )ES在超平面上实际平均首达时间与理论上的时间上下界.从表中可以看出, 随着种群规模λ 不断增长, 实际运行平均首达时间不断减少, 这与理论分析的结果一致.文献[30]通过加性漂移(Additive Drift)分析(1+1)EA在超平面上的计算时间上界, 得到紧致的闭合表达式, 但未关注首达时间下界.同时本文模型将(1+1)EA推广到(1, λ )ES, 得到更通用的结果.

表2

Table 2

表2(Table 2)

表2 五维超平面上理论与实际平均首达时间对比 Table 2 Comparison of theoretical and actual first hitting time on a five-dimensional hyperplane λ $E_{\text{low}}^{2}({{T}_{\tau }}|d({{\xi }_{0}}))$ $E\left( \bar{T}~_{{{d}_{\text{min}}}\left( \xi _{opt}^{t} \ \ \right)}^{i}|d({{\xi }_{0}}) \right)$ $E_{up}^{2}({{T}_{\tau }}|d({{\xi }_{0}}))$ 2 13.87 14.43 30.11 4 6.94 9.36 15.56 6 4.62 7.64 10.70 8 3.47 6.45 8.28 10 2.77 6.38 6.82 12 2.31 5.77 5.85 14 1.98 5.10 5.16 16 1.73 5.21 4.64

表2 五维超平面上理论与实际平均首达时间对比 Table 2 Comparison of theoretical and actual first hitting time on a five-dimensional hyperplane