共建共享双层策略驱动的复杂装备组合优化求解

陈子夷, 豆亚杰, 徐向前, 谭跃进, 杨克巍, 姜 江

(国防科技大学系统工程学院, 湖南 长沙 410073)

0 引 言

近年来,世界主要国家和经济体的国防预算增速不断放缓。根据瑞典斯德哥尔摩国际和平研究所2020年4月27日发布的《全球军事支出趋势》报告显示,2003～2019年来,世界军费年增长率大幅下降,期间更是在2015年到达过负增长的低点。我国的军费问题历来是中外舆论的焦点,自2007年以来,我国军费增速一直保持着下降趋势,占国内生产总值(gross domestic product, GDP)总量的百分比相较于世界平均水平一直处于相对较低的水平[1]。特别是新冠疫情严重影响了全球所有国家和地区的经济增长,在后疫情时代,全球军费增速将伴随GDP增速出现同步下滑趋势。而从我国军工装备研发制造主体、十大军工央企披露的数据来看,2013～2018年,我国军费投向的重点在于优化武器装备规模结构以及发展新型武器装备[2]。因此,在国防预算投入增速下降的背景下,“资源整合,多家共建,合理分配,各部共享”成为近年来各国装备发展规划的趋势。美军在其国防部的统筹规划下,已经完成了陆、海、空军靶场的绝大多数试验站点的联合能力建设和改造,可支持各军兵种和部队进行跨靶场与设施边界、跨试验与训练边界、跨真实-虚拟-构造边界的联合试验训练。我军也提出要用系统工程观念谋划发展,用严格规范的“路线图”指引发展,破除传统的“条块式”抓建,“烟囱式”发展,确保发展的持续性和可操作性[1]。在这种共建共享的趋势影响之下,传统的装备发展规划模式无法统筹考虑复杂装备、研发单位、应用场景之间的关联,导致装备重复建设、功能单一、资源无法共享,造成大量的资源浪费。因此,这种传统的装备发展规划模式与增速降低的国防预算以及迫切的发展需求之间存在着巨大的矛盾,如何更加高效和优质地进行复杂装备的组合优化,实现装备的共建与共享,成为亟待解决的重要问题。

针对装备发展规划领域来说,“共建共享”是一个新名词,但不管是美军大力开展的“联合试验与评估计划”还是我军装备发展规划的新尝试,其实都已经暗含了“共建共享”的理念。因此,本文提出共建共享双层策略驱动的复杂装备组合优化,是指在复杂装备发展规划的过程中,由于复杂装备的功能多、弹性高、自适应性强,涉及的关键技术多,参与研制的利益相关方多,需要统筹考虑研发阶段的资源整合利用,此为共建。同时,在规划过程中,还要超前考虑分配时的装备建设现状和预期运用阶段典型场景下的功能资源共用问题,此为共享。由此可见,共建共享理念下的装备发展规划,不仅是传统装备规划自身发展的结果,也是提高资源利用效益和效率的必然。

与一般的组合规划问题以及传统的装备体系发展规划问题相比,考虑共建共享的复杂装备组合优化求解研究面临着如下的挑战和问题。

(1) 所得方案需要是在共建阶段和共享阶段的综合最优方案。传统发展规划和组合选择问题的简单结合并不能保证“1+1=2”。复杂装备的组合优化问题,不仅要考虑共建阶段投资组合的复杂性,还要超前考虑预期运用阶段典型场景下的功能和资源共享问题,投资研发阶段共建和运用阶段中的共享都影响着复杂装备组合的优化决策。分开考虑共建和共享问题固然可以分开解决相应的问题,但各阶段最优并不一定可以保证是全局最优。这就需要设计一种相应的基于共建共享双层策略的优化算法来解决这一问题。

(2) 方案设计需要从已有基础和未来规划的角度考虑整体布局。共建和共享阶段的紧密联系要求解决方案之间具有更强的关联性。考虑共建共享的复杂装备组合优化问题不是单纯的数学计算,不是冷冰冰的模拟仿真,一个阶段装备体系的建设发展是需要几年甚至十几年的时间来进行打磨和精益求精,而共建阶段的研发方案和共享阶段的分配方案又不是完全割裂开来的,这其中涉及的人因作用十分重要,相关的历史数据、专家经验和决策偏好等反映到组合规划方案之上,便是其一步一个台阶的阶段性发展中方案之间的传承和关联性。如何在规划方案时体现出这种关联性,是如今交互式决策的重点。

