基于改进花朵授粉算法与K-means算法的人体姿态库构建方法研究

2019-01-03徐达焦庆龙

兵工学报 2018年12期

徐达，焦庆龙

(陆军装甲兵学院兵器与控制系，北京 100072)

0 引言

维修性验证是对装备的维修性设计指标进行检验，其目的是全面考核装备是否满足规定的维修性设计要求[1-2]。当前，基于虚拟仿真的装备维修性验证方法凭借其良好的集成性、时效性和经济性等优点，已成为装备维修性验证的重要方法[3-4]。在该方法应用过程中，虚拟人体维修作业姿态(以下简称人体姿态)编辑次数繁多是较多领域的技术人员普遍反映的一个问题，且严重影响装备维修性仿真验证的效率。因此，如何对人体姿态进行预处理，是高效开展装备维修性仿真验证的一个难点。

针对这一难点问题，已有学者构建了人体姿态库[5-8]。该库中人体姿态案例的建立方法为首先建立虚拟人体的整体姿态(如蹲姿、站姿和跪姿等)，并在整体姿态基础上对虚拟人体各关节进行局部调整，进而得到各个人体姿态案例。这一方法虽然简单易行，但对于不同型号的装备或装备中不同的子系统，在较长的维修时间内，从宏观角度来看，维修人员的维修作业姿态势必具有目标维修任务的“烙印”。因此，文献[5-8]中所构建的人体姿态库的目标维修任务针对性存在不足，且难以确定有限数量条件下库中的人体姿态案例。沈亚斌等[9]认为在建立人体姿态库时应考虑处理相似的人体姿态，但并未给出有效解决该问题的方法。综上所述，如何在对大量相似人体姿态进行有效处理基础上[10-12]，构建满足目标装备维修性仿真验证任务需求的人体姿态库，具有十分重要的实际应用价值。目前，国内外还鲜见学者对这一问题的研究成果。

剑桥大学Yang[13]于2012年提出了花朵授粉算法(FPA)。该算法具有参数设置少、框架简明和搜索方式易于调节等优点[14]，已广泛应用于线性天线阵列优化[15]、离散空间优化[16]和拆卸序列规划[17]等领域，取得了良好的效果。但从文献[15-17]中FPA的寻优过程与寻优结果来看，FPA存在收敛速度慢和寻优精度不够理想的问题。乌鸦搜索算法(CSA)是伊朗学者Alireza[18]于2016年提出的一种新兴元启发式群体智能优化算法，该算法具有参数设置简便、搜索能力强和寻优效率高等优点。目前，国内外有关CSA应用于工程实践的文献较少[19-20]，而对CSA进行报道的中文文献则更为鲜见。鉴于CSA的优异性能，本文将CSA引入FPA，提出一种改进FPA(IFPA)，旨在有效地弥补FPA性能上的不足，并将IFPA与K-means算法相融合(记二者融合后的算法名称为IFPA-K)，通过IFPA-K有效地处理相似的人体姿态，构建能够有效地提高目标装备维修性仿真验证任务效率的人体姿态库。

1 FPA、CSA与IFPA简介

1.1 FPA简介

自然界中花朵凭借鸟类、昆虫和风等多种媒介进行传粉和授粉，Yang[13]根据花朵的这种繁衍方式和行为并通过科学地数学演化提出了FPA. FPA有两种授粉方式：全局授粉方式和局部授粉方式，这两种授粉方式通过转换概率Pt进行调节。文献[13]的研究结果表明，当Pt=0.8时，FPA的寻优效果较好。

令FPA的种群为X，种群规模(即花朵总数)为N1，迭代次数为T1，k∈[1,N1]，t∈[1,T1]，则全局授粉方式为

(1)

(2)

(3)

局部授粉方式为

(4)

(5)

记FPA的适应度函数为F，则在个体值比较结束后进行个体更新：

(6)

(7)

至此，第t次迭代计算即完成，FPA继续进行个体比较与迭代计算，直到满足终止条件时退出循环，并输出XB及F(XB)。

1.2 CSA简介

乌鸦被认为是较为聪明的鸟类之一，受自然界中乌鸦觅食和藏匿食物等众多行为的启发，Alireza[18]提出了CSA，并给出了CSA的4个准则：

