第十五弹——毒爆虫优化算法：一种新型群体智能优化方法 ...

BlaXuan

引言

大学期间，我特别喜欢玩暴雪公司出品的《星际争霸II》(StarCraftⅡ，以下简称SCII)。不同于《魔兽争霸III：冰封王座》，SCII更偏向于未来科技化。受SCII中虫族主力之一爆虫(也叫毒爆虫，我觉得这个名字霸气一点)独特设定的启发，我根据毒爆虫在游戏中的设定将其模拟至现实生活中，并作出一定的修改。完成此项工作后，提出一种基于毒爆虫的新型元启发式优化算法——毒爆虫优化算法(Baneling Optimization Algorithm,BOA)，并利用标准测试函数、标准工程测试问题对BOA算法与其他五种算法进行对比测试。为了让读者有更好的阅读体验，本期主要分为以下几个版块：星际争霸II背景简述、毒爆虫简介、毒爆虫优化算法模型介绍、性能测试及结果分析。在本期编写过程中，很多知识都来源与网络，大家看着开心就好，对于某些部分不要太较真[捂脸]~
星际争霸II故事背景

考虑到某些读者没有玩过SCII，所以我在这里简述一下SCII的故事背景。在SCII中，主要有三大种族：
1.人族：人类是科普卢星区的新移民。他们的祖先是数世纪前来自地球的殖民远征军，是一支遭到政府抛弃的叛军。在异虫入侵期间，革命领袖阿克图尔斯·蒙斯克率军推翻了腐朽的联邦政府。现在，人类帝国已经从联邦政府的废墟中崛起，并成为了一个以阿克图尔斯元首为首的强大势力。由于被迫在星区内最严酷的环境中生存，人类逐渐适应，成为了生存大师。既没有星灵的发达科技，也没有异虫的天生神力，人类的军队由各种混合单位组成。从基本却高效的陆战队员到重型武装的战列巡航舰，人类单位靠着坚固的装甲、强大的火力及数量的优势在战线上活跃着。



图1 人族

2.虫族：异虫是一个与人类及星灵截然不同的种族。它们通过感染其他种族从而将他们感化成异虫的一员。这些生物迅速且有选择地进化成了冷酷的杀戮机器，以此进一步地巩固了异虫的绝对统治地位。异虫通过生物同化以及有计划的虫群变异来有效地武装自己。就连异虫的建筑其实也是由虫巢中的活体器官转化而来。异虫基地会散布菌毯，一种滋养并维持虫群殖民地的生化物质。菌毯治疗着异虫的单位并为他们提供移动速度加成。所有异虫地面单位都可以学习潜地能力。所有的虫族的部队都是由孵化场中的“幼虫”变异而来，这些不停运动的幼虫即虫族生物的基本形态。



图2 虫族

3.神族：星灵又称神族，他们凭借其高度发达的科技和强大的灵能力量，一度将自己信奉为宇宙中最强大的种族，但与异虫的战争却将此信心粉碎殆尽。星灵从来不是依靠数量取胜的种族，他们通常使用机械战争武器来维持军队的数量。星灵战士有着无人可比的单兵作战能力，科技与可怕灵能力量的混合更是让他们在战场上如虎添翼。星灵最大的优势之一是他们的舰队，多种多样的强大战舰足以让任何敌人化为灰烬。



图3 神族

毒爆虫生物学特性

时值21世纪，人类的工业化已经十分发达。随着大片森林被砍伐殆尽，为了避免与人类的频繁冲突，虫族大举搬迁至山地、沙漠、丘陵等人迹罕至的地区。前文提到，所有的虫族的部队都是由孵化场中的幼虫变异而来。所以在自然界中，毒爆虫的成长与苍蝇、蚊子的变态式发育非常像：



图4 毒爆虫的成长过程

不要觉得图中毒爆虫非常可爱，事实上仅凭一只毒爆虫宝宝就可炸掉主人的一只手臂！所以“爆虫虽可爱，饲养需谨慎”！对于捕食者而言，它是爆浆美食；而对于猎物，它是爆浆恶魔。为了应对残酷的自然环境，千百年来毒爆虫得以不断进化，经解剖发现其主要具有以下四个特点：



