第 ２６ 卷第 ６ 期 ２００９ 年 ６ 月　 计 算 机 应 用 研 究 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ｖｏｌ．２６ Ｎｏ．６ Ｊｕｎ．２００９ 基 于 改 进 多 目 标 蚁 群 算 法 的 无 人 机 路 径 规 划 王振华， 章卫国， 李广文 （西北工业大学 自动化学院， 西安 ７１００７２） 摘　要： 针对无人机 ＳＥＡＤ 任务的路径规划问题，利用 ＶＯＲＯＮＯＩ 图构建初始路径，分析了路径代价计算方法， 并使用改进的多目标蚁群算法对路径进行优化选择。 针对该特殊应用场景，引入了各路径段与起始点—目标点 连线的夹角信息作为新的启发信息，加快了算法的搜索速度，同时改进启发信息的计算公式，适当缩小各可选路 径段启发信息量的差异，加强了蚁群算法的全局搜索能力。 仿真结果显示，与基本多目标蚁群算法相比，改进后 的算法有效提高了路径搜索的效率和质量。 关键词： 无人机； 路径规划； ＶＯＲＯＮＯＩ 图； 多目标蚁群算法 中图分类号： ＴＰ３９１　　　文献标志码： Ａ　　　文章编号： １００１唱３６９５（２００９）０６唱２１０４唱０３ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１唱３６９５．２００９．０６．０３１ ＵＡＶ ｐａｔｈ ｐｌａｎｎｉｎｇ ｕｓｉｎｇ ｉｍｐｒｏｖｅｄ ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ ａｎｔ ｃｏｌｏｎｙ ｓｙｓｔｅｍ ＷＡＮＧ Ｚｈｅｎ唱ｈｕａ， ＺＨＡＮＧ Ｗｅｉ唱ｇｕｏ， ＬＩ Ｇｕａｎｇ唱ｗｅｎ （School of Automation， Northwestern Polytechnical University， Xi’an ７１００７２， China） Abstract： Ｂａｓｅｄ ｏｎ ｔｈｅ ＶＯＲＯＮＯＩ ｄｉａｇｒａｍ，ｔｈｉｓ ｐａｐｅｒ ｃａｌｃｕｌａｔｅｄ ｔｈｅ ｐａｔｈ ｃｏｓｔｓ， ａｎｄ ｔｈｅｎ ｕｓｅｄ ｔｈｅ ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ ａｎｔ ｃｏｌｏｎｙ ｓｙｓｔｅｍ（ＭＡＣＳ） ａｌｇｏｒｉｔｈｍ ｔｏ ｓｏｌｖｅ ｔｈｅ ｒｏｕｔｅ ｐｌａｎｎｉｎｇ ｐｒｏｂｌｅｍ ｏｆ ｔｈｅ ＵＡＶｓ ｔａｋｉｎｇ ｔｈｅ ＳＥＡＤ ｍｉｓｓｉｏｎ．Ｃａｌｃｕｌａｔｅｄ ａｎｄ ｉｎｔｒｏ唱 ｄｕｃｅｄ ｔｈｅ ａｎｇｌｅｓ ｂｅｔｗｅｅｎ ｐａｔｈ ｓｅｇｍｅｎｔｓ ａｎｄ ｔｈｅ ｌｉｎｅ ｓｅｇｍｅｎｔ ｊｏｉｎｉｎｇ ｔｈｅ ｓｔａｒｔ ｐｏｉｎｔ ａｎｄ ｔｈｅ ｔａｒｇｅｔ ｐｏｉｎｔ， ａｓ ｈｅｕｒｉｓｔｉｃ ｉｎｆｏｒｍａ唱 ｔｉｏｎ， ｉｎｔｏ ｔｈｅ ＭＡＣＳ ａｌｇｏｒｉｔｈｍ ｔｏ ａｃｃｅｌｅｒａｔｅ ｔｈｅ ｓｅａｒｃｈｉｎｇ ｓｐｅｅｄ．Ａｎｄ ａｌｓｏ，ｔｈｉｓ ｐａｐｅｒ ｉｍｐｒｏｖｅｄ ｔｈｅ ｅｘｐｒｅｓｓｉｏｎ ｏｆ ｔｈｅ ｈｅｕｒｉｓｔｉｃ ｉｎｆｏｒｍａｔｉｏｎ， ｗｈｉｃｈ ｒｅｄｕｃｅｄ ｔｈｅ ｄｉｆｆｅｒｅｎｃｅｓ ａｍｏｎｇ ｔｈｅ ｐａｔｈ ｓｅｇｍｅｎｔｓ， ａｎｄ ｅｎｈａｎｃｅｄ ｔｈｅ ｇｌｏｂａｌ ｓｅａｒｃｈｉｎｇ ａｂｉｌｉｔｙ ｏｆ ｔｈｅ ａｌｇｏ唱 ｒｉｔｈｍ．Ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ：ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｅ ｏｒｉｇｉｎａｌ ＭＡＣＳ，ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｃａｎ ｆｉｎｄ ａ ｂｅｔｔｅｒ ｒｅｓｕｌｔ ｍｏｒｅ ｅｆｆｉｃｉｅｎｔｌｙ． Key words： ＵＡＶ； ｐａｔｈ ｐｌａｎｎｉｎｇ； ＶＯＲＯＮＯＩ ｄｉａｇｒａｍ； ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ ａｎｔ ｃｏｌｏｎｙ ｓｙｓｔｅｍ 来越广泛的关注 0　引言 无人机最重要的特点是无须考虑人机系统，因而具有高机 动性、零伤亡、费用低等一系列优点，在军用、民用领域受到越 ［１］。 尤其在军事领域，无人机被用于执行侦 察、电子干扰、充当诱饵、目标攻击等任务。 由于无人驾驶，无 人机的任务规划就显得尤其重要。 路径规划是任务规划中最 为基础，也是最重要的部分。 合理的航路规划将有助于无人机 有效地规避威胁、减小飞行路径长度，提高其生存概率和作战 效率。 无人机路径规划方法主要有 ＶＯＲＯＮＯＩ 图搜索法、格栅搜 索法、人工势场法、基于生物激励神经网络的算法和基于模糊 逻辑的路径规划算法等。 文献［２，３］中均以 ＳＥＡＤ（ｓｕｐｐｒｅｓｓｉｏｎ ｏｆ ｅｎｅｍｙ ａｉｒ ｄｅｆｅｎｓｅ）作战任务为背景，利用 ＶＯＲＯＮＯＩ 图构建 初始路径，以最小化路径长度和威胁强度为目标进行路径的构 建。 对于该多目标优化问题，文献［２］中采用满意剪枝策略对 搜索过程中的不满足航路代价指标的航路直接进行剪枝，以搜 索无人机初始航路集合；文献［３］ 中使用了 Ｄｉｊｋｓｔｒａ 算法对路 径进行优化选择。 上述文章中均是通过线性加权和法将多目 标优换问题转换为单目标问题进行求解。 这样便面临着权重 系数如何选取的问题，同时，一旦任务决策者对各个目标的偏 好程度发生变化，便需要更改权重系数，重新进行优化选择。 为了克服上述算法的缺点，本文通过引入新的启发信息，同时 修改启发信息计算公式对基本多目标蚁群算法进行改进，利用 改进的蚁群算法进行路径选择和优化，找出问题的 Ｐａｒｅｔｏ 最优 解集提交给决策者，为决策者更好地作出决定提供了帮助。 1　问题描述及环境模型的建立 无人机的 ＳＥＡＤ 任务路径规划可以简单描述为：给定起始 点和目标点，规划一条路径使得从起始点出发的无人机能够绕 开障碍物和敌防空火力威胁顺利到达目的地，从而执行其攻击 或监视任务。 为了讨论方便，本文将障碍物、威胁均简化为点 状威胁，假设所有威胁点位置是已知且固定不变的，并且各个 威胁对无人机的威胁强度是相同的。 在该假设前提下，以各个 威胁点为基础构建 ＶＯＲＯＮＯＩ 图，如图 １ 所示。 ＶＯＲＯＮＯＩ 图 的边构造出了所有的可行路径，这些边的交点即为所有可行路 径点。 无人机路径规划是一个多目标的优化问题，本文以最小化 路径长度和最小化威胁代价为目标进行路径的选择优化。 在 已构建的初始路径的基础上，一条可行路径由包括起始点和目 收稿日期： ２００８唱１０唱１６； 修回日期： ２００８唱１２唱０７ 作者简介：王振华（１９８３唱），男，河南林州人，博士研究生，主要研究方向为群智能优化、路径规划（ｗｚｈｕａ＿ｒａｎｄｙ＠１６３．ｃｏｍ）；章卫国（１９５６唱）， 男，安徽南陵人，博导，博士，主要研究方向为飞行器控制、先进控制理论；李广文（１９７８唱），男，河北献县人，讲师，博士，主要研究方向为进化算法、 飞行控制技术． 

