基于改进FCM和MPI的并行鸡群算法

王龙， 闫娜

(1. 河南省洛阳经济学校 计算机系， 河南 洛阳 471000；2. 信息工程大学洛阳校区 职业教育中心， 河南 洛阳 471000)

0 引言

鸡群优化(Chicken Swarm Optimization，CSO)算法[1]是学者Meng X等人在2014年提出的一种全新群智能优化技术，具有结构简单、参数较少、容易实现等特点，已被应用于物联网[2]、无线传感网络定位[3]、路径规划[4]、电网技术[5]等领域。研究表明[6-7]，在求解复杂高维大规模多极值问题时，CSO算法存在全局寻优性能相对较弱、易产生“早熟”现象等缺陷。针对CSO算法存在的不足，有效提升全局收敛效率是当前研究热点。

许多学者提出了系列改进措施：吴定会等[7]利用 Markov链模型证明了CSO算法具有全局收敛性，同时指出算法在运算速度上有待进一步提升；吴忠强等[8]通过引入混沌序列和自适应惯性权重，有效增强了算法寻优精度；但改进算法在寻优效率上仍有改进空间；WU等[9]通过设计“交叉算子”，较好地降低了“早熟”现象发生概率，但是算法运算后期搜索停滞问题需进一步研究；文献[10]以提高鸡群种群多样性为目的，设计了改进因子及去重操作算子，仿真结果也证明了该算法具有良好的优化性能，但该算法收敛速度慢的问题仍然存在。

为了有效解决CSO算法多维大规模复杂优化问题收敛效率不高、运算速度慢的缺陷，提出了一种基于改进FCM和MPI的并行鸡群算法(MCSO)：利用基于贪婪聚类初始化策略的改进FCM，建立融合聚类分析的鸡群等级关系；在MPI并行运算架构下，多个鸡群子族群独立执行迭代进化计算，并协同交流信息，从而实现全局最优解求解。仿真实验结果表明，相比文献[8]提出的改进鸡群算法(ICSO)和灰狼优化算法(GWO)[11]等，MCSO算法具有更高的收敛精度和更快的运算速度。

1 基本CSO算法

CSO算法对鸡群觅食行为进行抽象，将鸡群等级关系转化为个体适应度值优劣，赋予公鸡、母鸡、小鸡不同进化策略，每隔一定时间，重新建立等级关系，并按照新的等级关系进行迭代进化，如此往复，最终实现全局最优解求解。鸡群个体更新策略如下(CSO算法实现流程见相关文献，不再赘述)。

(1) 公鸡更新策略。定义种群内适应度最优的一定数量的个体为公鸡，其更新策略，为式(1)。

(1)

(2) 母鸡更新策略。建立“母鸡跟随公鸡”等级关系，其更新策略，为式(2)。

(2)

(3) 小鸡更新策略。建立“小鸡跟随母鸡”等级关系，其更新策略为式(3)。

(3)

在CSO算法内，适应度值不同的个体采取不同的进化更新机制，在表达形式上，具有参数少、结构简单的特点；在进化过程上，多种更新策略使得算法能够有效保持种群样本多样性，提高算法收敛效率。

2 MCSO算法实现

CSO算法设计了三种不同类型的个体，而且每类个体采用不同更新进化方式，一定程度保持了算法样本多样性，但是如果个体学习对象与自身具有更多的相似性，则加速了算法向同一方向进化的概率，特别的，当种群分布在局部极值空间范围内时，算法很容易陷入局部最优，产生“早熟”现象。由此可见，合理选择个体学习进化对象对有效保持种群多样性具有重要意义，为此，采用改进FCM对种群进行聚类划分，得到若干个子族群，使得同一子族群内个体具有更多相似性，不同子族群具有更大差异性，在此基础上，建立鸡群等级关系。

2.1 改进FCM

FCM(模糊C均值聚类算法)作为应用最为广泛的聚类算法，其核心思想是通过“隶属度”实现对数据样本分类。对于数据样本X={xk}(k=1,2,…,N)，定义μik为xk对第i个分类(i=1,2,…,C，共划分C个分类)的隶属度，FCM通过一定次数的迭代计算，使得聚类目标函数F(U,V)达到最小值时，实现最佳数据样本分类，为式(4)。