(3) 大量约束和关联使问题具有更高的复杂度,需要更高效的求解方式。马赛克战、分布式杀伤、多域战等新型作战理念对我军未来的装备体系建设提出了更高的要求,现如今的新战场环境更加青睐多功能、高弹性和高自适应性的复杂装备[3],这些关联更加复杂的装备导致候选方案增多,使得复杂装备组合优化问题随着规模变大而出现组合爆炸的现象。同时统筹考虑共建和共享的问题使得变量和约束增多,解空间更加巨大和复杂。如何针对该问题设计一种高效的优化算法,从数量众多的解空间中快速找到高质量的解,对考虑共建共享的复杂装备组合优化问题的求解是至关重要的。

众多研究人员在以上方面进行了大量的研究。针对传统的装备发展规划问题,美军提出了基于能力的规划(capability based planning, CBP)[4-5]和根据其内涵发展出的能力组合管理(capability portfolio management, CPM)[6],主要是概念层的流程标准和建模框架分析[7-8]。而国内学界针对传统的装备发展规划问题和装备组合选择问题分别进行了研究,张西林等[9]基于设计结构矩阵对高端装备研制任务进行多目标优化求解,周宇等[10]设计了多目标差分进化算法将高维多目标问题转换为一般多目标优化模型,进行装备体系组合规划。向南等[11]提出了专家信任网络的概念,用于解决不完全信息条件下的武器选择问题,豆亚杰等[12]介绍了系统组合选择方法,并探讨了军事领域组合选择的应用与发展,但均是对于共建阶段的装备发展规划问题和共享阶段的装备组合优化问题进行分开研究。针对方案之间的强关联性,优化算法方面几乎未见尝试,研究人员多使用偏好关系理论来进行决策[13-16]。至于提升算法效率方面,近年来研究成果丰硕,有经典的遗传算法(genetic algorithm, GA)[17]、蚁群算法[18]、非支配排序遗传算法(non-dominated sorting genetic algorithms, NSGA)[19-20],也有研究者尝试使用深度学习帮助树搜索算法[21-22]或是利用机器学习加快上下限收敛过程[23]。综上所述,虽然目前对传统的发展规划问题和组合选择问题多有研究,但鲜有成果直接面向综合考虑共建与共享的复杂装备组合优化、统筹考虑方案之间的关联、针对性设计高效的优化算法。通过分析问题的特点,聚焦于问题的特殊性、方案的关联性、算法的高效性,助力于顶层决策者的装备发展论证工作,是本研究的主要研究动机。

针对以上挑战,本文提出了一种共建共享双层策略驱动的复杂装备组合优化求解方法,考虑在国防预算缩减的背景下,利用有限的经费投入,快速寻找合适的有效的复杂装备组合优化方案,使得发展规划的装备体系效益最大化。本文通过对多阶段问题进行建模描述,由深度神经网络辅助的分支定界启发式算法(deep neural network assisted branch-and-bound heuristic algorithm, DNNB&BH)在优化过程中进行同步求解。主要贡献包括:

(1) 实现了对于共建阶段发展规划问题和共享阶段组合选择问题的同步求解与优化。对于多阶段优化,分步分开解决问题所得的各阶段最优解并不一定是全局最优解,而每一步中都求解两个问题进行综合考虑又大大降低了优化的效率。本文所采用的DNNB&BH借助概率优先的决策方式和树搜索的探索方式,可以实现对于多阶段相关规划问题的综合考虑与同步求解优化。

(2) 充分考虑方案之间的传承和关联性。以往应用于一般问题的GA[17,24]、蚁群算法[18,25]和NSGA系列算法[19,20,26]等,这类算法从0开始求解,无法考虑方案的关联,借助的算子、变异等机理容易造成较大程度的跨越,相较于这些算法,本文所采用的神经网络的内在结构和可学习机理与方案本身以及之间的关联有一定的契合性,同时使用可学习的神经网络模型来辅助求解过程,可以通过神经网络模型将人因因素反映到求解过程中。