王振华，等：基于改进多目标蚁群算法的无人机路径规划 ｍｉｎ F１ ＝钞n －１ ｍｉｎ F２ ＝钞n －１ 第 ６ 期 标点在内的 n 个顺序排列的路径点所表示：ｐａｔｈ ＝｛p１，p２，…， pn －１，pn｝。 其中 p１ ＝ps 和 pn ＝pt 分别表示给定的起始点和目 标点。 pi 和 pi ＋１（i ＝１，２，…，n －１）之间必须有 ＶＯＲＯＮＯＩ 图的 边（可行路径）相连接。 那么，对可行路径的优化目标为 （１） i ＝１li， j ＋１ （２） i ＝１ti， j ＋１ 其中：li，i ＋１ 和 ti，i ＋１ 分别表示路径点 pi 和 pi ＋１ 之间路径的长度和 无人机选择该路径时所受到的威胁强度。 最常用的一种威胁模型认为，雷达对无人机的威胁与两者 之间的距离的四次方成反比：T ＝K ×１／R４。 因此，从路径点 pi 到达 pi ＋１ 的威胁强度为 ti，i ＋１ ＝∫Tｄl。 为了简化计算，引文献 ［２］中取每条边的１／４、１／２ 和３／４ 处的三个点的代价求和，但 是由于各条边的长度差距悬殊，这使得采样点的分布很不均 匀，严重影响了计算的精确性。 为此，本文作出如下改进： 在路径点 pi 与 pi ＋１ 之间的路径上均匀地取 k０ 个点，记为 pik，k ＝１，２，…，k０∈N。 其中 k０ 由下式求解得到：k０ ＝［li，i ＋１／ ｉｎｔｅｒｖａｌ］。 Ｉｎｔｅｒｖａｌ 为预先设定的采样点间距，采样间距越小， 则采样点越多，威胁强度的计算越精确；［a］ 表示取实数 a 的 整数部分。 从而，由路径点 pi 到达 pi ＋１的威胁强度为 ［４］ ti，i ＋１ ＝钞k０ k ＝１１／d４ ik ＋１／d４ i ＋１ 蚁群算法最初是 Ｄｏｒｉｇｏ 等人 （３） 其中：dik、di ＋１ 分别表示路径点 pik、pi ＋１ 与离它们最近的威胁点 之间的距离。 对于多目标优化问题，各个目标要求之间经常是相互冲突 的，对于其中一个目标最优的解对另一个目标而言往往并不 好。 因此，对于多目标优化通常是寻找它的 Ｐａｒｅｔｏ 最优解集。 本文利用改进的蚁群算法对上述多目标优化问题进行求解。 2　蚁群算法 为了改善蚂蚁算法在 ＴＳＰ 中的表现而提出来的。 相对于蚂蚁算法，蚁群算法：ａ） 使用了 不同的状态转移规则；ｂ） 全局信息素更新规则只应用于最优 的蚂蚁路径上；ｃ）在蚂蚁的搜索过程中使用局部更新规则。 文献［４］ 中用蚁群算法求解 ＴＳＰ 时，当蚂蚁由当前路径点 （城市 r）向下一个路径点（城市 s）移动时状态转移规则为 （４） 其中：Jk（r） 为从城市 r 出发的蚂蚁 k 尚未访问的所有城市的 集合；τ为城市 r 与 u 之间路径 Rru上信息素的含量； （５） 为路径 Rru长度的倒数，作为启发信息引入到算法中来；q 为 ［０，１］区间均匀分布的随机数；q０ 为一事先确定的参数（０≤ q０≤１）；s 为根据式（６）确定的概率分布而随机选定的城市。 u∈Jk（r）｛［τ（r，u）］ ×［η（r，u）］｝　若 q≤q０ s ＝ ａｒｇ ｍａｘ η（r，u） ＝１／Lru u∈Jk（r）［τ（r，s）］ × ［τ（r，s）］ ×［η（r，s）］ β／ 钞 ［η（r，s）］ β　若 s∈Jk（r） ０ （６） pk（r，s） ＝ 在蚂蚁完成一次搜索，构建出一个可行解时，蚂蚁实施全 （７） 局信息素更新。 全局信息素更新规则为 其中： τ（r，s） ＝（１ －α） ×τ（r，s） ＋α×Δτ（r，s） 否则 否则 S ０ 否则 τ０ ＝（n ×Lnn） －１ Δτ（r，s） ＝ （Lgb） －１　若 Rrs∈Rgb ·５０１２· 　　　 （８） ０ ＜α＜１ 为全局信息素的挥发系数；Lgb为目前搜索到的最优路 径 Rgb的长度。 只有全局最优的蚂蚁释放信息素，其目的是引 导后续蚂蚁在当前所找到的最优路径的邻域中搜索，使得搜索 更具有指导性。 在蚂蚁进行路径搜索过程中，每确定一个路径点，便运用 局部信息素更新规则对该段路径上的信息素进行更新。 局部 信息素更新规则为τ（r，s） ＝（１ －ρ） ×τ（r，s） ＋ρΔτ（r，s） （９） 其中：０ ＜ρ＜１ 为局部信息素的挥发系数；Δτ（r，s） ＝τ０，τ０ 为 初始信息素水平。 文献［４］中通过实验发现，当 （１０） 时，可以产生较好的效果。 其中：n 为城市的数量；Lnn为最优路 径长度的估计值，该估计值可由任意优化算法近似求得。 当蚂 蚁由城市 ｒ 向城市 ｓ 移动时，局部更新规则使得相应轨迹上的 信息素减少，从而避免所有的蚂蚁都集中在最优解附近进行 搜索。 3　基本多目标蚁群算法 蚁群算法最重要的特点就是创造性地使用了启发信息，即 通过引入信息素播撒机制，将之前搜索到的最优解用于指导后 续的搜索。 在蚁群算法的众多改进算法中，对信息素播撒机制 ［５］，本文的算法改进工作正 是基于此。 另外，蚁群算法与其他搜索算法相结合，来改进蚁 由式（５）（８）和（１０） 可看出，状态转换规则和信息素播撒 的量均为路径长度的函数。 而最小化路径长度正是 ＴＳＰ 中惟 一的一个优化目标。 因此，对于两目标的优化问题，本文重新 构造了状态转换规则和信息素播撒量函数，使得它们成为路径 长度和威胁强度的二元函数。 文献［７］ 将类似的方法用于带 时间窗口的车辆路径问题的优化。 在本文第１ 章所建立的环境模型的基础上，对多目标蚁群 算法的表述如下： 对应于单目标蚁群算法中的式（５），多目标蚁群算法状态 （１１） 对应于单目标蚁群算法中的式（１０），多目标蚁群算法局 部信息素更新规则表示为τ０ ＝（n ×Lp０ ×Tp０） －１ （１２） 其中：n 为路径点的数目；Lp０ 和 Tp０ 分别为最小路径长度和最小 威胁强度的估计值，该估计值可由任意优化算法近似求得。 对应于单目标蚁群算法中的式（８），多目标蚁群算法全局 转换规则中的启发信息表示为η（r，s） ＝１／（lrs ×trs） 的改进是研究者最为关注的一点 群算法也是一条重要途径 ［６］。 信息素更新规则表示为 Δτ（r，s） ＝钞k０ （１３） 其中：k０ 为到目前为止搜索到的 Ｐａｒｅｔｏ 解集中解的个数。 即， 对所有属于 Ｐａｒｅｔｏ 最优解集中的路径实施信息素全局更新，且 k ＝１Δτk（r，s） 若 Rrs是第 k 条 Ｐａｒｅｔｏ 最优路径中的一段 Δτk（r，s） ＝ （LkTk） －１ ０ 否则 （１４） 其中：Lk 和 Tk 为第 k 条 Ｐａｒｅｔｏ 最优路径的总长度和总威胁 

