智能优化算法已经成为当前的研究热点^[1]，被广泛应用于各个领域^[2]. 通过模拟自然界物种的生存进化规律，不同类型的智能优化算法^[3-5]相继被提出，为求解复杂全局优化问题提供了全新思路. 早熟收敛以及收敛效率不高是各种智能优化算法亟需解决的难题^[6]. 对于高维度、多模态复杂优化问题，研究者围绕算法改进策略开展了系列深入研究. 改进方法主要围绕提高粒子个体学习对象多样性和扩展种群不同类型智能进化行为2个方面，通过采用特定知识模型对个体学习进化方向进行引导，或者引入不同算法协同进化实现大幅度提升算法求解性能的目的. Liang等^[7]提出具有典型意义的改进策略，通过引入历史信息指导粒子进化方向，不仅使得个体具有“记忆功能”，而且学习对象更加多样化. 类似地，田瑾^[8]提出的和声粒子群算法、马卫等^[9]提出的改进布谷鸟优化算法，在种群现有进化规则的基础上，采用特定的知识模型引导个体进化方向，目的是让个体在保留自身搜索能力的同时具备改进策略带来的突出优势，提高算法跳出局部最优的概率. 但是，改进策略往往只对特定问题具有良好的优化效果，研究成果缺乏系统的理论分析支撑，可扩展性和通用性不强. 崔晓晖等^[10]将粒子群算法与模拟退火算法相结合，在融合2种算法不同进化策略的基础上协同进化，有效改善算法的全局寻优能力. 但是，不同算法相互结合的形式只是简单融合了不同类型的智能优化算法，合理性需要进一步研究；此外，采用哪些类型的算法进行融合具有主观性，缺乏科学准确的判定规则. 大部分改进策略从算法本身出发，忽略了待求解问题对算法种群多样性的影响. 为了模拟碰撞过程中物体物理属性相互影响的变化过程，提出新的智能优化算法—弹性碰撞优化（elastic collision optimization，ECO）算法，引入改进的核模糊C均值聚类（fuzzy C-means, FCM）算法，从理论角度对算法种群多样性进行动态分析，针对性地提高粒子学习对象的合理性与多样性.

无线传感器网络（WSNs）是由大量低成本、具有无线通信和计算能力的传感器节点组成的自组织网络^[11]，为实时准确收集不同环境中所需的数据提供了可能. 随着WSNs规模不断扩大，需要处理的节点数据呈现爆炸式增长，给大规模WSNs管理带来严峻挑战. 不断成熟的云计算技术为解决WSNs面临的诸多问题开辟了新的研究思路^[12]，诞生了传感云（sensor cloud）系统. 传感云运用云计算技术进行WSNs数据采集、处理与存储，为用户提供全新的用户体验^[13]. 云环境资源调度是云计算关键技术之一，Tian等^[14]设计基于运行成本的云计算资源分配方案，能够确保云提供商效益最大化，但是不适用于动态变化的应用场景. Chohan等 ^[15]提出基于拍卖竞价策略的云资源调度算法，但是计算复杂度高.

传感云的研究处于起步阶段，国内外相关研究相对较少，为此以传感云资源调度为应用背景，在弹性碰撞优化算法研究的基础上，给出具有较高目标收益的传感云资源调度策略，并且利用多维复杂测试函数以及传感云资源调度实例，验证提出的ECO和传感云资源调度方案的有效性.

1 弹性碰撞优化算法

智能优化算法隶属于随机启发式搜索技术范畴，在目标解空间内部署具有一定数量粒子的种群，粒子按照一定规则选择优秀的个体进行学习，使得种群能够向着全局最优解方向进化.

定义1　对于 $n$ 维优化问题 $ < {{S}},f > $ （ ${{S}} \in {\mathbf{R}^n}$ 为解空间， $f$ 为目标函数），存在智能优化算法 $G$ （算法种群 ${P}\left( t \right) = \left\{ {{{X}_1}\left( t \right),{{X}_2}\left( t \right), \cdots ,{{X}_N}\left( t \right)} \right\}$ 由 $N$ 个粒子组成），定义 $G$ 优化求解 $ < {{S}},f > $ 过程为

$ \left.\begin{aligned} & {{{X}}_i}\left( t+1 \right)={ \aleph} \left( {{{X}}_i}\left( t \right),{ \delta} \right),\quad{{{X}}_i}\left( t \right)\in \;{{P}}\left( t \right),\quad{{P}}\left( t \right)\in {{S}}; \\ & {{{X}}_i}=\left( {x_{i1}},{x_{i2}},\cdots ,{x_{in}} \right),\quad i=1,2,\cdots ,{{N}}; \\& {\xi _{j\min} }\leqslant{x_{ij}}\leqslant{\xi _{j\max} }, \quad j=1,2,\cdots ,{{n}}. \end{aligned}\right\}$

(1)

式中：t、 $t + 1$ 为智能优化算法迭代次数， ${\delta }$ 为 ${{\aleph}} $ 搜索过的解， $\left( {{x_{i1}},{x_{i2}}, \cdots ,{x_{in}}} \right)$ 、 $\left( {{\xi _{j\min }},{\xi _{j\max }}} \right)$ 分别为粒子 ${{X}_i}$ 的决策变量和约束变量.

定义2　 G收敛充分非必要条件. 对于算法G，种群 ${P}\left( t \right)$ ， $\left\{ {{P}\left( t \right),\;t = 1,2, \cdots } \right\}$ 构成离散时间随机过程，如果满足（以最小化问题为例）条件：

$ \left.\begin{array}{l}p\left\{ {{P}\left( t \right)\left| {{P}\left( 1 \right),{P}\left( 2 \right), \cdots ,{P}\left( {t - 1} \right)} \right.} \right\} = \\ \quad p\left\{ {{P}\left( t \right)\left| {{P}\left( {t - 1} \right)} \right.} \right\},\\f\left( {\aleph \left( {{{X}_i},{{ \delta}} } \right)} \right) \leqslant f\left({{ \delta}} \right).\end{array}\right\}$

(2)

称 $\aleph $ 依概率1收敛于全局最优解. 对于定义2给出的结论根据马尔科夫链理论进行推导证明.

定义1给出智能优化算法的一般性数学描述，不同类型算法 $\aleph$ 赋予粒子 ${{X}_i}$ 不同的学习对象 ${\delta }$ ，粒子群优化（particle swarm optimization，PSO）算法^[5]选取种群最优解 ${{X}_{{\rm{best}}}}$ 、布谷鸟优化（cuckoo search，CS）算法^[9]随机选取2个不同个体 ${{X}_j}$ 和 ${{X}_k}$ （ $i \ne j \ne k$ ）等等. 大部分算法选择目标函数值优秀个体作为 ${\delta }$ ，但是这种选择方式存在严重缺陷：首先，忽视了 ${\delta }$ 空间位置对迭代进化的影响，导致算法收敛效率不高. 如图1所示，以 $n = 2$ 为例，存在3个不同粒子 ${{X}_1}$ 、 ${{X}_2}$ 和 ${{X}_3}$ ，由于 ${{X}_1}$ 与 ${{X}_3}$ 具有相同的目标函数值，因此 ${{X}_2}$ 以相同概率选取 ${{X}_1}$ 或 ${{X}_3}$ 进行更新. 但是，从图1（b）和（c）可以看出， ${{X}_1}$ 与 ${{X}_3}$ 的空间位置对 ${{X}_2}$ 的进化作用不同，仅仅根据 $f\left( {\delta } \right)$ 选取 ${\delta }$ 具有盲目性，算法收敛速度不高. 其次容易导致早熟现象发生. 同样以图1为例，如果 ${{X}_3}$ 为局部极值点，并且 ${{X}_2}$ 选取 ${{X}_3}$ 进行更新，由于 ${{X}_1}$ 与 ${{X}_3}$ 位置相对较近， ${{X}_1}$ 很难摆脱 ${{X}_3}$ 的吸引力，使得 ${{X}_1}$ 陷入局部最优，发生早熟现象. 针对上述问题，模拟物体碰撞现象，提出ECO，并且利用模糊聚类对种群进行聚类分析，使得粒子在选取学习对象时更加具有针对性和合理性.

