结合遗传算法的匹配追踪算法的性能分析﹡

高丽贞

0 引言

匹配追踪[1]( MP, Marching Method)是谱分解算法的一个重要分支。MP算法的原理简单，便于实现。但是MP算法在每一次求精的分解过程中，需要在超完备展开函数集合中找最优原子，是一个非常耗时的过程。因而，庞大的计算量成为MP算法在实际应用中的瓶颈。

近年来，不少学者发展了很多 MP算法的改进算法[2-5]，均具有一定的实际意义。其中，遗传算法[6](GA，Genetic Algorithm)是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。文中采用遗传算法来减少匹配追踪算法的计算量，得到了相同的匹配结果，显著提高了计算效率。

1 算法的原理及其实现步骤

1.1 MP算法的原理

加法信号模型表示自然信号，在信号处理与数据分析等领域一直得到非常广泛的应用。该模型用公式可以表示为：

式中，f(t)表示信号，hn(t)表示信号的基函数，an表示基对应的系数。即，信号被分解为加权的基函数的迭加形式。

匹配追踪算法实际上是上述式(1)的近似求解方法。令 H表示 Hilbert空间，定义 H中的原子库D = ( ei)i∈I，且满足ei= 1。其中， ei是通过对一个简单窗函数 g (t)∈ L2(R)的时间平移、频率调制和尺度变换，而生成一个过完备时频原子库，式子表述为：

式中，任意的 0s＞ 为尺度变换参数，ξ为频率调制参数，u为时移参数。

令信号fH∈，为了尽可能逼近f，MP算法首先从过完备子库中选择最为匹配的一个原子0e，即满足：

这样，信号经过第一步分解，得到如下形式：

式中， R1f表示信号 f由原子 e0表示后，所产生的残差(误差)。显然 e0和 R1f正交，因此，

为了使得逼近误差的能量最小，必须选择 e0使得最大。在无穷维或者高维的情况下，由于计算复杂度的限制，通常无法找到的最大值，只可能选择在一定意义上的近似最佳原子 e0，使得

式中，0＜α＜1为优化因子。接下来，不断地对产生的残差进行与f同样的分解操作。也就是MP过程是一个不断地将残差投影到原子库中一个最匹配它的向量熵，从而继续对它进行分解。假定将上述分解过程已经执行到了 n+1阶，由于 en与 Rn+1f正交，那么

此时，信号f可以表示为以下求和形式：

类似的，能量可表示为：

1.2 GA算法的原理

遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（Generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。

遗传算法作为一种高效并行的全局搜索方法，其一般步骤包括：

（1）创建一个随机的初始状态

初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代。

（2）评估适应度

对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。

（3）繁殖(包括子代突变)

带有较高适应度值的那些染色体更可能产生后代(后代产生后也将发生突变)。后代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。

（4）下一代

如果新的一代包含一个解，能产生一个充分接近或等于期望答案的输出，那么问题就已经解决了。如果情况并非如此，新的一代将重复他们父母所进行的繁衍过程，一代一代演化下去，直到达到期望的解为止。

1.3 结合GA算法的MP算法

结合GA算法的MP算法执行步骤与MP算法基本一致，需要改变的是：将原子的参数组和信号或信号残差与原子的内积的绝对值分别作为GA算法中的染色体和适应度函数，进而利用GA算法在过完备库中寻找最佳匹配原子，该过程如图1所示。

图1 GA算法寻找最佳匹配原子程序流程

2 MP算法及其结合GA算法的仿真实例

文中全部仿真利用MATLAB实现。程序选取从较有代表性的原始图像(如图 2所示)中抽取出来的一维数据作为一维输入信号。分别使用编写的 MP算法代码和GA-MP算法代码进行30次分解（即将输入信号分解为30个原子）的测试实验，运行结果和分析讨论如下（如图3、图4、图5、图6、图7、图8、图9和图10所示）。

图2 原始图像

图6 和图10分别是MP算法和GA-MP算法执行30次分解以后所得的最终结果。可见，两种算法的重建信号较好地近似表示了输入信号，且使用这两种方法所重建的信号在直观上相差无几。

图3 原始信号

图5 MP分解后的残差信号

图4 MP算法选中的最优原子

图6 重建信号

图7 原始信号

图9 GA-MP算法分解后的残差信号

图8 GA-MP算法选中的最优原子

图10 重建信号

图11 是两种算法历次分解所耗费的CPU时间比较图。其中，横坐标表示迭代次数，纵坐标表示CPU时间。图11证明了结合GA算法的MP算法可以大大提高原始MP算法的计算速度，并且随着分解次数的增加，GA-MP算法效率高的优点越明显。因此，GA算法可以很好地消除MP算法在实际应用中的瓶颈之限。

图11 两种算法各次分解所耗费的CPU运行时间比较

3 结语

MP算法由于其具有原理简单、便于编程等优点，已经成为目前最常用的信号稀疏分解和谱分解方法。但是，该算法通常需要很大的计算量，使得它在实际应用中对处理器等设备的要求非常高，而且无法对数据进行实时处理。文中介绍了用遗传算法实现匹配追踪分解的方法，通过仿真证明了这种方法可以搜索到最佳匹配信号结构的参数，并且计算时间有大幅的降低。目前，不少学者发展了很多遗传算法的改进算法[7-9]，下一步的工作是结合改进遗传算法实现MP算法来弥补遗传算法易出现局部最优解的缺陷。

[1] MALLAT S,ZHANG Z.Matching Pursuits With Timefrequency Dictionaries[J].IEEE Transactions on Signal Processing,1993,41(12):3377-3415.

[2] 范虹,孟庆丰.用混合编码遗传算法实现匹配追踪算法[J].西安交通大学学报,2005,39(03):295-299.

[3] 高强,张发启.遗传算法降低匹配追踪算法计算量的研究[J].振动、测试与诊断,2003,23(03):165-167.

[4] LIU Q, WANG Q, WU L. Dictionary with Tree Structure for Matching Pursuit Video Coding[J].Electronics Letters,2000,36(15):1266-1268.

[5] 高飞,玉振明.匹配追踪分解算法的简化实现[J].广西大学梧州分校学报,2002,12(01):35-37.

[6] 陈国良,庄镇泉.遗传算法及其应用[M].北京:人民邮电出版社,1996.

[7] 邱柳钦.改进遗传算法在MF-TDMA资源规划中的研究[J].通信技术,2013,45(04):117-120.

[8] 余意,陈宇拓,李键红.基于 TSP问题的混合遗传算法研究[J].信息安全与通信保密,2009(03):101-103.

[9] 朱祥贤,潘汗怀,吕明.基于改进遗传算法的传感器非线性校正[J].通信技术,2009,42(03):156-158.