(3) 在算法效率方面,可学习的模型在分支选择和修剪的过程中给出合理的建议。分支决策加快了求解过程逼近最优解的速度,定界决策修剪掉多余的分支,缩小了解空间规模,大大提升求解效率,可解决问题求解过程中出现的组合爆炸问题。

本文的行文结构如下:第1节基于目标规划技术对共建共享双层策略驱动的复杂装备组合优化问题进行分析和建模,第2节描述了DNNB&BH和求解步骤,第3节以侦察预警监视体系研发的组合规划过程为例,验证了本文建立的共建共享双层策略驱动的复杂装备组合优化问题模型和所提出DNNB&BH的有效性,第4节总结了本文的研究成果。

1 问题分析及建模

1.1 问题描述

共建共享双层策略驱动的复杂装备组合优化问题可以描述如下:在进行装备发展规划时,以共建策略为驱动,从待研发的复杂装备集合中,选择若干项复杂装备进行研发工作,从备选研发单位中选取若干研发单位分别承担不同的研发任务,以均衡满足不同的能力需求。根据不同装备研发所需要的技术要求,将复杂装备分为几个大类,不同类型的复杂装备均可满足一种以上的能力需求。不同的研发单位侧重点和实力不同,可承担的武器装备研发类型不同和同时承担的研发任务工程量也不同。同时,还需考虑装备协同、经费预算、不同幅度的数量增加对能力提升的不同幅度等约束,尽可能最小化研发时间、研发经费和能力冗余。在进行装备组合选择时,以共享策略为驱动,根据各不同建制单位的装备配备现状和承担的使命任务,将复杂装备进行合理分配,以最大化满足各建制单位的能力需求。

如图1所示,对于需综合考虑共建和共享的复杂装备组合优化问题,传统的装备发展规划求解方法可以求出该问题解空间内的最优解,但需要注意到,每一个可能的装备发展规划方案都对应着装备组合选择问题的一个完全独立的解空间,因此,分开考虑装备发展规划问题和装备组合选择问题只能保证组合选择问题的解是发展规划问题最优解对应的解空间内的最优,其余发展规划问题的非支配解对应的装备组合选择问题的解空间并没有探索,无法保证得出了最优的发展规划方案后,仍然可以得到高质量的组合选择方案。因此,本文针对该类型的复杂装备组合优选问题,综合考虑共建共享策略,在双层策略共同驱动下,同时探索该问题的解空间,实现对于相关组合优化问题的综合考虑与同步求解优化。

图1 共建共享双层策略驱动的复杂装备组合优化求解框架Fig.1 Framework for combinatorial optimization solution of complex equipment driven by contribution and sharing two-tier strategy

1.2 问题建模及约束描述

表1对建模所使用的决策变量和符号进行说明。其中,xij,tij和nij为决策变量,其余为建模中所使用的符号。

表1 决策变量与符号定义

那么共建共享双层策略驱动的复杂装备组合优化问题可以表述如下:

minwt·tnorm+wm·mnorm

(1)

∀c∈C

(2)

xij=0, ∀i∈I; ∀j∈N1i

(3)

(4)

(5)

2xijlbti≤xijtij+tij≤2xijubti, ∀i∈I;∀j∈J

(6)

2xij≤xijnij+nij≤2xijubni,∀i∈I;∀j∈J

(7)

(8)

nij≤tij·μij, ∀i∈I;∀j∈J

(9)

(10)

qik=0, ∀i∈I;k∈N2i

(11)

(12)

∀c∈C

(13)

1.3 问题属性分析

由于存在以上诸多约束,假设待研发装备为Im项,备选研发单位为Jm家,待接收装备的单位为Km个,则可供共建共享双层策略驱动的复杂装备组合优化问题选择的解空间规模为

(14)

且随着待发展装备和备选研发单位的增加,解空间规模S呈指数增长,因此共建共享双层策略驱动的复杂装备组合优化问题是非确定性多项式难(nondeterministic polynomially hard, NP-hard)问题。

