改进的萤火虫群优化算法及其非线性盲源分离

黄浦博，尉 宇，2

(1.武汉科技大学 武汉430070；2.华中科技大学 武汉430047）

1 引言

盲源分离（blind source separation,BSS）的提出起源于“鸡尾酒会（cocktail party）”，即从若干观测到的混合信号中恢复出无法直接观测的各个独立原始信号的过程，是信号处理中一个极具挑战性的课题。“盲”指两个方面：源信号未知；混合系统未知。源信号的未知因素导致了数学模型很难建立，于是对盲源的分离便顺其自然。对盲源分离的实质性研究最早开始于Jutten和Herault[1]两位学者。之后Sorouchyari和Comon[2]在Signal Processing上发表了关于该研究的文章。在工程实际中应用盲源信号分离时，绝大部分假设信号是线性混叠，但实际上，当信号通过传感器时很可能会发生非线性畸变，信号常常是非线性的。早期Hyvarinen[3]和Pajunen[4]对非线性混合模型解的唯一性问题进行了讨论。国内对盲源分离的研究起步比较晚，但近几年得到大力的发展。盲源分离方法已形成三大主流，即ICA、NMF[5]和SCA。目前对盲源分离的研究是很有意义的，盲源分离广泛运用于很多技术中，如语音信号分离与识别、数据通信与阵列信号处理、图像处理与识别和地学空间信息处理。非线性盲源分离的解决方法可以归纳为以下两类：运用自组织映射提取信号中的非线性分量的方法；基于假定非线性混合模型的方法。其中包括基于粒子群优化算法、基于自然梯度算法和基于稀疏成分分析算法等。本文采用萤火虫群优化 （glowworm swarm optimization,GSO）算法来研究非线性盲源分离问题。

2 非线性信号盲分离模型

相比于线性变换模型，非线性变换模型更适用于实际。本文采用Burel[6]两层感知器结构的非线性模型。

设有m个源信号，有m个观测信号。源信号s（t）=[s1,s2,s3,…,sm]T和观测信号x（t）=[x1,x2,x3,…,xm]T之间关系表示如下：

其中,xi表示为：

其中，s（t）=[s1,s2,s3,…,sm]T为m个源信号构成的m×1维向量，x（t）=[x1,x2,x3,…,xm]T是m×1维 观 测 数 据 向 量；m×m维矩阵A称为信号混合矩阵。F=[f1,f2,f3,…,fm]T是可逆的非线性变换矩阵。该模型为非线性混合[7]与分离模型。

如图1所示，该系统分为两部分：混合与分离。混合部分组成：混合信号矩阵A线性混合，独立非线性失真函数F=[f1,f2,f3,…,fm]T；分离系统组成：gi每一个通道的独立非线性反变换和W分离矩阵。输出信号yi（t）表示为：

这种数据的表示可写成矩阵的形式。

图1 非线性混合与分离模型

一般而言，非线性混合信号模型是将非线性问题根据某种规则转化为线性。非线性最大的难度在于参数的估计。这因为空间内存在大量的局部最优化问题。为解决这个问题，先后出现了用RBF（radial basis function，径向基函数）神经网络算法、遗传算法和粒子群优化算法等群智能优化算法，取得了较好的结果。本文拟采用基于优化的萤火虫群算法解决盲源分离问题。该算法具有操作简单、宜于并行处理、顽健性强等特点。

3 基于萤火虫群优化算法的非线性盲分离

3.1 萤火虫群优化算法简介

萤火虫群优化算法是群智能优化算法的一种新思路。已有较多相关的介绍与研究。该算法在解决连续型最优化问题方面表现出了良好的性能。在GSO算法中，每一只萤火虫分布在二维空间中，空间中萤火虫本身有萤光，每个萤火虫都有各自的视觉范围，即决策域半径。萤火虫的位置越好，荧光素值越高，萤火虫亮度越大，此时的目标函数值越接近所需结果，说明萤火虫亮度与自己所处位置有关。空间中，较亮的邻居拥有较高的吸引力吸引附近萤火虫往自己方向移动，萤火虫会在决策域半径内，根据一定的概率选择方向，并飞向邻居。不仅如此，决策域半径范围的大小会根据邻居密度的不同而受到影响，从而更新萤火虫决策域半径。密度较低，萤火虫的决策半径会加大，扩大范围，便于寻找更多的邻居；密度较高，则相对地会缩小。GSO算法的目标是为了达到种群寻优。解空间的每一个解被视为自然界中的萤火虫，初始解随机分布在搜索空间内，如同萤火虫随机出现在规定范围内。依照萤火虫的移动方式，解空间内每只萤火虫按规则移动。移动后更新萤火虫各参数，通过每次更新，最终使得大量萤火虫聚集在荧光素较高的萤火虫周围，找到多个极值点，达到目标。

群体在优化过程中，每次迭代都由4部分组成：荧光素更新、移动概率更新、位置更新、动态决策域半径更新。如下是GSO算法的基本步骤描述。

（1）初始阶段

初始化时，萤火虫解个体随机均匀地散布在解空间内，并且每只萤火虫拥有相同的荧光素和感知半径。在搜索空间内随机生成i（i=1,…,n）只萤火虫，且所有萤火虫都带有荧光素l0，动态决策域r0。

（2）荧光素更新

萤火虫的荧光素更新规则如下：

其中，ρ为荧光素衰减因子，介于（0,1），（1-ρ）为亮度衰减率，控制过去经验比重。γ为比例常数，控制此回合搜索解的经验比重。J（xi（t））代表的是在t回合第i个萤火虫所处位置xi（t）对应的适应度函数值，li（t）代表第t回合第i只萤火虫的荧光素值。萤火虫的荧光素更新等于萤火虫的当前适应度值减去随时间衰减的萤火虫素值。每一次萤火虫移动完毕，下一次开始前，萤火虫荧光素完成更新。

取目标函数值倒数的目的是因为目标函数求极小，目标函数越小的萤火虫，其亮度就越亮。计算亮度后，萤火虫与萤火虫之间在区域决策半径内以自己的亮度作为沟通的方式，从中挑选一个邻居，以此移动到较好的群中心位置上。

（3）寻找萤火虫i的邻居j

萤火虫比较自身决策域半径内邻居的荧光素的大小选择飞行方向，寻找荧光素比自己高的邻居。

||xj（t）-xi（t）||表示t时刻第i只萤火虫的邻居集合。0<（t）≤rs，是萤火虫j与i的欧几里得距离。为萤火虫个体i在t时刻的感知半径。其中，j∈Ni（t）。

（4）移动概率更新

萤火虫移动规则如下：

其中，移动方向由邻居集合中萤火虫荧光素值决定。Pij（t）表示t时刻第i只萤火虫向邻居集合中第j只萤火虫移动的概率。

（5）位置更新

设移动步长为b（b>0），第i只萤火虫由移动概率Pij（t）选择其移动方向移向邻域内个体j，即轮盘赌法则。第i只萤火虫的位置更新规则如下：

（6）动态决策域半径更新

萤火虫群优化算法采用自适应动态领域决策范围。规则如下：

其中，rs为萤火虫感知范围，rid（t）表示t时刻第i只萤火虫的决策范围，β表示领域变化率，ni表示个体领域集内包含的萤火虫数目阈值。

（7）判断是否达到最大迭代次数

若达到，则停止并输出结果，否则，转向步骤（2）。

3.2 改进萤火虫优化算法

GSO算法执行到后期时，会出现很多情况。比如，结果很快会陷入局部最优、求解精度不高、萤火虫个体在峰值附近出现震荡现象等。为了改进算法，之前提出了很多方法，如最佳萤火虫分布算法，在一开始便使得萤火虫个体的位置最佳，在原算法的基础上有效改进结果；自适应变步长萤火虫群优化算法，从搜索过程中改变萤火虫移动步长，此算法动态调整步长，处理好全局寻优能力和寻优精度之间的关系。

本文也是从算法中期对萤火虫群进行人工处理。人为将该群体放入镜子挡板，此时从视觉上看，萤火虫群体数量大，有效改善了萤火虫群的布局，丰富了萤火虫个体的多样性，丰富的群体多样性改善了求解精度不高的问题。加入挡板后的萤火虫群体中，个体由于附近的荧光素强度改变，决策域半径改变，移动概率更新，相应的位置也会更新，使得萤火虫群体跳出局部最优，个体重新搜索。本文将该现象称为“挡板效应”。采用该方式的GSO算法称为“BGSO”算法。该优化算法的重点在于，当完成一次基本GSO算法后计算得到评价函数值，再加入“挡板效应”，更新评价函数值，并比较两次评价函数值的大小，保留最优的函数值。下次重复该步聚，直到完成最大迭代次数，并输出结果。

当遍历一次后，在群体中加入人工挡板，用表达式表示为：

本文中ti∈[-1,1]，取m=4,此时迭代出来的结果互不相关。在原GSO算法中，群体适应度值差别大，在寻优过程中可能还有很少的个体保留下来。加入“挡板效应”的GSO算法，即BGSO算法，丰富了种群多样性，一定程度上抑制了GSO算法易陷入局部解的发生，提高了求解精度。

3.3 评价函数

对于盲源分离的评价函数可以有很多种形式，比如互信息最小化、信息传输最大化和负熵最大化等。本文采用互信息作为评价函数。

可以看出，I（y）=0时，说明yi相互独立。式（10）中H（yi）的计算需要估计yi的分布密度函数。对H（yi）的计算常用Edgeworth展开或者Gram-Charlie展开。由于Edgeworth展开在训练时存在发散问题，这里采用Gram-Charlier展开，其每一分量的熵H（yi）只与它的三阶累积量和四阶累积量有关：

为了使式（11）的期望值为0，方差为1，其在计算前需要对信号进行中心化和白化处理。中心化是减去信号中的均值矢量，从而使其成为零均值变量；然后对观测矢量进行线性变换得到新矢量，即白化。其各分量不相关且方差为1。这里采用I（y）的倒数作为评价函数，以此增强各随机变量之间的独立性。当评价函数得到最大值时，说明各个信号之间最接近独立。

J（xi（t））即式（4）中的适应度函数。式（12）中如果I（y）=0，说明各个信号之间独立。仿真时，I（y）越小，则越接近所需要结果，此时J（xi（t））也就越大。当J（xi（t））取最大值时，即全局最优解。

图2 BGSO算法流程

3.4 算法的应用

非线性混合分离系统中，各个通道的非线性参数空间相互独立。令非线性参数空间的萤火虫群为G=[G1，G2，…，Gn]，Gj=[gj1，gj2，…，gjp]。非线性函数与源信号的概率密度函数有关，但由于实际的源信号概率密度未知，因此一般根据不同分布情况采用不同的非线性函数。

基于BGSO算法的非线性盲源分离实现步骤如下。

步骤1读取源信号。

步骤2初始化非线性去混合函数参数。随机产生去混合函数参数G=[G1，G2，…，Gn]，Gj=[gj1，gj2，…，gjp]。

步骤3对yi（t）进行中心化和白化处理。按式（10）计算评价函数。

·若某个萤火虫的评价函数值优于其历史最优评价函数值，则记当前为历史最优值，同时该位置为历史最优位置。

·寻找当前各子群内最优和总群内部最优。

·当子群内历史最优萤火虫位置趋近于无变化时，在萤火虫内部使用“挡板效应”。

所有Sim(Kei，Kej)|∀i，j[1，2，…，n]构成一个模糊等价关系，也可表现为一个对称的相似度矩阵：

步骤4参数更新。对于非线性参数，按照改进萤火虫优化算法更新萤火虫荧光素、决策域半径、位置和适应度函数。

步骤5若达到最大迭代次数，则停止，并输出结果。否则转至步骤3。

4 实验仿真

本次采用两个语音信号、一个LFM雷达信号和一个高斯白噪声来验证算法的有效性。根据所得混合信号，随机产生混合矩阵A，并求得中心化和白化矩阵O。

选取的混合函数分别选为：

萤火虫个体数量n=40，最大迭代次数i_max=2 000。结合基本萤火虫算法，对参数初始化。ρ=0.4,γ=0.6,β=0.08,nt=5,s=0.03,l0=5。随机产生萤火虫初始位置xi（0）,初始步长si（0）。连续迭代不变化次数阈值Maxstep=20，并且规定最佳适应度变化率小于1/1 000,认为无变化。源信号图和中心化以及白化后的混合信号和分离信号如图3～图5所示。

求得的性能矩阵P=W·g（f（O·A））=y-1·S如下：

分离矩阵W如下：

图3 原信号s（t）

图4 混合信号x（t)

