《用于静态和动态武器目标分配的实时启发式和元启发式算法》163页博士论文

用拦截器（武器）库瞄准和攻击单个导弹（目标）的问题被称为武器目标分配问题。自 1958 年的开创性工作以来，人们对这一问题进行了深入研究。武器目标分配问题有两种不同的类型：静态和动态。静态武器目标分配问题考虑的是已知数量的来袭导弹与有限数量的拦截弹交战的单一实例。相比之下，动态武器目标分配问题考虑的是第一次交战失败后的后续交战、随后的来袭导弹齐射或两者兼而有之。

本研究试图定义并解决一个现实的动态模型。首先，开发了分配启发式和元启发式方法，为静态武器目标分配提供快速的近优解决方案。接着，研究人员开发了一种技术，能够通过近似动态规划确定每种拦截器类型应为第二次齐射保留多少数量。最后，还开发了一个模型，该模型能够现实地考虑到来袭导弹飘忽不定的飞行路径，并在模拟中确定拦截器的分配和发射顺序，以尽量减少击中受保护资产的次数。

此外，还介绍了自 1985 年以来对武器目标分配问题的首次当代调查。总之，这项工作将导弹防御研究扩展到了实际应用中，比目前文献中的研究更为深入。

本论文的重点是武器目标分配（WTA）问题。具体来说，它建立了防空问题的框架模型，并提出了新的启发式算法，以 "实时 "找到这些模型的解决方案。我们将启发式算法定义为 "实时"，即该算法能够在导弹从发射到到达弹着点的时间内找到解决方案。

WTA 可分为静态（SWTA）和动态（DWTA）两种。SWTA 模拟的是一种防空情景，在这种情景中，已知数量的来袭导弹被观测到，并且有一定数量的拦截器可用于单次交战。对拦截器与导弹的分配结果以及交战的时间框架不作探讨。也就是说，如果二十五枚拦截器拦截五枚来袭导弹，每枚拦截器分别拦截五枚导弹，那么解决方案不会探讨这种发射顺序如何发生，也不会探讨是否有导弹在拦截过程中幸存。

相比之下，DWTA 将 SWTA 的结果视为后续问题。射击-观察-射击 "变体要求确定哪些导弹（如果有的话）在交战中幸存下来，并允许重新交战。两阶段 "变体的第一阶段与 SWTA 相同，第二阶段只知道来袭导弹数量的概率分布。在上述每个变体中，解决方案都必须考虑为连续交战或连续阶段保留多少拦截器。

定义 WTA 的第二个分类是不同类型拦截器的数量。在同质问题中，每枚拦截弹的类型相同，因此每枚拦截弹成功摧毁来袭导弹的概率或击杀概率相同。或者，在异质问题中，存在不同类型的拦截器，每种拦截器的杀伤概率各不相同，从而使问题变得更加复杂。事实上，异质 SWTA 是一个 NP 难问题（Lloyd & Witsenhausen，1986 年）。

在本论文中，考虑了一阶段和二阶段异构 WTA，其中每一章都是一篇独立的学术文章。第 2 章对有关 WTA 的文献进行了当代调查，重点关注 SWTA 和 DWTA 的模型、最优算法和启发式算法。在第 3 章中，介绍了一种元启发式算法，它能够为 SWTA 找到文献中一些最大问题的实时解决方案。第 4 章探讨了在使用商业求解器 BARON 过程中发现的一个系统性问题。在求解 SWTA 时，我们开发并使用了对数变换和带有特定实例参数的约束条件来提高 BARON 的性能。第 5 章中开发了一种新的启发式，在求解质量和所需计算量方面改进了第 3 章中的工作。第 3、4 和 5 章中使用的 SWTA 模型最初由 Manne（1958 年）提出，在文献中广为人知并被广泛使用。在第 6 章中，由 Murphey（2000 年）开发的同质两级 DWTA 模型被用于两级异质 DWTA，并在其中求解。在第 7 章中，使用贝塞尔曲线对连续导弹飞行路径进行建模，并开发了一种在现实模拟中解决问题的 DWTA 求解技术。

第 2 章回顾了自 1958 年（Manne，1958 年）WTA 创立以来的相关文献。定义了 SWTA 和 DWTA 的一些不同模型，说明了模型假设中的不同参数或变化。调查报告接着回顾了 SWTA 和 DWTA 的最优算法。如前所述，异质 SWTA 是 NP-Hard，因此最优算法一般适用于以下三种模型之一：同质 WTA（多项式时间内可获得最优解）、异质 WTA 的线性变换或拦截器和导弹数量极少的异质 WTA。下面回顾了一些用于 WTA 的启发式和元启发式算法。其中一些算法（如遗传算法）已在文献中多次使用，本章将对其中一些引用较多的作品进行探讨。本章最后研究了文献中的一些最新进展，探讨了 WTA 研究的一些其他应用，并确定了一种方法，通过这种方法可以对大量文献进行截断，以便进行更全面的综述。