2 共建共享双层策略驱动的复杂装备组合优化问题求解方法

共建共享双层策略驱动的复杂装备组合优化问题属于NP-hard问题,其解空间规模大,使用精确方法可能找到最优解,但是同时付出的时间成本也非常昂贵,且单一的最优解也不一定适合辅助专家讨论进行决策。深度神经网络辅助的分支定界(branch and bound, B&B)法是一种新兴的启发式算法[21-22],其神经网络模型的可学习性大大降低了操作的复杂性,同时大幅度降低了求解所需的时间,不仅在求解特定的共建共享双层策略驱动的复杂装备组合优化问题上有良好的表现,同时通过不断的积累与学习,对于后期出现的同类型的共建共享双层策略驱动的复杂装备组合优化问题的求解上可以大大提升求解效率和求解质量。

DNNB&BH是将深度神经网络模型集成到B&B法的树搜索过程中,决定在搜索过程到达一个新的节点时,下一步选择哪一个分支,修剪掉哪些分支的算法。深度神经网络模型通过对专家经验、决策者偏好等各种历史数据和规划方案的有监督学习,从而实现在搜索过程中辅助制定选择和修剪分支的决策。该方法的核心思想是将每个可行解视为矩阵,通过定义的邻域结构来对矩阵进行改变,从而逐渐接近最优解。在整个过程中,利用树搜索来探索所有的可能性,辅以深度神经网络模型来确定探索的顺序,精简搜索树。每当搜索过程进入一个未探索节点时,深度神经网络模型就会通过评估几种既定的变化策略得到的子节点,并预测哪一种变化策略得到的子节点具有最高的概率通向最佳解决方案,从而确定下一个搜索的节点。同时通过对各个子节点的下界进行预测,修剪掉那些具有比当前最优解目标函数值更高的下界对应的节点,以达到精简搜索树,缩短搜索时间的目的。

2.1 邻域结构

B&B法是围绕搜索树进行的,可用于解决优化问题的一种方法。B&B法从根节点开始,通过系统地探索根节点的子节点及其后续节点来探索搜索树。分支的过程就是不断给树增加子节点的过程。而定界就是在分支的过程中检查子问题的下界,如果子节点不能产生一个比当前最优解还要优的解,那么就修剪掉这一支。直到所有子节点都不能产生一个更优的解时,整个搜索流程结束。给定优化问题的解决方案可以理解为树中的叶节点[28]。

对于一个给定的可行解Si,可以通过对其施加某些变化得到一个新的可行解Si+1,那么这个新的解就是可行解Si的邻域解,该变化可称为邻域变化v,将v作用于Si所得的邻域解的集合定义为V(Si),那么对于共建共享双层策略驱动的复杂装备组合优化问题可以定义如下的邻域结构[29]。

邻域 1分配原本未承担装备i研发的单位j针对该装备的研发任务,该邻域变化的集合为

V1(Si)={v1(i,j)|∀i∈I, ∀j∈J,xij=0}

(15)

邻域 2取消原本已承担装备i研发的单位j针对该装备的研发任务,该邻域变化的集合为

V2(Si)={v2(i,j)|∀i∈I, ∀j∈J,xij=1}

(16)

邻域 3交换两家研发单位j1,j2针对装备i的研发任务,该邻域变化的集合为

V3(Si)={v3(i,j1,j2,tij1,tij2,tij2,nij1,nij2)|∀i∈I, ∀j1,j2∈J,xij1,xij2≠0}

(17)

邻域 4将装备i分配给原本未接收该装备的单位k,该邻域变化的集合为

V4(Si)={v4(i,k)|∀i∈I, ∀k∈K,qik=0}

(18)

邻域 5将原本已分配给单位k的装备i取消,该邻域变化的集合为

V5(Si)={v5(i,k)|∀i∈I, ∀k∈K,qik≠0}

(19)

2.2 深度神经网络模型

2.2.1 模型构建

