周 晶 林 众 卢一鸣 何应强

（海军大连舰艇学院作战软件与仿真研究所 大连 116018）

1 引言

对空防御作战是海上编队的重要作战样式，其典型特征是战斗节奏快，影响决策因素多，反应时间短［1～2］。任务分配问题是编队对空防御中核心问题之一，在有限的时间内完成科学有效任务分配问题是编队进行对空防御的关键［3］。任务分配问题中要考虑敌方威胁程度、完成任务收益、任务执行时间和资源消耗等多种因素制约，因此编队对空防御中的任务分配问题是一个典型的多目标优化问题（Multi-Objective Optimization Problem，MOOP）。多目标优化问题求解已被证明是NPH问题，当任务规模增加时，求解难度呈几何增长。除了优化目标多，任务分配问题还需要考虑涉及时间、空间、兵力能力和执行顺序等大量的约束条件。目前已有一些算法用于多目标任务分配。早期最常见的方法是采用集中式方式进行求解，完成求解后将分配方案指派给各执行兵力［4］，但这类方法存在单点失效问题和容错性较差等问题，且无法解决大规模问题。近年来，分布式多任务分配方法被提出，大致可分为以下几类：分布式完全搜索算法、分布式局部搜索算法、基于拍卖机制的算法和分布式蚁群算法等［5～7］。分布式完全搜索算法能确保解最优，但各节点间需要较大的通信和计算成本，在单节点计算或通信资源有限的情况下难以适用；分布式局部搜索算法则大量减少了通信和计算的代价，各个节点在本地搜索最适合自己的任务分配方案，然后通过通信来实现全局任务分配的统一和协同，但这类方法通常难以保证解的质量，求解的效果依赖于具体的应用场景；……