图5 毒爆虫的坚韧甲壳特性



图6 毒爆虫的腿部特性



图7 毒爆虫的声纳系统



图8 毒爆虫的器官变异

1.坚韧甲壳：外骨骼进化的更加坚硬，可以起到一定的防御作用；骨板软化后使得毒爆虫身体抗撞击能力增强，且在接近人类机枪兵时更容易爆开。
2.爬行虫腿：毒爆虫腿部变细后在行进时产生的会噪音大大降低，使得机枪兵难以发现。
3.声纳系统：与鲸鱼相似，毒爆虫的眼部与体型比例十分不协调，因此其通过发射脉冲来获取空间信息。
4.器官变异：这就有点类似人类肠胃中存在的大肠杆菌，保持共生关系，帮助毒爆虫调节体内酸度。
在SCII官网上对毒爆虫是这样描述的：

“爆虫长有充满酸液的囊，外形臃肿不堪，甚至无法正常行走；战场上有时甚至会见到爆虫蜷缩成一团滚动前行！当爆虫接近敌人时，会触发体内的不稳定化学物质进行反应，将自身引爆，向外泼洒强酸。自爆会摧毁爆虫，但同时会对敌人造成大量伤害。异虫种族与生俱来的潜地能力使得爆虫的威胁更为致命。从地下突然钻出的爆虫会迅速冲向敌人，使其无从反应，看似平静的安全区域随即变成死亡的陷阱。”——可能是阿巴瑟说的

在游戏中，毒爆虫有两种变异类型，玩家可以随意选择：



图9 左为分裂虫，右为猎杀虫

其中分裂虫为普通毒爆虫与生活在毒猎兽的结合体：



图10 毒猎兽介绍

可以看到，分裂虫牺牲后可以分为两个小的个体继续攻击敌人，造成高程度AOE伤害，但是小个体无法继续分裂。下图11为分裂虫的实战测试(可怜的追猎者啊)：



图11 分裂虫实战测试

猎杀虫的诞生为特殊环境下自然选择的结果(你住在哪里不好非要住在岩浆附近？？)：



图12 猎杀虫的诞生

这种变体在翻滚式行进的同时会以弹跳的方式越过较高的较高的障碍物，对猎物进行偷袭：



图13 猎杀虫对人类基地进行偷袭

因此，我们可以对毒爆虫的生物学行为做出如下假设：
1.毒爆虫在接近猎物的过程中，因兴奋而导致其体内的酸性不断升高。个体间能够感知相互的酸度，并根此进行移动。
2.毒爆虫可以自爆或者在被击杀时爆炸，因此当群体内某一只毒爆虫与猎物非常接近时会采取自爆措施。爆炸时会产生一个溅射半径，处于该范围内的其余毒爆虫也会自爆，瞬间对猎物造成大量酸性伤害。(这就好像红警中的自爆卡车，一辆一辆过去送效率太低，不如直接大家一爆)
3.当有毒爆虫自爆后，种群内会再次产生相应数量的毒爆虫，以维持种群的狩猎能力。
4.群体内20%的个体因兴奋而以同等概率变异为分裂虫或猎杀虫。
5.若毒爆虫变异为分裂虫，则其爆炸后以爆炸点为中心的溅射半径内生成随机生成两个新个体。
6.若毒爆虫变异为猎杀虫，则其向酸度最高个体的行进速度加快。
毒爆虫优化算法

基于前文叙述我们可以确定，在毒爆虫种群内存在四种个体：普通毒爆虫、分裂虫、猎杀虫、分裂虫子代，因此在描述数学模型前，我们先将四者的身份id 记为id=1、id=2、id=3、id=4。
个体未自爆
当最优个体自爆后，毒爆虫会根据溅射半径来判断是否自爆。判断标准为：


其中mean(*)为求平均值的函数，X_best为当前最优个体位置，Rr 为溅射半径：


取ub、lb分别为搜索空间上、下限，考虑到维度越高，溅射的空间面积越大，故Rr 与维度D 成正比。若个体位于溅射范围以外，其会根据适应度值优于自身的个体及当前种群最优个体来进行位置更新，对猎杀虫则作单独处理：