多目标蚁群算法通过将之前搜索到的最优解的路径长度 ·６０１２· 强度。 信息和威胁强度信息同时用于指导下一次的搜索，从而达到对 两个目标同时进行优化的目的。 4　算法改进及其流程 ＴＳＰ 中要求每个城市必须且只经过一次，且各城市之间都 有路径相连。 此时，使用禁忌表可以很好地加快搜索速度，并 避免同一个城市经过两次的情况发生。 但在前述 ＶＯＲＯＮＯＩ 图路径规划问题中，各路径点之间的连接是由 ＶＯＲＯＮＯＩ 图的 边（即可行路径段） 所严格限制的。 此时若使用禁忌表，搜索 过程中一旦偏离目标方向，将会使搜索陷入无路可走的境地。 若引入解禁策略，则又面临着解禁策略难以制定、算法复杂性 增加等问题。 因此在本文的算法中摈弃了禁忌表的使用，同时 引入了一个新的启发信息。 在本文的路径规划问题中，由于路径起始点和目的地的相 对位置是已知的，考虑以此空间几何关系作为启发信息引入到 算法中去，指引蚂蚁的搜索方向。 如图２ 所示，记 pipj 为由路径点 pi 到路径点 pj 的有向路 径段，pspt 为连接起始点和目的地的有向线段，θij为 pipj 与 pspt 之间的夹角。 根据矢量间夹角定义，图２ 中以路径点 p１ 为例， 给出了与其相连接的三条路径段与 pspt 所构成的三个夹角： θ１s、θ１２ 和 θ１３。 笔者认为与 pspt 夹角越小的路径段越有可能是 全局最优路径的一部分，蚂蚁在进行路径选择时选中该路径段 的概率也越大。 威胁点 出发点 目标点                          延长线 任务路径规划模型 图 启发信息示意图 图    u∈J（i）θiutiu） 由于与当前路径点相连的各路径段的夹角信息的值差距 在本文的路径规划问题中，对于单目标的蚁群算法，将启 发信息替换为上述角度信息后，启发信息计算式（５）修改为 （１５） η（i， j） ＝１／（θij ＋１／N 钞 u∈J（i）θiu） 对于多目标蚁群 算法， 将路径选择的启发信 息计算式 （１１）修改为 η（i， j） ＝１／（θij ×tij ＋１／N 钞 （１６） 其中：J（i）为所有与当前路径点之间有路径段相连的路径点所 组成的集合，N 为该集合中元素的个数。 可能会很大，这将导致各路径段的启发信息量差异悬殊，从而 使得蚂蚁对个路径段的选择概率差距过大，再加上信息素播撒 的正反馈效应，算法将迅速地收敛于局部极值。 为了缓解该问 题，本文在式（１５）（１６）中加入了 １／N 钞 u∈J（r）K 项，适当缩小了各 可选路径段启发信息量的差异，相对增加启发信息量小的路径 段选择该概率，使得算法的全局搜索能力得到加强。 其效果相 当于遗传算法中增加了种群多样性，避免了过早地收敛于局部 极值。 蚂蚁在搜索路径的过程中，不可避免地会重复走一些路径 段。 为了减小这些不必要的圈子对后续的搜索造成的不良影 响，在全局信息素更新之前，先删除掉路径中重复的路径段，然 后对精简后的路径计算其长度并带入式（１４）计算信息素更新 计 算 机 应 用 研 究 第 ２６ 卷 量，对精简后的路径实施全局信息素更新。 流程： 解，则令 P ＝P∪pi，同时去掉解集中被 pi 支配的解； 新； 在此基础上，本文给出用于路径优化的多目标蚁群算法 ＭａｉｎＦｕｎｃｔｉｏｎ： ／倡初始化过程倡／ 只用启发信息构造初始可行路径； Ｐａｒｅｔｏ 最优解集； 利用式（１２） 计算； Ｒｅｐｅａｔ／倡主循环倡／ 对每一只蚂蚁 i∈｛１，２，…，m｝ 调用子程序，构建路径 pi； 对每一条路径 pi，计算 F１ 和 F２，若 pi 为 Ｐａｒｅｔｏ 最优解集的非支配 根据式（７），对 Ｐａｒｅｔｏ 最 优解集 中的所 有元素 进行全 局信息 素 更 Ｕｎｔｉｌ 满足终止条件。 ／倡算法结束倡／ ＳｕｂＦｕｎｃｔｉｏｎ ｃｏｎｓｔｒｕｃｔ＿ｒｏｕｔｅ（i） pi ＝｛ps｝；／倡第 i 条路径的所有的路径点 依次存 放在集 合 pi 中。 初始化，将一只蚂蚁放在 ps倡／ Ｒｅｐｅａｔ 根据式（１６），计算启发信息 η（i， j）； 根据式（６），对所有与当前路径点有可行路径相连的路径点，计算 其被选择的概率； 产生一个随机数 q，根据式（４） 选择下一个路径点，pj； pi ＝pi∪pj； Ｕｎｔｉｌ 到达目的地。 去掉路径 pi 中重复走过的路径点； 根据式（９），实施局部信息素更新； ／倡子程序结束倡／ 5　算法仿真 性能，本文分别在１５０、１８０、３００ 和４００ 个威胁点的情况下进行 了仿真验证。 两个算法中，ρ、q０、α、β以及蚂蚁数量等参数设 置均相同。 图３ 给出了仿真实验所得到的 Ｐａｒｅｔｏ 最优解集，图 中横坐标表示路径长度，纵坐标表示威胁强度。 为了比较基本多目标蚁群算法和改进多目标蚁群算法的 &              &                    !"# $%   &              !"#  $%           ' %$ ' %$           $% !"#     $% !"#    &              (         ' %$ ' %$     #    搜索结果。 图 ３　两种算法得到的 Ｐａｒｅｔｏ 前沿比较 注：ｉｍｐｒｏｖｅｄ 表示改进算法 的搜索结 果；ｏｒｉｇｉｎａｌ 表 示 基 本 算 法 的 在１５０ 个威胁点的情况下，基本多目标蚁群算法搜索得到 的 Ｐａｒｅｔｏ 前沿上有三个解，而改进算法的 Ｐａｒｅｔｏ 前沿上有八个 解，且完全支配基本算法得到的三个解。 在１８０ 个威胁点时， 改进算法得到的四个解也完全支配由基本算法得到的五个解。 在４００ 个点的情况下改进算法同样是完全支配由基本算法得 到的解。 值得一提的是，在进行３００ 个点的实验时，基本算法 一个可行解都没有得到，而本文的改进算法的 Ｐａｒｅｔｏ 前沿上有 四个解可供选择。 图４ 给出了１８０ 个威胁点时，由基本算法得到的 Ｐａｒｅｔｏ 前 沿上的五条路径和改进算法得到的四条路径的对比图。 可以 很直观地看出，改进算法得到的结果要优于基本多目标蚁群 算法。 （ 下转第 ２１０９ 页） 