1) 乌鸦是群居的鸟类。

2) 乌鸦能够记住它们藏身的位置。

3) 乌鸦能够相互跟踪去完成盗窃。

4) 在完成盗窃后，乌鸦能够以一定的概率保护它们藏身的位置。

(8)

2)乌鸦c已感知到乌鸦i跟踪它，则乌鸦c就会避免乌鸦i知道其藏身之处，乌鸦c就会飞到乌鸦d的位置来迷惑乌鸦i，则乌鸦i在第t+1次迭代时的位置为

(9)

至此，综合上述两种情形，乌鸦i在第t+1次迭代时的位置为

(10)

式中：r1为服从均匀分布的随机数，r1∈[0,1]；Pp为在第t次迭代时乌鸦c感知乌鸦i跟踪它的概率。

(11)

式中：kl与ku分别为个体取值的下限与上限。

(12)

(13)

对于调节CSA的搜索范围，Pp具有较为关键的作用。如果减小Pp，则CSA趋向于寻找局部最优解，此时CSA的搜索密集度较高；如果增大Pp，则CSA趋向于搜索局部最优解的可能性较小，而是在更大范围内搜索全局最优解。

1.3 IFPA简介

鉴于CSA能够有效地对搜索范围进行调节，本文将CSA引入FPA，提出一种IFPA。旨在通过CSA良好的搜索能力来扩展FPA的搜索空间，增加搜索到适应度函数值更优个体的概率，弥补FPA寻优精度不高、易陷入局部最优解的不足。IFPA的基本步骤如下：

步骤1算法参数初始化：N1、T1、β、σ、fl、Pp和Pt，设置X和x，令Xi=xi，i∈[1,N1]，k=t=1.

步骤2计算与比较种群X中个体的适应度函数值，得到XB及F(XB)。

步骤8如果Fmin≤F(XB)，则XB=S3，F(XB)=Fmin. 否则XB=XB，F(XB)=F(XB)。

步骤9如果k

步骤10如果t

步骤11迭代计算结束，输出XB及F(XB)。

2 仿真实验测试

选取4个智能优化算法测试函数对粒子群优化(PSO)算法[21]、FPA和IFPA进行测试和比较。这4个函数[22]分别为

(14)

式中：zm∈[-100,100]，该函数在zm=0时取得全局最优适应度函数值0，即f1的理论值。

(15)

式中：zm∈[-32.768,32.768]，该函数在zm=0时取得全局最优适应度函数值0，即f2的理论值。

陈升茶厂成立于2006年，经过12年的发展，已经成为一家拥有300余名员工，数百户签约农户，集普洱茶精制加工、生产、销售及茶文化和民族风情为一体的省级产业化重点龙头企业。而陈升茶厂所在的勐海县被称作“中国普洱茶第一县”，吸引着大批企业家投资设厂，其中包括一些不规范的代加工企业，他们在规范化生产、人力、设备等各方面投入成本低，有些甚至存在虚开发票等违法行为，严重影响和扰乱了市场秩序，对大型民营企业发展也造成了很大压力。

(16)

式中：zm∈[-600，600]，该函数在zm=0时取得全局最优适应度函数值0，即f3的理论值。

(17)

式中：zm∈[-5，5]，该函数在zm=0时取得全局最优适应度函数值0，即f4的理论值。

3种算法的特征参数设置如下：

PSO算法取惯性权重w=0.5，学习因子c1=c2=2；

FPA算法取β=1，σ=0.1，Pt=0.8；

IFPA算法取β=1，σ=0.1，fl=2，Pp=0.2，Pt=0.8.

令种群规模分别为30和80，迭代次数为2 000，独立计算次数为50，则3种算法的测试结果如表1所示。

表1 PSO、FPA与IFPA的测试结果

由表1可以看出，在相同的测试条件下，相比PSO和FPA，IFPA的4项指标结果均为最小，平均值的计算结果比PSO和FPA的平均值更加接近各测试函数的理论值，表明IFPA的寻优能力和寻优过程的稳定性明显优于PSO与FPA，验证了IPFA的优越性。

3 IFPA-K

3.1 K-means算法及其不足