图5 分离信号y（t）

从性能矩阵中的数值可以看出，每一行都有一个数值远大于其他数值（例如，第一行第二列远大于该行其他数值）。而在盲源分离的算法研究中，性能指标常常运用交错误差表示。如下：

P的性能误差EP=0.976 1。性能矩阵受到了非线性混合函数的影响，但误差不大。另一方面证明了信号分离效果较好。

然而，在盲源分离中，分离输出信号yi与源信号si的相关系数也可以作为一个盲源分离算法的评价标准。定义如下：

分离信号i与源信号j由于误差不可能完全分离，ξij的值只能接近于1；而当该值趋近于0或者距离1较远时，则说明分离并未完成。将分离元素与源信号元素代入式（18）中，可得ξij=0.894 3，该结果接近1。由分析可知，分离结果非常接近源信号，可说明效果理想，分离完成。

在使用BGSO算法的过程中，不同的萤火虫子群对搜索成功率和达到最优路径的平均代数有影响。一般采用3～4个子群数的效果较好。子群之间重叠的萤火虫个数对成功率和达到最优路径的平均代数也有影响。重叠过多，易导致局部收敛；重叠太少，会导致迭代次数和时间的增加。由此看来对于空间维度较高的情况将使得搜索时间大大增加。

5 结束语