深度神经网络,是一种模仿生物神经网络的结构和功能的模型,用于对函数进行估计或近似。神经网络由大量的人工神经元联结进行计算。每个神经元从上一层神经元接受一个或者多个加权输入,将这些输入汇总后由激活函数处理,所得的值将传输给下一层的神经元。深度神经网络通过优化各层神经元之间连接的权重值来进行学习。深度神经网络既可以用来解决分类问题(解空间Y由一组离散值组成),又可以用于回归问题分析(解空间Y可以是R中的任意值),本文使用的是回归网络模型。其中,分支决策深度神经网络模型用来预测输入的解决方案可能接近最优解的概率,而分支修剪深度神经网络模型用来预测输入的解决方案的最优下限。分别定义“距离”和“概率”来说明解决方案可能接近最优解的概率的含义。

定义 1距离。当前解决方案通过邻域变化转化为最优解决方案需要的变化次数。

定义 2概率。当前解决方案通过邻域变化可以转化为最优解决方案的可能性。

相应的,当前解决方案与最优解决方案之间的距离越短,概率越高,那么当前解决方案可以通过搜索得到最优解决方案的可能性也就越大。 图2展示了如何理解距离和概率之间的关系。如图3所示,本文使用的深度神经网络第一层为输入层,具有Im×Jm个节点,用于将输入的多维矩阵一维化。中间层为隐藏层,第一层也具有Im×Jm个节点,其后每层节点数依次减半,直到节点数为2。隐藏层的每个节点的激活函数均为ReLU函数,其定义为ReLU(x)=max{0,x}。输出层只包括一个节点,用于输出所预测的概率或最优下限。

图2 距离和概率示意图Fig.2 Figure of distance and probability

图3 神经网络结构示意图Fig.3 Figure of neural network structure

下面介绍进行分支决策的深度神经网络模型在B&B法中如何发挥作用。当搜索进度到达了某一节点n时,对该节点顺序采用邻域变化进行矩阵变换,变换后所得节点为nk,该节点对应的解决方案矩阵sk,sk作为输入传输进分支决策深度神经网络模型。通过分支决策模型得到一个输出,该输出即代表对应节点nk对应的概率值。然后使用这些输出来确定应该探索节点n的哪些分支(例如首先探索与对应概率值最高的节点所在分支)。概率值的存在不仅仅为这些子节点提供了一个先后排名,也可以代表由分支决策模型给予每个子节点的置信度。图4显示了搜索过程中如何使用分支决策模型。

图4 分支决策深度神经网络模型示意图Fig.4 Figure of branch decision deep neural network model

定界决策深度神经网络模型与分支决策模型具有相似的结构。两种模型都使用同一个输入(与节点nk对应的解决方案矩阵sk),不同的是定界决策模型的输出代表所预测的该分支的最佳下限,这意味着如果后续搜索沿着该分支往下,可能会得到最终最佳目标函数值的大小。所以,如果预测的最佳下限超过或等于当前已经找到的最佳解的目标函数值,那么该分支就不具有继续探索的价值。由于定界决策模型在预测过程中波动稍大,因此可以将其乘以0到1之间的权重以减少其启发式下限。图5显示了整个搜索流程中定界决策的示例。其中B_pred1,B_pred2,B_pred3分别代表图中第1、第2和第3个子节点通过分支决策模型所得到的最佳预测下界,B_found代表图中搜索流程目前已经找到的最优解目标函数值,在这种情况下,将修剪掉第3个子节点,因为其预测的最佳下界大于当前已经找到的最佳目标函数值。

图5 分支定界决策深度神经网路模型示意图Fig.5 Figure of branch bounding decision deep neural network model

2.2.2 模型训练

深度神经网络模型需要使用大量和任务相关的数据集来训练模型,用以调整适合模型的参数,例如不同层神经元之间连接的权重。这些被用来训练模型的数据集是本文结合人因信息的数据来源。通过将包含专家经验和偏好信息的大量历史数据转化为神经网络的对应输入数据形式和输出形式,即将历史数据和决策结果分别转化为可输入神经网络的模式化矩阵和数值标签,形成一批涵盖相关的历史数据、专家经验、决策偏好等人因信息的训练集。其中的传承和关联性通过神经网络的训练的反向传播过程,以逐层更新神经元之间连接的权重的方式,被学习到最后的神经网络模型中。

