头脑风暴优化算法(Brain Storming Optimization Algorithm, BSO)
一、算法灵感二、算法介绍2. 1 初始化2. 2 聚类2. 3 个体更新2. 4 算法伪代码三、实验结果3. 1 F1收敛曲线3. 2 F5收敛曲线3. 3 F8收敛曲线四、参考文献一、算法灵感
头脑风暴优化算法(Brain Storming Optimization Algorithm, BSO)是提出的一种群智能优化算法,其灵感来源于头脑风暴法。当一群人围绕一个特定的兴趣领域产生新观点的时候,这种情境就叫做头脑风暴。头脑风暴法是一种充分开发人类创造性思维解决问题的方法。
二、算法介绍
2. 1 初始化
在种群初始化过程中,聚集一组尽可能不同背景的人,可以看作是在解空间的动态范围内随机均匀分布的个体种群。整个个体种群可以是完全随机产生的,或者只随机产生一部分种群,其余的个体种群将通过从已经随机产生的个体添加随机扰动来产生。
2. 2 聚类
头脑风暴中任何不同的想法都可以作为寻找更好的解决方案的线索。头脑风暴小组每一轮需要产生足够的想法,但不需要太多,因为太多的想法容易发散,导致远离了目标。为了加快寻找足够好的想法,我们还需要让头脑风暴小组集中精力在一些具有高潜力的领域产生想法。因为每个问题所有者都有不同的专业知识,因此所选择的想法是不同的。因此BSO采用的是 k-means 聚类算法,将相同领域或者相似领域的成员分为一组。种群中所有的个体都被聚集成几个集群。每个集群的集群中心可以是该集群中性能最好的个体,也可以是集群的中间个体。
2. 3 个体更新
在BSO算法中,新个体是选取一个或几个集群中的中心或者普通个体添加随机扰动产生的,当选取一个集群产生新个体时,公式如下:
Xnew=Xold+ξ(t)∗random(t)(1){X_{new}} = {X_{old}} + \xi \left( t \right)*random\left( t \right) \tag{1}Xnew=Xold+ξ(t)∗random(t)(1)式中,XnewX_{new}Xnew 是产生的新想法,XoldX_{old}Xold 是原来的想法,ttt 为当前迭代次数,random()random()random() 是用来生成 000 到 111 之间的随机数,ξ()ξ()ξ() 是一个对随机值对新个体的贡献进行加权的系数。ξ()ξ()ξ() 的计算公式如下:
ξ(t)=logsig(T2−tk)∗random(t)(2)\xi \left( t \right) = logsig\left( {{{{T \over {\rm{2}}} - t} \over k}} \right)*random\left( t \right) \tag{2}ξ(t)=logsig(k2T−t)∗random(t)(2)其中,logsig()logsig()logsig() 是一个传递函数,TTT 为最大迭代次数,kkk 是控制 logsig()logsig()logsig() 斜率的系数。
当选取两个集群来产生新个体时,公式如下:
Xolds=w∗Xold1+(1−w)∗Xold2(3){X_{olds}} = w*{X_{old1}} + \left( {1 - w} \right)*{X_{old2}} \tag{3}Xolds=w∗Xold1+(1−w)∗Xold2(3)Xnew=Xolds+ξ(t)∗random(t)(4){X_{new}} = {X_{olds}} + \xi \left( t \right)*random\left( t \right) \tag{4}Xnew=Xolds+ξ(t)∗random(t)(4)式(3)中,XoldsX_{olds}Xolds为Xold1X_{old1}Xold1和Xold2X_{old2}Xold2的加权和,www为随机产生的0到1之间的系数,Xold1X_{old1}Xold1和Xold2X_{old2}Xold2是分别从两个集群中选取的想法。
2. 4 算法伪代码
初始化种群规模 NNN、维度 dimdimdim、最大迭代次数 TTT初始化参数和种群 Xi(i=1,2,...,N)X_i(i=1,2,...,N)Xi(i=1,2,...,N)Whilet<Tt<Tt<Tdo利用 k-means 聚类算法将 nnn 个个体聚类为 mmm 个聚类计算每个个体的适应度值并排名,将最佳个体记录为每个聚类中的聚类中心Ifrand<0.2rand<0.2rand<0.2then随机生成一个个体来替换随机选取的一个聚类的中心End IfFori=1i=1i=1toNNNdoIfrand<0.8rand<0.8rand<0.8then选取一个聚类的中心或随机个体Else选取两个聚类的中心或随机个体End If通过式(1)产生新的个体,计算适应度值将新生成的个体与现有个体进行比较,将保留较好的个体End ForEnd While输出最终解三、实验结果
BSO在23个经典测试函数(设置维度 dim=30dim=30dim=30)的F1、F5、F8中的收敛曲线,测试函数公式如下:
3. 1 F1收敛曲线
3. 2 F5收敛曲线
3. 3 F8收敛曲线
四、参考文献
[1] Shi Y. Brain storm optimization algorithm[C]//Advances in Swarm Intelligence: Second International Conference, ICSI , Chongqing, China, June 12-15, , Proceedings, Part I 2. Springer Berlin Heidelberg, : 303-309.