基于改进TICC聚类算法的智能博弈宏观策略生成技术*

周 盼 程健庆 初 阳

（江苏自动化研究所 连云港 222006）

智能博弈是指在仿真条件下拥有智能思维的博弈双方根据战场实时态势数据，自主做出决策判断，并反馈于战场，进而控制战场的兵力、装备等形成智能对抗行为的过程。目前智能博弈技术在很多领域都取得了显著突破。在民用领域，智能AI已经在人机对抗赛中战胜人类顶尖选手。如AlphaGo/AlphaZero（围棋AI）［1］、AlphaStar（星际争霸AI）［2］和绝悟（王者荣耀AI）［3］等。在军事领域，作战与指挥智能博弈问题也得到了积极研究，美国一直推进智能博弈技术的发展，希冀借此提高作战指挥的效能，缩短筹划时间，先后启动了“深绿”［4］、指挥官虚拟参谋［5］、“指南针”（COMPASS）等一系列项目。

智能博弈中智能体输出的自主决策主要分为微观决策和宏观策略两种。微观决策是指决策智能体根据当前时间点的博弈态势输出对战场兵力进行控制的决策指令，如控制兵力进行转向、移动或发射武器等；
宏观策略指智能体根据一段时间内整体博弈态势输出的更高层次的策略方案，如全面进攻敌方目标、撤退防守我方阵地等。目前，通过基于微观决策的深度强化学习算法可以做到让计算机在博弈对抗时获得近似于人类表现的决策［6］，但无法直接满足当前作战指挥中日趋复杂的宏观策略需要。鉴于现实中复杂决策问题通常为宏观策略问题，智能博弈中宏观策略生成技术亟需研究。

在宏观策略研究领域，Synnaeve 等［9］对收集到的回放数据进行预处理，提出了将星际争霸玩家的开放决策模式从有限的决策模式中集中分类的识别方法。Justesen、Rsis 等［8］提出一种基于DNN 方法的来学习博弈对抗中的宏观全局状态策略评估。Gabriel S 等［7］提出基于贝叶斯网络的模型，专门应对态势信息中的不确定性和不完全性进行宏观策略。

总体来说，目前关于宏观策略的研究主要集中在数据预处理、决策识别分类以及决策效果评估等领域，而且大部分研究是面向固定领域任务的宏观策略，在海上作战方向，结合智能博弈生成宏观策略的方法研究不多。鉴于智能博弈具有巨复杂、高动态、强对抗等特点，为解决宏观策略生成问题，本文在以微观决策为主的智能博弈中收集特征数据，对TICC 聚类算法进行改进，提出一种基于FS-TICC 分割聚类算法的智能博弈宏观策略生成框架，并使用该算法对某博弈中高维特征时间序列数据进行了分割聚类，验证了算法的有效性。本研究能够清晰地展示智能博弈中的宏观策略生成过程，使智能体的自主决策较直观、可信，且在某种程度上具有一定的可解释性，为使用人工智能技术生成作战方案奠定基础。

针对智能博弈决策过程获取的博弈态势S 和微观决策时间序列D，为了对其时变相关性结构进行建模和聚类，本文提出一种智能博弈宏观策略生成框架，将由博弈态势S 和微观决策D 组成的智能博弈特征变量时间序列Xorig进行了阶段分割，并对不同阶段的宏观策略进行了聚类，最后对聚类结果进行分析，生成框架如图1所示。

图1 智能博弈宏观策略生成框架

具体步骤如下：

1）智能博弈特征数据采集

对智能博弈过程中实时产生的微观决策指令和对应时间点的博弈态势进行记录，可以得到的博弈态势时间序列和微观决策时间序列。

博弈态势时间序列：

微观决策时间序列：

这两个序列将作为聚类算法输入的智能博弈特征数据，其中T 为智能博弈过程在时间维度上的长度，博弈态势si表示时间点为i 时智能体已知的环境态势和敌我双方的状态的n1元变量。微观决策di表示时间点为i 时智能体直接控制兵力、武器单元执行的相关动作指令的n2元变量。

2）分割聚类

为了获取时间序列数据在特征维度之间和连续时间段之间的时间上相互依赖关系，通过特征选择输入、阶段分割和策略聚类三个步骤对获取的博弈数据进行分割聚类，具体方法见第4节介绍。

3）宏观策略生成

使用算法聚类结果对智能博弈特征变量时间序列Xorig进行阶段分割和宏观策略聚类。Xorig由智能博弈的博弈态势S 时间序列和微观决策D 时间序列共同组成：