具体的训练过程如下。在训练过程中,训练集中的每个实例都被输入到深度神经网络中,并由网络逐层传播,以生成相对应的输出。然后,使用损失函数将这些输出的值与训练集中的标签进行比较,来计算预测的准确性。下一步,根据网络权重对损失函数的影响来调整网络中连接的权重,以减少下一次迭代(梯度下降)中损失函数的值。处理完训练集中的所有实例后,一次训练就结束了。训练过程可以重复很多次,直到得到满意的模型为止。

2.3 算法框架与流程

针对共建共享双层策略驱动的复杂装备组合优化问题设计的DNNB&BH求解步骤如下。

步骤 3将集合V1(Sa),V2(Sa)和V3(Sa)中所有的解决方案矩阵输入各自的分支决策深度神经网络模型,这些数据将通过神经网络进行传播,并到达输出层,在输出层中使用sigmoid激活函数来获取0到1之间的结果,这些结果便可以被视为概率。然后,将每个邻域变化所得集合中概率最高的结果留下来,作为该邻域结构分支的子节点,因此在共建策略下的搜索树中,对应3个邻域结构,每个父节点都会有3个子节点,在共享策略下的搜素树中,对应两个邻域结构,每个父节点都会有两个子节点,根据第2.1节中提到的邻域对应关系,邻域变化1所得的子节点与邻域变化4所得的子节点对应,邻域变化2所得的子节点与邻域变化5所得的子节点对应。

步骤 4将共建策略下的搜索树所获得的子节点再次输入给定界决策深度神经网络模型,将输出与当前已找到的最优目标函数值进行比较,如果小于当前已找到的最优目标函数值,则保留该子节点对应的分支,否则修剪掉该子节点对应的分支,同时剪掉共享策略搜索树中对应的子节点分支。

图6展示了整个算法流程示意图。

图6 搜索流程示意图Fig.6 Diagram of search process

3 案例

3.1 案例描述

现代战争是全方位、多维度、高技术条件下的信息化战争,战争形态和样式都发生了深刻变革,在陆、海、空、天、电的立体战场内,需要诸多类型的侦察、预警和监视装备构成完善的装备体系,共同作业,协同作战,以满足特定使命任务下的能力需求。但现代高新军事装备造价昂贵,待研发型号类型多样,通过数量优势满足体系要求代价过高,因此在研发和建设阶段就需要统筹规划如何用最小的代价构建最完善的装备体系。除此之外,装备之间功能各有侧重,某些装备在执行任务时具有不可替代性,这就需要决策者在顶层规划的时候,不仅仅考虑装备如何建的问题,还要考虑装备怎么用,最终使研发出的装备成体系发展,以履行新的历史使命,完成多样化军事任务。该侦察预警监视装备体系的装备信息、备选研发单位信息、能力需求集合和待接收单位装备建设现状如表2～表5所示。

该侦察预警监视装备组合优化问题需要分别将以上8种不同装备的研发任务交由备选的10家研发单位进行装备发展,在完成研发任务后还需考虑不同接收单位的装备配备现状和承担的使命任务,完成装备的列装工作。问题中的研发时间、研发数量和分配方案满足第2章中提到的各类约束。表2中“√”表示横向对应装备可满足的纵向能力,以侦察卫星为例,其最大支持经费为60亿元,可规划研发时间范围为5到20年,可规划研发数量为5到20颗,可支持目标识别、定位跟踪、持续监视和传输分发4种能力。表3中√表示横向对应研发单位纵向对应可承研复杂装备类型,以单位1为例,其每单位工程量所需经费为1.8亿元,其最大可承担工程量为30年,可承担航天类、配属类和系统类3种类型的装备研发任务。

表2 待研发复杂装备信息

表3 备选研发单位信息

表4 能力需求集合

表5 待接收单位装备建设现状

本案例主要用于方法的有效性验证,因此训练集数据来自基于上文描述的案例约束,随机生成及人为规划的可行装备发展规划方案及对应的人工打分输出标签,通过将可行装备组合优化方案通过邻域变化来增加方案之间的关联性,通过理智思考,各自填充标签来充当专家经验和决策偏好,假设经过以上措施,这些数据已经包涵了相关的历史数据、专家经验、决策偏好等人因信息。