本文采用萤火虫群算法进行非线性混叠信号盲分离，并在原有的基础上进行改进，采用镜面反射的原理，运用到萤火虫优化算法中，较好地使结果得到改进，精确度得到提高。改进的方式需要让算法遍历一次后重新更新，步骤较为复杂。如何将步骤简化，并将结果与其他算法相比较，将是下一步需要做的工作。

1 Jutten C,Herault J.Blind separation of sources,partⅠ:an adaptive algorithm based on neuromimatic architecture.Signal Processing,1991,24（1）:1～10

2 Comon P.Independent component analysis,a new concept.Signal Processing,1994,36（3）:287～314

3 Hyvarinen A.Independent component analysis for timedependent stochastic processes.Proceedings of the International Conference on Artificial Neural Network（ICANN’98）,Sk’bvde,Sweden,1998

4 Pajunen P,Hyvarinen A,Karhunen J.Nonlinear blind source separation by self-organizing maps.Proceedings of the International Conference on Neural Information Processing,Hong Kong,China,1996（2）:1207～1210

5 Catral M,Han L,Neumann M,et al.On reduced rank non-negative factorization for symmetric non-negative matrices.Linear Algebra Application,2004（393）:107～126

6 Burel G.Blind separation of sources:a nonlinear neural algorithm.Neural Network,1992,5（6）:937～947

7 Woo W L,Khor L C.Blind restoration of nonlinearly mixed signals using multilayer polynomial neural network.IEE Proceedings on Vision,Image and Signal Processing,2004,151（1）:51～61

8 余先川.盲源分离理论与应用.北京：科学出版社，2011 Yu X C.The Theory and Application of Blind Source Seperation.Beijing:Science and Technology Press,2011

9 Krishnanand K N,Ghose D.Theoretical foundations for multiple rendezvous of glowworm-inspired mobile agents with variable local-decision domains.Proceedings of American Control Conference,Minneapolis,MN,USA,2006