K-means算法是MacQueen首次提出的一种高效的聚类算法[23-24]，该算法的目的是实现数据分类，即将M个R1维数据Y={Y1,Y2,…,Yl,…,YM}划分为D个类{C1,C2,…,Cs,…,CD}，使得同一类内的数据具有较高的相似性，不同类内的数据具有较低的相似性。数据聚类过程就是要找到一个D，使得数据聚类结果满足以下3个条件：

1)Cs≠∅，s∈[1,D]；

2)Cs∩Cu=φ，s、u∈[1,D]，s≠u；

并满足总的类间和类内的数据离散度和最小：

(18)

式中：J表示总的类间和类内的数据离散度之和，J值越小，表示聚类效果越好；当Yl与Cs的中心Hs距离相比Yl与其他各类的中心距离更小时，表明Yl∈Cs，l∈[1,M]；d(Yl,Hs)表示Yl与Hs的距离。

采用欧式距离来定义d(Yl,Hs)：

(19)

式中：Yl,o表示Yl的第o个维度数据；Hs,o表示Hs的第o个维度数据，s∈[1,D]。

K-means算法虽然具有很好的拓展性，但也存在以下两点不足：1)初始聚类中心的选取对K-means算法的聚类效果具有重要影响，如果初始聚类中心选取不当，将会导致聚类失败；2)易陷入局部最优解，得到全局最优解的机会较小，这与K-means算法采用梯度法进行聚类具有一定的关系。

3.2 IFPA-K个体编码及其操作函数

针对K-means算法存在的不足，部分学者将智能优化算法引入K-means算法，以借助智能优化算法较强的搜索能力和寻优能力来改善K-means算法性能。实例应用结果证明了这一做法的有效性[24]，使K-means算法的聚类效果有了大幅改善。为了更为准确地获取到各类的中心，使人体姿态案例具有更好的覆盖性，本文采用二进制编码方式来设计个体编码以及定义个体操作函数。

鉴于本文是采用各类中心来构建人体姿态库，可将IFPA-K初始种群中的每个个体定义为所有类的中心顺序排列，如图1所示。

图1 个体编码
Fig.1Individualencoding

设每个类的中心为h位二进制数，h可根据求解精度设定，则初始种群中的每个个体共有M1=Dh位二进制数。

为了便于后文对IFPA-K进行描述，首先定义两个个体操作函数：

1)交叉操作函数

交叉操作是遗传算法(GA)中个体更新的重要方式[25]，交叉操作使得优秀的基因片段能够在不同个体间进行传播，进而增加了优秀个体产生的概率。通常情况下交叉操作是由两个以上个体参与完成的，并根据参与交叉操作的个体数量来设计交叉方式。本文选取两个个体参与交叉操作，所设计的个体交叉操作方式为

Ic=λh·Ii+(D-λ)h·Ik，

(20)

式中：Ic为交叉操作产生的个体；Ii、Ik为参与交叉操作的两个父代个体，i、k∈[1,N1]，i≠k；λ为继承因子，λ∈[1,D-1]。

(20)式表示Ic分别从Ii与Ik中继承了λh位与(D-λ)h位二进制数，即将Ii的第1～第λh位与Ik的第λh+1～第M1位二进制数进行重组。交叉操作过程如图2所示。

交叉操作函数可定义为

Ic=fun(Ii,Ik,D).

(21)

2)变异操作函数

变异操作是GA的另一种个体更新方式，不同于交叉操作是由两个个体参与完成的，变异操作是由单一个体参与完成的，是一种基因强制突变的操作。该操作避免了基因片段重组所导致的基因更新方式受限问题，有效地丰富了种群的多样性。为增强该操作的有效性，首先产生1～M1的全排列G，而后根据M1长度取G的前R位数，对这前R位数所在位置的元素进行取反操作。操作过程如图3所示。

变异操作函数定义为

(22)

4 实例应用

4.1 维修作业姿态特征数据提取

以商业软件DELMIA为例，在编辑人体姿态时，技术人员通常是对虚拟人体的手臂和腿部姿态进行优先编辑，使人体姿态初步具有目标维修作业姿态的轮廓，然后对虚拟人体的腹部、头部和足部等部位姿态进行编辑，以实现人体姿态的舒展和协调。有鉴于此，选取虚拟人体的前臂、大臂、肩、大腿和小腿作为需要提取维修作业姿态特征数据的人体部位，这5个部位的动作范围(左侧、右侧部位的动作编号分别采用下标l和下标r进行区分)如表2所示。