1.1 ECO算法粒子更新机制的模拟抽象

弹性碰撞融合了不同物体物理属性相互影响的变化过程，某种意义上来说碰撞过程具有一定的学习能力. 虽然碰撞后2个物体的动量变化的绝对值相同，但是碰撞前动量大的物体较大地影响了动量小的物体的空间位置，因此可以将弹性碰撞过程抽象为智能算法的粒子进化更新过程，对对心完全弹性（complete elastic，CE）碰撞、完全非弹性（complete inelastic，CI）碰撞和非完全弹性（non complete elastic，NCE）碰撞3种情形进行研究，分别将物体速度 $v$ 和物体质量 $m$ 抽象为粒子目标函数值 $f\left( {X} \right)$ 和单位质量“1”.

定义3　碰撞更新. 对于粒子 ${{X}_i}$ （ ${{X}_i}$ 代表问题的一个解，分布于优化问题的解空间内，可以抽象为解空间内处于某个位置的单位质量物体），设定 ${\delta } = \left\{ {{X}'} \right\}$ （ ${X}' \in {P}\left( t \right) \wedge {X}' \ne {{X}_i}$ ）， ${{X}_i}$ 与 ${X}'$ 分别以速度 $f\left( {{{X}_i}} \right)$ 和 $f\left( {{X}'} \right)$ 相向运动， $\Delta t$ 时刻发生碰撞，随后又经 $\Delta t$ 时刻 ${{X}_i}$ 到达新的位置 ${{X}}_{i,{\rm{new}}}$ .

${{X}}_{i,{\rm{new}}}$ 推导过程（以最大化问题为例）如下. 对于完全弹性碰撞，根据动量守恒和能量守恒定律：

$\begin{aligned}\quad\quad\quad\quad\;\;\;{\rm{CE}}: \end{aligned}$

$\begin{aligned}\left. \begin{aligned} &mf\left( {{{{X}}_i}} \right) + mf\left( {{{X}}'} \right) = mf\left( {{{{X}}_{i,{\rm{new}}}}} \right) + mf\left( {{{{{X}}'}_{{\mathop{\rm \! \! \! \! new}\nolimits} }}} \right),\\ & \frac{1}{2}m{\left[ {f\left( {{{{X}}_i}} \right)} \right]^2} + \frac{1}{2}m{\left[ {f\left( {{{X}}'} \right)} \right]^2} = \\ & \quad\quad\;\; \frac{1}{2}m{\left[ {f\left( {{{{X}}_{i,{\rm{new}}}}} \right)} \right]^2} + \frac{1}{2}m{\left[ {f\left( {{{{{X}}'}_{{\rm{\!\!\!\!new}}}}} \right)} \right]^2},\end{aligned}\right\} \\\end{aligned}$

(3)

则