式中，t 为当前迭代次数；Sum_better 为根据适应度值排序后优于当前个体的所有个体各维度之和，Sum_best 为当前最优个体的各维度之和；r1∈[0.5,1]、r2∈[-1,1]为系数向量；aci(t )表示当前最优个体的酸性吸引度：


其中X_bestp、X_bestip分别为前一次迭代中的最优位置、次优位置，X_besti 为当前迭代中的次优位置，为防止分母为0，本文参照麻雀搜索算法取一参数w。由式(2)可知，当r2<0时，个体i 呈远离最优个体的趋势，以进行全局搜索，r2>0时个体i 趋向于最优个体，实现局部搜索：



图14 当r2＞0时毒爆虫呈接近趋势



图15 当r2＜0时毒爆虫呈远离趋势

个体自爆
当毒爆虫位于溅射范围内时，其会随之自爆。若当前个体为分裂虫，其会产生两个新个体，即分裂虫子代，但该子代无法继续分裂或是变异。分裂虫的设定是为了在该较优个体附近产生更多个体，对搜索空间进行充分的局部勘探：


式中lower、upper分别为当前个体所有维度中的最小、最大值。对于除分裂虫外的其他类型个体，其位置将在下一次迭代时被替换：


此操作与分裂虫子代的形成相似，只不过这里的low(j )、upp(j )分别为当前种群在第j 维的最小、最大值。对于身份认定，为了便于理解，在公式(6)中增添了许多空格以使if与else相对齐：


其中N为当前种群规模。结合前文所述，BOA算法迭代伪代码如下：


性能测试

为了全面验证BOA算法的性能，现选取粒子群优化算法(PSO)、蝗虫优化算法(GOA)、灰狼优化算法(GWO)、麻雀优化算法(SSA)、鲸鱼优化算法(WOA)与BOA算法进行对比测试。
利用标准测试函数进行对比测试
首先我们利用部分单峰、多峰测试函数进行对比测试。16个标准测试函数详情如图16、图17所示：



图16 标准测试函数中的部分单峰函数



图17 标准测试函数中的部分多峰函数

取种群规模为30，维度为30，最大迭代次数为500，运算10次后记录运算平均值(MEAN)、运算方差(STD)、运算最优值(BEST)、运算最劣值(WORST)。本文选取前12个函数进行测试。运算结果如下：



图18 六种算法在F1上的迭代曲线



图19 六种算法在F2上的迭代曲线



图20 六种算法在F3上的迭代曲线



图21 六种算法在F4上的迭代曲线



图23 六种算法在F6上的迭代曲线



图24 六种算法在F7上的迭代曲线



图25 六种算法在F8上的迭代曲线



图26 六种算法在F9上的迭代曲线



图27 六种算法在F10上的迭代曲线



图28 六种算法在F11上的迭代曲线



图29 六种算法在F12上的迭代曲线



表1 六种算法在12个标准测试函数上的运算结果

对于单峰函数F1~F7，由表1可知BOA算法在F1、F2、F3、F4、F7上各项指标均排名第一，在F5、F6上SSA算法与其他算法性能相差较大，优化性能较佳；对比图18~图24可知，BOA算法在F1、F2、F3、F4上的在保证收敛精度的情况下同时具有最快的收敛速度，酸性吸引度指标起到了较大的引导作用；在F5F6F7上BOA算法收敛速度虽不及SSA算法，但相对于其他算法仍具有一定优势。
对于多峰函数F8~F12，由图25~图29可知面对复杂的多峰函数，大多数算法在求解过程中均出现长时间陷入局部最优值的状况，在F8上此现象尤为严重；在F12上SSA算法展现出了较佳的求解性能，BOA算法在F9、F10、F11上与SSA算法、WOA算法性能性能相似且较其他算法有一定优势，这得益于BOA算法中独特的变异机制。
利用标准工程测试函数进行对比测试
为了测试BOA算法的适用性，现利用粒子群优化算法(PSO)、生物地理学优化算法(BBO)、麻雀优化算法(SSA)、正余弦算法(SCA)、灰狼优化算法(GWO)与BOA进行对比测试，测试时取种群规模为50，最大迭代次数为100，运算20次后记录运算平均值(MEAN)、运算方差(STD)、运算最优值(BEST)、运算最劣值(WORST)。三种工程应用问题我在之前的博客中已经提到过了，为了进一步方便读者阅读，在此我将再次介绍各个问题。
1.焊接梁优化设计
该问题的目的是使焊接梁的制造成本最小化，焊接梁模型如图30所示：



