多样性指数与头脑风暴算法研究

沈兆琪　曹倬铭　王文国

摘要：头脑风暴算法是目前仅有的受人类社会性行为启发的优化算法，该算法和其它群体智能算法一样，存在执行效率低和收敛速度慢等缺点。首次定义了一个香农多样性指数来估算样本群落的多样性以及均匀性，并对原始头脑风暴优化算法进行多次初始化，从而有效加快算法后期的收敛性。利用6个标准测试函数对改进后的算法进行了可行性验证，统计分析后表明，该算法只要选择多样性及均匀性足够好的初始种群，就能显著减少迭代次数。改进后的头脑风暴算法在执行效率和收敛速度上都有所提高。

关键词：头脑风暴算法；多样性指数；均匀性；收敛速度

DOIDOI：10.11907/rjdk.172450

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2018）003007103

英文摘要Abstract：Brain storm is the only swarm intelligence algorithm with origin from modeling human activities， which can help solve some NP problems but often behaves odd and converges slowly. To overcome its shortcomings， a new idea of diversity index arising from ecology is introduced for brain storm optimization， which will measure diversity and uniformity of a solution group， and help us select a good starting point for optimization. Simulation tests with 6 benchmark functions have been conducted， and results show that the improved brain storm optimization with diversity index can speed up convergence and reduce number of iterations significantly.

英文关键词Key Words：brain storm； diversity index； uniformity； convergence rate

0引言

群体智能算法是一种基于随机搜索机制的优化方法，具有灵活应对群体内部和外部搜索环境变化的能力，即当搜索条件多变或自身的某些个体失败时，能够自组织逃离并发现更优的位置。群体智能算法与传统的完备算法相比，尽管不一定能找到最优解，但可以确保在短时间内找到较优质的解。由于其在解决优化问题上具有独特的优势，群体智能算法应用于很多实际问题中，如机器人控制、无人驾驶交通工具、社会性行为预测、通信网络加强、医学图像处理等。然而这些算法常常存在易陷入局部最优、早熟或收敛过慢等问题。

大多数经典算法是受低等生物的社会性行为启发的，但长期没有由人类的社会行为启发而提出的智能算法。2011年史玉回[12]提出了头脑风暴优化算法。头脑风暴优化算法是一种非常有潜力的方法，通常能够产生超出经典智能算法的结果。

目前，头脑风暴优化算法的研究与应用还处于初级阶段。许多人在过去的几年中尝试对头脑风暴优化算法进行各种研究及改进。史玉回等[3]提出了引入两种组件提高传统头脑风暴优化的性能，第一个组件使用一个简单分组操作符的分组方法（SGM），代替聚类方法从而减轻算法的计算负担；第二个组件使用一个想法不同的策略（IDS）代替高斯随机策略来创建操作符；Jingqian Xue等[4]提出了一种新的基于头脑风暴过程的多目标优化算法（MOBSO），在目标空间采用了聚类策略，并通过两种不同的变异算子——高斯变异和柯西变异产生新个体；史玉回等[5]在原始头脑风暴优化算法基础上改进了新个体的生成和选择策略。首先根据个体在每个维度的动态范围调整步长，然后用一个批处理模式生成新个体并选择新个体；杨玉婷等[6]引入分组合作机制以优化算法的实现过程，提出了基于讨论机制的头脑风暴优化算法，同时进一步引入差分步长从而避免算法进入局部最优。头脑风暴优化算法迅速发展，不同领域都开展了应用研究[712]。

头脑风暴算法的改进算法依然存在缺点，如执行效率低和收敛速度慢等。为克服此类缺陷，本文将首次定义一个香农多样性指数来估算样本群落的多样性以及均匀性，并对原始头脑风暴优化算法进行多次初始化，從而有效加快算法后期的收敛性。

1基本头脑风暴优化算法

头脑风暴优化（Brain Storm Optimization， BSO）算法是受头脑风暴过程启发而产生的优化算法。头脑风暴过程的核心思想是将一群不同背景的人聚集起来，就同一个问题进行头脑风暴，为待解决问题提出大量解决方案，最后通过交流及方案的融合共同解决问题。在面对许多问题时，个人的能力有限，但若是由一群来自不同背景的人进行头脑风暴，通常可以极大程度地提高解决问题的可能性。

基于人类的头脑风暴过程，史玉回提出了BSO算法。BSO算法过程简单，算法中的毎个个体都代表一个潜在的问题解，算法包含3个操作：初始化、聚类和更新个体，如图1所示。

图1BSO算法流程

BSO算法实现过程中，通过kmeans聚类算法将n个个体聚成m个类；更新个体则根据概率选择4种方式进行，分别为类中心添加随机值、个体添加随机值、两个类中心融合添加随机值、两个随机个体融合添加随机值。融合过程可用以下公式表示：

xdcombined=vxd1+（1-v）xd2（1）

式（1）中，xcombined是随机选中的个体xd1和xd2融合生成的个体，d是d维上的取值；v∈[0，1]是一个符合均匀分布的随机数。

添加随机值生成新个体的过程按式（2）进行：

xdnew=xdselect+ξ×n（μ，σ）（2）

式（2）中，xdnew是新生成个体的d维值，xdselect是随机选中个体的d维值，n（μ，σ）是均值为μ、方差为σ的一个高斯随机函数，ξ是步长，用来控制随机扰动幅度。