其中n=n1+n2，xi表示时间点为i时的智能博弈联合特征的n 元变量。智能体在阶段i 的时间段中，会遵循一个宏观策略li，当智能博弈转换为下一个阶段i+1 时，智能体会更新当前的宏观策略为li+1。其中，阶段是使用聚类结果将Xorig中的博弈态势进行分割的q 个区间段落。而宏观策略为通过算法对不同阶段的特征数据进行聚类，从而提取不同阶段下的宏观策略模式。

4）聚类结果分析

对智能博弈特征变量Xorig进行分割聚类后，可以获取分割后各个阶段的宏观策略标签和聚类特征。通过宏观策略聚类的特征数据随时间变化的特点，对聚类结果进行分析解释。通常可以选择决策人员主要关注的部分态势特征变量，绘制一组分割聚类后的时间序列数据，由此将分割聚类的结果进行可视化，在此基础上对聚类结果进行分析。

综上所述，智能博弈宏观策略生成的总体框架是首先将智能博弈中采集的高维时间序列特征数据博弈态势S 和微观决策D 分割为q 个阶段，然后将这q 个阶段中的宏观策略聚类为K 个类，最后对结果作出分析解释。其中最关键的步骤是对特征数据进行分割聚类，这是本文的一大挑战，不但需要在分割阶段后对重复出现的宏观策略模式进行识别和合并，还不同于单独的子序列聚类，需要尽可能地将相邻时间戳聚为一类。传统聚类方法通常依赖于基于距离的指标，在时间维度上的考量并不深入，很难适用于高维时间序列数据的分割聚类。本研究将智能博弈中的宏观策略生成过程转换为一种特殊的对多元时间序列进行无监督分割和聚类的过程，对Hallac 等提出的TICC 算法［10］进行改进，提出FS-TICC 算法，实现基于特征选择和时变相关性结构的分割聚类。

托普利兹逆协方差聚类算法（Toeplitz Inverse Covariance-based Clustering，TICC）是一种基于模型的聚类方法，考虑了数据之间的时变相关性，在时间序列聚类上可以获得较为理想的聚类结果。智能博弈过程特征变量的多元时间序列Xorig由博弈态势时间序列S 和微观决策时间序列D 共同组成，博弈过程中阶段的划分标准取决于博弈态势在时间上的变化特征，与微观决策没有直接相关性。TICC 算法直接将特征变量Xorig作为特征输入时，多余的特征会增加复杂度以及可能过拟合。为了降低数据的冗杂度和计算复杂度，提高算法的计算速度以及增强聚类结果的可理解性，本文将基于特征输入选择（Feature Selection）来改进TICC。

3.1 TICC算法介绍

在TICC 算法中，为了便于考察智能博弈特征变量Xorig时变相关性，定义大小为w<< T 的时间窗口，并将xi之前相邻的w 个时间点拼接成一个向量Xi=［xi-w+1，…，xi］T作为算法的输入。算法还定义了能够描述各特征变量之间时变相关性的K 个对称分块Toeplitz 矩阵的逆协方差Θi，Θi可以捕获特征变量之间时变结构模式，并根据不同阶段的特征变量的逆协方差Θ与Θi的相似度将阶段下的宏观策略模式进行聚类。

TICC 算法最终求解目标为K 个逆协方差Θ={Θ1，Θ2，…，ΘK}，及其分割集合P=｛Pk|k=1，…，K｝，其中Pk⊂｛1，…，T｝，求解该上述多元时间序列分割聚类问题的整体目标函数数学表达式如下：

其中，λ为正则化参数；
ℓℓ(Xt，Θi)为Xt于聚类i的对数似然函数值；
β1{Xt-1∉Pi}为确保使相邻时间向量Xi-1和Xi尽可能聚为一类，保持时间一致性的参数。

3.2 特征输入的改进

本文提出的FS-TICC算法的核心是求解式（1）中分割集合P 和簇参数逆协方差Θ两组变量参数时各自选择特征变量输入，该求解过程是一个混合组合和连续优化的高度非凸问题，通过对期望最大化算法［11］（EM算法）进行改进来解决该问题。主要思路是在更新分割集合参数P 以及更新簇参数Θ之间选择各自的输入特征变量，并交替进行迭代最小化。

改进后的TICC算法迭代过程主要分为两步：

1）更新分割集合P：初始化各个簇即各个逆协方差参数Θ，并且固定这些参数，以更新分割集合参数P，这一步的目的是得到智能博弈过程中的特征时间序列数据的阶段划分，故只需要输入特征变量中博弈态势部分。因此，现阶段子问题转化为如下目标函数：

