·208· 智能系统学报 第15卷 像其他算法那样有明确的步骤，需要结合动态规 Dorigo等在蚁群算法基础上进一步发展的一种通 划的思想设计相应的优化算法。 用的优化技术s0。其流程图见图4。 分支定界法B是一种求解整数规划B问题 常用的广度优先算法，它把全部可行解空间反复 开始 的分割成越来越小的子集，即分支；然后，对每 个子集内的解集，计算下一个目标的上下界，即 初始化参数，m只蚂蚁位于起始 点等待出发 定界；每次分支之后，凡是不满足界限要求的可 行解目标值直接删除，即剪枝；最后，将剩下的 日 子集加入到可行集中，如此循环重复，直至找到 每只蚂蚁根据状态转移概率选择下 一个到达点，实现任务分配 问题的可行解；分支定界算法多用于求解约束条 件和变量数目较少的约束问题的一个解或在求 计算蚂蚁分配目标函数.保存最 解的一组解中找到满足某一约束条件的极值，该 优分配解 算法灵活且便于求解，但计算量较大，且求解效 率低。 根据目标函数，调整信息 3)随机性智能优化算法。随机性智能优化 算法)是受自然现象或社会行为启发而发展 的一种随机搜索方法，最早于20世纪70年代被 是否满足迭代信息 提出，该算法在求解大规模优化问题时，可获得 较好的解。进化算法、群智能算法、人工免疫算 y 法、禁忌搜索算法、模拟退火算法是典型的智能 输出最优分配方案 优化算法。 结束 群智能优化算法于1989年由Gerardo B提 出，是将代表候选解的多个个体组成一个群体， 图4蚊群优化算法求解任务分配 通过部分或全体之间的信息交互，达到寻优的目 Fig.4 The framework of ACO in task allocation 的。代表性的算法有粒子群优化算法、蚁群优化 由上可知随机智能算法易实现、搜索能力 算和鱼群算法。 强、鲁棒性好、计算复杂度低且性能优越，在大规 进化算法(evolutionary computation)241是以 模并行计算中优势凸显。典型的智能优化算法： 达尔文的进化论为基础，是自然界与遗传机制的 蚁群算法、遗传算法和模拟退火算法均具有较强 自组织、自适应搜索过程，主要由选择、重组和变 的鲁棒性，且扩展性强，能与其他算法混合使 异3个环节组成。代表性的算法有遗传算法、差 用。遗传算法可适用于大规模、非线性问题，通 分进化算法等。 用性强。蚁群算法和模拟退火算法易求得全局最 粒子群优化算法46是模拟鸟群寻找食物的 优解，而粒子群优化算法求得的解多为局部最 一种方法，1995年粒子群算法由Kennedy和Eber- 优。粒子群算法相较于其他智能算法的显著区别 hart首次提出，其原理是通过更新惯性系数、社会 在于算法中需要调整的参数少。在一些典型的优 系数和认知系数，由适应度函数评估局部最优和 化问题中，粒子群算法比遗传算法获得更好的优 全局最优等操作，实现集群最优搜索。粒子群算 化结果倒。 法计算简单、鲁棒性好、搜索能力强且收敛速度 综上所述，无人机任务分配的目的即是寻找 快，然而该算法易出现早熟收敛和停滞倾向。 最优匹配方案，任务分配和路径规划是两个密不 蚁群算法974是一种启发式算法，依据蚂蚁 可分的环节，在最优分配的基础上，才能规划出 在行动中留下的信息素，其他蚂蚁通过协同感知 可行、安全的飞行路径。本节在给出任务分配的 信息素浓度，倾向于向信息素浓度高的位置移 相关概念基础上，就任务分配的几个约束指标给 动，最终以一种有效的方式找到蚁穴到食物之间 出常用模型及分类标准，由2种典型的任务分配 的最短路径。ACO算法关键在于信息素更新、状 模型引出启发式算法、数学规划方法和随机性智 态转移和启发式函数的构建。该算法搜索较优解 能优化算法3种求解任务分配的方法，并给出相 的能力强，扩充性好，但是易陷入对某一区域的 应算法的优缺点。表1是任务分配算法的对比 过度搜索，且求解速度较慢。蚁群优化算法是M 结果。像其他算法那样有明确的步骤，需要结合动态规 划的思想设计相应的优化算法。 分支定界法[38] 是一种求解整数规划[39] 问题 常用的广度优先算法，它把全部可行解空间反复 的分割成越来越小的子集，即分支；然后，对每 个子集内的解集，计算下一个目标的上下界，即 定界；每次分支之后，凡是不满足界限要求的可 行解目标值直接删除，即剪枝；最后，将剩下的 子集加入到可行集中，如此循环重复，直至找到 问题的可行解；分支定界算法多用于求解约束条 件和变量数目较少的约束问题的一个解或在求 解的一组解中找到满足某一约束条件的极值，该 算法灵活且便于求解，但计算量较大，且求解效 率低。 3) 随机性智能优化算法。随机性智能优化 算法[40-41] 是受自然现象或社会行为启发而发展 的一种随机搜索方法，最早于 20 世纪 70 年代被 提出，该算法在求解大规模优化问题时，可获得 较好的解。进化算法、群智能算法、人工免疫算 法、禁忌搜索算法、模拟退火算法是典型的智能 优化算法。 群智能优化算法于 1989 年由 Gerardo B 提 出，是将代表候选解的多个个体组成一个群体， 通过部分或全体之间的信息交互，达到寻优的目 的。代表性的算法有粒子群优化算法、蚁群优化 算和鱼群算法。 进化算法 (evolutionary computation)[42-43] 是以 达尔文的进化论为基础，是自然界与遗传机制的 自组织、自适应搜索过程，主要由选择、重组和变 异 3 个环节组成。代表性的算法有遗传算法、差 分进化算法等。 粒子群优化算法[44-46] 是模拟鸟群寻找食物的 一种方法，1995 年粒子群算法由 Kennedy 和 Eber￾hart 首次提出，其原理是通过更新惯性系数、社会 系数和认知系数，由适应度函数评估局部最优和 全局最优等操作，实现集群最优搜索。粒子群算 法计算简单、鲁棒性好、搜索能力强且收敛速度 快，然而该算法易出现早熟收敛和停滞倾向。 蚁群算法[19,47-48] 是一种启发式算法，依据蚂蚁 在行动中留下的信息素，其他蚂蚁通过协同感知 信息素浓度，倾向于向信息素浓度高的位置移 动，最终以一种有效的方式找到蚁穴到食物之间 的最短路径。ACO 算法关键在于信息素更新、状 态转移和启发式函数的构建。该算法搜索较优解 的能力强，扩充性好，但是易陷入对某一区域的 过度搜索，且求解速度较慢。蚁群优化算法是 M. Dorigo 等在蚁群算法基础上进一步发展的一种通 用的优化技术[48-50]。其流程图见图 4。 开始 初始化参数，m只蚂蚁位于起始 点等待出发 计算蚂蚁分配目标函数，保存最 优分配解 每只蚂蚁根据状态转移概率选择下 一个到达点，实现任务分配 根据目标函数，调整信息 是否满足迭代信息 输出最优分配方案 结束 Y N 图 4 蚁群优化算法求解任务分配 Fig. 4 The framework of ACO in task allocation 由上可知随机智能算法易实现、搜索能力 强、鲁棒性好、计算复杂度低且性能优越，在大规 模并行计算中优势凸显。典型的智能优化算法： 蚁群算法、遗传算法和模拟退火算法均具有较强 的鲁棒性，且扩展性强，能与其他算法混合使 用。遗传算法可适用于大规模、非线性问题，通 用性强。蚁群算法和模拟退火算法易求得全局最 优解，而粒子群优化算法求得的解多为局部最 优。粒子群算法相较于其他智能算法的显著区别 在于算法中需要调整的参数少。在一些典型的优 化问题中，粒子群算法比遗传算法获得更好的优 化结果[51]。 综上所述，无人机任务分配的目的即是寻找 最优匹配方案，任务分配和路径规划是两个密不 可分的环节，在最优分配的基础上，才能规划出 可行、安全的飞行路径。本节在给出任务分配的 相关概念基础上，就任务分配的几个约束指标给 出常用模型及分类标准，由 2 种典型的任务分配 模型引出启发式算法、数学规划方法和随机性智 能优化算法 3 种求解任务分配的方法，并给出相 应算法的优缺点。表 1 是任务分配算法的对比 结果。 ·208· 智 能 系 统 学 报 第 15 卷