905 次浏览

Brain Storm Algorithm(头脑风暴)

头脑风暴算法,听着就很给力的亚子。。。

头脑风暴算法是一种智能算法,受人类创造性问题解决过程启发的优化算法,人为万物之灵,不同于动物群体的固有行为模式,我们个体有更好的独立性创造性,同时也有很好的协作能力,通过模仿(研究)人类自己本身行为来进行智能算法的开发,似乎是得比动物群体算法要好。

像许多团队进行开发,想idea时,会召开头脑风暴会议,各抒己见,本人以前就参加一个三人的头脑风暴会议,我主要就是提出想法,其他两人就自己的见解提出问题来,然后讨论这个想法的适用性,可拓展性等等,reference 1就头脑风暴这一人类群体行为进行了总结:
1. 召集一群头脑风暴的人,他们的背景应尽可能多样化;
2. 根据讨论主题产生想法;
3. 让几个(例如3个或5个)客户作为问题的所有者,从每个所有者那里挑选几个(例如一个)想法,作为解决问题的更好想法;
4. 将在第3步中挑选的想法比其他想法更有可能作为线索,并根据表2中的规则生成更多想法;
5. 让所有者选择第3步中产生的更好的主意;
6. 随机选择一个对象,并以该对象的功能和外观作为线索,根据表2中的规则产生更多想法;
7. 请所有者选择一些更好的主意;
8. 希望可以通过考虑和/或合并所产生的想法来获得足够好的解决方案。

讨论的主题也为分为四类,称为Osborn’s Original Rules。
a. Suspend Judgment: 想法的判断推迟到最后,至少在头脑风暴之前
b. Anything Goes: 记录任何提出的想法
c. Cross-fertilize (Piggyback) : 许多想法可以基于已经产生的想法,任何产生的想法都可以作为产生更多想法的线索
d. Go for Quantity: 提出足够多的想法

算法过程:
预定义的数据: 迭代次数iters, 更新集群中心概率\(\)\(p_{ucc}\)\(\),个体生成方式概率\(\)\(p_{gi}\)\(\),集群被选择概率\(\)\(p_{sc}\)\(\),集群中心被选择概率\(\)\(p_{scc}\)\(\),两个集群中心被选择概率\(\)\(p_{2scc}\)\(\)
1. 随机初始化n个潜在解
For i : iters:
2. 将n个潜在解聚类成m类
3. 评估计算n个潜在解
4. 对每个集群中的解进行排名,将集群中最佳解作为集群中心并保存下来
5. 随机生成\(\)\(r_1 \in (0, 1)\)\(\)
a. if \(\)\(r_1 < p_{ucc}\)\(\):
(1) 随机挑选一个集群中心
(2) 随机生成一个解替代为集群中心
6. 生成新个体
a. 随机生成\(\)\(r_2 \in (0, 1)\)\(\)
b. if \(\)\(r_2 < p_{gi}\)\(\)
(1) 以概率\(\)\(p_{sc}\)\(\)选择集群
(2) 随机生成\(\)\(r_3 \in (0, 1)\)\(\)
(3) if \(\)\(r_3 < p_{scc}\)\(\): 将选中集群的中心加上随机值生成新解
(4) else: 随机选择选中集群的一个点加上随机值生成新解
c. else 随机选择两个集群来生成解:
(1) 随机生成\(\)\(r_4 \in (0, 1)\)\(\)
(2) if \(\)\(r_4 < p_{2scc}\)\(\): 组合两个集群中心并加上一个随机值生成新解
(3) else: 随机从两个集群中各选择一个个体组合并加上一个随机值生成新解
d. 对比拥有相同索引的新个体与旧个体,留下更好的个体,成为最终的新解
7. 重复6直至生成n个新解
End For

本人使用python实现了BSO算法,函数是reference 2中使用的函数,效果如下,概率都使用的是0.5。

BSO首先通过聚类来选取小组leader(当前最优解),然后保存小组最好解,leader带着组员冲业绩,组员也要发展进步,组内内部已经有一个带头人了,leader已经是组内最高成就者了,leader们就凑一块来帮助他们提高,一是组内发奋,leader教授给年轻组员们,让他们冲冲冲,二是leader们做引导,进行互助交流会,进行学术探讨,三是leader们当巨人,将leader们的知识结合教授给组员。世界在发展,新旧要更替,leader也有退居幕后的,发展促使更换leader,给其他人一个领导的机会,新leader也会吸引着一批志同道合之人,整个系统又将重组,焕发新的活力。

同于PSO,人类也是需要领头羊的,靠着leader的领导。但是人类之间的竞争关系以及学习关系是BSO所更突出的进步。下面描述以BSO在reference 2函数寻优,以概率0.5为线的基础上,个人的一点总结:

  1. 实验调整降低\(\)\(p_{ucc}\)\(\),提高\(\)\(p_{gi}\)\(\),各组就会分割严重,单纯依靠于组间竞争
  2. 实验调整降低\(\)\(p_{gi}\)\(\),提高\(\)\(p_{ucc}\)\(\),整体系统重组相互学习,组间学习关系更强
  3. \(\)\(p_{scc}\)\(\),\(\)\(p_{2scc}\)\(\)则是考虑leader是否到达天花板,个人感觉用于微调
  4. 这些参数同PSO一样在整体上用衰减方式会有更好的效果。

reference
1. Shi Y. Brain storm optimization algorithm[C]//International conference in swarm intelligence. Springer, Berlin, Heidelberg, 2011: 303-309.
2. http://blog.nodetopo.com/2020/04/28/pso%e7%ae%97%e6%b3%95/