2）更新逆协方差Θ：在更新完分割集合参数P之后，固定P，以交替更新逆协方差Θ。该步骤是为了提取博弈过程中的宏观策略模式，故需要输入特征变量中博弈态势和微观决策两个部分，在该步骤中整体目标函数中的β1{Xt-1∉Pi}将变成不影响最小化目标函数的常数C。这样，该阶段的子问题目标函数将定义如下：

其中Ci为Xi的博弈态势和微观决策特征参数计算得到的当前协方差阵。式（7）只有对数似然项和稀疏项，可以采用交替方向乘子法［13］（Alternating Direction Method of Multipliers，ADMM）来求解该参数优化问题，由此得到每个簇的逆协方差矩阵Θi。

重复1），2）两步，直到分割聚类结果收敛或者达到迭代次数的上限时终止，并输出分割集合参数P和逆协方差矩阵参数Θ。

3.3 参数选择

在本文提出的FS-TICC算法求解步骤中，需要对时间窗大小w、聚类簇数K 两个参数进行选择或设置。

时间窗大小w 表示算法中最小的数据粒度，该值越大，输入的时间序列数据越长。w 不宜太大，因为如果太大可能很难正确地分割时间段边界上的点，在边界上的关于时不变结构的假设可能不成立。因此，w 的取值一般相对较小，选取时应该综合考虑在智能博弈领域的以往经验、观察数据的粒度和平均期望长度，或者针对具体的博弈场景进行多次预先实验来确认。

聚类簇数K表示提取的宏观策略类的数量，有多种方法可以确定K 的具体数值，一般可以基于相应领域的专业先验知识来确定一个理论上的聚类数，或者结合BIC 分数、轮廓系数或交叉验证等方法综合考虑K 的具体数值。在本研究中聚类簇数的确定值往往主要取决于智能博弈场景本身，其主要因为除了聚类准确性之外，还需要给予结果的可解释性。

为了验证提出算法的有效性，采用某智能蓝军项目构建的决策智能体和仿真系统开展研究。仿真想定为蓝方某大型海上编队起飞战斗机，突破红方防空拦截线，对红方重要水面目标进行打击。运行仿真系统，开展100 组红蓝博弈对抗，博弈对抗中蓝方某架战斗机飞行轨迹如图2所示。

图2 蓝方某架战斗机飞行轨迹

选取博弈对抗数据中的总得分、起飞飞机数量、发射武器数量、己方兵力信息、探测到的敌方兵力信息、摧毁敌方飞机数量、摧毁敌方重要目标数量和己方被摧毁的单位价值等作为博弈态势时间序列S 以及智能体控制兵力执行的动作等作为微观决策时间序列D 作为分割聚类算法的输入。本次实验为了使聚类结果更加合理准确，对获取的数据进行了归一化预处理，并以博弈中蓝方智能体视角获取的数据来进行实验。

4.1 实验中算法参数选择

在进行分割聚类之前，首先要对算法的参数进行选择，以选择合适的窗口大小w 和聚类簇数K。主要思路是结合智能博弈场景和轮廓系数法，设计了9 组不同参数求解轮廓系数s。不同参数选择下计算得到的轮廓系数如表1所示。

表1 不同参数选择下的聚类结果的轮廓系数

经过对比分析，第4 组的轮廓系数得分最高，所以本次实验选择的参数为窗口大小为4，聚类簇数为4。

4.2 聚类结果与分析

利用本文提出的FS-TICC 算法对数据进行分割聚类，将分割聚类后的一部分时间序列数据（总分数、起飞飞机数量、己方单位总价值、发现敌方单位数量、发射武器数量、摧毁敌方单位的价值、摧毁敌方重要目标的总价值、被摧毁飞机数量）的聚类结果绘于图3 中。其中时间序列的横轴统一为时间刻度，分割结果为各个阶段的簇标签，不同阶段用线划分，并将其用A～D字母进行标记。

图3 宏观策略FS-TICC分割聚类结果

下面对聚类结果及其标签做出分析解释。

阶段一的宏观策略聚类标签为A，博弈对抗过程刚开始，己方逐步起飞飞机，但是尚未发现敌方单位，可以解释当前宏观策略为进行兵力部署；

阶段二的宏观策略聚类标签为B，总分数、起飞飞机数量继续上升，开始发现大量敌方单位，但发射武器数量和摧毁敌方单位数量一直处于低位，没有发生大规模冲突，可以解释当前宏观策略为侦查敌情；