本案例使用的神经网络具有1个输入层、6个隐藏层和1个输出层。其中,输入层有80个神经元,6层隐藏层的神经元个数分别为80、40、20、10、5和2个,输出层具有1个神经元。具体实现使用Python 3.7算法,使用tensorflow 2.0.0下的keras 2.3.0作为深度神经网络的实现后端。所有的模型都使用基于梯度下降[30]的自适应矩估计(adaptive moment estimation, Adam)优化器进行训练,构建出该共建共享双层策略驱动下的侦察预警监视装备组合优化问题模型。

3.2 算法对比分析

分别采用DNNB&BH、B&B、GA和Gurobi求解器对上述问题求解。Gurobi是新一代大规模优化器,目前广泛应用于生产制造、金融、保险、交通和服务等领域。通过分别与未嵌入神经网络模型的B&B方法,经典优化算法和知名商业求解器的对比,来验证本文提出的神经网络辅助的混合优化算法的性能。

从第1.2节的问题描述和第1.3节的问题NP-hard属性分析可知,共建共享双层策略驱动的复杂装备组合优化是一个多阶段优化问题,包含装备建设时的发展规划和装备分配时的组合选择,同时问题也具有NP-hard属性。因此,受限于各自设计之初的算法结构,GA和Gurobi求解器只能对该问题进行分阶段求最优解,即在求出第1阶段的最优解后,在第1阶段的最优解的参数限制下,求解第2阶段的最优解。但对于DNNB&BH和去掉了神经网络模型B&B方法的来说,在共建共享双层策略的指导下,即第2.3节步骤3中描述的邻域联动变化策略,DNNB&BH求解该问题是寻求两个阶段的综合最优,对问题进行整体求解。所以,将阶段1目标函数和阶段2目标函数进行分开对比,需要注意的是,无论是在图7(a)还是图7(b)中,DNNB&BH和B&B对应的曲线都是在共建共享双层策略驱动下对整个问题直接进行求解的曲线,而Gurobi和GA对应的曲线则是分开求解的各自阶段的曲线。

由图7可知,Gurobi在第1阶段收敛速度极快且优化效果很好,GA收敛速度较快,但陷入了局部最优,其第1阶段问题目标函数值略逊于本文提出的DNNB&BH。但需要注意到的是,图7中反应的DNNB&BH的收敛曲线是该方法在同时考虑共建和共享的情况下对整个问题进行求解的收敛曲线,因此并不意味着其真实收敛速度弱于GA。没有神经网络模型指导的B&B方法,虽然其收敛曲线也是同时考虑共建和共享的情况下对整个问题进行求解的收敛曲线,但与DNNB&BH相比,可以发现其寻优速度明显变慢,且求解质量明显下降。在图7(b)中,体现出了共建共享双层策略驱动的优势,Gurobi求解器虽然仍然保持了收敛速度快的优势,但由于整个问题被分开考虑,其第2阶段问题目标函数值的上限被限制,因此无法得到高质量的第2阶段问题解,而GA无论是在收敛速度还是最终解的质量上都有一定的差距,至于没有神经网络模型指导的B&B方法,虽然在初期,相比于GA略占优势,但不论是相比于可以进行交叉变异操作的GA,还是有神经网络模型指导的DNNB&BH方法,后期缺少了神经网络模型辅助的B&B方法在探索解空间时策略过于简单的弊病就体现了出来,陷入了解质量较差的局部最优解且无法逃离。可见,神经网络模型对搜索过程的辅助决策确实发挥了作用,且DNNB&BH在综合表现上更加稳定。这是因为在共建共享双层策略的驱动下,同时探索了阶段1和阶段2的解空间,而不是在分开求解的过程中,因为追求各阶段最优而舍弃了可能达到综合更优的次优解。

3.3 方案分析

我们可以得到共建共享双层策略驱动下的侦察预警监视装备组合优化方案,如表6所示。表6中每一栏有两项数据,第一项代表组合规划方案所规划的研发单位针对该项装备的研发时间,第二项代表研发单位针对该项装备的研发数量。以侦察卫星为例,表中数据表示将侦察卫星的研发任务分别分配给单位1和单位5两家单位,单位1的研发任务为10年完成11颗侦察卫星的研发任务,单位5的研发任务为8年完成8颗侦察卫星的研发任务。