图30 焊接梁结构设计（a）尺寸示意图（b）应力热图（c）置换热图

其包含如下约束条件：


上述五者分别为：剪切应力、梁内部的弯曲应力、杆上的屈曲荷载、梁端挠度、侧面约束。该问题的优化变量为：焊缝厚度(h)、钢筋附着部分长度(l)、杆的高度(t)、杆的厚度(b)。基于此，可得该问题的数学模型：


2.压缩弹簧优化设计
该问题的目的是使压缩弹簧的重量最小化。下图31为该弹簧模型：



图31 （a）弹簧示意图 (b）优化设计时的应力分布（c）优化设计时的位移分布

该问题存在三个待优化变量：钢丝直径(d)、平均线圈直径(D)、有效线圈数(N)。该问题的数学模型为：


3. 压力容器优化设计
该问题的目标是使一个两端有盖，头部为半球形的圆柱形容器的材料、成型和焊接总成本最小化，该容器的模型如图32所示：



图32 压力容器（a）尺寸示意图（b）应力热图（c）置换热图

同样，该问题也有四个待优化变量——壳体厚度(Ts)、顶部厚度(Th)、内半径(R)、忽略顶部的圆柱形截面长度(L):


该问题的数学模型为：


各算法对三种优化设计问题的求解结果如下：



图33 各算法对于焊接梁优化问题的迭代过程



图34 各算法对于压缩弹簧优化问题的迭代过程



图35 各算法对于压力容器优化问题的迭代过程



表2 各算法对标准工程测试问题的优化结果

很遗憾，BOA算法在标准工程测试问题上性能并不是很突出，仅仅优于PSO算法和BBO算法。GWO算法性能确实数一数二，难以匹敌。虽然BOA算法的求解最优值能和SSA算法、SCA算法、GWO算法在精度量级上比肩，但是其鲁棒性仍有提升。
总结
本期基于星际争霸II中毒爆虫的生物学特性，提出一种基于毒爆虫的新型元启发式智能优化算法。毒爆虫种群中的个体主要分为四类，每一类都具有不同的特性。将提出的算法在标准测试函数、标准工程测试问题上与其他算法进行对比测试，实验结果表明在标准测试函数上BOA算法较大多对比算法具有一定的性能优势，但在标准工程测试问题的优化上其性能仍有待提升。测试后我认为有这么几点可以改进的地方：改进分裂虫子代的特性、更改个体变异几率并测试、猎杀虫对于最优个体的趋近速度。
总之，能迈出这第一步是不容易的。我们一直把“创新”这个词挂在嘴边，但是真正能做出创新点又怎能那么简单？对于这个毒爆虫优化算法我仅仅是一时兴起，里面有一些创作思路也是借鉴了其他算法，所以我的这点操作也谈不上创新，就当博君一笑吧~~~
很是怀念当年和死党打星际的日子，可惜现在星际停更，玩起来也没有当时的乐趣了。不过当看到b站上一些相关视频时还是会感到热血澎湃，因为，我即是虫群!!!

FeastSC

楼主要不考虑下发表出来？[惊喜]

maltadirk

哈哈，承蒙厚爱，毒爆虫这个仿生的设定就有点小问题，上不了大台面，况且目前写的也不是很成熟，难登大雅之堂啊哈哈[爱]

RecursiveFrog

噢噢，完善一下嘛。我只是见你这想法这么新颖，实验结果也不错。可以搞个水刊投投，不过可能你对自己要求比较高哈哈哈

LiteralliJeff

大学刚毕业，没得基金经费[流泪]

mypro334

这么看工程应用和标准函数测试差别还挺大的，差的有点离谱

Doris232

肯定的，理论和实际还是有很大差别的