(1991-), 女, 博士, 副教授, CCF 专业会员, 主要研究领域为软件演化与自适应, 智能化软件运维
(1998-), 男, 硕士, 主要研究领域为自适应软件, 微服务软件运维
(1973-), 男, 博士, 博士生导师, CCF 杰出会员, 主要研究领域为面向智能体的软件工程, 软件演化与自适应
(1996-), 男, 硕士, 主要研究领域为自适应软件, 微服务负载均衡
(1999-), 男, 硕士, 主要研究领域为自适应软件, 故障诊断技术
指挥控制信息系统(指控系统)运行在动态变化的复杂环境中且任务需求时刻变更, 亟需一种自适应决策方法以动态产生调整系统的最优策略, 从而适应环境或任务变化, 确保系统长期稳定运行. 随着指控系统自身及其运行环境的持续复杂化, 自适应决策方法需具备应对多个非预期变化的在线权衡决策能力, 以避免造成冲突的调整后果或无法及时响应未知情况. 然而, 当前指控系统多采用基于先验知识、应对单一变化的自适应决策方法, 尚无法完全满足该能力需求. 因此, 提出了一种基于并行搜索优化的指控系统自适应决策方法. 方法采用基于搜索的软件工程思想, 将自适应决策问题建模为搜索优化问题, 并采用遗传粒子群算法, 实现针对同时发生的多个变化进行在线权衡的目标. 并且, 为解决该方法在指控系统中实际应用时存在的搜索效率保障、策略择优选择问题, 分别采用并行遗传算法和后优化理论, 对决策方法实现了并行化并建立了策略多指标排序法, 以确保方法的实用性.
The command and control information system (command and control system) runs in a dynamically changing and complex environment with constantly changed mission requirements. A self-adaptation decision-making method is urgently needed to dynamically generate the optimal strategy for adjusting the system, so as to adapt to changes in the environment or missions and ensure the long-term stable operation. At present, as the command and control system itself and its operating environment continue to become more complex, self-adaptation decision-making methods need to have the online trade-off decision-making ability to deal with multiple unexpected changes, so as to avoid conflicting adjustment consequences or failure to respond to unknown situations in a timely manner. Nevertheless, the current command and control system mostly adopts self-adaptation decision-making methods based on prior knowledge and responding to single changes, which cannot fully meet this capability requirement. Therefore, this study proposes a self-adaptation decision-making method for the command and control system based on parallel search optimization. This method uses search-based software engineering ideas to model the self-adaptation decision-making problem as a search optimization problem, and uses the genetic particle swarm algorithm to achieve the goal of online weighing against multiple changes that occur at the same time. In addition, in order to solve the problems of search efficiency guarantee and strategy selection in the actual application of this method in the command and control system, this study uses parallel genetic algorithm and POST-optimization theory to parallelize the self-adaptation decision-making method and establish a strategy multi-index sorting method to ensure the practicality of the method.
指挥控制信息系统软件[
为实现该自适应能力, 美军提出了“OODA” (observe-orient-decide-act)理论, 建立了包括“观察、判断、决策和行动”4个环节的自适应过程, 以实现系统对环境变化和任务变更需求的实时响应[
首先, 由于指控系统运行在高动态环境下, 环境变化频繁发生, 且同一时刻可能同时存在多个环境变化. 考虑到指控系统本身是一个具有复杂运行机理的物理系统, 根据现实世界的规律与实践经验, 同一时刻发生的变化可能存在一定的关联关系. 这种关联关系会导致每个变化各自的调整策略极可能存在潜在冲突[
其次, 由于系统运行环境瞬息万变且指控系统内部状态和行为空间爆炸, 在系统运行前几乎无法穷举所有可能的调整策略, 也无法预测策略的实际有效性. 这种策略的不确定性及效果的不可预测性, 导致自适应决策方法仅凭预定策略无法正确应对已知变化, 更无法处理未有相关策略的未知变化. 因此, 自适应决策方法必须具备根据变化情况, 动态产生调整策略的在线决策能力.
然而, 现有指控系统中采用的自适应决策方法并不能完全满足上述两方面的能力需求. 例如, 基于规则/策略的方法, 需在系统运行前预定义自适应策略, 无法支持在线决策. 基于目标、效用函数和优化函数的决策方法, 每次仅处理单一变化, 容易产生出互相冲突的自适应策略. 虽然也存在部分研究通过定义变化间的权重关系产生折中策略, 但由于变化间的优先关系在系统运行过程中会发生演化, 因此该类研究无法保证其始终有效[
本文拟采用基于搜索的软件工程(search-based software engineering, SBSE)理论, 将自适应决策视作在调整策略组成的搜索空间中, 评价并选择最优策略的搜索优化问题, 采用搜索优化方法建立一种满足在线权衡决策需求的自适应决策方法, 从而有效应对环境变化与任务需求变更. 该类决策方法可采用多目标搜索优化技术, 在不定义变化优先级的情况下, 实现对多种变化的权衡处理, 并可动态根据非预期变化情况在线搜索产生出相应的调整策略.
然而, 在应用该方法具体解决指控系统的自适应决策问题时, 仍存在效率提升与策略选择等实际应用问题. 首先, 该方法的计算效率受搜索空间规模影响. 而指控系统对自适应过程的实时性要求较高. 因此, 必须保障该方法能够快速产生决策结果. 其次, 该类方法针对多目标进行权衡决策时, 会产生一个最优策略集合, 即前沿. 前沿内部的策略已无法再根据优化目标区分优劣性. 然而, 指控系统必须依据唯一的调整策略对系统结构、行为或参数实现准确调整. 因此, 必须保证该方法可从前沿中选择出当下最适用策略.
因此, 本文提出了一种基于并行搜索优化的指控系统自适应决策方法(self-adaptation decision-making based on parallel search optimization for command and control information system), 通过将自适应决策问题转化为搜索优化问题并设计了多目标优化算法以满足指控系统在线决策及决策权衡的需求, 同时为提升决策效率设计了基于后优化理论的策略选择方法, 能够有针对性的选择当下最适用策略. 具体包括以下要点:
1) 自适应决策问题建模. 本文分析自适应决策问题特征, 定义了该类问题的自适应策略、策略空间、目标函数、适应度函数与约束函数, 将自适应决策问题建模为搜索优化问题. 本文设计的自适应决策建模方法可以根据指控系统特征, 快速建模独特的自适应决策问题模型, 将自适应决策问题转化为搜索优化问题, 针对指控系统环境变化动态生成策略空间.
2) 基于并行的多目标优化算法. 本文结合并行遗传算法、粒子群算法等理论, 建立了基于遗传粒子群(genetic algorithm and particle swarm optimization, GAPSO) 的并行自适应决策方法, 并通过算法的并行化设计保障算法可快速产生调整策略. 通过此方法, 不仅能够针对指控系统复杂运行环境下的多个环境变化在线产生最优策略, 避免了由于仅考虑单个变化引起的策略冲突. 此外, 本文通过种群切割、引入迁移算子等方法实现了算法的并行化设计提升了决策效率.
3) 基于后优化理论的策略选择方法. 本文基于后优化理论, 针对不同决策问题在决策偏好、时效性约束等方面的不同特征, 建立了基于和谐性分析法 (elimination et choice translating reality, ELECTRE)的多指标排序法, 能够有针对性地选择当下最适用策略, 从而指导指控系统实现自适应调整.
本文第1节介绍了相关背景知识. 第2节给出了本文的研究框架, 说明了各研究工作之间的关系. 第3节则分别介绍了本文的核心研究工作, 即自适应决策问题建模、基于并行GAPSO的自适应决策方法、及基于ELECTRE的多指标排序法. 在第4节中, 本文分别采用了指控系统典型自适应场景和大规模模拟场景对本文提出的方法及相关研究方法进行了对比实验, 并对实验结果进行了分析探讨. 第5节分析了相关工作. 第6节总结了本文工作.
本节介绍基于搜索的自适应决策方法所采用的理论技术, 即基于搜索的软件工程、并行遗传算法与后优化理论.
基于搜索的软件工程的思想是通过将传统软件工程中的问题映射为基于搜索的优化问题, 通过使用启发式搜索算法, 在可行解空间中找到最优解的方法[
传统的软件工程的思想是通过针对问题设计解决算法以求得最优解, 基于搜索的软件工程是通过在可行解空间中针对问题构造适度函数以指引搜索方向, 经多次迭代得到最优解. 因此, 基于搜索的软件工程解决问题一般需要满足两个条件.
1)设计出问题解决方案表达方式(solution representation): 对所需解决问题的结果, 必须能通过相应的编码表示出来, 以构成搜索算法中的染色体, 进行相应的运算.
2)设计出相应的适应度函数(fitness function ): 对解进行评价, 比较不同解之间的优劣. 在搜索解空间内, 适应度函数可以指引搜索的方向, 寻找满足条件的区域.
由于基于搜索的软件工程解决问题的方法主要由以上两步组成, 针对任何问题, 只要能够设计出问题解的表示方式和适应度函数, 就可以应用该方法, 因此具有很强的普适性, 可以方便地应用到不同领域问题上. 另外, 针对同一问题的不同规模, 基于搜索的方法求解方式是不变的, 因此容易扩展到大规模的工程问题求解上去. 基于搜索的软件工程方法避免了传统方法的一些不足, 能在尽可能降低成本的前提下尽可能高效地自动化完成软件开发任务, 是软件工程领域中一种高效实用的新方法.
本文所要解决的问题为自适应决策问题, 自适应决策问题具体是指在系统面临一系列难以应对的环境变化时, 需要系统产生相应策略以自适应的调整行为和状态, 在这个过程中遇到的策略生成、策略权衡选择等一系列问题即为自适应决策问题. 依据上述的基于搜索的软件工程方法, 本文设计了将自适应决策问题映射为最优化问题的方法以实现获取自适应决策问题的最优解. 由于最优化问题是指通过选择一组决策变量, 在满足一系列有关的限制条件(约束)下, 使设计目标函数达到最优值. 因此, 在建模过程中同样需要明确自适应问题中的决策变量、目标函数以及约束条件等内容. 具体含义如下:
1) 决策变量是指影响目标函极值的变量, 也是优化算法搜索的对象.
2) 目标函数是指最优化问题优化的目标.
3) 约束条件是指限制决策变量取值的条件, 在数学描述中被称为约束函数, 依据限制条件不同可分为等式约束和不等式两种.
遗传算法(genetic algorithm, GA)[
随着计算机计算能力的提升和大规模并行计算框架的发展, 利用集群的计算能力提升GA的运行速度的想法促进了并行遗传算法(parallel genetic algorithm, PGA)[
目前PGA的模型可以分为主从式、粗粒度、细粒度和混合模型共4大类型. 主从式模型是指选择、交叉和变异等全局操作由主节点串行进行, 而计算由各从节点机并行执行; 粗粒度模型是适应性最强、应用最广的遗传算法并行模型, 其原理是将种群划分至多个节点并行处理; 细粒度模型相比于粗粒度模型要求子群体的划分要更加细小, 理想状态是每个节点机只有一个个体; 混合模型是指将前3种模型混合形成模型结构. 四种模型中主从模型通信代价过高, 细粒度模型划分过于细致需要占用大量计算节点, 混合模型设计较为复杂, 而粗粒度模型需要的计算节点较少且各节点能独立完成遗传进化. 因此, 本文选用了粗粒度模型作为建立并行搜索方法的基础模型. 粗粒度模型具体是通过利用了GA算法结构在种群层的并行性, 实现多个子种群的并行进化. 假设并行计算集群中计算节点的个数为
完整的基于搜索的自适应决策方法除了通过多目标优化方法产生的前沿策略集合之外, 还需要解决后优化(POST-optimization)问题[
而由多目标函数优化算法产生的前沿集合与基于搜索的自适应决策方法产生的最优方案集合高度相符. 因此, “从方案集合中选择唯一策略”的问题本质上与第2类后优化问题“从前沿中选择最优解”一致. 因此, 本文将考虑采用与第2种后优化问题相关的理论技术建立本文的方案选择机制. 为方便论述, 后文提及“后优化问题”时, 仅特别指代“第2类后优化问题”.
目前, 根据现有文献的分析, 针对后优化问题的解决方法, 即后优化方法, 可被分为以下4种. 第1种是偏好排序法, 即通过对前沿中的解根据设定的偏好进行排序, 从而获得排序后的最优解[
因此, 本文拟通过ELECTRE (elimination et choice translating reality) 方法建立一种多指标排序方法以从多个生成策略种选择出唯一策略, 该方法与其他依赖于偏好排序的方法不同, ELECTRE方法可考虑多种指标避免了完全按照偏好造成的风险, 相比于图像方法和聚类算法ELECTRE较为简单能够快速实现策略选择的任务. ELECTRE 方法是由 Bernard Roy 在 1965年提出的一种多标准决策分析(multi-criteria decision analysis, MCDA)方法. 该方法是通过建立方案间的优先次序关系从而实现方案排序[
本文的研究问题包括如何通过搜索优化技术建立自适应决策方法, 以及如何保证该决策方法可在实际指控系统中应用. 因此, 本文建立了如
Search based adaptive decision framework
基于搜索的自适应决策框架
(1) 自适应决策问题建模与搜索算法设计, 解决在线权衡决策问题
本文首先分析了自适应决策问题的本质特征并与最优化问题进行了类比, 随后定义了自适应决策问题的决策变量、目标函数和约束函数, 将自适应决策问题建模为最优化问题. 在此基础上, 本文首先采用全局搜索能力强的进化算法对空间进行初步搜索. 在经过多次迭代后, 本文挑选出精英个体, 并进一步采用收敛能力强的粒子群算法实现局部深入搜索, 获得最终结果.
(2) 基于并行GAPSO的自适应决策方法, 解决效率保障问题
在本文建立的决策算法中, 前期采用的进化算法承担了对策略空间的全局搜索任务. 因此, 提升该算法效率将有助于保障整体决策效率. 根据并行遗传算法思想, 本文建立了基于并行GAPSO (genetic algorithm and particle swarm optimization) 的自适应决策方法, 采用迁移算子划分全局搜索空间并对多个种群进行并行搜索, 达到加速算法收敛目的. 并且, 本文采用Spark并行计算框架和多线程技术两种方式实现该算法, 以对比不同实现方式对算法时间效率的影响.
(3) 基于ELECTRE的多指标排序法, 解决策略择优问题
本文基于排序法中的ELECTRE方法建立了多指标排序法, 以从搜索结果中选择出唯一策略. 在设计排序指标时, 本文除了量化建模指挥员偏好外, 将充分考虑不同战场环境下的决策需求, 建立了作战偏好、资源态势、任务时效性等指控系统关切的特殊指标, 通过开展和谐性与非和谐性检验, 逐步精化搜索结果, 达到选择最优策略的目标.
根据上文将自适应问题映射为最优化问题的基本理论, 本节对其具体方法进行描述. 在自适应问题中影响其调整结果的变量为自适应策略, 因此, 本文将自适应策略作为自适应问题的决策变量. 在指控系统中自适应策略包含了大量系统信息及系统行为, 为更好的描述指控系统的自适应策略本文将自适应策略的组成部分定义为可变点(variable point, vp), 即在自适应调整过程中对调整结果可以产生影响的可调整对象, 这些可调整对象不仅包含指控系统资源(如计算节点CPU、内存的利用率等)、指控系统的组织结构(如组成作战单元数量、部署位置等)、组成单元的行为或参数(如系统组成单元的功能等), 同时也包括指控系统运行中可调整的属性(如网络带宽等).
由于可变点的取值情况不同, 因此可变点可被划分为离散可变点、连续可变点和量化可变点.
• 离散可变点是指可变的取值为离散数值. 如分布式计算节点只能以离散数值描述.
• 连续可变点是指可变点的取值时连续的. 例如内存利用率可以用[0, 100%]的连续数值进行描述.
• 量化可变点是指可变点中有些没有具体的数字化取值, 因此需要对这些可变点进行数字量化. 例如可以将3种不同的系统行为以{1, 2, 3}这3个数值代表, 实现可变点量化.
由于决策变量是指自适应策略, 因此将这些可变点组合起来就形成了自适应策略集合即决策变量取值, 在基于搜索的软件工程中也被称为解空间. 如
Feasible solution space of adaptive decision problem
自适应决策问题的可行解空间
上述方式建立的解空间是通过在线分析可变点(即系统状态及行为)产生的, 不存在预定的关系, 同时由于解空间中的每个点均是独立的, 因此不同策略之间不存在冲突. 这种方式可以有效避免策略冲突, 动态选择出最优的自适应策略以实现在线决策.
(1)目标函数
在指控系统中自适应决策问题的优化目标就是使需要自适应调整的系统能够适应软件变化, 以达到期望的系统目标. 在本文中软件变化具体是指由于环境变化和战场需求变更等因素引起的系统内部变化, 这些变化导致了系统无法正常稳定运行. 本文以期望调整后稳定的系统目标作为目标函数, 并将其分为直接相关函数和间接相关函数两部分.
首先, 需要明确在软件变化发生后期望的系统目标. 系统目标可以由两种方式获得. 一个是通过指控领域专家经验获取; 另一个是通过多次模拟战场环境变化和需求变更等场景进行多次实验, 观察受到影响的系统资源和行为, 受到影响的部分即为与此变化直接相关的目标函数. 例如, 在“负载均衡”这个场景下可能会发生“节点负载超载”变化, 为获取这个变化的直接目标函数, 需要重复进行实验, 通过分析系统运行日志可以发现“系统响应时间”受到了影响. 因此“响应时间”就是该变化的一个直接相关目标函数.
其次, 由于多种环境变化和需求之间可能存在联系. 因此, 不能简单考虑直接相关的目标函数, 通过对多种软件变化之间进行分析, 可明确相关的可变点信息. 受到这些可变点取值变化影响的系统目标, 则称为该变化的间接相关目标函数. 通过在自适应决策问题中引入间接目标函数, 可以在一定程度上避免由于软件变化之间的联系引起的反复调整等一系列系统振荡现象. 例如, 在“负载均衡”场景下, 与“节点负载超载”变化相关的可变点是节点的任务分配量, 同时这个可变点影响着系统的运行开销. 虽然系统运行开销暂时并未受到“节点负载超载”的影响, 但从长远的角度上, 将其纳入间接目标函数可避免由于调整不当引起的“系统运行开销过大”等软件变化.
由于指控系统的运行环境复杂, 同一时刻可能同时存在多个环境变化和任务需求变更的发生, 自适应决策需要同时考虑多种变化. 因此, 需要将这些变化的直接相关目标函数和间接相关目标函数合并去重, 作为自适应决策的整体目标函数且这些目标函数之间不用定义任何的优先关系, 并将通过量化公式的形式定义. 具体公式内容需要根据不同系统具体的决策问题需要而建立.
(2)约束函数
在自适应决策问题中, 约束函数仍旧是传统优化问题中的等式或不等式约束形式, 主要用于对可变点的取值范围进行限制, 但其产生的来源则包括如下两种.
• 可变点约束主要源于自适应调整系统运行时上下文对可变点取值的特殊要求. 例如, “集群计算节点数量”这个可变点的取值范围本身是明确的, 但如果系统管理人员临时规定了计算节点的可用数量, 则这个可变点的取值就将受到影响.
• 功能约束则源于用户对系统的功能期望. 自适应策略不仅要保证决策问题中目标函数的最优, 也要保证在基于该策略调整系统后, 系统必须对外提供的服务和服务水平不能受到影响. 也就是说, 该类约束函数主要用于保证可变点的取值不会影响系统为用户提供必备的对外功能.
根据上一节所述方法本文实现了在指控系统下的自适应决策问题建模. 如何从模型确定的可行解空间, 也就是可行自适应策略空间中选择最优自适应策略是本节将解答的问题.
目前, 工业界采用最多的多目标优化算法为遗传算法(例如, nondominated sorting genetic algorithm-II, NSGA-II)与群体智能算法(例如, multi-objective particle swarm optimization, MOPSO)[
因此, 本文提出了一种基于遗传算法的并行遗传粒子群(genetic algorithm and particle swarm optimization, GAPSO)算法以搜索最优自适应策略并加快演化策略的生成速度, 提升搜索效率. 该算法主要由两部分组成, 分别是用于算法前期迭代的多目标优化算法NSGA-II, 用于算法后期精确搜索的NSGA-II算法. NSGA-II算法时间开销较小, 故用于实现算法前期对策略空间的全面覆盖搜索, 避免算法陷入局部最优. 因为可行自适应策略空间中的点是离散分布的, 所以在算法执行后期, 采用离散的MOPSO算法以对局部精英种群进行深入搜索, 缩短算法收敛时间. 此外, 为进一步提高搜索效率, 本文结合粗粒度并行遗传算法思想, 通过将大种群切分为若干子种群实现并行进化, 并通过引入迁移算子实现子种群间个体迁移, 保障各子种群的多样性. 算法流程如算法1所示.
算法
Input: 目标函数、约束函数、决策变量及算法参数, 迁移代数
Output: 前沿集合.
1. NSGA-II初始化. 在该步骤中获得算法参数, 产生算法运算所需要的初始群体.
2. 切分初始种群为
3. 对于每一个子种群
4. 对子种群中的个体进行交叉、变异操作, 计算个体的适应度值.
5. 由3, 4两步的中间种群组合得到下一代种群, 并对个体按照适应度值进行排序, 保留固定种群大小数目个体, 抛弃多余个体.
6. 获取当前迭代次数. 若迭代次数为
7. 判断是否达到NSGA-II的终止条件, 若满足, 则转步骤8; 否则, 转步骤3.
8. 确定种群大小、维度、每个维度上的取值及微粒的初始位置和初始速度, 微粒在每个维度上位置和速度的上下界限值.
9. 以前沿策略为初始粒子群, 按照适应度排序及拥挤度排序结果抛弃多余微粒.
10. 计算每一个微粒的适应度值, 进行非支配排序, 记录个体最优位置
11. 判断迭代次数, 决定是否结束算法, 若达到算法终止条件, 则将最优集合进行非支配排序, 输出前沿集合
如算法1所示, 并行GAPSO算法过程如下.
(1) 初始化. 在该步骤中确定NSGA-II算法和MOPSO算法执行所需要的群体特征. 主要为种群规模、维度、各维度上取值约束、粒子的初始化信息及粒子在各维度上位置和速度的取值约束.
(2) 子种群进化. 将初始种群划分为若干子种群. 每个子种群根据适应度函数计算每个个体的适应度值. 对个体进行非支配排序, 拥挤度计算, 并进行交叉、变异操作, 更新个体的适应度值. 不同子种群通过迁移算子交换优势个体, 不断进化迭代.
(3) 深度寻优. 达到NSGA-II的终止条件后, 确定种群大小、维度、每个维度上的取值及微粒的初始位置和初始速度, 微粒在每个维度上位置和速度的上下界限值以前沿策略为初始粒子群, 按照适应度排序及拥挤度排序结果抛弃多余微粒. 计算每一个微粒的适应度值, 进行非支配排序, 计算并记录每个个体的最优位置
(4) 算法终止. 判断迭代次数, 决定是否结束算法, 若达到算法终止条件, 则将最优集合进行非支配排序, 输出前沿.
结合上述算法流程, 给出本文GAPSO算法设计细节, 如
并行GAPSO算法设计存在着一定的挑战和难点. 首先, 由于遗传算法一般采用二进制编码方法对个体进行编码该编码方式易于实现变异等进化操作. 然而, 自适应决策问题的决策变量取值被离散化了, 如果采用二进制编码, 则容易产生无效取值, 且由于决策变量的取值随时可能会发生变化, 因此针对自适应决策变量的编码方式必须支持决策变量取值的灵活调整. 其次, 本文将在算法前期迭代将切分出若干子种群实现并行进化, 然而如果种群切分过大会导致收敛效率过低, 种群切分过小又会导致陷入局部最优解, 需要考虑在结果质量和收敛速度间寻找平衡, 可以接受的时间范围内尽可能的提供较优的结果. 为解决上述问题, 在算法中进行了相关的设计如
Algorithm detail design
算法细节设计
内容 | 说明 | 算法 | 本文设计 | |
NSGA-II | 离散MOPSO | |||
个体编码 | 表征个体的方式 | √ | √ | 见“(1)编码方法” |
初始种群 | 种群的初始化生成方式 | √ | 随机生成方式 | |
在GA最优解附近随机生成 | ||||
√ | 以NSGA-II前沿为初始种群 | |||
适应度函数 | 评价个体优劣性的标准 | √ | 将目标函数作为适应度函数 | |
√ | Pareto支配关系和拥挤度 | |||
选择算子 | 规定保留父代种群哪些个体进入
|
采用线性排序法选择个体, 并采用精英选择法直接保留最优个体 | ||
√ | 带有精英策略的选择算子 | |||
交叉算子 | 规定个体间如何交互部分基因的操作 | √ | 单点交叉即交换点位 |
|
交叉率 | 规定采用交叉算子的个体规模 | √ | 0.6至1设置得稍高以推进搜索进程 | |
变异算子 | 规定修改个体哪些基因位取值的操作 | √ | 采用单点变异随机选择一个基因位, 并采用均匀变异随机选择一个取值代替原值 | |
变异概率 | 规定采用变异算子的个体规模 | √ | 0.005至0.1, 实际中可设置较高, 以扩大搜索范围 | |
速度更新操作 | 决定个体飞向最优解解的步长和方向 | √ | 将标准速度更新操作直接应用于离散空间 | |
位置更新操作 | 记录个体目前的取值情况 | √ | 将标准位置更新操作直接应用于离散空间, 对个体位置进行近似取整 | |
学习因子 | 调节个体向最优解学习的步长 | √ | 采用通用取值2 | |
随机函数 | 增加搜索随机性 | √ | 取值范围[0, 1]二者相互独立 | |
非支配集构造 | 依据多个目标函数选出每代较优解集 | √ | 快速非支配排序法 | |
外部存档维护 | 存放每次迭代后获得的非支配解 | √ | 聚集密度法, 即采用拥挤距离评价个体, 定期剪辑非支配集 | |
个体最优选取 | 记录个体所经历过的最好解 | 采用标准个体最优值更新方式 | ||
√ | 对比历史最优位置与新位置非支配关系 | |||
全局最优选取 | 从所有个体最优值中选择最优的解 | 采用标准全局最优选择方式 | ||
√ | 见“(2)群体最优选择” | |||
惯性权重 | 保持个体运动惯性 | √ | 见“(3)惯性权重设计” | |
终止条件 | 终止算法的条件 | √ | √ | 见“(4)终止条件设计” |
迁移算子 | 定义子种群个体交换规则 | √ | 见“(5)迁移算子设计” |
(1)编码方法
正在运行的系统中, 决策变量取值发生变化的可能性较大. 因此, 自适应决策变量在编码层面需要对变量取值的灵活调整提供支持. 本文特别提出了一种数组编码方法, 对决策变量, 即GA与PSO算法中的个体进行编码. 如
(2)群体最优选择
对于MOPSO, 本文使用理想解法(technique for order preference by similarity to an ideal Solution, TOPSIS)用于群体最优的选取. 该方法在初次迭代时会预选选取每个目标函数的最优极值和最劣极值, 并以此作为理想最优值和理想最劣值. 该方法通过计算各个个体最优与理想最优值和理想最劣值之间的距离, 将离理想最优值最近且离理想最劣值最远的个体最优值为群体最优值. 此外, 通过比较最新的最优值与历史群体最优值的非支配排序关系, 以确定最新群体最优值. 该方法能够有效避免随机选择方法不准确性带来的影响及聚集密度等方法的计算复杂度等问题.
Chromosome coding process based on array
基于数组的染色体编码过程
(3)惯性权重设计
对于PSO算法的惯性权重, 本文根据“随着算法迭代的进行, 惯性权重进行减小, 有助于保证算法前期迭代的全局搜索和后期迭代的局部收敛能力”的研究结论[
其中,
(4)终止条件设计
考虑到自适应决策问题需要尽快获得决策结果, 且一般实际工程问题并不特别要求获得真正意义上的最优解, 因此本文采用规定迭代次数, 达到时即终止算法.
当迭代次数达到规定的数值便停止迭代, 终止算法, 迭代次数的取值则是依据专家经验及系统历史情况确定. 本文的终止条件兼顾了时间开销和决策结果, 在实际场景中更具应用价值.
(5)迁移算子设计
本文采用了并行遗传算法的思想, 引入迁移算子, 用于实现各个子种群中个体的迁移. 迁移算子主要作用是控制各个子种群间个体的迁移, 如式(2)所示.
式(2)中种群迁移率指子种群之间迁入新个体占原子种群的比重; 迁移周期指子种群之间进行个体迁移的时间间隔; 迁移策略是指子种群之间个体迁移策略, 一般包括如何选择向外迁移的个体、种群接收个体后的置换策略以及迁出个体的保留策略; 迁移拓扑是指种群之间个体的迁移路径.
本文遗传算子设置如
引入迁移算子后, GAPSO算法将划分出若干子种群, 通过采用多线程的技术并行搜索方案空间, 并通过迁移算子实现个体迁移和信息交互, 最终获得最优解集, 实现并行搜索提高搜索效率.
针对指控系统策略的战场空间大、不确定因素多, 情况可变性强的特点, 在战时决策中既需要提高决策效率, 又要确保决策的科学性. 因此, 本文基于ELECTRE (elimination et choice translating reality) 方法, 量化指挥员偏好、调整开销和调整时间等与指控系统相关的评价指标, 然后结合和谐性和非和谐性的概念, 设定了两种检验方法, 实现对前沿自适应策略集合的评估和排序.
Design of transfer operator
迁移算子设计
在和谐性检验方面, 本文量化了用户偏好和调整开销的评价指标, 在此基础上, 对比前沿调整策略的质量, 从而解决由于不同目标函数产生的结果不同导致的调整策略不唯一的问题, 进一步优化选择最佳策略.
其中, 在战场环境下的用户偏好主要指的是指挥偏好, 是对不同目标函数的设置的权重值, 通常在策略生成过程中进行; 在此基础上, 通过加权计算出方案
调整开销表示自适应决策机制执行特定调整方案的演化重构开销. 包含资源消耗
在上述两种评价指标的基础上, 本文结合自适应系统决策经验, 通过对不同的评价指标设定权重值, 计算策略总得分. 其中, 本文考虑指控系统的自适应决策需求并通过咨询专家经验, 认为在战场环境下策略选择过程中, 用户偏好对决策结果的影响力应大于调整开销, 为此本文将用户偏好的比重设置为0.7, 调整开销比重设置为0.3, 如公式(3)所示可计算最终的总得分
在非和谐性检验方面, 本文设定了用户对评估指标和目标函数所能够接受的阈值, 其中包括对用户偏好、调整开销以及目标函数结果3个部分. 通过将阈值作为调整策略是否非和谐的衡量依据, 筛选出所有得分都在合理阈值之内策略, 并进一步通过和谐性检验方法选择最佳策略, 能够满足用户偏好, 有效提高调整策略的合理性和适用性.
在上述两个部分的策略评估方法的基础上, 本文建立了多指标排序法的主要流程如算法2所示. 该方法首先获取可变节点的状态信息, 计算出各调整策略的总得分, 然后通过和谐性检验和非和谐性检验依次筛选, 最终选择出唯一的最佳调整策略.
因此, 本文所提出的多指标排序方法能够适应较为复杂的战场环境, 针对多目标函数的自适应决策问题, 综合分析多种影响因素对调整策略的影响, 并对不同的调整策略进行量化评分, 从而选择出唯一策略. 该方法结合了用户指控偏好, 并利用专家经验处理实际战场指控的需求, 能够有效弥补人工参与的局限性, 有利于提高自适应决策结果的有效性和合理性.
本节介绍了本文对基于并行搜索的自适应决策方法在军事指挥控制系统领域中开展的实验及结果分析工作. 首先介绍实验的具体方法, 然后给出实验的实际结果并进行分析讨论.
为验证方法的有效性, 本文尝试设计了3个实验对其进行验证.
算法
Input: 前沿策略集; 目标的权重; 可变点调整开销; 和谐性指标阈值; 目标函数阈值;
Output: 最优方案
1. for
2. 计算用户偏好得分
3. 计算调整开销得分
4. 根据式(3)计算方案总得分
5. end
6. sort(
7. for
8. for
9. if 第
10. then 剔除此方案;
11. end
12. for
13. if
14. then 剔除此方案;
15. end
16. end
17. Print
本文模拟了军事系统中的搜索子系统作为案例系统, 并在系统中选择典型场景, 测试方法的策略效果, 以此评价方法效果. 具体实验设计如下.
自适应控制平台. 为更好的实现对案例系统的自适应调整, 本文使用了本团队开发的自适应控制平台, 平台由开发层、运行层和基础设施层组成. 其中开发层提供了用于自适应演化逻辑设计阶段的系统设计开发工具集; 运行层提供了用于自适应演化机制运行阶段的基于Agent的演化运行支持平台, 由主控制平台和从平台两种类型组成; 基础设施层提供了支持软件正常运行所需的主流软硬件环境. 结构如
首先, 在开发层平台会通过Agent包装工具将需要进行自适应演化的软件单元封装为Agent并提供对外的调用接口. 其次会通过集成规则设计工具生成初步的演化规则, 在本文的方法中对应的是自适应决策问题的可行解空间. 然后, 通过演化约束规则设计工具形成演化约束规则即本文中的约束函数, 并通过演化约束规则检查工具进行验证. 在运行层, 分为主控制平台与平台两种类型. 其中, 从平台负责实现对软件系统正常运行的支持, 主要负责Agent的维护以及通信等功能. 主控制平台除需要支持软件系统的正常运行外, 同时还需负责提供软件动态集成演化过程中所需的各项服务. 其核心组件为演化控制引擎, 演化控制引擎会解析并向各从平台分发集成演化规则, 实现对Agent自身结构或Agent间协作关系的调整, 从而实现软件的动态演化.
测试系统选择. 在指挥控制系统中对于战场环境的信息收集能力和处理能力有着较高的需求, 同时在具有较大的动态性和不确定性的战场环境下, 数据信息也呈现出复杂多变的特征. 因此, 本文以信息搜集入手设计了一个搜索子系统, 通过模拟复杂动态环境变化以验证本方法在指控领域的有效性. 考虑到动态的战场环境, 本文设计的搜索子系统将7×24不断运行, 并通过关闭运行节点、负载调整等方式以模拟动态场景. 在这种环境下该系统为保证稳定运行将面临3方面的特殊需求. 具体而言, 首先其面临着节点毁伤、任务调整等多种突发性情况, 对于这些情况系统需要保证其稳定可靠性, 需要进行在线进行演化调整. 其次, 在调整过程中, 由于每个节点的物理信息是不同的(CPU、内存等), 且服务实例需求不同, 形成的调整方案空间是庞大的. 例如, 现有节点上的8个相关服务实例需要进行调整, 此时, 有10个节点可供调整, 产生的方案空间将达到一亿的规模. 并且, 由于运行环境的复杂性, 是无法准确预测到系统的变化情况, 仅依靠人力进行调整是不可行的, 因此需要自主策略生成. 最后, 是关于策略权衡问题, 当系统发生多种变化时, 可能会产生多个对同一资源进行调度的策略进而产生新的问题出现, 因此需要针对这种情况对产生的策略进行权衡选择出合理的调整策略. 本文提出的方法能够解决在此案例系统下由于动态环境引起的突发性问题, 对其进行在线调整, 产生合理的调整策略.
Agent-based adaptive software control framework
基于Agent的自适应软件控制框架
测试系统概述. 本文设计的搜索子系统包含了一个区域的组成信息、设备信息以及环境信息, 结构如
本文实验所设计的搜索子系统包含13个节点, 每个节点中包含若干数据处理实例和感知监控实例, 13个节点的配置分为3类, 主要负责信息维护的节点, 主要负责信息通信节点服务以及主要负责信息分析的节点. 其中信息维护节点共有7个, 编号为node1–node7. 信息通信节点共有3个, 编号为node8至node10. 信息分析节点共有3个, 编号为node11–node13, 具体节点配置信息如
测试场景概述. 本实验选择了在军事环境中典型的毁伤替换场景作为测试场景. 毁伤替换场景是指在搜索子系统在运行的过程中, 某一个或者某些服务的实例可能由于某种原因而异常终止运行, 需要重新部署毁伤节点上运行的服务实例并通过寻找系统中可用的其他节点来替代已毁伤的节点, 继续执行该节点的任务, 以保证系统的正常运行. 本文在该场景下进行实验以验证方法, 具体流程如下, 本文在该过程采用了基于并行搜索的自适应决策方法将自适应决策过程映射为多目标优化的问题, 进行决策处理. 针对毁伤替换场景, 主要包含4个步骤.
(1) 通过分析节点特点以及领域特征建立目标函数, 以选择出重新部署的节点;
(2) 为毁伤节点寻找替换节点进行接替;
(3) 由于选择进行替换的节点在重新部署后可能会产生诸多的问题, 也就是上文提到的策略可能会发生冲突, 为此还需对系统负载进行监控调整, 以实现权衡决策. 具体通过对毁伤服务重新部署并密切监控搜索子系统整体状态, 若负载较重, 实施负载均衡措施;
(4)重新计算负载, 调整部署.
Search subsystem architecture diagram
搜索子系统体系结构图
Node configuration information table
节点配置信息表
节点类别 | CPU | 内存 | 硬盘 | 网络 |
信息维护节点
|
型号:Intel(R)Core(TM) i3-2120
|
类型: DDR2
|
类型: RAID0
|
丢包率: 0.42
|
信息通信节点
|
型号: Intel(R)Core(TM) i3-2120
|
类型: DDR3
|
类型: RAID0
|
丢包率: 0.12
|
信息分析节点
|
型号: Intel(R)Core(TM) i4-2120
|
类型: DDR3
|
类型: RAID0
|
丢包率: 0.12
|
测试指标概述. 为了更好的衡量本方法在指控领域场景下效果, 本实验建立了两个度量指标具体如下.
• 指标1: 每秒响应请求数. 系统在单位时间内的响应请求数量, 通过监听器可以获得秒钟内成果响应请求的数量. 每秒响应请求数通常是用作系统性能测试的度量标准之一, 在本实验中将其作为系统是否正常运行, 以及策略质量的标准. 如果系统的每秒响应请求数在正常范围内证明系统在正常运行, 并且通过可以通过每秒响应请求数量的变化观察策略质量的情况.
• 指标2: 节点负载量. 在本系统内节点的负载主要表现为CPU负载率、内存占用率、磁盘占用率, 为对本文方法产生的策略质量进行评估, 本文设计了节点负载量进行量化, 为上述3种指标设置权重以综合判断节点负载情况, 具体为CPU负载率的比重为0.4, 内存占用率比重为0.3, 磁盘占用率为0.3.
本文通过模拟大规模场景以及极端环境进行了方法的性能及健壮性测试, 通过设计大规模计算节点以模拟未来向大规模方向发展的战场趋势, 通过测试大规模环境下的算法响应时间以验证算法的性能. 其次为验证本方法在极端环境是否依然有效, 本实验通过改变在大规模计算节点的毁伤比例观察策略效果以验证本方法的健壮性.
测试环境设计. 本文设计模拟了一个大规模场景进行毁伤测试, 模拟了4 700个虚拟节点, 每个节点中包含一个感知监控服务以及一个数据处理服务, 实验环境如
Experimental computer information
实验计算机信息
环境 | 参数 | 值 |
物理机环境 | 计算机型号 | OptiPlex 7050 |
处理器 | Intel 酷睿i5 7500 3.4 GHz×4 | |
内存 | 8 GB | |
硬盘 | 1 TB | |
虚拟机环境 | 虚拟机软件 | VMware® Workstation 15 Pro |
内存 | 3 GB | |
处理器核数 | 2 | |
硬盘 | 50 GB |
测试指标概述. 为更好的对本方法在毁伤接替场景下进行评价, 本文建立两个度量指标具体如下.
• 指标1: 算法响应时间. 自适应决策算法响应时间的长短可以在一定程度上反应算法的优劣. 在实际测试中, 记录自适应决策算法开始决策的时间为
• 指标2: 策略调整时间. 策略调整时间是指自适应决策方法产生的策略从策略下发开始到系统调整完成的时间, 例如有一调整策略发出, 此时记录的时间为
本文选择将基于并行搜索的自适应决策方法与目前自适应领域中常用的自适应决策方法进行比较, 从基于搜索的自适应决策方法以及其他军事指控的自适应决策方法层面进行类别划分, 选择了包括Coker团队提出的基于决策树形式的复合自适应决策方法[
对比方法选择. 选取上述方法的主要原因总结如下.
• 在基于搜索的方法中选取了Coker团队提出的基于决策树形式的复合自适应决策方法, 该方法是目前唯一相关的基于搜索的软件工程方法与自适应决策相结合的方法, 主要考虑软件变化之间的关系且存在动态优先级变化的特点, 采用静态离线的方式实现基础的策略生成. 因此, 本文选择该复合自适应决策方法与本文的并行搜索方法进行对比.
• 在指控领域下对比方法选择了中国电科28所金欣团队提出的基于规则的方法以及来自空军工程大学焦志强团队提出的基于效用的方法. 其原因是在指控领域种应用最广泛的自适应方法即为基于规则、基于效用等方法, 这些方法经过多年研究证实了其在指控领域的适用性. 其次, 这两种方法的研究工作来自于中国电科28研究所以及空军工程大学, 其研究背景与指控领域有着很高的相关性, 能与本文提出的方法形成更可靠、更有效的对比. 具体来说, 基于规则的自适应决策方法是依据统外部环境发生变化, 从已有的专家知识库和规则库选择合适策略做出决策, 因其简单高效的运行效率、较强的可解释性等优势成目前在指控系统应用最广泛的方法, 因此本文选取基于规则的自适应决策方法进行对比以测试本文方法在执行效率上是否能优于该经典方法. 基于规则的方法的静态性使得策略最优化问题上效果不佳, 而基于效用的自适应决策方法, 根据对一定客观现实的主观判断结构把专家意见和分析者的客观判断结果直接而有效地结合从而定义效用, 依据效用值的大小选择最优决策以实现系统自适应. 因此, 本文通过对比基于效用的方法以测试本文方法在策略寻优上的效果.
测试环境设计. 为了确保本文方法在军事指控领域存在实际的应用价值, 本文选择将对比实验的运行环境依照上述问题一中所采用的搜索子系统的测试环境进行配置, 有效验证了本文方法在军事指控领域的可用性. 同时, 利用同样的测试环境进行实验, 可以解决由于不同测试环境导致的对比实验结果存在误差的问题, 有利于确保实验结果的可靠性.
测试指标概述. 在此基础上, 本文准备了策略效率和策略效果两类对比测试, 模拟上述方法的在具体场景下的应用情况, 旨在测试评估各类方法的有效性和优劣性. 同时, 为了更好的量化实验效果, 本文选取了决策过程耗时和策略质量值两种评估指标, 分别对方法的效率和效果进行测试.
• 指标1: 决策过程耗时. 从自适应决策方法从开始执行到完成的完整自适应决策过程的耗时.
• 指标2: 策略质量值. 调整方案在可行解空间中所存在的位置坐标距离理想点的距离.
其中, 为了对比决策方法的效率, 本文拟计算自适应决策过程的耗时. 在实际测试中, 在决策方法执行前后进行时间日志输出处理, 记录自适应决策算法开始决策的时间为
为对比决策方法的效果, 本文拟分析决策方法产生的策略的优劣性. 当前多数策略评估方法都采用由Hwang和Yoon提出的TOPSIS[
在毁伤替换场景中, 首先需要根据节点信息以及环境特点等因素将服务实例重新部署过程映射为多目标优化过程, 根据结果将毁伤的实例重新部署到选择的节点上, 由于各个节点的性能不同, 重新部署的服务可能会造成节点负载过重的问题, 因此需要对部署后的实例进行负载进行调整以使系统达到更佳的状态. 具体实验过程及结果分析如下.
(1)将自适应决策过程映射为多目标优化问题
在毁伤替换场景中, 影响系统选择替换节点的因素主要包括3方面, 节点本身的底层环境信息、节点之间的交互性以及军事系统的领域特点等, 需要综合考虑上述因素选择替换节点, 建立目标函数来搜索最优的可替换节点. 具体考虑的指标如下:
• 节点的底层环境信息, 即节点的CPU、内存、磁盘的使用情况和可用情况以及总的能力. 这些信息是保证节点可以正常执行任务的必要条件.
• 节点之间的通讯能力. 对于军事信息系统来说, 其运行环境的复杂性和高实时性的要求使得系统内部的节点之间需要经常进行交互来保证系统的正常运行, 因此, 节点之间的通讯能力对于节点正常的执行任务也显得尤为重要.
• 节点的可靠性和安全性. 由于军事领域中的军事信息系统的特殊性, 其数据和节点需要高度的保密机制和安全机制也是不可缺少的考虑因素.
针对上述3种因素, 本文在毁伤替换的搜索过程中建立了CPU、内存、磁盘、网络及安全5种目标函数, 如下.
如公式(4)所示
如公式(5)所示
如公式(6)所示
如公式(7)
如公式(8)
(2)毁伤节点实例重新部署决策
为模拟毁伤接替场景, 本文关闭了搜索子系统中的节点node7以模拟节点毁伤, 该节点共部署实例8个, 包含数据处理服务实例3个, 实例编号为I0、I1、I2, 数据检索实例3个, 实例编号为I3、I4、I5, 以及感知监控服务实例2个, 实例编号为I6、I7.
该节点毁伤之后, 感知机制无法获取该节点信息, 判断该节点毁伤并发布“毁伤替换”事件. 系统收到“毁伤替换”事件及相关信息, 触发决策行为. 此时, 为了保障搜索子系统的搜索结果的实时性, 自适应决策需要在其他节点上重新部署毁伤节点上的服务实例. 自适应决策根据其他节点状态, 考虑节点整体的资源利用率, 依次为毁伤节点上的服务实例寻找部署节点, 根据目标函数计算得到各节点在CPU、内存、磁盘、网络及安全5个维度上的得分, 计算得分片段如
通过计算得出了实例重新部署在各个节点中的得分, 由于I0、I1、I2为数据处理服务实例对CPU及内存的需求更为迫切, 因此决定将其部署在node12节点上. I3、I4、I5为数据检索服务对内存以及磁盘需求较高, 因此决定将其部署在node13节点上, I6、I7为感知监控服务实例, 对网络和安全需求较高, 因此决定将其部署在node9节点上.
(3)部署节点负载均衡调整决策
由于计算节点性能各不相同, 可部署的实例种类及数量不尽相同. 考虑到节点负载能力有限, 若感知机制监控到当前系统有负载较重的趋势, 自适应决策将触发负载均衡重新规划部署方案.
在进行负载均衡调整之前, 需要考虑节点利用率以及服务运行效率这些与负载均衡相关的数据, 建立目标函数来搜索最优的负载调整方案. 具体目标函数建立如下.
节点利用率得分
其中,
服务运行效率
其中,
Example of service scoring fragments at each node
服务在各个节点得分片段示例
实例名称 | 部署节点 | CPU得分 | 内存得分 | 磁盘得分 | 网络得分 | 安全得分 |
I0 | node1 | 0.61 | 6.21 | 5.10 | 3.21 | 16400 |
node2 | 0.71 | 6.30 | 4.97 | 4.32 | 24100 | |
node3 | 0.63 | 5.94 | 4.13 | 5.41 | 18400 | |
… | … | … | … | … | … | |
node12 | 0.74 | 6.40 | 4.06 | 8.87 | 16500 | |
node13 | 0.65 | 6.31 | 5.76 | 8.39 | 36000 | |
I1 | node1 | 0.65 | 6.34 | 5.12 | 4.21 | 16400 |
node2 | 0.73 | 6.36 | 5.06 | 4.66 | 24100 | |
node3 | 0.65 | 6.13 | 4.53 | 5.55 | 18400 | |
… | … | … | … | … | … | |
node12 | 0.79 | 6.64 | 4.12 | 8.35 | 16500 | |
node13 | 0.73 | 6.40 | 5.15 | 7.87 | 36000 | |
… | … | … | … | … | … | … |
I7 | node1 | 0.54 | 6.24 | 5.54 | 4.65 | 16400 |
node2 | 0.65 | 6.35 | 5.13 | 5.14 | 24100 | |
node3 | 0.61 | 5.92 | 4.67 | 6.21 | 18400 | |
… | … | … | … | … | … | |
node12 | 0.77 | 6.41 | 4.27 | 8.12 | 16500 | |
node13 | 0.74 | 6.32 | 6.74 | 7.62 | 36000 |
随后, 自适应决策方法根据目标函数, 计算搜索子系统在剩余12个节点上的最佳部署策略. 若12个节点暂时无法满足搜索子系统的资源需求, 系统将根据选择减少一些次要服务的实例数量甚至关闭一些次要服务, 以保证主要搜索任务的进行; 最后, 产生适合调整部署的策略集合. 经过自适应决策方法得出了在6个节点内调整的较优策略, 如
(4)基于后优化理论的负载均衡策略选择
自适应机制在执行调整策略时, 必须依据唯一的策略方案对系统结构和行为作出调整. 因此, 完整的自适应决策方法还需要在上述方法产生的前沿策略集合的基础上, 根据不同决策环境下的决策需求与选择指标, 结合作战偏好、资源态势等指标进行评估排序, 产生最优的唯一调整策略. 具体评估计算方法如下.
Optimal instance adjustment strategy
较优实例调整策略
部署策略 | Node2 | Node4 | Node8 | Node9 | Node12 | Node13 | 节点利用率得分 | 服务运行效率得分 |
策略1 | I2 | I1 | I3、I5 | I6 | I0、I7 | I4 | 1.3334 | 0.8857 |
策略2 | I3 | I1 | I2、I5 | I6 | I0、I7 | I4 | 1.3283 | 0.9705 |
用户偏好得分
调整开销得分
部署策略总得分
以本次场景验证实验为例, 在上述策略集合中, 假设节点资源有限, 应该较多地考虑节点资源利用率, 策略1的得分情况略微高于策略2, 但若想更好地提供服务, 策略2显著优于策略1. 因此, 考虑到上述两种策略在资源利用率指标上差距不大, 本文将服务运行效率的用户偏好权重设置为0.7, 将节点利用率的用户偏好权重设置为0.3, 计算不同策略的用户偏好得分. 然后, 将每个服务实例的调整行为时间开销设置为1, 策略1调整了5个服务实例,
Strategy evaluation calculation table
策略评估计算表
部署策略 | 节点利用率得分 | 服务运行效率得分 | 用户偏好得分 | 调整开销 | 开销得分 | 总得分 |
策略1 | 1.3334 | 0.8857 | 1.02001 | 5 | 0.25 | 0.789007 |
策略2 | 1.3283 | 0.9705 | 1.07784 | 5 | 0.25 | 0.829488 |
因此, 根据总得分, 本文选取了服务质量整体表现更为优秀的策略2作为系统部署调整的策略.
为更好的说明本方法能够保证系统正常平稳运行, 本实验进行每秒请求响应数量的测试, 通过向毁伤节点中的3种类型的服务发送大量请求观察每秒请求响应数量, 如果每秒请求数量保持在正常范围内则证明系统处于平稳运行状态. 实验结果如
Changes in the number of requests and responses per second
每秒请求响应数量变化图
从测试结果可以看出, 在自适应决策过程开始的一段时间内请求响应数量仅保持在个位数, 这是由于算法需要一定的执行时间, 而且将毁伤节点上的实例重新部署到其他节点上并进行调整需要一定的时间. 这个时间从图中可以看出在7–8 s间, 请求响应数量恢复正常范围内并趋于稳定, 这是有由于毁伤节点上的实例调整部署完毕, 系统恢复平稳运行状态, 这个时间间隔维持在了10 s以内, 能够满足指控领域的需求, 因此方法能够有效进行自适应调整.
同时为验证本方法在进行策略调整时最终产生的策略是有效的, 本文对进行调整的节点进行了节点负载量监控, 主要监控了参与调整的node2、node4、node8、node9、node12以及node13这6个节点的节点负载量, 实验结果如
Node load change graph
节点负载量变化图
从测试结果可以看出, 策略调整之初由于将毁伤节点集中部署在了node9、node12以及node13节点上导致了这3个节点的负载过高, 偏离了正常负载范围, 而node4、node5以及node8节点负载过低没有得到充分利用, 从图中我们能够看到偏离正常负载范围的节点在经过执行调整策略后负载逐渐合理并趋于平稳. 这证明了本方法产生的策略能够有效调整系统, 使得系统平稳运行.
从上述实验可以看出, 本文提出的自适应决策方法能够在指控领域毁伤接替场景下实现自适应决策问题到最优化问题的转化, 同时可以针对多种因素实现策略的权衡决策, 最后通过后优化理论产生唯一策略.
为验证本方法的性能及健壮性, 本文设计了在大规模环境下算法响应时间的测试实验以及不同毁伤程度下的产生策略的效果, 具体实验如下.
(1)大规模环境下算法性能测试
为了验证方法在大规模场景下依然具有实时性, 本文进行了自适应决策算法响应时间测试, 通过调整节点数量观察算法的响应时间. 本实验中从200个节点开始进行测试, 并依次增加100、200、300、400、500、600、700、800、900个节点直到4 700个节点, 观察算法响应时间的变化情况, 针对每个规模进行10次实验, 并取平均值作为实验结果. 节点数与自适应决策响应时间如
Node number and adaptive decision response time
节点数与自适应决策响应时间
从测试结果可以看出, 本文提出的自适应决策方法, 随着计算节点的快速增加, 算法的响应时间始终保持在一个可接受的范围内. 其中, 算法响应时间在3 800个可选择节点下超过了2 s, 在1 700个模拟节点以下算法响应时间均不超过1 s, 这说明尽管随着指控领域计算规模的变大, 本方法依然能够满足军事系统的高实时的需求 .
(2) 极端环境下方法健壮性测试
考虑到在极端环境下, 节点毁伤比例将会到达很高的比例, 为验证在此种极端环境下的健壮性, 本文通过调整节点毁伤比例观察系统节点毁伤调整时间变化情况. 本实验中将测试节点毁伤比例测试区间确定为10%–60%, 每次节点毁伤比例增加10%. 针对不同节点毁伤比例进行10次实验, 并取每次时间的平均值为节点毁伤调整时间. 节点毁伤比例与调整时间如
Change of adjustment time with node damage ratio
调整时间随节点毁伤比例变化图
从测试结果可以看出, 在节点毁伤比例处于10%–60%时, 系统运行正常, 节点毁伤调整速度较快, 调整时间不大于1 min, 能够保证军事系统能够持续可靠运行. 因此, 本文所提出的方法能够产生有效的调整策略, 保证系统在极端环境下平稳运行.
本文准备了策略效率和策略效果两类对比测试, 模拟了本文方法与其他相关方法的在实际场景下的应用情况, 旨在测试评估各类方法的有效性和优劣性. 具体实验如下.
(1)决策效率测试
在决策方法的效率测试中, 本文将决策过程耗时(指标1)作为衡量标准, 测试评估本文串行版本的自适应决策方法以及并行搜索的自适应决策方法、Coker提出的复合自适应决策方法[
Change of decision-making process time with node damage ratio
决策过程耗时随毁伤节点比例变化图
在基于搜索的方法对比测试结果中可以看出, 本文提出的自适应决策方法和Coker提出的复合决策方法, 随着毁伤比例的增长, 决策过程耗时也不断增长, 但都不超过2 s. 可以明显看出, 并行方法的决策过程耗时普遍低于串行方法. 在大部分情况下, Coker’s决策方法耗时普遍低于串行和并行方法, 这是由于Coker’s决策方法作为一种静态决策方式本身就比动态决策方法耗时短所决定的. 而在毁伤节点为50%时, 静态决策方法的决策过程耗时大幅度增长, 高于串行和并行方法, 这是由于静态离线方法的规则库具有一定的局限性, 所有的策略与事件映射都需要预先设置, 当不存在50%毁伤情况下的调整策略时, 需要搜索遍历完整的可行解空间, 在搜索失败后选取与其情况类似的毁伤40%时的调整策略.
在与指控领域的其他方法对比测试结果中可以看出, 随着节点毁伤比例的增长, 本文提出的基于并行搜索的自适应决策方法的决策执行时间会增大, 且其在整个过程中的决策执行时间基本高于基于规则的自适应决策方法并与基于效用的自适应决策方法的决策执行时间相差不大. 本文提出的方法的决策执行时间在节点毁伤比例为10%–30%基本高于基于规则的自适应决策方法, 这是由于基于规则的自适应决策方法判断的规则往往通过静态的方式进行, 决策时间偏少. 而当节点毁伤比例高于40%时, 由于整个系统毁伤比例过高, 节点数目减少, 为了完成系统需求, 每个节点必须增大其自身线程的数量, 从而导致其决策执行时间折线图突然猛增, 但是仍然低于基于效用的自适应决策方法.
(2)策略效果测试
在决策方法的效果测试中, 本文将策略质量值(指标2)作为衡量标准, 测量评估上述除串行方法以外的4种决策方法生成策略的优劣. 首先, 本文在上述决策过程耗时测试环境的基础上, 针对不同节点毁伤比例分别进行20次试验, 分别计算不同策略每次的策略质量值并取平均值. 节点毁伤比例与策略质量数耗时如
Change of strategy mass number with node damage ratio
策略质量值随毁伤节点比例变化图
在基于搜索的方法对比测试结果中可以看出, 本文提出的自适应决策方法和静态方法的质量值在毁伤替换场景下不同毁伤比例下的策略效果相似, 与理想点质量值存在一定差距, 且随毁伤比例的增加而不断降低. 在毁伤50%情况下, 静态方法的质量值大幅度降低, 且低于毁伤40%和60%时的质量值. 是由于在毁伤50%情况下, 静态方法搜索可行解空间失败, 然后选取毁伤40%的调整方法, 然而由于毁伤比例的增加, 同样的调整方案并不适用于毁伤50%的情况, 策略效果低于毁伤40%的策略效果. 因此, 在实际应用时, 采用基于并行搜索优化的自适应决策方法可以在牺牲一定的决策过程耗时的条件下生成更稳定、可靠的策略, 而采用静态方法实现自适应决策的过程中可能会获得更快速的效果, 然而也有一定概率规则匹配失败, 严重影响软件运行, 不满足实际军事应用场景的需要.
在与指控领域的其他方法对比测试结果中可以看出, 3类方法的策略质量值均随着节点毁伤比例的增大而减少. 这说明节点毁伤比例对策略质量存在着直接影响, 这是因为随着节点毁伤比例的增大, 策略寻优的过程变得愈发复杂. 本文提出的基于搜索的自适应决策方法在不同的毁伤比例下, 策略质量均优于基于规则和基于效用两种方法. 在毁伤比例小于等于40%的情况下, 3类方法的策略质量值之间差异较小, 在毁伤大于等于50%情况下, 基于规则的策略质量数则出现大幅降低, 显著低于其他两类的方法. 这是因为基于规则的方法是不能依据当前场景动态产生规则, 其策略质量也就有所下降. 在策略质量值接近的情况下, 本文方法在策略耗时上低于基于效用的方法, 这是因为基于效用的方法在执行过程中每次都需经过5次计算, 因此比较耗时. 依据上述对比, 可以得出, 本文方法产生的策略质量和策略执行耗时上明显优于其他两种方法, 证明了本文方法策略质量和时间开销上的优越性.
本文主要分析了目前主流自适应决策方法的研究现状及其在指控系统中的应用情况, 并重点将本文工作与目前存在的基于搜索的自适应决策方法进行了对比分析.
Lalanda在《Autonomic Computing》一书中, 按照自适应决策方法所采用的知识类型, 将目前面向通用领域的主流决策方法分为基于规则/策略、模型、效用函数、目标共4种[
基于规则/策略的自适应决策方法通过规则匹配或规则推理的方式, 获得恰当的自适应策略. 由于该方法的处理效率极高[
基于目标的自适应决策方法, 以系统目标作为决策目标, 将策略对目标的满足程度作为比较不同策略优劣性的衡量标准, 从而选择出最符合系统目标要求的自适应策略. 相关研究工作可分为两类. 一类是通过建立自适应需求模型, 并以此为依据建立自适应策略[
效用函数指系统进行自适应调整后所能获得目标完成情况(即收益)与自适应调整导致的开销之间(即成本)的关系函数. 基于效用函数的自适应决策方法, 以系统效用作为决策目标, 采用效用函数衡量不同自适应策略调整系统后所能增加的系统效用, 从而选择出最优自适应策略[
基于模型的方法本身根据对模型的相关性, 又可以分为模型相关方法和模型无关方法(model free method). 基于模型的方法, 通过建立模型并获取系统状态信息, 实现对系统状态趋势的预测与分析, 常用的模型包括深度神经网络[
目前, 基于搜索的软件工程已成为软件工程领域的研究热点之一. 然而, 将该理论应用于自适应软件的研究仍处于探索阶段[
与本文最相关的研究工作是由美国卡内基梅隆大学(CMU)的Coker团队[
作为国防与军队信息化建设中的重要系统, 指控系统亟需建立应对动态运行环境和多变任务需求的自适应过程, 以确保系统可长期有效稳定运行. 自适应决策方法作为该过程中的重要环节, 应具备在线权衡决策能力. 因此, 本文提出了一种基于并行搜索优化的指控系统自适应决策方法. 该方法根据自适应决策问题特征, 将自适应决策问题建模为搜索优化问题, 并采用遗传算法与粒子群算法, 实现针对同时发生的多个变化进行在线权衡的目标. 并且, 本文采用并行遗传算法和后优化理论, 结合作战需求与指挥员偏好, 分别实现了并行化的自适应决策方法与策略多指标排序法, 以解决该方法在指控系统中实际应用时存在的搜索效率保障、策略择优选择问题. 实验结果表明, 本文提出的决策方法在模拟环境下能够在线产生应对毁伤接替典型指控场景的权衡策略, 达到有效指导系统开展调整行为, 实现对环境变化与任务变更的动态响应的目标.
当然, 本文所提出的决策方法依然存在很多值得探讨的工作: (1)本文所提出的方法在自适应建模阶段对专家意见有一定依赖性, 需要专家预先给出建议的目标函数、约束函数以及可变点的取值范围. 本文后续考虑构建指控领域知识图谱以辅助自适应问题建模, 并通过实验方式获取可变点的取值与效果的关系, 通过算法计算阈值. (2) 随着系统规模和不确定的上升, 导致方案空间将不断增大. 如何通过优化算法提高收敛效率以满足系统的实时性需求, 是本文后续需要考虑的一个问题. (3) 本文后续考虑建立策略模板, 对搜索产生的结果进行建模, 以实现在不同运行环境下的策略迁移, 减少系统开销. (4) 为保证策略的有效性, 本文后续希望通过引入强化学习, 根据反馈信息对调整策略进行在线修正.
孙宇祥, 周献中, 唐博建, 徐爽, 朱紫. 智能指挥与控制系统发展路径与未来展望. 火力与指挥控制, 2020, 45(11): 60–66. [doi: 10.3969/j.issn.1002-0640.2020.11.012]
Sun YX, Zhou XZ, Tang BJ, Xu S, Zhu Z. Research on development path and future prospect of intelligent command and control system. Fire Control & Command Control, 2020, 45(11): 60–66 (in Chinese with English abstract). [doi: 10.3969/j.issn.1002-0640.2020.11.012]
裴燕, 徐伯权. 美国C4ISR系统发展历程和趋势. 系统工程与电子技术, 2005, 27(4): 666–671. [doi: 10.3321/j.issn:1001-506X.2005.04.024]
Pei Y, Xu BQ. Development course and trend of the US C4ISR system. Systems Engineering and Electronics, 2005, 27(4): 666–671 (in Chinese with English abstract). [doi: 10.3321/j.issn:1001-506X.2005.04.024]
吴桐, 李青山, 戴清, 毛晓彬. 指挥控制信息系统动态演化的自适应决策方法. 指挥信息系统与技术, 2018, 9(5): 43–50. [doi: 10.15908/j.cnki.cist.2018.05.007]
Wu T, Li QS, Dai Q, Mao XB. Self-adaptive decision method for dynamic evolution of command and control information system. Command Information System and Technology, 2018, 9(5): 43–50 (in Chinese with English abstract). [doi: 10.15908/j.cnki.cist.2018.05.007]
王成栋, 张优云. 基于实数编码的自适应伪并行遗传算法. 西安交通大学学报, 2003, 37(7): 707–710. [doi: 10.3321/j.issn:0253-987X.2003.07.012]
Wang CD, Zhang YY. Adaptive pseudo-parallel genetic algorithm based on real coding. Journal of Xi’an Jiaotong University, 2003, 37(7): 707–710 (in Chinese with English abstract). [doi: 10.3321/j.issn:0253-987X.2003.07.012]
Vafaeyan S, Thibault J. Selection of pareto-optimal solutions for process optimization using rough set method: A new approach. Computers & Chemical Engineering, 2009, 33(11): 1814–1825. [doi: 10.1016/j.compchemeng.2009.07.007]
Luque M, Ruiz F, Miettinen K. Global formulation for interactive multiobjective optimization. Or Spectrum, 2011, 33(1): 27–48. [doi: 10.1007/s00291-008-0154-3]
Rosenman MA, Gero JS. Reducing the pareto optimal set in multicriteria optimization (with applications to pareto optimal dynamic programming). Engineering Optimization, 1985, 8(3): 189–206. [doi: 10.1080/03052158508902489]
Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182–197. [doi: 10.1109/4235.996017]
王勋, 张杰勇, 万路军, 焦志强. Holonic-C2组织决策分配及演化方法. 国防科技大学学报, 2020, 42(6): 157–166. [doi: 10.11887/j.cn.202006020]
Wang X, Zhang JY, Wan LJ, Jiao ZQ. Holonic-C2 organization decision allocation and evolution method. Journal of National University of Defense Technology, 2020, 42(6): 157–166 (in Chinese with English abstract). [doi: 10.11887/j.cn.202006020]
Ferreira JC, Fonseca CM, Gaspar-Cunha A. A new methodology to select the preferred solutions from the pareto-optimal set: Application to polymer extrusion. AIP Conference Proceedings, 2007, 907(1): 861–866. [doi: 10.1063/1.2729621] (查阅所有网上资料, 本条文献与第9条文献重复, 请确认)
Damianou N, Dulay N, Lupu EC, Sloman M. Ponder: A language for specifying security and management policies for distributed systems. Tribology, 2000, 2(3): 179–180. (查阅所有网上资料, 未找到标黄部分信息, 请确认)
Franco JM, Correia F, Barbosa R, Zenha-Rela M, Schmerl B, Garlan D. Improving self-adaptation planning through software architecture-based stochastic modeling. Journal of Systems & Software, 2016, 115: 42–60. [doi: 10.1016/j.jss.2016.01.026]
Cámara J, Lopes A, Garlan D, Schmerl B. Adaptation impact and environment models for architecture-based self-adaptive systems. Science of Computer Programming, 2016, 127: 50–75. [doi: 10.1016/j.scico.2015.12.006]
http://www.jos.org.cn/1000-9825/5951.htm]]>
http://www.jos.org.cn/1000-9825/5951.htm]]>
Cardellini V, Casalicchio E, Grassi V, Iannucci S, Presti FL, Mirandola R. MOSES: A framework for QoS driven runtime adaptation of service-oriented systems. IEEE Transactions on Software Engineering, 2012, 38(5): 1138–1159. [doi: 10.1109/TSE.2011.68]
Esfahani N, Elkhodary A, Malek S. A learning-based framework for engineering feature-oriented self-adaptive software systems. IEEE Transactions on Software Engineering, 2013, 39(11): 1467–1493. [doi: 10.1109/TSE.2013.37]
Michael CC, McGraw G, Schatz MA. Generating software test data by evolution. IEEE Transactions on Software Engineering, 2001, 27(12): 1085–1110. [doi: 10.1109/32.988709]
Barreto A, de O. Barros M, Werner CML. Staffing a software project: A constraint satisfaction and optimization-based approach. Computers and Operations Research, 2008, 35(10): 3073–3089. [doi: 10.1016/j.cor.2007.01.010]
Le Goues C, Nguyen T, Forrest S, Weimer W. GenProg: A generic method for automatic software repair. IEEE Transactions on Software Engineering, 2012, 38(1): 54–72. [doi: 10.1109/TSE.2011.104]