表6 共建共享双层策略驱动下的侦察预警监视装备组合优化方案

同时,如图8所示,与Gurobi求解器和GA所得的组合优化方案进行横向对比。可以发现,DNNB&BH所求得的方案可以在总经费和总工程量与GA方案相近的情况下,更好地满足能力需求,Gurobi所求得的方案分别在所需要的总经费和总工程量有所减少,但因此也付出了能力满足度降低的代价。这是由追求第1阶段最优从而导致的解空间有限的结果。图9将能力需求满足度进行更进一步的对比,虚线代表能力需求列表中不同能力的需求值。可以看到,在图9中,通过一一对比最终方案里,各个预接受单位按照方案建设后对能力需求列表中每一项能力的能力满足度,将图8中的平均能力需求满足度这一目标函数值之间的差距进一步放大。GA所求得方案在每一项能力中,都有绝大部分接受单位出现了明显的能力冗余或能力缺失。Gurobi求解器表现依然稳定,但在D和C的自适应能力和互操作能力,A的传输分发能力和B的目标识别、持续监视和定位跟踪能力上出现了小幅度的能力缺失,在D、B和A的指挥控制能力上出现了小幅度的能力冗余。而DNNB&BH所求得的最终方案表现较为均衡。可见,在共建共享的双层策略驱动下,DNNB&BH可以统筹考虑方案之间的关联,同时探索不同阶段的解空间,迅速完成算法的收敛,在短时间内求得不同目标下复杂装备组合优化问题的相关联高质量可行解,与传统GA相比占有一定的优势,与市面上广泛应用的商业优化器相比也有一定的竞争力。

图8 各组合规划方案对应各目标值Fig.8 Corresponding objective function value of each combinatorial planning scheme

图9 各组合规划方案对应各单项能力值Fig.9 Individual ability value of each combinatorial planning scheme

4 结束语

联合作战与体系对抗是现代战争的重要发展趋势,“彼此联合”与“形成体系”既是对未来复杂装备研发的目标需求,也是影响着装备体系研发组合规划方案的重要理念。决策者不可避免地要面对各种“组合规划”的问题。但目前对于共建共享双层策略缺失的复杂装备组合优化问题又缺乏完整、定量、高效的求解方法支撑。所以,本文研究了针对共建共享双层策略缺失的复杂装备组合优化问题的规划模型和优化算法,用于解决这一装备发展规划领域的重要问题。当给定各类相关参数、历史数据、专家经验和决策者偏好之后,通过本文提出的规划模型和DNNB&BH,可以快速获得包括装备研发任务分配、研发时间、研发数量和装备组合选择的具体方案。

相比于经典方法,本文使用共建共享双层策略驱动,从发展规划阶段的共建过程和预期运用阶段共享过程出发,整体设计获得全局综合最优,避免了分阶段考虑造成的资源浪费问题。在传统的启发式方法的基础上,本文引入深度神经网络模型的辅助决策,充分整合了历史数据、专家经验和决策者偏好,既为决策提供了可靠的依据,又是一种自动化决策理念的全新尝试。本文受限于敏感数据原因,设计了侦察预警监视装备体系的说明性案例对方案进行验证,如果后续可以将方法应用于工程项目的特定建设任务和典型场景中,则更能验证方法的应用价值。

除此之外,本文提出的问题模型对于能力的定量化描述、目标偏好处理、混合式启发式方法中神经网络模型的辅助决策以及自动化方法解决组合优化问题的创新尝试,都是可以被推广应用的通用性改进,虽然本文考虑的是复杂装备这一装备发展规划中的特殊情况,但本文在问题模型和混合式启发式方法上的通用改进同样适用于主管部门对于一般装备的统筹建设,通过将模型进行适当的拓展,可以推广到其他功能单一的一般装备的发展规划问题中,为问题的决策提供科学量化的理论支撑和模型依据,继而辅助部门管理者提升管理效率。