第3章开发并介绍了一种元启发式，它改进了之前的研究，在之前的研究中，开发了一种实现测验问题解决方案的启发式（即QP启发式）（Kline，2017）。这种元启发式被称为 "显性领域（ED）元启发式"，因为它通过否认启发式解决方案的一个子集，并使用 QP 启发式来解决问题，从而找到改进的解决方案。这种否定过程可以防止那些通过贪婪选择标准进行单一分配选择的解决方案阻碍后续分配，而后续分配可能是更优的解决方案，从而使改进解决方案成为可能。我们将 ED 的结果与 Ahuja 等人（2007 年）开发的启发式的结果进行了比较，后者是 SWTA 的一个已知基准。

在第 4 章中，介绍了 SWTA 公式的对数变换，利用这种方法，商业求解器 BARON 可以在可能的情况下更有效地找到最优解，并在 BARON 无法确定最优解时找到下限。不过，这种转换的计算成本很高，因此我们引入了一个针对具体实例参数的约束条件，以缩小问题的可行区域，从而提高 BARON 解决这种转换后问题的效率。

第 5 章改进了 QP 子程序，开发了一种与匈牙利算法相似的新启发式，称为 "类匈牙利贪婪启发式"（GH）。该启发式通过检查每种武器和每个目标的最佳可用分配，并选择两者中最佳的分配来进行分配。GH 的结果与 QP 和 ED 进行了比较，在进一步比较中，GH 被用作 ED 的子程序。

第 6 章考虑了异构两阶段 DWTA。本章扩展了 Ahner & Parson（2015 年）的工作，使用凹面自适应值估计（CAVE）算法，将 GH 作为子程序，计算第二阶段需要保留的拦截器数量，同时使用 GH 解决 CAVE 算法给出的每个阶段的问题。这种动态编程技术通过使用模拟来近似计算第二阶段中每种拦截器的值。CAVE 算法的解决方案与基线策略和小问题实例最优策略的解决方案进行了比较。此外，还对 CAVE 算法和基线策略在较大问题实例上进行了比较测试，因为在较大问题实例上找到最优策略并不容易。

第 7 章是对 Leboucher 等人（2013 年）工作的扩展，后者在一个阶段性问题中用二维贝塞尔曲线模拟了来袭导弹的飞行路径，要求确定发射序列。本扩展使用三维贝塞尔曲线来模拟每枚导弹的接近角，并根据每次交战所需的时间和与每枚拦截弹交战的机会窗口来确定发射顺序。此外，它还确定每次交战的结果，并允许在 "射击-瞄准-射击 "框架内进行后续交战。该模型扩展到两个阶段，从而模拟并解决了两阶段 "射击-瞄准-射击 "问题。该技术在来袭导弹发射时启动，要求解决交战计划，并在实时评估战损时重新分配拦截器。该解决方法的结果与现实的 "射击-射击-察看 "政策的结果进行了比较，后者是在导弹进入拦截器的有效射程时立即用两个拦截器与导弹交战。

本论文的贡献如下。首先，本论文使用 QP 启发式作为子程序，开发了一种实时元启发式，能够高效地为文献中发现的最大 SWTA 问题找到接近最优的解决方案，并在已知求解技术中占据优势（第 3 章）。在使用商业求解器 BARON 时，为 SWTA 开发了具有严格约束条件的对数变换，以提高求解的效率和质量（第 4 章）。开发了一种新的实时启发式算法，与已知的启发式算法相比，它能以更快的速度找到高质量的 SWTA 解，并在元启发式框架内实施，在比元启发式与 QP 启发式子程序所需的时间更短的时间内，找到 SWTA 解质量方面的最佳实时解（第 5 章）。在文献中首次开发并介绍了一种能够求解两阶段异构 DWTA 的求解技术，这是对 Ahner & Parson（2015 年）工作的扩展（第 6 章）。建立的 DWTA 模型考虑了来袭导弹的连续飞行路径和限制拦截器开火窗口的时间参数（第 7 章）。此外，还开发了一种能够解决两阶段射-看-射 DWTA 的求解技术，并在模拟中测试了其有效性（第 7 章）。最后，介绍了有关 WTA 的当代文献概览，重点介绍了基础性贡献以及按引用率衡量的主要贡献（第 2 章）。