(4)

式中，V={vi}、U=[μik]C×n分别为聚类中心集合和隶属度矩阵，m为模糊加权指数。分别对V、U求偏导，如有，为式(5)—式(7)。

∂J/∂μik=0,∂J/∂vi=0

(5)

(6)

(7)

对式(6)进行迭代计算，直到满足终止条件为止。

研究表明，FCM聚类结果很容易受初始聚类中心的影响[12]，为此提出贪婪聚类初始化策略，即以概率P(vi)确定第i个初始聚类中心，其实现过程为：

Step1. 随机选取一个样本xk为第1个聚类中心，v1←xk。

Step2.以概率P(v2)在剩余数据中选择xj(xj≠xk)作为第2个聚类中心v2←xj，为式(8)。

(8)

Step3. 以概率P(v3)在剩余数据中选择xo(xo≠xj≠xk)作为第3个聚类中心v2←xj。为式(9)。

(9)

Step4.以此类推，最终以“贪婪”形式确定出初始聚类中心。

2.2 基于改进FCM的鸡群等级关系建立

利用改进FCM对鸡群种群进行分析，得到多个分类(子族群)，使得同一子族群内个体具有更多相似性，不同子族群具有更大差异性，这为个体学习对象选择提供了合理依据，在此基础上建立鸡群等级关系，并改进学习进化策略。

(10)

(11)

2.3 MCSO算法实现

MPI(消息传递接口)[13]利用多个硬件资源，能够极大地提高运算速率。本文构建MPI并行运算架构：设定一个主节点，主要运行初始化、种群聚类分析、鸡群等级关系建立等操作；设定C个从节点，每个从节点主要执行G轮子族群内部更新进化操作。基于改进FCM和MPI的并行鸡群算法(MCSO)实现过程，如图1所示。

图1 MCSO算法实现流程图

3 实验仿真

采用典型测试函数分析MCSO算法性能。测试函数主要选取多维复杂函数，为式(12)—式(15)。

(12)

2],n=30,-100

(13)

(14)

(15)

MCSO算法参数设置如下：设定鸡群种群规模N′=300、G=6、C=10、λ=3、算法最大迭代次数Tmax=500、ε为计算机能达到的最小正数。

图2 函数f1收敛曲线

图3 函数f2收敛曲线

图4 函数f3收敛曲线

图5 函数f4收敛曲线

对比结果如表1所示。

表1 评价指标对比结果

从表1和4个函数收敛曲线可以看出，在求解精度上，对于典型函数f1，3种算法都能够找到全局最优解，但是MCSO算法的标准方差要好于其它两种算法；对于多局部极值函数f2和f3，MCSO算法表现出更强的深度搜索能力，无论是最优解平均值，还是标准方差都要明显优于IGWO算法和ISSO算法；对于高维复杂函数f4，MCSO算法收敛精度更高，标准方差更小。在运算速度上，对于4个函数，MCSO算法运算效率明显快于IGWO算法和ISSO算法。这表明，对于复杂高维多极值函数优化问题，MCSO算法具有更优的全局收敛能力和更快的运行效率。

仿真结果表明，MCSO算法能够有效解决高维复杂函数优化问题。之所以MCSO算法具有突出的优化性能，是因为采用改进FCM对种群进行聚类分析，提高了学习对象选取的针对性和合理性，有效保持了种群样本多样性，较大程度地降低了算法陷入局部最优的概率，而且构建了MPI并行运算架构，极大提高了算法运行效率，有效降低了内部多轮迭代对算法运行效率的影响。

4 总结

本文提出了一种于改进FCM和MPI的并行鸡群算法(MCSO)，通过设计改进FCM、贪婪聚类初始化策略，实现对鸡群聚类分析；在此基础上，建立融合聚类分析的鸡群等级关系，有效提升了算法收敛能力；构建MPI并行运算架构，在并行运算架构下种群个体协同进化，大幅度提高了算法运算效率。仿真结果表明，MCSO算法在求解高维复杂多极值时具有更加突出的优化性能。