章　炯，等：基于资源类的时间加权协作过滤算法 的精确度是评价推荐算法的一个主要指标 第 ６ 期 评价的资源的评价分，从而为用户作出比较准确的推荐，算法 ［９，１０］。 平均绝对偏 差 ＭＡＥ（ｍｅａｎ ａｂｓｏｌｕｔｅ ｅｒｒｏｒ）是最常用的一种推荐质量度量方 法，通过计算预测用户评分与实际用户评分之间的偏差来度量 预测的准确性，ＭＡＥ 越小，推荐质量就越高。 ＭＡＥ 定义为 其中：N 为测试集大小；pi 为预测评分；qi 为实际评分。 实验采用 ＭｏｖｉｅＬｅｎｓ（ｈｔｔｐ：／／ｍｏｖｉｅｌｅｎｓ．ｕｍｎ．ｅｄｕ） 提供的 ［５］，包括 ９４３ 位用户对 １ ６８２ 部电影的１００ ０００ 条评分 数据，每位用户至少对２０ 部电影进行了评分，所有电影分属于 １９ 种电影类别。 基于资源类的时间加权推荐算法与一般的协 作推荐算法进行比较和分析，取最近邻居数分别为 ５、１０、１５、 ２０、２５，对上述两种算法分别进行实验测试。 实验结果如图 ２ 所示。 数据集 ＭＡＥ ＝钞N i ＝１｜pi －qi ｜／N ·９０１２· 　　　 户—资源类别评分数据，对用户资源兴趣度预测中引入时间加 权函数。 实验结果显示，该算法较传统的协作过滤推荐算法， 不仅大大降低了数据的稀疏程度，而且在用户兴趣预测中考虑 用户兴趣的变化，把时间加权函数引入到兴趣计算公式中，使 推荐更加准确。 从实验中发现在对用户进行不同的聚类时，也 影响着算法推荐质量的好坏，所以研究并选取一种更加有效的 聚类算法，可以提高推荐算法的信息推荐质量。 其次，本文在 用户的个性化方面的支持程度还不够，对 ｅ唱Ｌｅａｒｎｉｎｇ 用户的个 性特征还需要进一步研究。 参考文献： ［１］ 王霞，刘琴．协同过滤在推荐系统中的应用研究［Ｊ］．计算机系统 应用，２００５，14（４）：２４唱２７． ［２］ 许建潮，王红梅．改进的协 同过滤算法［Ｊ］．吉林大学学报，２００８， 26（１）：９９唱１００． ［３］ 张锋，常会友．使用 ＢＰ 神 经 网 络 缓 解 协 同 过 滤 推 荐 算 法 的 稀 疏 性问题［Ｊ］．计算机研究与发展，２００６，43（４）：６６７唱６７２． ［４］ 邓爱林，朱杨勇，施伯乐．基于项目评分预测的协同过滤算法［Ｊ］． 软件学报，２００３，14（９）：１６２１唱１６２８． ［５］ 潘红艳，林鸿飞，赵屏．基于矩阵划分和兴趣力差的协同过滤算法 ［Ｊ］．情报学报，２００６，25（１）：４９唱５４． ［６］ ＳＵＭＩＹＡ Ｔ，ＣＨＵＮ Ｊ Ｈ，ＬＥＥ Ｓ Ｇ，et al．Ａ ｗｅｉｇｈｔｅｄ ｓｉｆｔｉｎｇ ｍｅｔｈｏｄ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｃｏｌｌａｂｏｒａｔｉｖｅ ｆｉｌｔｅｒｉｎｇ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｒｅｇｉｏｎ １０ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ ＴＥＮＣＯＮ’０４．２００４：２６６唱２６９． ［７］ ＫＵＯ Ｒ Ｊ，ＬＩＡＯ Ｊ Ｌ，ＴＵ Ｃ．Ｉｎｔｅｇｒａｔｉｏｎ ｏｆ ＡＲＴ２ ｎｅｕｒａｌ ｎｅｔｗｏｒｋ ａｎｄ ｇｅｎｅｔｉｃ Ｋ唱ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｎａｌｙｚｉｎｇ Ｗｅｂ ｂｒｏｗｓｉｎｇ ｐａｔｈｓ ｉｎ ｅｌｅｃ唱 ｔｒｏｎｉｃ ｃｏｍｍｅｒｃｅ［Ｊ］．Decision Support Systems，２００５，40（２）： ３５５唱３７４． ［８］ ＺＨＯＵ Ｊｕｎ唱ｆｅｎｇ，ＴＡＮＧ Ｘｉａｎ，ＧＵＯ Ｊｉｎｇ唱ｆｅｎｇ．Ａｎ ｏｐｔｉｍｉｚｅｄ ｃｏｌｌａｂｏｒａ唱 ｔｉｖｅ ｆｉｌｔｅｒｉｎｇ ｒｅｃｏｍｍｅｎｄａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ［Ｊ］．Journal of Computer Research and Development，２００４，14（１０）：１８４２唱１８４７． ［９］ 黄光球，靳峰，彭绪友．基于兴趣度的协同过滤商品推荐系统模型 ［Ｊ］．微电子学与计算机，２００５，22（３）：５唱８． ［１０］ 郭艳红，邓贵仕．协同过滤的一种个性化推荐算法研究［Ｊ］．计算 机应用研究，２００８，25（１）：３９唱４２． 攻击。 参考文献： ［１］ 朱战霞，袁建平．无人机编 队飞行问题初探［Ｊ］．飞行力学，２００３， 21（２）：５唱８． ［２］ 叶媛媛，闵春平， 沈林成， 等．基于 ＶＯＲＯＮＯＩ 图的无人机空域任 务规划方法研究［Ｊ］．系统仿真学报，２００５，17（６）：１３５３唱１３５９． ［３］ ＭｃＬＡＩＮ Ｔ Ｗ，ＢＥＡＲＤ Ｒ Ｗ．Ｔｒａｊｅｃｔｏｒｙ ｐｌａｎｎｉｎｇ ｆｏｒ ｃｏｏｒｄｉｎａｔｅｄ ｒｅｎ唱 ｄｅｚｖｏｕｓ ｏｆ ｕｎｍａｎｎｅｄ ａｉｒ ｖｅｈｉｃｌｅｓ［ Ｃ］ ／／Ｐｒｏｃ ｏｆ ＡＩＡＡ Ｇｕｉｄａｎｃｅ， Ｎａｖｉｇａｔｉｏｎ，ａｎｄ Ｃｏｎｔｒｏｌ Ｃｏｎｆｅｒｅｎｃｅ．Ｄｅｎｖｅｒ：［ｓ．ｎ．］，２０００． ［４］ ＤＯＲＩＧＯ Ｍ，ＧＡＭＢＡＲＤＥＬＬＡ Ｌ Ｍ．Ａｎｔ ｃｏｌｏｎｙ ｓｙｓｔｅｍ：ａ ｃｏｏｐｅｒａｔｉｖｅ ｌｅａｒｎｉｎｇ ａｐｐｒｏａｃｈ ｔｏ ｔｈｅ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ［Ｊ］．IEEE Trans on Evolutionary Computation，１９９７，1（１）：５３唱５６． ［５］ 王颖，谢剑英．一种自适应蚁群算法及其仿真研究［Ｊ］．系统仿真 学报，２００２，14（１）：３１唱３３． ［６］ 丁建立，陈增强，袁著祉．遗传算法与蚁群算法的融合［Ｊ］．计算机 研究与发展，２００３，40（９）：１５３１唱１５３６． ［７］ ＢＡＲ樿Ｎ Ｂ，ＳＣＨＡＥＲＥＲ Ｍ．Ａ ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ ａｎｔ ｃｏｌｏｎｙ ｓｙｓｔｅｍ ｆｏｒ ｖｅ唱 ｈｉｃｌｅ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ ｗｉｔｈ ｔｉｍｅ ｗｉｎｄｏｗ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ｔｈｅ ２１ｓｔ ＩＡＳＴ唱 ＥＤ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ．Ｉｎｎｓｂｒｕｃｋ：［ｓ．ｎ．］，２００３：９７唱１０２． ［８］ 陈烨．变尺 度 混 沌 蚁 群 优 化 算 法［Ｊ］．计 算 机 工 程 与 应 用，２００７， 43（３）：６８唱７０． ［９］ 刘利强，于飞，戴运桃．基于蚁群算法的水下潜器三维空间路径规 划［Ｊ］．系统仿真学报，２００８，20（１４）：３７１２唱３７１６．          差 偏 对 绝 均 平 传统的协作推荐算法 基于资源类的时间加权推荐算法      最近邻居个数 图 推荐算法的平均绝对偏差比较  由图２ 可知，基于资源类的时间加权推荐算法具有更小的 ＭＡＥ。 根据学生学习知识兴趣规律的分析，以类别为单位进行 资源推荐内容的延展性更好，更符合学生学习需求；另外通过 增加时间权值，能随用户兴趣的转移发现最近的兴趣所在进行 推荐，与传统协同过滤算法相比推荐更具准确性。 4　结束语 本文提出了一种基于资源类的时间加权推荐算法，在对资 源项目依内容划分的基础上，将用户—项目评分数据转换为用 （ 上接第 ２１０６ 页）                  !"#$%  & 图 个威胁点时的路径搜索结果比较 路径规划是无人机任务规划中最为基础的且极为重要的 6　结束语 一个环节。 本文首先以 ＶＯＲＯＮＯＩ 图为基础，构建了无人机的 路径规划模型；其次，引入新的角度启发信息，使得搜索更具有 方向性，提高了算法的搜索效率，同时修改了启发信息的计算 公式，算法的全局搜索能力得到加强，避免了过早地收敛于局 部极值；最后，使用改进的多目标蚁群算法进行路径的选择和 优化。 仿真结果表明，与基本多目标蚁群算法相比，改进的算 法明显提高了搜索结果的质量。 在得到 Ｐａｒｅｔｏ 解集后，决策者就可以根据自己的偏好，对 路径长度和威胁强度进行权衡，很方便地从其中选择一条路 径，完成路径规划过程，进而，无人机便沿此路径对目标实施