阶段三的宏观策略聚类标签为C，起飞飞机数量上升趋势减缓，发现敌方单位数量和发射武器数量迅速上升，敌我双方开始交战，双方均出现战损，可以解释当前宏观策略为主动进攻敌方目标；

阶段四的宏观策略聚类标签为D，己方被摧毁飞机数量开始出现大规模上升的情况，但同时起飞更多飞机加入战斗，同时摧毁的敌方单位数量上升，可以解释当前宏观策略为防守待援；

阶段五的宏观策略聚类标签为C，总分数迅速上升，且己方在迅速摧毁敌方重要目标和敌方单位，可以解释当前宏观策略为主动进攻敌方目标。

最终宏观策略聚类结果分析解释见表2。通过上述分析，可以定性的认为本文提出的FS-TICC算法分割聚类的结果与智能博弈宏观策略生成过程的特征一致，证明了该算法的有效性。

表2 宏观策略聚类结果分析解释

4.3 不同聚类算法对比结果

本小节将实验中获取的数据取平均值，将FS-TICC 算法与TICC 算法、FCM 算法和K-means算法进行比较研究。所有算法的输入数据集相同，聚类簇数均设置为4，聚类后不同结果转化为二维的生产资源数量-己方单位总价值散点图形式，其中聚类效果的展示如图4～7 所示。FS-TICC 算法与TICC算法平均计算时长如表3所示。

表3 FS-TICC 算法与TICC算法平均计算时长

图5 TICC 算法聚类效果

图6 FCM算法聚类效果

1）FS-TICC算法与FCM等传统聚类算法比较

由图7可以明显看出，传统聚类算法只是对时间序列数据进行了分割，并没有发现博弈过程中的阶段五的宏观策略聚类标签，得到的结果与智能博弈宏观策略模型并不相符。分析其中原因是传统聚类分析算法只是基于数据的结构在边界阈值上进行分段划分，无法反映出不同参数时域上的变化关系，而智能博弈中高维时序数据的维度之间以及连续时间段的数据是有着一定的关系，所以传统的时序数据聚类算法对智能博弈中高维数据进行准确的聚类。

图7 K-means算法聚类效果

2）改进的TICC算法与改进前算法比较

由表3可以看出，由于FS-TICC算法在特征变量选择针对TICC 算法做出了改进，减小了一部分输入特征变量的维度，大大提高了计算效率。

对比图3 和图4 可以看出，由于TICC 算法在分割阶段时的特征变量输入较为冗杂，分割成了较为繁复的六个阶段，而且在阶段一和阶段二之间，阶段三和阶段四之间的均出现分界不清晰的情况，给聚类结果的分析带来了困难。

综上可知，FS-TICC 算法对智能博弈中的高维时间序列数据进行时间序列分割聚类的效果要优于其他几种算法，结果更加符合智能博弈中宏观策略模型。

目前，智能博弈对抗中的高维时间序列数据的日趋繁多，然而传统聚类分析算法忽略了高维时间序列数据中特征参数在时间域上的关系，从而限制了传统聚类算法对宏观策略聚类的性能。本文提出了一种智能博弈宏观策略生成框架，并对TICC算法进行改进，实现对高维时间序列数据分割聚类，采用某智能博弈实验收集到的数据进行了实验验证，通过对比分析可以看出，针对高维时间序列分割聚类问题，改进的TICC 算法比传统算法具有更好的聚类效果，能够表现一定程度的可解释性，聚类结果可作为利用智能博弈技术生成作战方案的基础。

猜你喜欢宏观聚类决策为可持续决策提供依据纺织科学研究(2021年9期)2021-10-14决策为什么失误了中学生数理化·七年级数学人教版(2019年6期)2019-06-25基于DBSACN聚类算法的XML文档聚类电子测试(2017年15期)2017-12-18基于高斯混合聚类的阵列干涉SAR三维成像雷达学报(2017年6期)2017-03-26宏观与政策中国机电工业(2016年5期)2016-12-01宏观河南电力(2016年5期)2016-02-06宏观中国机电工业(2015年5期)2015-02-28一种层次初始的聚类个数自适应的聚类方法研究电子设计工程(2015年6期)2015-02-27自适应确定K-means算法的聚类数：以遥感图像聚类为例华东师范大学学报（自然科学版）(2014年6期)2014-02-27宏观资讯中国工程咨询(2014年1期)2014-02-16