$\begin{aligned}{{{X}}_{i,{\rm {new}}}} = & {\rm CE}\left( {{{{X}}_i},{{X}}'} \right) = \\ &{{{X}}_i}\displaystyle\frac{{2f\left( {{{X}}'} \right)}}{{f\left( {{{X}}'} \right) + f\left( {{{{X}}_i}} \right)}} + {{X}}'\displaystyle\frac{{f\left( {{{{X}}_i}} \right) - f\left( {{{X}}'} \right)}}{{f\left( {{{X}}'} \right) + f\left( {{{{X}}_i}} \right)}}.\end{aligned}$

同理，对于完全非弹性碰撞和非完全弹性碰撞：

CI：

$\begin{array}{l}mf\left( {{{{X}}_i}} \right) + mf\left( {{{X}}'} \right) = 2mf\left( {{{{X}}_{i,{\rm{new}}}}} \right),\\{{{X}}_{i,{\rm{new}}}} = {\rm{CI}}\left( {{{{X}}_i},{{X}}'} \right) = \\\;\;\;\;{{{X}}_i}\displaystyle\frac{{3f\left( {{{X}}'} \right) - f\left( {{{{X}}_i}} \right)}}{{2\left( {f\left( {{{X}}'} \right) + f\left( {{{{X}}_i}} \right)} \right)}} + {{X}}'\displaystyle\frac{{3f\left( {{{{X}}_i}} \right) - f\left( {{{X}}'} \right)}}{{2\left( {f\left( {{{X}}'} \right) + f\left( {{{{X}}_i}} \right)} \right)}}.\end{array}$

(4)

NCE：

${{X}}_{i,{\rm{new}}}= {\rm{NCE}}\left( {{{X}_i},{X}'} \right) = \beta {\rm{CE}}\left( {{{X}_i},{X}'} \right);\; \beta \in \left( {0,1.0} \right).$

(5)

式（3）~（5）给出3种不同碰撞更新策略，为粒子提供了多种学习策略. 为了进一步改善算法收敛效率，保持种群样本多样性，定义ECO算法粒子更新策略如下.

定义4　ECO算法粒子更新. 在ECO算法中，对于粒子 ${{X}_i}\left( t \right)$ ，更新机制定义为

${{X}_i}\left( {t + 1} \right) = \left\{ \begin{aligned}&{\rm{ECO}}\left( {{{X}_i}\left( t \right),{\delta }} \right),\quad{r_1} \geqslant \varepsilon ; \\&{{X}_i}\left( t \right),\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{r_1} < \varepsilon . \\ \end{aligned}\quad\quad\quad \right.$

(6)

$\begin{array}{l}{\rm{ECO}}\left( {{{{X}}_i}\left( t \right),{{\delta}} } \right) = \\\left\{ \begin{aligned}&{\rm{CE}}\left( {{{{X}}_i}\left( t \right),{{{G}}_i}\left( t \right)} \right),\;\;\;{r_2} \leqslant 0.5 ;\\&{\rm{CI}}\left( {{{{X}}_i}\left( t \right),{{B}}\left( t \right)} \right),\;\;\;\;\;0.5 <{r_2} \leqslant 0.5 + \xi ;\\&\alpha \left[{\rm{CE}}{\left( {{{{X}}_i}\left( t \right),{{{X}}_j}\left( t \right)} \right) + {\rm{CI}}\left( {{{{X}}_i}\left( t \right),{{{X}}_k}\left( t \right)} \right)} \right],\;{\text{其他}}.\end{aligned} \right.\end{array}$

(7)

式中： $\varepsilon \in \left( {0,1.0} \right)$ 、 $\xi \in \left( {0,0.5} \right)$ 为更新系数， ${{G}_i}\left( t \right)$ 为 ${{X}_i}\left( t \right)$ 历史最优解， ${B}\left( t \right)$ 为种群最优解， ${r_1} \in \left( {0,1.0} \right)$ 、 ${r_2} \in \left( {0,1.0} \right)$ 、 $\alpha \in \left( {0,0.5} \right)$ 为随机数.

从定义4可以看出，ECO更新过程实质是模拟弹性碰撞3种物理现象，而不是弹性碰撞恰好处于完全弹性碰撞和完全非弹性碰撞之间. 由于CE和CI具有明确的推导公式，因此引入比例系数可以将CE和CI转化为NCE. ECO更新涉及2个参数，算法实现相对简单，并且ECO以概率1–ε进行更新，更新策略融合3种碰撞更新机制，粒子分别在CE条件下“与种群最优碰撞”，使得粒子快速向种群最优解学习，提高算法进化速度；在CI条件下“与自身历史最优碰撞”，粒子增大逃离过去最优解的可能，增大算法跳出局部最优的概率；“随机碰撞”有效扩展了粒子学习空间，提高了群体样本多样性，算法收敛性能明显改善.

1.2 自适应核FCM模糊聚类算法

FCM是目前应用最为广泛的聚类算法之一，通过隶属度矩阵 ${U} = {\left[ {\mu _{ik}^{}} \right]_{C \times N}}$ 来描述样本个体属于某个分类的程度，将 $N$ 个样本划分为 $C$ 个分类^[16]. FCM使用欧氏距离评价相似度，仅适用于紧致度与离散度较好的数据. 为了扩大适用范围，引入核FCM聚类算法（kernel fuzzy C-means，KFCM），用内核诱导距离替换传统欧式距离. 虽然KFCM采用了内核诱导距离，提高了算法应用范围，但是需要事先设定聚类数目 $C$ ，然而大部分情况是事先并不知道数据样本分布情况. 为此，设计自适应KFCM（adaptive kernel fuzzy C-means，AKFCM）算法，根据隶属度信息“迭代比对”实现样本数据自动最佳聚类划分，具体实现过程如下.

定义5　迭代比对矩阵. 当聚类数为 $c$ （ $2 \leqslant c \leqslant {C_{\max }}$ ）时，采用KFCM对数据集合 $\left\{ {{{X}_1},{{X}_2}, \cdots ,{{X}_N}} \right\}$ 进行聚类分析并得到 ${{U}} = {\left[ {\mu _{ik}^c} \right]_{c \times N}}$ 和 $c$ 个分类 $\left\{ {{L_1},{L_2}, \cdots ,{L_c}} \right\}$ . 对于数据 ${{X}_i}$ ，令 $\mu _i^c = \mathop {\max }\limits_{k = 1}^c\; \left\{ {\mu _{ik}^c} \right\}$ ，定义迭代比对矩阵为

${{O}_{N \times N}} = {\left[ {{O_{ij}}} \right]_{N \times N}} = \sum\limits_{c = 2}^{{C_{\max }}} {{O}_{N \times N}^c} ,$

(8)

$\begin{aligned} & { O}_{N\times N}^{c}={{\left[ o_{ij}^{c} \right]}_{N\times N}}, \\ & o_{ij}^{c}=\left\{ \begin{aligned} & \mu _{i}^{c} \mu _{j}^{c},\;\;\;{{X}_{i}}\;,\;{{X}_{j}}\in {{L}_{k}};\\ & 0,\;\;\;\;\;\;\;\;\;{\text{其他}}, \\ &\end{aligned} \right. \\ &{ O}_{N\times N}^{c}=\left[ \begin{aligned} \,\,& 0 & o_{12}^{c} &\quad \cdots & o_{1N}^{c} \\ & o_{21}^{c} & 0\,\,\, &\quad \cdots & o_{2N}^{c} \\ & \,\,\,\,\vdots & \vdots\,\,\,\, &\quad {} & \vdots \;\;\; \\ & o_{N1}^{c} & o_{N2}^{c} & \quad\cdots & 0 \;\; \end{aligned} \right]. \end{aligned}$

(9)

从定义5可以看出， ${{{{O}}}_{N\times N}}$ 为对称矩阵，矩阵内每个元素反映了数据 ${ X}_i$ 与 ${ X}_j$ 在不同分类大小下隶属度累积 ${{{{O}}}_{ij}}=\sum{_{c=2}^{{{C}_{\max }}}}{o_{ij}^{c}}$ 大小，2个数据越相似， ${{{{O}}}_{ij}}$ 越大。依次对隶属度累积进行“减1”操作， ${{{{O}}}_{N\times N}}$ 内隶属度累积值小的元素更快地趋于0，表明相似度强的数据在任何聚类数目下都具有较大的相似度。为了便于迭代比对，设定相对度阈值， ${{\mu }_{\min }}$ 并且根据 ${{\mu }_{\min }}$ 对 ${{{{O}}}_{N\times N}}$ 进行处理：

$\begin{split}&{{O}'_{N \times N}} = {\left[ {{{O'}_{\!\!\!\!ij}}} \right]_{N \times N}},\\&O'_{ij} = \left\{ \begin{aligned}&\left\lceil{{O_{ij}}}\right\rceil ,\;{\rm{}}\;{O_{ij}} \geqslant \left( {{C_{\max }} - 1} \right){\mu _{\min }};\\& 0,\;\;\;\;\;\;\;\,{\text{其他}}. \\ \end{aligned} \right.\end{split}$

(10)

从式（10）可以看出， ${\mu _{\min }}$ 反映了 $o_{ij}^c$ 均值大小，只有当 $o_{ij}^c$ 均值不小于 ${\mu _{\min }}$ 时，2个个体隶属于同一分类. 判定准则与实际情况相符，聚类的目的是使得同类内个体具有更多的相同性，不同类个体具有更大的差异性.

AKFCM实现过程如下. 如图2所示为具体实例说明.

输入：KFCM初始化， $\left\{ {{{X}_1},{{X}_2}, \cdots ,{{X}_N}} \right\}$ ， ${C_{\max }}$

输出：最佳聚类结果

1. for $c = 2:{C_{\max }}$ do

2. 利用KFCM将 $\left\{ {{{X}_1},{{X}_2}, \cdots ,{{X}_N}} \right\}$ 进行 $c$ 类划分，并根　　　据定义5得到 ${{O}}_{N \times N}^c$ ；

3. end for

4. 根据式（9）得到迭代比对矩阵 ${{{O}}_{N \times N}}$ ，并根据式　　　　（10）得到 ${{{O}}'_{N \times N}}$ ；

5. while ( ${{{O}}'_{N \times N}} \ne {\bf{0}}$ )

6. {

7. $\left\{ {{L_1},{L_2}, \cdots ,{L_N}} \right\} \leftarrow \left\{ {0, \cdots ,0} \right\}$ ， $t \leftarrow 1$ ，集合 $J = 0$ ；

8. for $i = 1:N$ do

9. for $j = 1:N$ do

10. if ( $i = 1$ and ${O'_{ij}} \ne 0$ )　 ${L_i} \leftarrow {L_i} + \left\{ {O'_{ij}} \right\}$

11. 将 ${O'_{ij}}$ 对应列序号 $j$ 记录到 $J$ 中；

12. else if ( $i \in J$ )　 ${L_i} \leftarrow 0$

13. else if ( ${O'_{ij}} \ne 0$ and ${O'_{1j}} = 0$ and ${O'_{2j}} = 0$ ···and 　　　　 ${O'_{\left( {i - 1} \right)j}} = 0$ )　 ${L_i} \leftarrow {L_i} + \left\{ {{{O'}_{ij}}} \right\}$

14. 将 ${O'_{ij}}$ 对应列序号 $j$ 记录到 $J$ 中；

15. end for

16. end for

17. 更新 $\left\{ {{L_1},{L_2}, \cdots ,{L_N}} \right\}$ ，筛选去非空 ${L_k}( {k = 1,}$ ${2, \cdots ,N} )$ ，　　　并记录当前非空 ${L_k}$ 个数为 ${\rm C{N}_t}$ ；

18. 对 ${{ O}'_{N \times N}}$ 内所有非0元素进行“减1”操作， $t \leftarrow t + 1$ ；

19. }

20. $\left\{ {C{N_t}} \right\}$ 序列中相同数字最多的数即为最佳聚类　　　个数。

1.3 ECO算法实现与种群样本多样性分析

为了提高ECO粒子学习对象的合理性和针对性，将AKFCM算法引入ECO算法中，在每次迭代更新前对种群进行聚类分析，并且根据聚类结果合理选取粒子学习对象. $t$ 时刻，利用AKFCM将 ${P}\left( t \right)$ 自动划分为 $c$ 个分类，对于粒子 ${{X}_i}\left( t \right)$ ， ${B}\left( t \right)$ 选取当前种群适应度最优解下，且与 ${{X}_i}\left( t \right)$ 不在同一分类的个体，记为 ${B}'\left( t \right)$ ， ${{X}_j}\left( t \right)$ 、 ${{X}_k}\left( t \right)$ 随机选取与 ${{X}_i}\left( t \right)$ 不在同一分类的个体 ${{X}'_j}\left( t \right)$ 和 ${{X}'_k}\left( t \right)$ .

ECO算法实现过程如下.

输入：目标函数 $f\left( \cdot \right)$ 、种群规模N、算法相关参数、 ${T_{\max }}$

输出： ${{X}_{{\rm{best}}}}$ （种群最优解）

1. 在解空间内随机生成群体 ${{P}}\left( 0 \right)$ ， $t \leftarrow 1$ ；

2. while ( $t \leqslant {T_{\max }}$ )

3. {

4. 利用AKFCM算法对 ${{P}}\left( 0 \right)$ 聚类分析；

5. for $i = 1:N$ 　do

6. 根据聚类结果为 ${{X}_i}\left( t \right)$ 选取 $B'\left( t \right)$ 、 ${{X}'_j}\left( t \right)$ 、 ${{X}'_k}\left( t \right)$ ，根　　　据式（6）和（7）对 ${{X}_i}\left( t \right)$ 更新；

7. 如果 $f\left( {{{X}_i}\left( {t + 1} \right)} \right) \leqslant f\left( {{{X}_i}\left( t \right)} \right)$ ，用新得到的粒子替换　　　 ${{X}_i}\left( t \right)$ ；否则保持 ${{X}_i}\left( t \right)$ 不变；

8. 更新 ${{X}_i}\left( t \right)$ 历史最优解 ${{{G}}_i}\left( t \right)$ ；

9. end for

10. 更新种群最优解 ${{X}_{{\rm{best}}}}\left( t \right)$ ， $t \leftarrow t + 1$ ；

11. }

12. 种群最优解 ${{X}_{{\rm{best}}}}$ 即为目标函数最优解.

1.3.1 ECO算法全局收敛性

ECO在迭代进化过程中保留了优秀个体，ECO算法满足定义2的收敛充分非必要条件，因此ECO算法具有全局收敛性. 具体证明过程如下.

证明：令 ${Z}\left( {{P}\left( t \right)} \right)$ 为 ${P}\left( t \right)$ 内最优解个数. 对于ECO更新，显然有 ${Z}\left( {{P}\left( {t + 1} \right)} \right) \geqslant {Z}\left( {{P}\left( t \right)} \right)$ ，即 $\left\{ {{Z}\left( {{P}\left( 0 \right)} \right), \cdots ,{Z}\left( {{P}\left( t \right)} \right)} \right\}$ 是单调不递减的.

$p\left( {{Z}\left( {{P}\left( t \right)} \right) > 0\left| {{Z}\left( {{P}\left( {t - 1} \right)} \right) > 0} \right.} \right) > 0,\;\forall t \geqslant 1.$

(11)

设t时刻 ${Z}\left( {{P}\left( t \right)} \right) = 0$ 的概率为 $p\left( {{Z}\left( {{P}\left( t \right)} \right) = 0} \right)$ ，由于P(t)为马尔科夫链，因此根据条件概率公式可以得到：

$\begin{split} &p( {{Z}}{\left( {{ P}\left( {t + 1} \right)} \right) = 0} ) =\\ &p\left({{Z}} {\left( {{ P}\left( {t + 1} \right)} \right) \!=\! 0\left| {{Z}}{\left( {{ P}\left( t \right)} \right) \!=\! 0} \right.} \right) \! \times p\left( {{Z}}{\left( {{ P}\left( t \right)} \right) = 0} \right) +\\ &p\left({{Z}} {\left( {{ P}\left( {t + 1} \right)} \right) = 0\left| {{Z}}{\left( {{ P}\left( t \right)} \right) \ne 0} \right.} \right) \times p\left( {{Z}}{\left( {{ P}\left( t \right)} \right) \ne 0} \right).\end{split}$

(12)

根据式（11）可知 $p\left( {{Z}\left( {{P}\left( {t + 1} \right)} \right) = 0\left| {{Z}\left( {{P}\left( t \right)} \right) \ne 0} \right.} \right) = 0,$

$\begin{split}p(& {Z}( {{P}( {t + 1}) )} = 0 ) = \\ &p( {Z}( {{P}( {t + 1} )}) = 0| {Z}( {{P}( t )} ) = 0 )\times p( {{Z}( {{P}( t )} ) = 0} ).\end{split}$

(13)

根据式（11）可知，对于 $\forall t \geqslant 1$ ，有一个足够小的正实数 $\gamma $ 使得 $p\left( {{Z}\left( {{P}\left( t \right)} \right) > 0\left| {{Z}\left( {{P}\left( {t - 1} \right)} \right) = 0} \right.} \right) > \gamma $ 成立，

$\begin{aligned}& p\left( {{Z}\left( {{P}\left( {t + 1} \right)} \right) = 0\left| {{Z}\left( {{P}\left( t \right)} \right) = 0} \right.} \right) =\\ & \quad 1 - p\left( {{Z}\left( {{P}\left( {t + 1} \right)} \right) > 0\left| {{Z}\left( {{P}\left( t \right)} \right) = 0} \right.} \right) \leqslant 1 - \gamma .\end{aligned}$

(14)

联立式（13）、（14）可以得到

$\begin{gathered}\!\!\!\!\!\!p\left( {{Z}\left( {{P}\left( {t + 1} \right)} \right) = 0} \right) \leqslant \left( {1 - \gamma } \right)p\left( {{Z}\left( {{P}\left( t \right)} \right) = 0} \right) ,\\ \!\!\!\!\!\!p\left( {{Z}\left( {{P}\left( {t + 1} \right)} \right) = 0} \right) \leqslant \cdots \leqslant {\left( {1 - \gamma } \right)^{t + 1}}p\left( {{Z}\left( {{P}\left( 0 \right)} \right) = 0} \right). \\ \end{gathered} $

(15)

当 $t \to \infty $ 时， $\mathop {\lim }\limits_{t \to \infty } {\left( {1 - \gamma } \right)^{t + 1}} = 0$ ，所以有 $p\left( {{Z}\left( {{P}\left( {t + 1} \right)} \right) = 0} \right) \leqslant 0$ ，由于 $p\left( {{Z}\left( {{P}\left( {t + 1} \right)} \right) = 0} \right)$ 表示概率值，因此有

$\mathop {\lim }\limits_{t \to \infty } p\left( {{Z}\left( {{P}\left( {t + 1} \right)} \right) = 0} \right) = 0.$

(16)

根据式（16），随着算法不断运行， ${P}\left( t \right)$ 不含有最优解的概率为0，表明ECO算法以概率1收敛于全局最优解.

证毕.

1.3.2 ECO算法计算复杂度

ECO种群初始化复杂度为 $O\left( {nN} \right)$ ，KFCM每次迭代复杂度为 $T\left( {{C_{\max }} - 1} \right)O\left( N \right)$ （T为KFCM迭代次数），AKFCM每次迭代复杂度为 $QO\left( {{N^2}} \right)$ （ $Q$ 为AKFCM迭代次数，显然 $2 \leqslant Q \leqslant {C_{\max }} - 1$ ），每次迭代的粒子更新复杂度为 $O\left( {nN} \right)$ ，因此ECO复杂度为 $O\left( {nN} \right)+{T_{\max }}$ $\left[ {T\left( {{C_{\max }} - 1} \right)O\left( N \right) + QO\left( {{N^2}} \right) + O\left( {nN} \right)} \right]$ = $\left( {{T_{\max }} + 1} \right)O\left( {nN} \right)$ + ${T_{\max }}\left[ {T\left( {{C_{\max }} - 1} \right)O\left( N \right) + QO\left( {{N^2}} \right)} \right]$ . 由于通常 $n \ll N,$

$\begin{aligned}&\left( {{T_{\max }} + 1} \right)O\left( {nN} \right)+{T_{\max }}[ {T\left( {{C_{\max }} - 1} \right)} O\left( N \right) + \left.QO\left( {N^2} \right)\right] \approx\\ &{T_{\max }}QO\left( {{N^2}} \right).\end{aligned}$

式中：T_max为KFCM最大迭代次数。

1.3.3 ECO算法种群多样性

引入AKFCM能够增加种群样本多样性，而且有效避免算法陷入局部最优，为了定量分析算法种群样本多样性，给出ECO多样性评价指标.

定义6　定义ECO算法群体多样性评价指标 $\varGamma \left( {{P}\left( t \right)} \right)$ 为

${\varGamma} \left( {{P}\left( t \right)} \right) = \frac{1}{{Nn}}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^n {{{\left[ {{x_{ij}}\left( t \right) - \frac{1}{N}\sum\limits_{i = 1}^N {{x_{ij}}\left( t \right)} } \right]}^2}} } .$

(17)

式中：x_ij(t)为粒子更新函数。

定理1　ECO算法能够有效保持群体多样性.

证明：由式（11）可知， $\varGamma \left( {{P}\left( t \right)} \right)$ 的数学期望值为 $\left({\text{令}}\overline {{x_j}\left( t \right)} = \left.\left[ {\displaystyle\sum\limits_{i = 1}^N {{x_{ij}}\left( t \right)} } \right]\right/N\right)$

$\begin{split}E&\left[ {{{P}}\left( t \right)} \right] = \frac{1}{{Nn}}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^n {E{{\left[ {{x_{ij}}\left( t \right) - \overline {{x_j}\left( t \right)} } \right]}^2}} } = \\ &\frac{1}{{Nn}}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^n {E{{\left[ ({{x_{ij}}\left( t \right) \!-\! E{x_{ij}}\left( t \right)) + (E{x_{ij}}\left( t \right)\! -\! {\overline {{x_j}\left( t \right)})} } \right]}^2}} }\!=\! \\ &\frac{1}{{Nn}}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^n {\left\{ {E{{\left[ {{x_{ij}}\left( t \right) - E{x_{ij}}\left( t \right)} \right]}^2} - } \right.} } \\ &2E \left( {\left[ {{x_{ij}}\left( t \right) - E{x_{ij}}\left( t \right)} \right]\left[ {E{x_{ij}}\left( t \right) - \overline {{x_j}\left( t \right)} } \right]} \right) + \\ &\left. {E{{\left[ {E{x_{ij}}\left( t \right) - \overline {{x_j}\left( t \right)} } \right]}^2}} \right\}.\quad\quad\quad\quad\quad\quad\quad\quad\quad(18)\end{split}$

令 $\sigma _{ij}^2\left( t \right) = E{\left[ {{x_{ij}}\left( t \right) - E{x_{ij}}\left( t \right)} \right]^2}$ ，有

$\left.\begin{aligned}& \begin{aligned}&\left. E\left( {\left[ {{x_{ij}}\left( t \right) - E{x_{ij}}\left( t \right)} \right]\left[ {E{x_{ij}}\left( t \right) - \overline {{x_j}\left( t \right)} } \right]} \right) = \sigma _{ij}^2\left( t \right) \right/N,\\ & E{\left[ {\overline {{x_j}\left( t \right)} - E{x_{ij}}\left( t \right)} \right]^2} = \frac{1}{N}\sum\limits_{k = 1}^N {\sigma _{kj}^2\left( t \right)} + \\ & \quad\quad\quad\quad\quad\quad\quad\quad\;{\left[ {E{x_{kj}}\left( t \right) - \frac{1}{N}\sum\limits_{k = 1}^N {E{x_{kj}}\left( t \right)} } \right]^2},\end{aligned}\\ &E\left[ { {{{P}}\left( t \right)} } \right] = \frac{{N - 1}}{{{N^2}n}}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^n {\sigma _{ij}^2} } \left( t \right) + \varGamma \left( {E{x_{ij}}\left( t \right)} \right).\end{aligned}\right\}$

(19)

式中： $\varGamma \left( {E{x_{ij}}\left( t \right)} \right)$ 为 $E{x_{ij}}\left( t \right)$ 的多样性. 从式（19）可以看出，ECO群体多样性期望值与 $\sigma _{ij}^2\left( t \right)$ 有关，采用AKFCM对群体进行聚类分析，粒子在更新过程中选择差异性较大的个体进行学习，ECO算法相比于其他智能优化算法具有更好的群体多样性.

证毕.

2 传感云资源调度 2.1 问题描述与模型构建

Tan^[17]将传感云定义为WSNs云端服务平台，有机结合多种传感网络应用与云端，为用户提供远程控制、监测等云端服务. 传感云的出现改变了传统WSNs数据采集处理模式，WSNs只需要负责采集数据，而数据处理、分析等任务由云端完成. 传感云资源调度的目的是合理地为多个传感器网络服务请求配置云计算资源，并且使得效益最大化. 由于云资源架构的异构性，不同服务器处理相同任务的能耗和时长不同，并且研究表明系统能耗已经成为云端运营最大的开销，因此基于系统能耗和任务调度的传感云资源调度研究具有重要意义.

对于 $m$ 个任务集 ${{V}}= \left\{ {{v_i}} \right\},\; i = 1,2, \cdots ,m$ ， ${v_i}$ 的任务长度为 ${l_i}$ ，根据任务前驱和后继关系，定义 ${{Z}}\left( i \right)$ 、 ${{Y}}\left( i \right)$ 分别为 ${v_i}$ 的直接前驱任务集和直接后继任务集，如果 ${v_i}$ 与 ${v_j}$ 通信需求为 ${w_{ij}}$ ，定义通信矩阵 ${{E}_{m \times m}} = {\left[ {{w_{ij}}} \right]_{m \times m}}$ . 对于传感云系统计算资源集合 ${{K}} = \left\{ {{k_i}} \right\},\; i = 1,2, \cdots ,g$ ， ${k_i}$ 的服务速度为 ${I_i}$ 、功率为 $\left( {{P_{i,{\rm{work}}}},{P_{i,{\rm{low}}}}} \right)$ （ ${P_{i,{\rm{work}}}}$ 、 ${P_{i,{\rm{low}}}}$ 分别为执行任务和空闲时功率）、通信准备时间为 ${T_i}$ ， ${k_i}$ 与 ${k_j}$ 通信速度为 ${q_{ij}}$ . 定义调度决策变量 ${x_{ij}}$ ，如果 ${v_i}$ 被安排至 ${k_j}$ 执行，则 ${x_{ij}} = 1$ ，否则 ${x_{ij}} = 0$ .

定义7　定义传感云资源调度模型为在满足约束条件下，将任务集合 ${{V}}$ 调度分配到云资源集合 ${{K}}$ 上，使得调度优化函数 $f\left( {{V},{{K}}} \right)$ 达到最优.

$\begin{split}&f\left( {{{V}},{K}} \right):\min \; \left\{ {{\rm{WT}},{\rm{WE}}} \right\};\\&\left.{\rm{s.t.}} \begin{array}{l}\displaystyle\sum\limits_{j = 1}^g {{x_{ij}}} = 1,\; i = 1,2, \cdots ,m,\\{T_{\rm{st}}}\left( i \right) \geqslant {T_{\rm{fi}}}\left( j \right),\;{\rm{if}}\;{v_j} \in {{Z}}\left( i \right).\end{array}\right\}\end{split}$

(20)

式中： ${\rm{WT}}$ 和 ${\rm{WE}}$ 分别为系统任务执行时间和系统能耗， ${T_{{\rm{st}}}}\left( i \right)$ 、 ${T_{{\rm{fi}}}}\left( i \right)$ 分别为任务开始执行时间和任务执行结束时间.

推导1 设定任务 ${v_i}$ 被调度至 $\;{k_a}\;$ 处理， ${v_i}$ 任务开始时间为

${T_{{\rm{st}}}}\left( i \right) = \left\{ \begin{aligned}&{\max} \; \left( {{T_a},\mathop {\max }\limits_{{v_j} \in {{Z}}\left( i \right)} \Big( {{T_{{\rm{fi}}}}\left( j \right) + {T_{{\rm{con}}}}\left( {i,j} \right)} \Big)} \right),\; {{Z}}\left( i \right) \ne {\bf 0}; \\& 0,\quad{{Z}}\left( i \right) = {\bf 0}. \\ \end{aligned} \right.$

(21)

式中： ${T_{{\rm{fi}}}}\left( j \right)$ 为 ${v_j}$ 执行结束时间， ${T_{{\rm{con}}}}\left( {i,j} \right)$ 为 ${v_i}$ 与 ${v_j}$ 通信时间. 如果 ${v_j}$ 被调度至 ${k_b}$ 处理，

${T_{{\rm{con}}}}\left( {i,j} \right) = \left\{ \begin{aligned}& {T_a} + {w_{ab}}/{q_{ab}},\quad &a \ne b; \\&0,\quad &a = b. \\ \end{aligned} \right.$

(22)

式中：w_ab为任务之间通信传输数据量，q_ab为任务之间通信传输速率。

${v_i}$ 在 ${k_a}$ 处理时间为

${T_{{\rm{wor}}}}\left( {i,a} \right) = {l_i}/{I_a}.$

(23)

联立式(23)后得到

$\begin{aligned}{T_{{\rm{fi}}}}\left( i \right) = {T_{{\rm{st}}}}\left( i \right) + {T_{{\rm{wor}}}}\left( {i,a} \right), \end{aligned}$

(24)

则

$\begin{aligned}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\rm{WT}} = \mathop {\max }\limits_{i = 1}^m \;\left( {{T_{{\rm{fi}}}}\left( i \right)} \right).\end{aligned}$

推导2 系统能耗分为执行任务能耗 ${{\rm{WE}}_{{\rm{on}}}}$ 和空闲能耗 ${{\rm{WE}}_{{\rm{off}}}}$ . 如果 ${k_i}$ 执行 ${v_i}$ 任务，

${{\rm{WE}}_{{\rm{on}}}}\left( i \right) = \sum\limits_{{v_i}} {\left( {{l_i}/{I_i}} \right)} {P_{i,\operatorname{work} }},$

(25)

${{\rm{WE}}_{{\rm{off}}}}\left( i \right) = \left( {{\rm{WT}} - \sum\limits_{{v_i}} {\left( {{l_i}/{I_i}} \right)} } \right) {P_{i,{\rm{low}}}}.$

(26)

联立式（25）、（26）得到

$\begin{gathered}{\rm{WE}} = \sum\limits_{i = 1}^g {\left( {{\rm W{E}_{{\rm{on}}}}\left( i \right) + {\rm W{E}_{{\rm{off}}}}\left( i \right)} \right)},\end{gathered} $

(27)

则

$\begin{split}{\rm{WE}} =& \sum\limits_{i = 1}^g {\sum\limits_{{v_i}} {\left( {{l_i}/{I_i}} \right)} {P_{i,{\rm{work}}}}} +\\ &\sum\limits_{i = 1}^g {\left( {{\rm{WT}} - \sum\limits_{{v_i}} {\left( {{l_i}/{I_i}} \right)} } \right) {P_{i,{\rm{low}}}}} . \end{split}$

(27)

确定 ${\rm{WT}}$ 与 ${\rm{WE}}$ 计算公式后，调度优化函数 $f\left( {{V},{K}} \right)$ 包含2个优化目标，采用多目标ECO算法进行求解，提供多种决策方案.

2.2 传感云资源调度实现

传感云资源调度问题属于多目标离散优化问题，因此在Pareto最优解方法的基础上，对粒子编码和更新过程进行离散化处理，并且提出多目标离散ECO（multi-objective discrete ECO，MDECO）算法.

定义8　Pareto最优解. 对于 ${{X}_i}$ 和 ${{X}_j}$ ，如果满足

${f_1}\left( {{{X}_i}} \right) \leqslant {f_1}\left( {{{X}_j}} \right) \wedge {f_2}\left( {{{X}_i}} \right) \leqslant {f_2}\left( {{{X}_j}} \right),$

(28)

称 ${{X}_i}$ 支配 ${{X}_j}$ （记 ${{X}_i} > {{X}_j}$ ）. 如果满足 ${{X}^{*}}\in {{X}_{i}}:{{X}_{i}}> {{X}^{*}}{\text{，}} $ 称 ${{X}^{*}} $ 为Pareto最优解，由 ${{X}^*}$ 组成的解集称为Pareto最优解集.

定义9　MDECO离散编码. 对于MDECO算法粒子 ${{X}_i}$ ，当 $g \ll m$ 时，定义编码方式为

${{X}_i} = \left( {{v_1},{v_2}, \cdots ,{v_m},\overbrace {0, \cdots ,0}^{g\left\lceil {m/g} \right\rceil - m}} \right).$

(29)

式中： ${{X}_i}$ 内0元素个数为 $g \left\lceil {m/g} \right\rceil - m$ . ${{X}_i}$ 代表了可能的任务调度方案，为了将任务与云资源一一对应，对 ${{X}_i}$ 内元素序列进行 $\left\lceil {m/g} \right\rceil $ 块均等分割，每块子序列依次对应云资源 ${K} = \left\{ {{k_i}} \right\}$ . 图3为任务调度分配示意图.

从图3列举实例可以看出， $m = 8$ 、 $g = 3$ ，需要在 ${{X}_i}$ 内添加1个“0”元素. 将 ${{X}_i}$ 进行三等分，可以得到 ${k_1}$ 、 ${k_2}$ 、 ${k_3}$ ，执行任务序列为 ${k_1}:{v_2},{v_7},{v_6}$ 、 ${k_2}:{v_3},{v_8}$ 和 ${k_3}:{v_1},{v_4},{v_5}$ .

离散粒子更新　对于采用“定义9”编码形式的粒子A、B、C，给出C更新公式为

${C} = \left\{ {b \otimes \left( {{A} \odot {B}} \right)} \right\} \to {A}.$

(30)

式中： $\left( {{A} \odot {B}} \right)$ 为筛选A中与B对应编码不同的编码位， $b \otimes \left( {{A} \odot {B}} \right)$ 为随机选择b个A中与B对应编码不同的编码位， $\left\{ {b \otimes \left( {{A} \odot {B}} \right)} \right\} \to {A}$ 为将A中b个不同编码随机调换位置.

定义10　定义MDECO粒子更新公式为

${{X}_i}\left( {t + 1} \right) = \left\{ \begin{aligned} &{\rm{MDECO}}\left( {{{X}_i}\left( t \right),{\delta }} \right),\;&{r_1} \geqslant \varepsilon ; \\ &{{X}_i}\left( t \right), &{r_1} < \varepsilon , \end{aligned} \right.$

(31)

$\begin{array}{l}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\rm{MDECO}}\left( {{{X}_i}\left( t \right),{\delta } } \right) = \\\left\{ \begin{aligned}& \left\{ {\varphi \left( {1 - f\left( {{{G}_i}} \right)/\left( {f\left( {{{X}_i}} \right) + \zeta } \right)} \right) \otimes \left( {{{G}_i}\left( t \right) \odot {{X}_i}\left( t \right)} \right)} \right\} \to \\ & \quad\quad{{G}_i}\left( t \right),\quad{r_2} \leqslant 0.5;\\ & \left\{ {\varphi \left( {1 - f\left( {B} \right)/\left( {f\left( {{{X}_i}} \right) + \zeta } \right)} \right) \otimes \left( {{B}\left( t \right) \odot {{X}_i}\left( t \right)} \right)} \right\} \to \\ & \quad\quad{B}\left( t \right),\quad 0.5 < {r_2} \leqslant 0.5 + \xi ;\\ & \left\{ {\varphi \left( {1 - f\left( {{{X}_j}} \right)/\left( {f\left( {{{X}_i}} \right) + \zeta } \right)} \right) \otimes \left( {{{X}_j}\left( t \right) \odot {{X}_i}\left( t \right)} \right)} \right\} \to \\ & \quad\quad{{X}_j}\left( t \right),\quad {\text{其他}}.\end{aligned} \right.\end{array}$

(32)

式中： $\zeta $ 为极小数， $\varphi $ 为控制系数， ${{B}}\left( t \right)$ 与 ${{X}_j}\left( t \right)$ 选取方式与ECO算法相同. 从式（7）可以看出，算法根据粒子进化程度自适应选取不同数量的编码位进行更新，有利于提高算法收敛效率和收敛精度.

基于MDECO算法的传感云资源调度算法实现过程可以描述如下.

输入：传感云系统相关参数，待处理任务数据、MDECO算法参数

输出：多个传感云资源调度方案

1. 根据定义9生成初始种群，并对Pareto最优解集初　　　始化；

2. while ( $t \leqslant {T_{\max }}$ )

3. {

4. 执行AKFCM操作；

5. for $\;i = 1:N$ do

6. 为 ${{X}_i}\left( t \right)$ 选取 ${{B}}\left( t \right)$ 与 ${{X}_j}\left( t \right)$ ，并根据定义10更新 ${{X}_i}\left( t \right)$ ；

7. 判定更新后粒子是否满足约束条件，如果满足则　　　进行支配性判定，即如果 ${{X}_i}\left( {t + 1} \right) > $ $ {{X}_i}\left( t \right)$ 则用新得　　　到的粒子替换 ${{X}_i}\left( t \right)$ ，否则保持 ${{X}_i}\left( t \right)$ 不变；

8. 更新 ${{X}_i}\left( t \right)$ 历史最优解 ${{{G}}_i}\left( t \right)$ ；

9. end for

10. 更新Pareto最优解 ${{X}^*}_{{\rm{\!\!\!\!\!\!new}}}\left( t \right)$ ，并判定 ${{X}^*}_{{\rm{\!\!\!\!\!\!new}}}\left( t \right)$ 能否　　　 进入最优解集；

11. $t + 1 \to t$

12. }

13. 输出Pareto最优解集，即多个传感云资源调度方案.

3 实验仿真 3.1 ECO算法验证实验

为了分析ECO算法的全局寻优性能，采用 ${f_1}:$ Sphere、 ${f_2}:$ Rosenbrock、 ${f_3}:$ Ackley、 ${f_4}:$ Griewank、 ${f_5}:$ Rastrigrin和 ${f_6}:$ Scaffer（ ${f_6}$ 全局最大值为 ${f_6}\left( {0,0} \right) = 1$ 取最小，即取其相反数，即全局最优解为–1）共6个基准测试函数进行实验仿真，6个测试函数的维度、取值范围参考文献[8]. 采用实验测定法给出ECO算法参数设置如下： $N = 250$ 、 $\varepsilon = 0.35$ 、 $\xi = 0.15$ 、 ${T_{\max }} = 500$ 、 ${\mu _{\min }} = 0.6$ 、 ${C_{\max }} = 60$ .

3.1.1 AKFCM算法性能测试

为了分析AKFCM聚类效果，分别采用真实数据和ECO种群数据进行实验测试. 真实数据测试实验中的数据来源于文献[18]提供的4组真实数据，分别采用文献[19]的自动确定聚类FCM算法和文献[20]的基于有效性函数的随机模糊聚类算法进行对比实验. 文献[19]通过图深度优先搜索方法获取出现次数的聚类个数，用来对比算法的迭代效率，文献[20]通过计算不同聚类个数下的最佳有效性函数以确定最佳聚类个数，用来对比算法的聚类准确性，聚类准确率 ${\rm{VOR}}$ 定义为被正确分类的样本数占总样本数的比值. ECO种群数据实验选取不同进化次数的ECO种群进行聚类分析，选取文献[19]提出的算法进行对比实验，评价指标选取文献[21]提出的基于类内离散度的聚类有效性指数 ${V_{\rm{D}}}$ ， ${V_{\rm{D}}}$ 取值越小表明该算法对应的聚类结果就越优秀. 图4为基于真实数据采用不同聚类算法的聚类结果对比，图5为不同迭代次数下ECO种群聚类结果对比，表1为3种聚类算法性能对比. 表中，NC为迭代次数，CN为聚类个数.

为了更加直观地分析本文聚类算法的性能，提出性能对比指标：

${\rm{PC}}\left(\varDelta \right) = \frac{1}{U}\sum\limits_{i = 1}^U {\frac{{I_{{\Theta _x}}^i - I_\Theta ^i}}{{I_\Theta ^i}}} .$

(33)

式中： $\varDelta $ 为评价指标， $\Theta $ 、 ${\Theta _x}$ 分别代表本文算法和对比算法， $U$ 为对比实验样本总数， $I_\Theta ^i$ 为本文算法在第 $i$ 个实验样本下的评价指标结果， $I_{{\Theta _x}}^i$ 为对比算法在第 $i$ 个实验样本下的评价指标结果. 从式（33）可以看出， ${\rm{PC}}\left( \varDelta \right)$ 反映了本文算法相比于对比算法的性能改善程度. 不失一般性，设定本文算法在不同评价指标下性能都为“1”，其他对比算法的性能为 $1 + {\rm{PC}}\left( \varDelta \right)$ ，图6为3种聚类算法的性能对比图.

对于真实数据测试实验，从图4可以看出，虽然文献[19]的算法与AKFCM算法得到的最佳聚类个数相同，但是迭代次数几乎是AKFCM算法的2倍. 设定2种算法具有相同的 ${C_{\max }}$ ，文献[20]每次都需要进行 ${C_{\max }}$ 迭代才能得到最佳聚类个数，表明AKFCM算法只需要较少次数的迭代过程就能够得到最佳聚类个数. 从表1可以看出，AKFCM具有很高的聚类准确率，除data1样本实验数据外，其他3种数据实验中AKFCM算法的 ${\rm{VOR}}$ 都达到了100%，而文献[19]和文献[20]算法的聚类准确率相对较低，4种数据测试中最大的 ${\rm{VOR}}$ 为86.3%. AKFCM算法的聚类有效性指数 ${V_{\rm{D}}}$ 优于其他2种算法，表明AKFCM算法不仅具有很高的聚类准确率，而且聚类效果好于其他2种算法. 图6为更加直观的3种算法性能， ${\rm{VOR}}$ 值越大，3种算法对应的性能越优秀；迭代次数和 ${V_{\rm{D}}}$ 值越小，3种算法对应的性能越优秀.

对于ECO种群数据实验，分别选取 ${f_1}$ 、 ${f_3}$ 和 ${f_5}$ 函数在 $t = 20$ 和 $ 80$ 时的种群进行对比实验. 由于无法获取聚类准确率 ${\rm{VOR}}$ ，只选取最佳聚类个数和 ${V_{\rm{D}}}$ 指标进行分析. 从图5和表1可以看出，对于不同 $t$ 取值下的 ${f_1}$ 和 ${f_5}$ ，AKFCM算法与文献[19]算法同样具有最佳聚类个数，但是文献[19]的迭代次数远远大于AKFCM算法. 对于 ${f_3}$ ，当 $t = 20$ 时，AKFCM算法与文献[20]算法的最佳聚类个数都是5，但是文献[19]算法得到的最佳聚类个数为4，并且AKFCM算法的聚类有效性指数 ${V_{\rm{D}}}$ 几乎是其他2种算法的1/2. 对于动态变化的数据样本，AKFCM算法不仅具有良好的聚类稳定性，而且聚类有效性指数要明显小于其他2种算法.

3.1.2 ECO算法对比实验

为了进一步对比分析ECO收敛性能，选取布谷鸟优化算法^[9]和量子粒子群优化（quantum-behaved particle swarm optimization，QPSO）算法^[8]进行对比实验. 评价指标选取为求解成功率 ${\rm{Su}}$ 、最大值 ${T_{{\rm{Max}}}}$ 、最小值 ${T_{{\rm{Min}}}}$ 、均值 $T_{\overline {{\rm{Ave}}}} $ 和算法时间TOT. 图7为不同函数收敛曲线，表2为不同算法评价指标对比结果. 同“AKFCM算法性能测试”实验类似，图8为不同评价指标下，ECO与CS、QPSO算法的性能对比结果.

$ {\rm{Su}} = \frac{{\sum\limits_i^Z {{z_i}} }}{Z},\left\{ \begin{array}{l} {z_i} = 1,\left| {s - \widehat {{s_j}}} \right| > \gamma ;\\ {z_i} = 0,\left| {s - \widehat {{s_j}}} \right| \le \gamma . \end{array} \right. $

(34)

式中： $Z$ 为实验次数， $\gamma $ 为控制阈值， $s$ 为理论最优解， ${\widehat s_j}$ 为算法第 $j$ 次实验得到的最优解.

从图7及表2可以看出，对于函数 ${f_1}$ 、 ${f_3}$ 和 ${f_5}$ ，3种算法都能够收敛于全局最优解，成功率都为100%. 由于多峰复杂函数 ${f_2}$ 、 ${f_4}$ 和 ${f_6}$ 存在大量局部极值，CS算法收敛成功率最高的也只有58%，QPSO算法和ECO算法成功率很高收敛于最优解，并且ECO算法的最大值 ${T_{{\rm{Max}}}}$ 、最小值 ${T_{{\rm{Min}}}}$ 、均值 $T_{\overline {{\rm{Ave}}}}$ 指标要好于QPSO算法. 对于高维病态函数 ${f_2}$ ，3种算法收敛成功率都很低，ECO算法最高，为23%. 对于算法收敛时间，由于ECO算法进化过程中需要进行种群迭代聚类分析，因此运算时间要长于其他2种算法. 图8更加直观地表明不同评价指标下不同智能优化算法的性能，T_Max、T_Min、 $T_{\overline {\rm{Ave}}} $ 和 $T\;$ 4个评价指标取值越小，算法性能更加优秀； $Su$ 取值越大，算法性能更加优秀. 除 $T$ 外，ECO展现了良好性能.

3.1.3 ECO算法验证实验结果分析

AKFCM算法具有可靠的聚类稳定性和聚类效果，特别是对于动态变化的样本数据，AKFCM算法能够在较少迭代次数下实现较高水平的聚类分析，因为AKFCM算法在聚类过程中以样本隶属度为划分基础，迭代过程更符合模糊聚类实际情况.

ECO算法具有较高的收敛成功率和收敛精度. 这是因为ECO算法在迭代过程中，实时分析种群样本多样性，并且根据种群聚类结果选取更加合理的学习对象指导粒子进化，使得算法在后期仍具有较强的深度搜索能力和较高的跳出局部极值的概率，但是，引入AKFCM算法使得ECO算法需要消耗更多的时间进行迭代进化.

3.2 传感云资源调度测试实验

利用NS2平台模拟80个具有不同规模、执行不同监测任务的无线传感器网络数据；利用CloudSim测试平台仿真15个云计算资源，由程序随机生成100个传感器网络数据处理任务对应的 ${Z}\left( i \right)$ 、 ${Y}\left( i \right)$ ，参考ECO参数设定MDECO参数.

3.2.1 MDECO与单目标调度算法对比

由于MDECO属于多目标资源调度优化算法，目前大部分文献列举方法为单目标算法，为了能够进行对比实验，选取MDECO算法Pareto最优解集中与单目标算法任务长度接近的解对比2种算法能耗，并且用 ${\rm{ET}}$ 表示MDECO算法相比于其他调度算法系统能耗增加（降低）比例，同理，定义 ${\rm{WT}}$ 表示MDECO算法相比于其他调度算法系统任务执行总时间长度增加（降低）比例. 对比算法选取文献[22]提出的FRP调度算法（单目标收益算法）、文献[23]提出的基于化学反应优化调度算法（多目标线性叠加算法）和文献[24]提出的资源调度算法，每种算法独立运行30次，实验结果取平均值. 表3为不同任务调度规模下4种算法性能对比.

从表3可以看出，处理不同传感云资源任务调度规模时，MDECO算法的ET好于文献[22]、文献[23]和文献[24]算法，并且MDECO算法能耗最大能够降低44.29%，最少能够降低6.67%；同样，MDECO算法的 ${\rm{WT}}$ 要优于其他3种算法，MDECO算法的 ${\rm{WT}}$ 分别平均降低18.82%、16.67%和1.60%. 对于超大规模云资源调度问题，MDECO算法的 ${\rm{ET}}$ 和 ${\rm{WT}}$ 表现出突出优势. 对于同样规模的传感云资源任务调度问题，MDECO算法能够给出系统能耗和任务长度更低的调度方案. 图9为不同指标下算法性能的对比结果. 可以看出，MDECO算法的系统能耗(SEC)和任务执行时间(Total Time)小于其他3种算法.

3.2.2 MDECO与多目标优化算法对比

选取文献[1]提出的多目标Memetic优化算法、文献[6]提出的多目标分组遗传算法和多目标粒子群算法（multi-objective particle swarm optimization，MPSO）进行对比实验，评价指标选取文献[1]提出的 ${\rm{IC}}$ 测度和Pareto最优解集多样度 $\theta \left( {{\rm{Par}}} \right)$ . ${\rm{IC}}\left( {X,Y} \right)$ 数值越大表明 $Y$ 被 $X$ 支配的程度越大， $\theta \left( {{\rm{Par}}} \right)$ 越小表示Pareto最优解集更均匀. 图10为不同传感云资源调度规模下 ${\rm{IC}}\left( {X,Y} \right)$ 和 $\theta \left( {{\rm{Par}}} \right)$ 对比结果.

从图10可以看出，对于不同传感云资源任务调度规模，IC（本文，Y）（Y表示为其他3种算法）都要大于IC（Y，本文）. 例如，对于IC（本文，Memetic），MDECO算法（本文算法）支配Memetic算法最优解的概率分别为80.2%、64.3%、61.1%、59.4%、57.2%、54.3%、50.1%、49.9%，Memetic算法算法支配MDECO最优解的概率仅有14.5%、20.7%、29.4%、30.1%、37.3%、36.8%、40.2%、41.1%，MDECO算法能够得到更多优秀的解. 对于不同传感云资源规模，MDECO算法的最优解集多样度要好于其他3种算法，MDECO算法得到的Pareto最优解集更加均匀.

3.2.3 传感云资源调度测试实验结果分析

从MDECO算法与单目标调度算法和多目标优化算法对比实验结果可以看出，基于MDECO算法的传感云资源调度方案更加合理，因为弹性碰撞优化算法优秀的全局寻优能力能够探索到更多潜在的任务调度问题最优解，有效降低系统能耗和任务处理时间，提高Pareto最优解集质量水平，并且MDECO算法采用多目标处理方式，不是简单地将多个优化目标加权成单目标，能够为决策者提供多种决策依据.

4 结　语

对新的弹性碰撞优化算法进行了研究，提出了全新的智能优化算法，并且从种群多样的角度对智能优化算法改进策略进行分析探索，引入自适应核FCM模糊聚类算法实现对种群样本多样性的实时分析，使得种群进化方向更加合理科学. 种群样本多样性定量分析和测试函数仿真结果证明ECO在运算后期仍然具有较好的种群多样性. 从传感云资源调度应用研究入手，构建多目标传感云资源调度优化模型、设计符合工程实际的弹性碰撞优化算法实现流程，最后仿真实验验证传感云资源调度方案的有效性. 下一步将针对高维病态函数优化和提高传感云资源调度效率进行研究.