第３９卷 第９期 Ｖ＿０１．３９ Ｎｏ．９ 计算机工程 ２０１３年９月 Ｓｅｐｔｅｍｂｅｒ ２０１３ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ・人工智能及识别技术・ 文章缩号：１ｏｏｏ＿一３４２８（２ｏ１３）ｏ９＿＿ｏ２４５．－＿ｏ５ 文献标识码：Ａ 中圈分类号。Ｖ２７９ 动态航迹规划关键技术研究 杨俊 ，朱摘凡 ，张健 ，郝震 （１．空军工程大学工程学院，西安７１００３８；２．中国人民解放军９４２７０部队，济南２５０１１７） 要：针对实际作战环境中常遇到的突发威胁、运动威胁、任务改变等情形，提出一种基于战场态势预测的滚动粒子群优化多 步预测规划算法。采用卡尔曼滤波和随机理论分别完成对威胁源指定时刻的状态预测和任务目标的概率对准，改进高效粒子群优 化算法，并将其运用到局部滚动优化过程中，以多步规划、单步执行的形式实时调整航迹。仿真结果表明，该算法对战场威胁态 势具有预测作用，对任务的改变反应灵敏，能较好地满足动态环境下的实时性要求。 关健词：态势预测；运动威胁；滚动粒子群优化；卡尔曼滤波；动态规划 Ｒｅｓｅａｒｃｈ ０ｎ Ｋｅｙ Ｔｅｃｈｎｏｌｏｇｙ ０ｆ Ｄｙｎａｍｉｃ Ｆｌｉｇｈｔ Ｐａｔｈ Ｐｌａｎｎｉｎｇ ＹＡＮＧ Ｊｕｎ ，ＺＨＵ Ｆａｎ ，ＺＨＡＮＧ Ｊｉａｎ ，ＨＡＯ Ｚｈｅｎ ｆ１．ＥｎｇｉｎｅｅｒｉｎｇＩｎｓｔｉｔｕｔｅ，ＡｉｒＦｏｒｃｅＥｎｇｉｎｅｅｒｉｎｇＵｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｎ ７１００３８，Ｃｈｉｎａ；２．Ｔｈｅ ９４２７０Ｕｎｉｔ ｏｆＰＬＡ，Ｊｉｎａｎ ２５０１１７，Ｃｈｉｎａ） ［Ａｂｓｔｒａｃｔ｜Ｆｏｒ ｓｏｍｅ ｃａｓｅｓ ｏｆ ｎｅｗ ｏｒ ｍｏｖｉｎｇ ｔｈｒｅａｔｓ ａｎｄ ｔａｓｋ ｃｈａｎｇｉｎｇ ｉｎ ｔｈｅ ｐｒａｃｔｉｃａｌ ｄｙｎａｍｉｃ ｃｉｒｃｕｍｓｔａｎｃｅ，ａ ｎｅｗ ｒｏｌｌ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ（ＰＳＯ）ｍｕｌｔｉｓｔｅｐ ｆｏｒｅｃａｓｔｉｎｇ ｐｌｎｎｉａｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｂａｔｔｌｅｆｉｅｌｄ ｓｉｔｕａｔｉｏｎ ｐｒｅｄｉｃｔｉｏｎ ｉｓ ｐｒｏｐｏｓｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ．Ｂｙ ｕｓｉｎｇ ｔｈｅ Ｋａｌｍａｎ ｆｉｌｔｅｒｉｎｇ ａｎｄ ｐｒｏｂａｂｉｌｉｔｙ ｔｈｅｏｒｙ，ｉｔ ｃｏｍｐｌｅｔｅｓ ｔｈｅ ｓｉｔｕａｔｉｏｎ ｐｒｅｄｉｃｔｉｏｎ ｆｏｒ ｔｈｒｅａｔ ｓｏｕｒｃｅ，ａｎｄ ｔｈｅ ｐｒｏｂａｂｉｌｉｔｙ ｏｆ ｔｈｅ ｔａｒｇｅｔ ｔａｓｋ． Ｃｏｍｂｉｎｅｄ ｔｈｅ ｕｐｇｒａｄｅ ＰＳＯ ａｒｉｈｍｅｔｔｉｃ ｗｉｔｈ ｈｅｔ ｒｏｌｌ ｏｐｔｉｍｉｚａｔｉｏｎ，ｉｔ ｃａｒｌ ａｄｊｕｓｔ ｈｅｔ ｐａｔｈ ｉｎ ｒｅａｌ ｔｉｍｅ ｂｙ ｍｕｌｔｉ－ｓｔｅｐ ｐｌａｎｎｉｎｇ ｎｄ ａｏｎｅ－ｓｔｅｐ ｅｘｅｃｕｔｉｎｇ．Ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔ ｉｎｄｉｃａｔｅｓ ｔｈａｔ ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｐｌａｙｓ ｗｅｌｌ ｉｎ ｄｙｎａｍｉｃ ｃｉｒｃｕｍｓｔａｎｃｅ ｅｓｐｅｃｉａｌｌｙ ｉｎ ａｓｐｅｃｔ ｏｆ ｐｒｅｄｉｃｔｉｏｎ ｔｈｅ ｔｈｒｅａｔ ｓｔａｔｅ ａｎｄ ｒｅｓｐｏｎｄｉｎｇ ｔｏ ｔｈｅ ｔａｓｋ ｃｈａｎｇｉｎｇ． ［Ｋｅｙ ｗｏｒｄｓｌ ｓｉｔｕａｔｉｏｎ ｐｒｅｄｉｃｔｉｏｎ；ｍｏｂｉｌｅ ｔｈｒｅａｔ；ｒｏｌｌ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ（ＰＳＯ）；Ｋａｌｍａｎ ｉｆｌｔｅｒｉｎｇ；ｄｙｎａｍｉｃ ｐｌｎｎｉａｎｇ ＤＯＩ：１０．３９６９￣．ｉｓｓｎ．１０００－３４２８．２０１３．０９．０５５ １概述 在飞行器智能规划领域中，航迹规划问题受到了相当 的重视。当具备了完整精确的环境信息后，可用一次性的 地面离线规划来得到一条飞行路线。 原理、随机概率理论、正交实验设计等思想引入到该算法 中，用于动态变化着的战场环境。 ２ 问题描述 给定一个规划区域建立坐标系，其上分布着种类不同 的威胁区，如雷达威胁、防空火力威胁等，每种威胁区的 威胁概率函数不尽相同，但都是关于飞行器与其中心位置 距离的函数，服从柏松分布ｐＪ。为了便于观察最终的规划效 果，将所有威胁的威胁概率函数都视为防空火力威胁概率 模型，禁飞区则视为威胁概率无限大的一片区域，如下： Ｐ：ｅ— —但在大多数情况下，战场环境是存在诸多未知因素的， 具体表现在未知威胁出现的突发性、运动威胁参数的不确 定性、未知威胁源数量的不确定性以及任务目标的临时变 动。在此种情况下，若仍旧按照原先的航迹飞行，势必会 给飞行器造成极大的安全隐患，因此，有必要根据动态变 化的环境对航迹进行实时调整。 目前，已有的动态航迹规划方法主要有人工势场法 Ｊ、 动态窗ＶＩ法 Ｊ、矢量场图 、模糊控制算法 等，但这些 方法并没有考虑到无人机运动与威胁环境的耦合关系，往 往只是在战场态势发生变化后被动地做出规避，缺乏预见 Ｒｍａｘ—－ｔ＂ 威胁源或是任务目标的位置状态模型可以描述成以下 形式： ｘ（ｋ＋１）＝Ａ・ （ ）＋ｑ（ｋ） （２） 性，从而未能充分利用实时战场信息，降低了实时航迹的 生成质量，严重时甚至造成规划失败。针对此情况，本文 提出一种基于战场态势预测的改进粒子群优化（Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）滚动搜索算法，并将卡尔曼预估 作者简介：杨其中，矩阵Ｘ＝［Ｘｋ Ｙ Ｐｋ］ 分别为笛卡尔坐标系下 威胁源或目标的位置和速度信息；Ａ为状态转移矩阵；矩 阵 为过程噪声。 凡、张健，副教授；郝震，助理工程师 俊（１９８７一），男，硕士研究生，主研方向：智能控制；朱收稿日期：２０１２—０３－２Ｏ ．＿｝回日期：２０１２－０５—２１ Ｅ－ｍａｉｌ：ＭａｊｏｒＭａｊｏｒ＠ｆｏｘｍａｉｌ．ｃｏｍ 计算机工程 ２０１３年９月１５日 由于战场实时威胁信息的获取主要以机载雷达为主， 因此要使飞行器具有实时航迹规划能力，其探测距离须长 于威胁半径或是地面信息中心能够在飞行器进入突发威胁 区域之前为其提供相关信息。同时，受基于安全飞行曲面 思想的启发，可以将三维空间规划问题转换为二维规划问 题。动态路径规划示意图如图１所示。其中，Ｄ ￣Ｄ 为静止 威胁区；Ｊｌ为突发威胁区；Ｊ２为移动威胁区；虚线圈为初始 威胁区域；点横线圈 为当前威胁区域。 图１动态路径规划示意图 ３基本原理 本文动态航迹规划算法是基于战场态势预测分析的滚 动搜索粒子群优化算法。滚动规划思想是解决未知环境下 规划问题的一种常见办法 Ｊ，其具有实时性强、能充分利用 已探测到的局部信息以及计算量小的特点，将其与地面离 线规划中常用的粒子群优化算法相结合，能有效地改善局 部窗口路径搜索的适用性和最优性。通过对战场态势进行 预测分析、多步预规划、单步执行，能够对变化的战场态 势提早做出调整。由于执行的每一步都是当前最优的，因 此保证了整条航迹也是最优的。动态航迹规划求解框架如 图２所示。 图２动态航述规射求解框架 ４战场态势预测及分析 将战场态势预测分析引入到实时规划中，可以提高算 法对环境适应的主动性。其分为２个部分：（１）对突发威胁 及运动威胁的态势预测；（２）任务目标的事件触发更新。通 过对威胁源及任务目标的预测分析，以为接下来的滚动规 划做准备。 ４．１威胁态势预测 威胁的态势预测是通过预测威胁源的位置走势情况， 以此作为未来一段时间航迹规划的依据。其目的是尽量避 免将来与威胁源“相撞”，因此，需要估算出未来两者可 能相遇的最近时间点ｔｅ，并将对应的时间段作为每次预测 的时间跨度ｔＬ，由于该时刻与无人机运动以及威胁源运动 三者之间存在耦合关系，因此每次更新都应该重新估算出 最近的相遇时刻ｔｅ，每次预测的时间跨度ｔＬ也会有所不同。 有了ｔｅ就可以反向推算出该时刻威胁源的位置 。规划窗 口每向前滚动一次，就需对当前窗口内的威胁态势更新一 次，更新周期 与滚动周期 一致。威胁态势预测如图３ 所示。 图３威胁态势覆 设当前飞行器位置为向量，移动威胁源中心位置为向 量 ｄ，将两者速度在固定坐标系上进行正交分解，可以想 象当飞行器在水平方向或是竖直方向“追上”威胁源运动 时，两者最有可能相遇，即飞行器落入威胁范围以内。由 两者相对运动关系，相遇时刻近似表示如下： （１）水平方向： ｔＣ＋Ｌ，ｘ ｔ＝ｃ ＋ ＋ （Ｓ － Ｒ）ｃ ｏｓＯ１‘３） ） （２）竖直方向： ｔＣ＋Ｌｙ＝ｔＣ＋ （Ｓ － Ｒ）ｓ ｉｎ０ １ （‘４） ，式（３）、式（４）分别为按Ｘ方向和按Ｙ方向估计出有可能 相遇的时间ｔｃ 、ｔｃ ，结果取距现在最近的时刻， ｃ 为当前时刻。于是，相遇时刻威胁源中心位置的估计值 便为： Ｉ ＝ＸｄＣ ３－ 。（ｔｃ＋三一ｔｃ） … 【 以＝ ＋ ｖ・（ｔｃ＋ｆＪ—ｔｃ） 其中， 、 为威胁源中心位置； 、 ６ 为威胁源 在更新周期内根据多个采样点所计算出来的速度预测值， 在此引入卡尔曼滤波对威胁源速度进行实时预测。 设状态向量 ＝［Ｘｋ Ｙ Ｙｋ］ 为威胁源中心 的位置和速度信息。由牛顿运动学定律写出以下状态方程 和观测方程： 第３９卷第９期 杨俊，朱凡，张健，等：动态航迹规划关键技术研究 ２４７ （１）状态方程： Ｘｋ＋１＝ ・ ＋ｗｋ （６） （２）观测方程： Ｚｋ＝Ｈｋ‘Ｘ ｋ七ｙｋ （７） 状态转移矩阵 为： １ ０ ０ ０ １ ０ ： ０ ０ １ ０ （８） ０ ０ ０ １ 观测矩阵巩为： ｒ１ ０ ０ ｏ７ １ ０ ０ ｆ （９） 其中， 为滤波更新周期；估计误差 、观测误差 分 另０为状态方程和量测方程的随机干扰向量。两者均为零均 值正态自噪声序列，可用协方差矩阵 、 表示如下： ：Ｅ［Ｗｋ・ 】 （１０） Ｒｋ： ・ ］ （１１） 系统的滤波回路方程为： （１）系统状态预测： ＋１／ｋ＝ ＋１． （１ ２） （２）系统滤波估计： ＋ｌ＝ ＋１／ｋ＋ ＋１（ ＋１一 ＋１ ＋１／ｋ） （１３） 由于威胁的预测周期 与滚动周期 一样，２次更新 之间间隔相对较长，此时，状态转移阵 １若仍视为定 常矩阵将会出现失真。为了充分利用实时观测信息，可以 在一个滤波周期内抽取Ⅳ个采样值，用级数的方法来求取 ＋１．ｋ ： Ｎ－１ ￣ｋ＋ｌ ｋ Ｊ＋△ ∑ （ ） （１４） ｉ＝０ 其中， （ ）＝ （ｔｋ＋ｉＡＴ），ｉ＝０，１，…，Ｎ－１。 此外，增益计算回路方程如下： （１）误差协方差预测： ＝ １ 一１ 一１＋ １ （１５） （２）增益系数： Ｋ℃： Ｈ Ｈｋ Ｈ ＋Ｒｋ １ ｔ１６ （３）先验协方差更新： ： ～Ｋｋ （１７） ４．２目标概率对准 整个规划过程是滚动式更新过程，故每次局部路径更 新应设置相应的子目标点。子目标点不仅关系到局部窗口 路径规划的最优性，同时，对全局最优性也有一定影响。 从航迹初始段到末尾段，飞行器不断逼近任务目标，规划 的定向性也随之加强，当规划窗口滚动到最后时，窗口子 目标点也就是任务目标。由此，本文提出一种基于方差可 调的目标概率对准模式。概率对准模式示意图如图４所示。 圈４概率对准模式示意图 如图４所示，子目标的生成区域为以基准点为中心， 标准差为 的线区域段ＡＢ内，该区域内任意点被选为子目 标点的概率服从高斯分布。 １ 一 ｆ（Ｙ）＝ ｅ （１８） Ｚ兀Ｄ 随着飞行器与任务目标的逐渐接近，任务目标对局部 规划的影响逐步增大，因此，要不断减小随机子目标的生 成范围，使之向基准点靠拢。在此，可令目标候选范围 按 以下方式自适应调整： Ｓ｝ Ｄ ‘ ａｘ （１９） ０ 这样在规划初始阶段放宽任务目标对局部规划的约 束，增大了规划灵活性，而在规划后期则加强规划的定向 性，以保证快速抵达目标。 ５基于滚动粒子群的实时规划 滚动粒子群算法结合了滚动时域优化思想和粒子群优 化算法 Ｊ全局搜索思想，根据态势预测的信息，在滚动窗口 中反复利用改进粒子群优化算法更新搜索局部路径，使得原 本适用于离线规划的粒子群优化算法能用到实时规划中来。 ５．１规划策略 整个算法分为窗口的滚动和窗口内局部路径的搜索更 新。从航迹起点到航迹终点，规划窗口滚动式前进，每向 前滚动一步都要根据先前预测的态势信息对窗１３内的局部 路径进行搜索。将局部航迹进行编码，便可以将改进后的 粒子群优化算法引入到航迹的寻优过程中。对于每次规划 出的局部航迹，无人机只是执行其中的一部分，也就是所 谓的多步规划，单步执行。这样便保证了生成的航迹既有 一定的预见性，又有灵活调整的余地。 ５．２航迹编码及代价函数 选定规划步长Ｓ，确定窗口大小三后，便可以得出规划 步数为Ｎ＝Ｌ／ｓ，相应的粒子的维数便为Ⅳ＋１。对当前窗口建 立局部坐标系，如图４所示，由于每个航路点只能在对应 的垂线上游走，因此一条局部航迹用一组纵坐标即可表示， 每个粒子表示着一条航迹，编码如下： ｘ＝［Ｙｌ，Ｙ２，…，ＹⅣ＋１］ （２０） 每一条航迹的代价可描述为： ２４８ 计算机工程 ２０１３年９月１５日 Ｊ＝Ｑｌ。 ∑Ｄ（ａ ，ａｉ＋１）＋Ｑ２∑Ｉ４ａｆ，ａｉ＋１） ｉ＝１ ｉ＝１ （２１） ５．４防早燕机制 针对粒子群优化算法后期容易出现的早熟停滞【ｌ 情 况，本文提出一种早熟判断机制，一旦算法有早熟的趋势， 就用一个随机值代替当前最优解，以便扰乱粒子的当前搜 索方向，使其跳出局部最优。这样就可大大减少无效迭代 次数，从而实现算法的快速收敛。具体方法为：当得到的 其中，Ｄ（ａ ，ａｆ＋１）代表２个相邻航路点的总威胁值； Ｉ４ａｆ，ａｉ＋１）代表两相邻航路点的总路程；Ｋ为等效系数，用 以解决威胁值与路径长度单位不统一；Ｑ１、Ｑ２为两者权 值。对于每段威胁值的计算，有以下近似： Ｄ（ａｉ ，＋ａｉ １）：＝』 ｅｅ‰ ∑— ｄｌ 圭冬盟． ・一ＳＡ （２２） 早熟的趋势，此时，将当前最优解的任一维修改成一个随 最优解在连续Ｋ次迭代过程中都无变化时，便认为算法有 ０ｉ Ｊ ｌ ＊Ｘｍａｘ ’ 威胁计算示意图如图５所示。 图５成胁计算示意图 有了代价函数便可进行粒子群算法迭代。每个粒子代 表着一条备选航迹，在设定好迭代次数后，当迭代完毕时， 对应的最优粒子即为所求的局部航迹段。算法的速度、位 置、惯性权重迭代方程如下： Ｐｉｄ（尼＋１）＝ｗ（ｋ）ｖ （ ）＋ｑＲ１（Ｐｉａ— （Ｊｉ｝））＋ ｃ２Ｒ２（ｇ —ｘｉａ（ｋ）） ｆ２３） ｆｄ（ ＋１）＝ （尼）＋ ｆｄ（ ＋１）（２４） Ｗ＝Ｗｍａ 一ｋ。Ｗｍ ／Ⅳ （２５） 其中，Ｐ ｇａ分别为粒子每一维历史最优位置和全局最优 位置；Ｎ为迭代总次数。 ５．３正交视始化 初始化对粒子群优化算法的搜索结果有着较大的影 响，在通常情况下，为了使算法达到全局最优或准最优， 会将初始化种群数量选的大一些，但种群数量过大会降低 算法的执行速度，为此，本文提出一种基于正交实验设计 思想【９ 的种群初始化方法。 正交实验设计的核心是均衡分布思想，力求用最少的 实验次数来达到最具代表性的实验效果。其基本设计工具 为正交表，它是运用组合数学理论所构造出来的一张表。 设一个实验有Ⅳ个因素，每个因素有Ｑ个水平，那么 一个等水平的正交表可写为ＬＭ（ｇ ），Ｍ表示不同水平的 组合数。本文将粒子的维数视为实验因素Ⅳ，粒子每一维 可取的纵坐标值视为每个因素的水平数Ｑ，而粒子的种群 数视为 ，那么初始化的种群应均匀的分布在这个Ⅳ维空 间中，通过查表【１ｏ］即可获得初始种群的分布位置，表示为 矩阵形式如下： （Ｑ ）：［ａｉ］ｊ Ⅳ （）２６ ，其中，每一行代表一个粒子，也即一条航迹，行数则是种 群数。 机值。 Ｘｇ＝［Ｙｌ，Ｙ２，…，Ｙｒｋ，ＹＮ＋１］（２７） 其中，矩阵 为目前找到的全局最优粒子；Ｙｒｋ为替换后 的随机扰动项，其大小和序号ｋ都是随机产生的，为保证 规划的实时性，需要对算法迭代次数 进行限制，即实际 迭代次数不能超过最大迭代次数 ，ｍ 。 ５．５算法流程 算法具体规划步骤如下： （１）飞行器开始执行上一次规划的一个步长，同时，滚 动窗口将下一个航路点设为起点。 （２）根据当前规划周期内的多个量测值，对威胁源态势 进行预测更新。 ・ （３）检测任务目标有无变化，确定局部规划终点。 （４）运用改进粒子群优化算法进行局部规划： １）设置各个参数。包括最大迭代次数 停滞判别计 数器ＳＫ、惯性权重初值％等。 ２）正交初始化。根据给定的种群数量查表生成初始 种群。 ３）迭代更新。根据代价函数进行算法更新。更新历史最 优解和全局最优解。 ４）当前代数加１，对比当前最优解和全局最优解，检查 是否早熟。若有，则对最优解施加扰动。 ５）检查是否达到最大迭代次数，若没有，则返回步 骤２），若有则退出本次迭代过程。 （５）更新下一周期航迹，等待飞行器执行。 ６仿真结果及分析 在Ｍａｔｌａｂ７．８环境下对算法进行仿真，在３００ ｋｍｘ ２００ ｋｍ的地形区域内，设置８个威胁区域，其中，Ｄ ～ Ｄ５分别为已知威胁；Ｄ６、Ｄ７为禁飞区；Ｄ８为静态突发威胁； Ｄ９为未知动态威胁（由北向南运动）；Ｇ１为原定目标；Ｇ２为 临时修改后的目标。设定规划步长 ＝３ ｋｍ，机载雷达探测 范围７５ ｋｍ，飞行速度２５０ ｍ／ｓ，初始种群数６５，最大迭代 次数５０次，威胁权重 和航程权重Ｑ２分别为０．９和０．１， 所得的航迹效果图如图６所示，其中，细线圆圈Ｄ ）７代 表固定威胁区域；粗线圆圈Ｄ８代表突发威胁区域；粗线圆 圈Ｄ９代表移动威胁作用区域；两粗线圆圈中心的连接线段 代表移动威胁Ｄ 区域中心的运动轨迹；标明圆心的为终止 第３９卷第９期 吴怡之，刘文轩：基于ＧＡ的心电信号稀疏分解ＭＰ算法改进 ２５３ １ ０２４ｘ３０次内积运算，基于ＧＡ的ＭＰ改进算法的内积运 Ａｌｇｏｒｉｔｈｍ ｗｉｔｈ Ｖａｒｉａｂｌｅ Ｔｈｒｅｓｈｏｌｄ［Ｊ］．ＩＥＥＥ Ｔｒｎａｓａｃｔｉｏｎｓ ｏｎ 算量较之ＭＰ算法已有大幅度提高。而本文算法设信号的 Ｂｉｏｍｅｄｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ，１９８８，３５（６）：４８９・４９４． 种群进化代数Ｎｇｅｎ＝３０，染色体个数ｎ＝２１，每一代都会产 ［３］Ａｌｅｓｎａｃｏ ｌ Ａ，Ｏｌｍｏｓ Ｓ，ｌｓｔｅｐａｎｉａｎ Ｒ，ｅｔ ａ１．Ａ Ｎｏｖｅｌ Ｒｅａｌ Ｔｉｍｅ 生一个最佳原子进入下一代，设每一段能量集中信号的长 Ｍｕｌｔｉｌｅａｄ ＥＣＧ Ｃｏｍｐｒｅｓｓｉｏｎ ａｎｄ Ｄｅ—ｎｏｉｓｉｎｇ Ｍｅｔｈｏｄ Ｂａｓｅｄ 度为 ，能量稀疏信号的长度为，，信号总长度为： ｏｎ Ｔｈｅ Ｗａｖｅｌｅｔ Ｔｒａｎｓｆｏｒｍ［Ｃ］／／Ｐｒｏｃ．ｏｆ Ｃｏｍｐｕｔｅｒｓ ｉｎ ，＝∑ ＋∑，，，ｉ＝１，２，…， ；Ｊ＝１，２，…，ｍ Ｃａｒｄｉｏｌｏｇｙ．Ｔｈｅｓｓａｌｏｎｉｋｉ Ｃｈａｌｋｉｄｉｋｉ，Ｇｒｅｅｃｅ：［Ｓ．ｎ．］，２００３． ２类信号均使用３０组原子重构，则内积的运算量为： 【４】Ｍｉａｏｕ Ｓ Ｇ，Ｃｈａｏ Ｓｈｕ－Ｎｉｅｎ．Ｗａｖｅｌｅｔ－ｂａｓｅｄ Ｌｏｓｓｙ—ｔｏ—ｌｏｓｓｌｅｓｓ ３０ｘ（２１—１）ｘ３０ｘＺｌｉ＋ｌＯｘ（２１一Ｉ）ｘ３ＯｘＺ／， ＥＣＧ Ｃｏｍｐｒｅｓｓｉｏｎ ｉｎ ａ Ｕｎｉｉｆｅｄ Ｖｅｃｔｏｒ Ｑｕａｎｔｉｚａｔｉｏｎ Ｆｒａｍｅ— 可以看出，内积的运算量又降低了１／３，而较原始ＭＰ ｗｏｒｋ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｂｉｏｍｅｄｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ，２００５， 算法的运算量更节省了１ ０００多倍。 ５２（３）：５３９—５４３． ［５］Ｈｕａｎｇ Ｃｈｕｎｇｕａｎｇ，Ｌｉｕ Ｊｉｎｊｉａｎｇ，Ｓｕｎ Ｊｉｘｉａｎｇ．Ｔｈｅ Ｃｏｍ— 表３算法内积运算量比较 ｐｒｅｓｓｉｏｎ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｅｌｅｃｔｒｏｃａｒｄｉｏｇｒａｍ Ｂａｓｅｄ ｏｎ Ｓｐａｒｓｅ Ｄｅｃｏｍｐｏｓｉｔｉｏｎ［Ｊ］．Ｃｈｉｎｅｓｅ Ｊｏｕｒｎａｌ ｏｆ Ｂｉｏｍｅｄｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ， ２００８，２７（２）：２２４—２２８． 【６］张静，方辉，王建英，等．基于ＧＡ和ＭＰ的信号稀疏 分解算法的改进［Ｊ］．计算机工程与应用，２００８，４４（２９）：７９—８１． ５结束语 ［７】 Ｗｕ Ｙａｎｌｉｎｇ，Ｚｈａｎｇ Ｈｏｎｇｘｉｎ，Ｗａｎｇ Ｈａｉｑｉｎｇ，ｅｔ ａ１．Ｔｈｅ Ｓｐａｒｓｅ 本文分析心电信号的特征，给出心电信号的窗函数， Ｄｅｃｏｍｐｏｓｉｔｉｏｎ ａｎｄ Ｃｏｍｐｒｅｓｓｉｏｎ ｏｆ ＥＣＧ ａｎｄ ＥＥＧ Ｂａｓｅｄ ｏｎ 提出一种基于ＧＡ的心电信号稀疏算法的改进算法。实验 Ｍａｔｃｈｉｎｇ Ｐｕｒｓｕｉｔｓ［Ｃ］／／Ｐｒｏｃ．ｏｆ ｔｈｅ ３ｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎ— 结果证明了该算法的有效性。但本文算法性能只在Ｍａｔｌａｂ ｆｅｒｅｎｃｅ ｏｎ Ｂｉｏｍｅｄｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｉｎｆｏｒｍａｔｉｃｓ．Ｙａｎｔａｉ， 仿真软件中实现，还未与实际嵌入式设备相结合，这可以 Ｃｈｉｎａ：［Ｓ．ｎ．］，２０１０． 作为下一步的研究方向。 ［８］Ｓｔｅｐｈａｎｅ Ｇ Ｍ，Ｚｈａｎｇ Ｚｈｉｆｅｎｇ．Ｍａｔｃｈｉｎｇ Ｐｕｒｓｕｉｔｓ ｗｉｔｈ Ｔｉｍｅ——Ｆｒｅｑｕｅｎｃｙ Ｄｉｃｔｉｏｎａｒｉｅｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ 参考文献 Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓ，１９９３，４１（１２）：３３９７—３４１５． ［１］ Ｌｅｅ Ｓａｎｇ－Ｊｏｏｎ，Ｋｉｍ Ｊ Ｍ，Ｍｙｏｕｎｇｈｏ Ｌ．Ａ Ｒｅａｌ・ｔｉｍｅ ＥＣＧ ［９】Ｄａｖｉｓ Ｌ．Ｈａｎｄｂｏｏｋ ｏｆ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍｓ［Ｍ］．［Ｓ．１．】：Ｖａｎ Ｄａｔａ Ｃｏｍｐｒｅｓｓｉｏｎ ａｎｄ Ｔｒａｎｓｍｉｓｓｉｏｎ Ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｎ Ｎｏｓ￣ａｎｄ Ｒｅｉｎｈｏｌｄ，１９９１． ｅ－Ｈｅａｌｔｈ Ｄｅｖｉｃｅ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｂｉｏｍｅｄｉｃａｌ ［１Ｏ】孙宝亮，肖 亮，韦志辉．基于Ｇａｂｏｒ感知多成分字典的图 Ｅｎｇｉｎｅｅｒｉｎｇ，２０１１，５８（９）：２４４８—２４５５． 像稀疏表示算法研究［Ｊ］＿自动化学报，２００８，３４（１ １）：１７３—１７８． ［２】 Ｂｏｒｉｖｏｊｅ Ｆ Ａｌｅｘ Ｐ Ａｎ Ａｄａｐｔｉｖｅ Ｒｅａｌ—ｔｉｍｅ ＥＣＧ Ｃｏｍｐｒｅｓｓｉｏｎ 编辑刘冰 （上接第２４９页） 参考文献 究［Ｄ］．长沙：国防科学技术大学，２００７． 【１］Ｈｕａｎｇ Ｌ．Ｖｅｌｏｃｉｔｙ Ｐｌａｎｎｉｎｇ ｆｏｒ ａ Ｍｏｂｉｌｅ Ｒｏｂｏｔ ｔｏ Ｔｒａｃｋ ａ 【７］ 秦永元，张洪钺，汪叔华．卡尔曼滤波与组合导航原理【Ｍ】． Ｍｏｖｉｎｇ Ｔａｒｇｅｔ＿Ａ Ｐｏｔｅｎｔｉａｌ Ｆｉｅｌｄ Ａｐｐｒｏａｃｈ［Ｊ］．Ｒｏｂｏｔｉｃｓ 西安：西北工业大学出版社，２００７． ａｎｄ Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍｓ，２００９，５７（１）：５５—６３． ［８］ Ｋｅｎｎｅｄｙ Ｊ，Ｅｂｅｒｈａｒｔ Ｒ．Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ． ［２】Ｆｏｘ Ｄ，Ｂｕｒｇａｒｄ Ｗ，Ｔｈｒｕｎ Ｓ．Ｔｈｅ Ｄｙｎａｍｉｃ Ｗｉｎｄｏｗ Ａｐｐｒｏａｃｈ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ．Ｐｅｒｔｈ． ｔｏ Ｃｏｌｌｉｓｉｏｎ Ａｖｏｉｄａｎｃｅ［Ｊ］．ＩＥＥＥ Ｒｏｂｏｔｉｃｓ＆Ａｕｔｏｍａｔｉｏｎ Ａｕｓｔｒａｌｉａ：［Ｓ．ｎ．］，１９９５． Ｍａｇａｚｉｎｅ，１９９７，４（１）：３２－３３． ［９］ 汪荣鑫．数理统计［Ｍ】．西安：西安交通大学出版社，２００４． ［３】Ｕｉｒｉｃｈ Ｉ，Ｂｏｒｅｎｓｔｅｉｎ Ｊ．ＶＦＨ ：Ｌｏｃａｌ Ｏｂｓｔａｃｌｅ Ａｖｏｉｄａｎｃｅ ｗｉｔｈ ［１Ｏ］ Ｌｅｕｎｇ Ｙ Ｗ，Ｗａｎｇ Ｙｕｐｉｎｇ．Ａｎ Ｏ￣ｈｏｇｏｎａｌ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ Ｌｏｏｋ－ａｈｅａｄ Ｖｅｒｉｉｆｃａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ．ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ ｗｉｔｈ Ｑｕａｎｔｉｚａｔｉｏｎ ｆｏｒ Ｇｌｏｂａｌ Ｎｕｍｅｒｉｃａｌ Ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］． Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｒｏｂｏｔｉｃｓ ａｎｄ Ａｕｔｏｍａｔｉｏｎ．Ｓａｎ Ｆｒａｎｃｉｓｃｏ，ＵＳＡ ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ，２００１，５（１）： ＩＥＥＥ Ｐｒｅｓｓ，２０００． ４１—５３． ［４】黄渤．对于自主移动机器人路径规划的模糊控制器［Ｊ】． Ａｎｇｅｌｉｎｅ Ｐ Ｊ．Ｅｖｏｌｕｔｉｏｎａｒｙ Ｏｐｔｉｍｉｚａｔｉｏｎ Ｖｅｒｓｕｓ Ｐａｒｔｉｃｌｅ 计算机信息系统，２００７，３（１）：１－８． Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ．ｏｆ ｔｈｅ ７ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ ［５５］ 胡 昱，高金源．战术飞行轨迹优化方法［Ｊ］．飞行力学， Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｐｒｏｇｒａｍｍｉｎｇ ＶＩＩ．Ｌｏｎｄｏｎ，ＵＫ： １９９７，１ ６（９）：７－１２． Ｓｐｒｉｎｇｅｒ，１９９８． 【６】霍晓华．对多攻击无人机动态建模与滚动优化方法的研 编辑刘冰