表2 部位动作范围

目前，维修作业姿态数据采集有多种方法，例如可采用先进的动作捕捉设备，如Kinect[26]。该设备虽然对维修作业姿态数据采集具有实时、准确的特点，但价格较为昂贵。此外，在实装维修时，维修人员通常是在装备多个方位同时开展维修作业，为了使维修作业数据采集的更为全面，就需要对多台Kinect进行合理布局，从而进一步增加了费用。对此，本文采用人工方法来提取维修作业姿态特征数据，即采用拍照和录像方式对实装维修过程进行拍摄和录制，然后参照照片或视频中维修人员的维修作业姿态，将虚拟人体姿态编辑至与其相同，进而提取维修作业姿态特征数据。

需要说明的是，商业软件DELMIA共提供了5个国家(美国、法国、德国、日本和韩国)的虚拟人体模型，这5个国家中95%人体百分位的男性虚拟人体模型在表2中5个部位的动作范围上不存在差异。因此，可选择任意国家95%人体百分位的男性虚拟人体模型进行姿态编辑，实现维修作业姿态特征数据提取。

4.2 实验对比分析

以维修任务“某型装甲车辆动力舱吊舱”为例，本文共收集了400个实装维修时维修人员的维修作业姿态特征数据。令IFPA-K中β=1，σ=0.1，fl=2，Pp=0.2，Pt=0.8，B=1. 本文所设计的算法应用程序均采用MATLAB R2010a软件编写。

鉴于所选取的维修作业姿态特征数据在十进制数时R1=24，在转换为二进制数后维数较高，为了使变异操作能够有效地提高IFPA-K的局部搜索能力，令R=30，并将J作为IFPA的适应度函数模型。此外，共设置两组初始条件(记法为N1-D-T1)进行算法的测试和比较，分别为：初始条件1为200-5-3000；初始条件2为300-6-2000.

4.2.1 IFPA-K与未设置任何变异操作的IFPA-K对比分析

为了验证本文所设计的IFPA-K操作步骤合理性与优越性，现取消IFPA-K中所有的变异操作。实现这一目的需要完成以下4个步骤：

步骤1将图4中虚线框1中左侧、右侧两个实线框中的公式分别用(23)式、(24)式替换：

(23)

(24)

步骤2将图4中虚线框2中实线框中的公式用(25)式替换：

(25)

步骤3将图4中虚线框3中左侧、右侧两个实线框中的公式分别用(26)式、(27)式替换：

S1=XB,

(26)

(27)

步骤4将图4中虚线框4中左侧、右侧两个实线框中的公式分别用(28)式、(29)式替换：

(28)

(29)

至此，本文将未设置任何变异操作的IFPA-K记为IFPAWM-K，则在初始条件1和初始条件2时，IFPA-K与IFPAWM-K的最优适应度函数值变化情况如图5所示。

由图5可以看出，在相同的初始条件下，在迭代过程中的每一步，IFPA-K搜索到的最优适应度函数值均小于IFPAWM-K搜索到的最优适应度函数值，表明IFPA-K的寻优能力明显好于IFPAWM-K. 此外，IFPA-K与IFPAWM-K搜索到的最优适应度函数值相差较大，表明变异操作对IFPA-K寻优过程和寻优结果具有重要影响。这是因为变异操作不同于交叉操作的基因重组，它是通过基因强制突变的方式给种群注入了“新鲜血液”，有效地剔除了原有个体中的不良基因，提高了IFPA-K的局部搜索能力。IFPAWM-K的最优适应度函数值在迭代计算的早期存在一定程度的下跌，但这个过程极为短暂，最优适应度函数值很快地就过早收敛，算法不易跳出局部最优解，无法实现良好的数据聚类。同时对比结果表明，通过交叉操作虽然能够改善IFPA-K的搜索能力，但改善程度较小，远不如变异操作对IFPA-K搜索能力的改善程度。

4.2.2 IFPA-K与其他算法对比分析

将PSO算法、GA、蝙蝠算法(BA)[27]、FPA和CSA分别与K-means算法融合，并记融合后的算法名称分别为PSO-K、GA-K、BA-K、FPA-K和CSA-K. 将这5种算法与IFPA-K进行比较。各算法的特征参数及GA-K的主要操作步骤如下：