ξ值按如下公式计算得到：

ξ=logsig0.5Nmax_gen-Ncur_genkrand（）（3）

式（3）中，logsig（）是对数变换函数，k用来控制logsig（）的变化速率， rand（）是0-1之间符合均匀分布的随机值。

2改进的头脑风暴算法

在上述基本头脑风暴算法搜索机制中，初始化步骤仅随机产生n个个体，这些初始解实际上距离最优解可能有很大的偏离，使得后续的寻优过程很漫长或者几乎不可达。基于这一考虑，本文将首次引进一个多样性指数来评估初始种群的多样性以及均匀性。

新算法根据两个判定条件选择出最有潜力或最优秀的初始种群：①种群多样性，判断依据是群内类的数目越多，种群多样性就越复杂，越能够包容全局最优；②均匀性，用来描述群内各个物种的相对丰度或所占比例，即在类数目相同条件下，群内所有类中的个体数量越均匀越好。

多样性指数是一个统计量，通常被用来描述一个群落或种群的多样性。在生态学中，往往使用香农多样性指数估计群落多样性，其公式如下：

H=-∑ni=1pilogpi2（4）

式（4）中，n代表种群总数，pi是第i个种群占总种数的比值。种群数越多，或者个体分配越均匀，则多样性指数越高，对应的群落越优秀。

香农多样性指数中包含两个重要部分：种群数目及每个种群之间个体分配的均匀性。H值的大小取决于每个种群之间个体分配是否均匀，均匀性越大H值就越大，反之则越小。因此，上述香农多样性指数既可以表示种群多样性，也可以反映种群均匀性。根据这两个判定条件挑选出相对优秀的初始群，就能确保BSO算法的正确方向和收敛速度，从而平衡控制算法的全局搜索方向和局部搜索能力。

改进后的算法流程如下：①多次初始化并聚类分析；②用多样性指数估计种群的多样性和均匀性，挑选出最有潜力的初始种群；③更新个体等后续BSO操作。

3仿真测试与分析

为了评测改进头脑风暴算法的效果，选取了6个测试函数进行测试，分别为Sphere、Step、Griewank、Rastrigin、Rosenbrock、Schaffer。其中6个经典函数中，Sphere、Step是单模函数，其余4个函数是多模函数。所采用的6 个测试函数及其值域范围见表1。

改进算法的主要参数取值与原始BSO算法中对应参数一致，其它参数根据经验设定，所有参数取值如表2所示。

仿真实验对6个测试函数进行50次独立测试，并对所得的优化结果进行对比分析。实验仿真平台为：Intel（R） Pentium E6500，CPU 主频2.93GHz，2GB内存，Windows 7 操作系统下的MATLAB 7.8 。 图2、表3分别为Sphere函数H值曲线对比和6个测试函数的收敛过程对比。可以看出，只要选择多样性及均匀性好的初始种群，就能显著减少迭代次数。

4结语

本文在深入研究原始头脑风暴算法的基础上，首次引入香农多样性指数来选择初始种群，以便获得最接近最优解的出发点进行寻优。仿真实验结果表明，改进的算法能极大提升原始算法的寻优效果，在优化速度和算法稳定性方面有明显优势。改进后的算法易于实现，对处理单模问题和多模问题均表现出良好的潜力及可塑性。

参考文献参考文献：

[1]SHI Y. Brain storm optimization algorithm[C].Springer Berlin Heidelberg，2011：303309.

[2]SHI Y. An optimization algorithm based on brainstorming process[J].International Journal of Swarm Inteligence Research（IJSIR），2011，2（4）：3562.

[3]ZHAN AH，ZHANG J，SHI YH，et al.A modified brain storm optimization[C]. In IEEE Congress on Evolutionary Computation， Brisbane，QLD，2012：18.

[4]XUE J，WU Y，SHI Y，et al.Brain storm optimization algorithm for multiobjective optimization problems[C].Springer Berlin Heidelberg，2012：513519.

[5]ZHOU D，SHI Y，CHENG S.Brain storm optimization algorithm with modified stepsize and individual generation[C].Springer Berlin Heidelberg，2012：243252.

[6]杨玉婷，史玉回，夏顺仁.基于讨论机制的头脑风暴优化算法[J].浙江大学学报：工学版，2013，47（10）：17051711.

[7]SUN C，DUAN H，SHI Y.Optimal satellite formation reconfiguration based on closedloop brain storm optimization[J].IEEE Computational Intelligence Magazine，2013，8（4）：3951.

[8]DUAN H，LI S，SHI Y.Predatorprey based brain storm optimization for DC brushless motor[J].IEEE Transactions on Magnetics，2013，49（10）：53365340.

[9]KENNEDY J， KENNEDY J F， EBERHART R C， et al. Swarm intelligence[M]. Morgan Kaufmann，2001：123265.

[10]余建平，周新民，陳明.群体智能典型算法研究综述[J].计算机工程与应用，2010，46（25）：7074.

[11]DUAN H，LI S，SHI Y.Predatorprey based brain storm optimization for DC brushless motor[J].IEEE Transactions on Magnetics，2013，49（10）：53365340.

[12]杨玉婷.头脑风暴优化算法与基于视频的非接触式运动定量分析方法研究[D].杭州：浙江大学，2015.

责任编辑（责任编辑：杜能钢）