PSO-K算法取w=0.5，c1=c2=2；

GA-K算法取交叉概率Pc=0.95，变异概率Pm=0.05，个体选择方式为轮盘赌选择，个体的交叉操作方式和变异操作方式为本文所设计的交叉操作方式和变异操作方式，令R=30；

BA-K算法取脉冲响度A=0.95，脉冲频度ν=0.05，脉冲响度衰减系数ε=0.95，脉冲频度增强系数γ=0.05；

FPA-K算法取β=1，σ=0.1，Pt=0.8；

CSA-K算法取B=1，fl=2，Pp=0.2.

则在初始条件1和初始条件2时，IFPA-K与上述5种算法的最优适应度函数值变化情况如图6所示。

由图6可以看出，在相同的初始条件下，IFPA-K搜索到的最优适应度函数值明显小于其他5种算法搜索到的最优适应度函数值，验证了IFPA-K寻优能力的优越性。此外，可以看出IFPA-K具有较快的搜索速度，在迭代计算的早期，IFPA-K相比其他5种算法，能够以更快的搜索速度从最大的适应度函数值下跌，趋向最小的适应度函数值。且整个搜索过程平稳有序，未出现GA-K在搜索过程中出现适应度函数值“跌宕起伏”的现象，表明IFPA-K的搜索过程具有良好的稳定性。这是因为CSA通过Pp对全局搜索方式和局部搜索方式进行转换，而FPA则通过Pt对全局授粉方式和局部授粉方式进行转换。在将CSA引入FPA后，通过CSA的搜索方式有效地拓展了FPA的搜索空间，并将IFPA中基于CSA的搜索方式与基于FPA的授粉方式分别得到的个体适应度函数值进行比较，使IFPA能够搜索到适应度函数值更为优秀的个体，使IFPA-K在迭代计算结束时所求取的最优适应度函数值为最小的适应度函数值。

鉴于图6中FPA-K与IFPA-K的寻优结果较为接近，令初始条件2时，IFPA-K中Pp=0.1，其余参数保持不变。将两种算法各独立计算15次。两种算法求取的最优适应度函数值分布情况如图7所示。

在15次独立计算结果中，IFPA-K与FPA-K搜索到的最大的最优适应度函数值分别为41 369与41 658，最优适应度函数值的平均值分别为40 540.5与40 873.9，最优适应度函数值的方差分别为461.88与471.24，最小的最优适应度函数值分别为39 651与39 744。纵观这4项指标的计算结果，IFPA-K均小于FPA-K，验证了IFPA-K的优越性。在图6(b)中，IFPA-K求取的各类中心数据如表3所示。

表3 初始条件2下IFPA-K求取的各类中心

将表3中各类中心数据作为虚拟人体的各部位动作角度输入参数，所得到的人体姿态案例如图8所示。基于图8的人体姿态案例所构建的动力舱吊舱人体姿态库如图9所示。

由图8可以看出，动力舱吊舱的人体姿态主要体现为站姿、跪姿和蹲姿，其中C1～C6所包含的人体姿态数量分别为2、145、61、32、56和104，站姿(C2、C4和C5)和蹲姿(C3和C6)分别包含了233个和165个人体姿态，占据人体姿态总量的99.5%. 人体姿态的聚类结果能够体现出动力舱吊舱过程中维修人员在多数时间时的维修作业姿态，与实际情况相符。

本文所提出的人体姿态库构建方法有效地解决了在人体姿态案例较少情况下，如何构建人体姿态库的难题。避免了文献[5-8]中人体姿态库构建方法存在的维修性仿真验证任务针对性不足、无法确定人体姿态案例的问题。实践应用结果表明，相比文献[5-8]中的人体姿态库构建方法，在开展动力舱维修性仿真验证时，基于本文所构建的人体姿态库，在设定目标人体姿态后，更为容易地在人体姿态库中对人体姿态案例进行选取。同时，虚拟人体部位动作角度编辑的幅度明显减小，人体姿态案例与目标人体姿态的贴合度较高，维修性仿真验证的效率有了明显提高，体现了本文所提出的人体姿态库构建方法的有效性和优越性。