-
摘要: 随着信息技术的发展, 复杂系统越来越多地呈现出社会、物理、信息相融合的特征. 因为这些系统涉及到了人和社会的因素, 其设计、分析、管理、控制和综合等问题正面临前所未有的挑战. 在这种背景下, 计算实验应运而生, 通过“反事实”的算法化, 为量化分析复杂系统提供了一种数字化和计算化方法. 对于计算实验方法的发展现状与未来挑战进行了全面梳理: 首先介绍了计算实验方法的概念起源与应用特征; 然后详细阐述了计算实验的方法框架与关键步骤; 接着展示了计算实验方法的典型应用, 包括现象解释、趋势预测与策略优化; 最后给出了计算实验方法所面临的一些关键问题与挑战. 旨在梳理出计算实验方法的技术框架, 为其快速发展与跨学科应用提供支撑.Abstract: With the development of information technology, more and more complex systems show the characteristics of the integration of society, physics and information. Because these systems involve human and social factors, their design, analysis, management, control and synthesis are facing unprecedented challenges. In this context, the computational experiment emerged. It algorithmizes “counterfactuals” as a digital and computational method for quantitative analysis of complex systems. This article reviews the development status and future challenges of computational experiment method. Firstly, it introduces the conceptual origin and application characteristics of computational experiment method; then elaborates on the method framework and key steps of computational experiments; then shows typical applications of computational experiment methods, including phenomenon explanation, trend forecast and strategy optimization; finally, some key problems and challenges faced by computational experiment method are given. The purpose of this paper is to provide the technical framework of computational experiment method, which will facilitate its rapid development and interdisciplinary application.
-
Key words:
- Computational experiments /
- artificial society /
- multi-agent modeling /
- experiment design /
- road map
-
作为作战力量的倍增器, 后装保障系统在现代战场上扮演着非常重要的角色. 它的主要功能是利用有限的保障资源, 在最短时间内及时高效地为前线部队提供急需的作战物质. 在海上分布式杀伤和大规模登陆作战等战场背景下, 由于远离本土作战, 前进基地或预置基地保障资源有限, 在分布式协同作战模式下, 保障需求点增多, 而且保障需求频率也大幅提高. 这种情况下, 一个高效的战时后装保障系统需要解决的问题包括:
1)当作战部队发出保障需求时, 如何选择合适的保障分队处理该需求;
2)每一个保障基地需要分配多少保障分队(负责投送作战物质或维修作战装备);
3)当作战部队发出保障需求时, 如何选择合适的保障分队处理该需求;
4)当保障分队不够时, 如果出现优先级高的保障需求, 能否中断当前保障任务重新规划;
5)当保障分队完成任务后, 如何根据当前战场态势部署至更为优化的地址.
以上问题中, 前3个问题已经有较多研究并得到较好解决, 例如, 昝翔等[1]和何岩等[2]分别利用遗传算法解决了维修任务−维修单元的指派, 曹继平等[3]给出了资源冲突时的优化调度方案; 曾斌等[4]利用混合Petri网建立了流程模型并提出了基于退火进化的保障单元调度算法, 任帆等[5]指出巡回维修中“预测性”策略要优于“最近修理组”策略, 但没有给出具体的预测算法.
而后2个问题可以看作前3个问题的延伸, 即在给定一定数量预置保障基地及每个保障基地预分配了一定数量的保障分队情况下, 当出现新的保障申请时, 如果当前没有空闲的保障分队, 如何重分配保障任务及重部署保障分队. 这一直以来也是后装保障的一个老大难问题, 陈春良等[6]在研究展望中专门指出目前关于装备维修任务调度的研究大多将其视为非抢占调度, 易导致维修任务调度不合理、维修资源利用不充分等问题, 急需开展抢占调度方向研究.
由于允许抢占拓展了解空间, 所以需要寻优, 而常规方法难以优化装备的抢占调度及重规划, 因此需要从智能化保障技术入手, 只有能够对后装保障与配属情况进行合理性预测, 才能制定鲁棒性强的保障计划与投送方案[7], 从而能够根据战场环境变化, 预见性地做出重规划决策.
作为预测决策的关键技术之一, 以马尔科夫决策过程(Markov decision process, MDP)为基础结构的强化学习逐渐在智能化应急服务中得到了应用并取得显著成果[8-9], 包括: 救护车的调度[10]、医疗资源的分配[11-12]、灾后救援优化策略[13-14]、战场伤员的疏散方案[15]以及应急电力系统的自适应控制[16-17]等, 这些研究给予本文以智能决策技术上的启发, 但同样也没有解决重规划问题.
本文的思路如下: 首先建立战时保障动态调度问题的MDP模型; 其次提出了该MDP模型的求解方法. 基于强化学习的试探−奖励−修正(策略迭代)自学习方式, 生成不同保障需求事件下的状态−动作序列, 以此作为样本数据来训练保障调度神经网络模型. 这样在实战过程中, 当战场环境发生变化引发新的保障需求时, 不同的保障决策动作将导致系统状态发生改变, 通过训练好的保障调度神经网络可以快速计算改变后状态的价值, 其中导致状态价值最大的决策即为最优决策.
本文主要贡献包括:
1)定义了支持重规划的后装保障动态调度问题, 建立了支持重规划(抢占调度、重分配及重部署)决策的MDP模型和求解算法;
2)在重规划MDP模型中综合考量了任务排队、保障优先级以及油料约束等问题的影响;
3)为了解决重规划MDP模型状态动作空间过大引起的“维度灾”问题, 借鉴了深度学习思想[18], 提出利用神经网络对基函数进行非线性组合, 从而逼近MDP值函数, 降低了计算复杂度;
4)采用决策后状态思想[19]降低了随机事件引起的计算复杂度.
1. 马尔科夫决策模型
1.1 状态空间
MDP的状态设计非常重要, 如果维度过大会影响求解算法的收敛, 过小则可能不足以用来描述系统的决策函数、状态转移函数以及奖励函数. 本文设计保障系统的状态$S = (t,e,M,R)$, 其中, $t$为当前时间, $e$表示当前事件类型, $M$为列表类型, 表示各个保障分队的所处状态, $R$为列表类型, 表示当前待处理的各个保障需求的状况.
1.1.1 事件类型
系统状态随着事件的产生而变化, 为此本文定义7种事件类型, 即$e(S) \in \left\{ {1,2,\cdots,7} \right\}$. $e(S) = 1$表示产生了保障需求需要处理; $e(S) = 2$表示保障分队到达保障仓库 (如果保障仓库与保障分队处于同一保障基地, 则不用产生此事件); $e(S) = 3$表示保障分队在保障仓库领取到本次任务需要的物质或备品备件; $e(S) = 4$表示保障分队到达需求点; $e(S) = 5$表示保障分队完成当前保障任务; $e(S) = 6$表示保障分队返回保障基地; $e(S) = 7$表示有保障分队处于待命状态.
1.1.2 保障分队状态
保障分队状态列表表示为: $M = {[{M_m}]_{m \in M'}} = [{M_1},{M_2}, \cdots]$, 其中, $M' = \{ 1, 2, \cdots \}$, 表示系统中所有保障分队集合, 列表中每个组成元素都为一个数组, 可表示为
$$ {M_m} = (M_m^s,\,M_m^l,\,M_m^\mu ,\,M_m^d,\,M_m^p,\,M_m^c) $$ 式中, $ M_m^s $表示第$ m $个分队的当前状态; $ M_m^l $表示第$ m $个分队当前的位置; $ M_m^\mu $表示第$ m $个分队完成当前分配任务所需花费的时间, 它与保障分队和任务申请点之间距离有关; $ M_m^d $表示第$ m $个分队在剩余油料支持范围内能够运输的距离; $ M_m^p $表示第$ m $个分队当前被分配任务的优先级; $ M_m^c $表示第$ m $个分队上一个未完成任务的奖励值, 因为中断所以没有得到该奖励. 本文将分队所处状态细分为8级, 即$ M_m^s \in \left\{ {1,2,\cdots,8} \right\} $, $ M_m^s = 1 $表示第$ m $个分队处于待命状态; $ M_m^s = 2 $表示第$ m $个分队前往保障仓库领取物质或备品备件; $ M_m^s = 3 $表示第$ m $个分队完成物质领取等准备工作, 准备出发; $ M_m^s = 4 $表示第$ m $个分队在前往需求点途中; $ M_m^s = 5 $表示第$ m $个分队正在保障之中 (装卸物质、更换配件或维修装备等) ; $ M_m^s = 6 $表示第$ m $个分队完成任务准备返回; $ M_m^s = 7 $表示第$ m $个分队在返航途中; $ M_m^s = 8 $表示第$ m $个分队在保障基地进行加油和保障装备维修维护工作. 其中第2级状态为可选状态, 当待申领物质的仓库与保障分队当前所处基地不在一起时才发生.
以上状态存在约束关系. 当$ M_m^s = \left\{ {1,6,7,8} \right\} $时, 表示第$ m $个分队没有分配任务或已完成任务, 所以此时$ M_m^\mu = M_m^p = 0 $.
当$ M_m^s = \{ 2,3,4,5\} $时, $ M_m^p = 1 $表示第$ m $个分队正在执行较低优先级的保障任务, $ M_m^p = 2 $表示第$ m $个分队正在执行较高优先级的保障任务.
$ M_m^s = 2 $时, 如果$ M_m^c >0 $, 表示第$ m $个分队当前任务被中断, 转而执行新的保障需求; 否则$ M_m^c=0 $.
1.1.3 保障需求状态
保障需求状态列表可表示为: $R = {[{R_r}]_{r \in R'}} = [{R_1},{R_2}, \cdots ]$, 其中, $ R' = \{ 1,2, \cdots\} $, 表示保障需求队列中待处理的所有保障需求集合, 列表中每个组成元素都为一个数组, 可表示为
$$ {R_r} = (R_r^s,\;R_r^l,\;R_r^t,\;R_r^p,\;R_r^n) $$ 式中, $ R_r^s $表示第$ r $个需求的状态, $ R_r^s{\text{ = }}0 $表示第$ r $个需求排队等待处理, $ R_r^s=m $表示第$ r $个需求被分配给第$ m $个保障分队处理, $ R_r^l $表示第$ r $个需求的保障申请点位置, $ R_r^t $表示第$ r $个需求的发出时间, $ R_r^p $表示第$ r $个需求的优先级, $ R_r^n $表示第$ r $个需求的工作量 (所需物质数量或损伤装备数量等).
如果当前没有保障需求, $ {R_r} = (0,0,0,0,0) $; 如果某个保障需求已被完成, 则该需求将会移出队列. 另外保障队列中等待的需求有一个最大阈值$ {r^{\max }} = \left| {R'} \right| $, 它表示保障系统能够支持的保障需求最大数量.
以上状态相对独立, 可以假设其满足马尔科夫过程无后效性性质. 其中时间状态即指当前的时刻, 因为较简单, 可以忽略.
1.2 决策空间
1.2.1 决策变量
为了描述决策空间, 首先定义如下集合.
1) $ B = \{ 1,2,\cdots,\left| B \right|\} $表示保障基地集合;
2) $ Q(S) = \{ r:r \in R',R_r^s = 0\} $表示当系统状态为$ S $时, 在队列中等待分派保障分队处理的保障需求集合;
3) $ {A_1}\left( S \right) \;=\; \{ m:m \in M',M_m^s \;\in\; \left\{ {1,6,7,8} \right\}\} $表示当系统状态为S时, 可以分派执行保障任务的保障分队集合;
4) $ {A_2}\left( S \right) = \{ m:m \in M',M_m^s \in \left\{ {2,3} \right\}\} $表示当系统状态为S时, 可以重规划保障任务的保障分队集合;
5) ${A_3}\left( S \right) = \{ m:m \in M',M_m^s = 6\} $表示当系统状态为S时, 可以重部署的保障分队集合.
本文中决策变量设计为3个布尔变量, 定义如下:
1) $ {X_{mr}} = 1 $表示第$ m $支保障分队被分派执行保障需求$ r $, 否则为0;
2) $ {Y_{mr}} = 1 $表示第$ m $支保障分队被命令中断当前保障任务, 重规划执行新的保障任务$ r $, 否则为0;
3) $ {Z_{mb}} = 1 $表示第$ m $支保障分队被重部署至保障基地$ b $, 否则为0.
1.2.2 决策约束
决策约束分以下4种情况讨论.
情况 1. 当$ Q(S) \ne \emptyset $ (存在待处理保障需求) 且发生事件类型为$ e(S) \in \left\{ {1,2,3,4,6,7} \right\} $时, 保障指挥人员需要执行2个决策: 分派任务和重规划任务. 其中, 分派任务负责分派哪一个保障分队执行队列中等待处理的保障任务; 当没有可用保障分队且出现高优先级任务时, 由重规划任务决定中断哪一个保障分队的当前任务, 转去执行新的保障任务.
这种情况下存在如下5种决策约束:
1)约束一个任务只需要一支分队处理, 如果需要多支分队处理一个任务, 可以组合成一个分队, 或放松此约束, 即
$$\sum\limits_{m \in {A_1}(S)} {{X_{mr}}} + \sum\limits_{m \in {A_2}(S)} {{Y_{mr}}} \leq 1,\;\;\forall r \in Q(S)$$ (1) 2)约束一支保障分队一次只能分派执行一个保障任务, 如果需要一支分队一次执行多个保障任务时, 可以把一个保障分队分解为多支分队, 或放松此约束, 即
$$\sum\limits_{r \in Q(S)} {{X_{mr}}} \leq 1,\;\;\forall m \in {A_1}(S)$$ (2) 3)约束一支保障分队一次只能重规划执行一个保障任务, 即
$$\sum\limits_{r \in Q(S)} {{Y_{mr}}} \leq 1,\;\;\forall m \in {A_2}(S)$$ (3) 4)约束保障分队一次只能分派执行或重规划执行剩余油料距离之内的保障任务, 设dmr表示保障支队m与需求点r之间的距离, 即
$${X_{mr}}{d_{mr}} \leq M_m^d,\;\;\forall m \in {A_1}(S),\forall r \in Q(S)$$ (4) $${Y_{mr}}{d_{mr}} \leq M_m^d,\;\;\forall m \in {A_1}(S),\forall r \in Q(S)$$ (5) 设分派调度决策列表为
$$ \begin{split} X =\;& {[{X_{mr}}]_{m \in {A_1}(S),r \in Q(S)}} = \\ \;& [{X_{11}},{X_{12}}, \cdots ,{X_{1|Q(S)|}},{X_{21}}, \cdots ,{X_{|{A_1}(S)||Q(S)|}}] \end{split} $$ 设重规划决策列表为
$$\begin{split} Y =\;& {[{Y_{mr}}]_{m \in {A_2}(S),r \in Q(S)}} =\\ \;& [{Y_{11}},{Y_{12}}, \cdots ,{Y_{1|Q(S)|}},{Y_{21}}, \cdots ,{Y_{|{A_2}(S)||Q(S)|}}] \end{split} $$ 情况1下的决策空间表述为
$$ {D}_{1}=\{(X,Y) \;\; {\rm{s.t}}.\;\;(1)\sim (5)\} $$ 情况 2. 当$ Q(S) = \emptyset $ (不存在待处理保障需求) 且发生事件类型为$ e(S) = 5 $(有保障分队完成当前保障任务) 时, 保障指挥人员需要决策保障分队$ m $的重部署地点. 注意此时$ {A_3}(S) = \left\{ m \right\} $. 设$ {d_{mb}} $为保障分队$ m $到基地$ b $的距离, $ {I_{mb}} $为指示函数, 如果保障分队$ m $剩余油料可以到达某基地$ b $, 则为1, 否则为0, 其表达式为
$${I_{mb}} = \left\{ {\begin{aligned} &1, \;\;\;{d_{mb}} \leq M_m^d \\ &0,\;\;\;其他 \end{aligned}} \right.$$ 因此, 有决策约束式为
$$\sum\limits_{b \in B} {{I_{mb}}{Z_{mb}} = 1} ,\;\forall m \in {A_3}(S)$$ (6) 该约束表示每一个保障分队只能部署到一个保障基地. 设该情况下重部署决策列表为
$$\begin{split} Z =\;& {[{Z_{mb}}]_{m \in {A_3}(S),b \in B}} =\\ \;& [{Z_{11}},{Z_{12}}, \cdots ,{Z_{1|B|}},{X_{21}}, \cdots ,{X_{|{A_3}(S)||B|}}] \end{split} $$ 情况2下的决策空间表述为
$$ {D}_{2}=\{ Z \;\; {\rm{s.t}}.\;\; (6)\} $$ 情况 3. 当$ Q(S) \ne \emptyset$ (存在待处理保障需求) 且发生事件类型为$ e(S) = 5 $ (有保障分队完成当前保障任务) 时, 保障指挥人员可以选择以下3种决策:
1)分派任务: 分派哪一个保障分队执行队列中等待处理的保障任务;
2)重规划任务: 中断哪一个保障分队的当前任务, 重安排其执行新的保障任务;
3)重部署保障分队: 如果保障分队m没有分派执行队列中等待处理的保障需求, 重部署m到哪一个基地.
注意此时有$ {A_3}(S) = \left\{ m \right\} $. 约束表示为
$$\sum\limits_{r \in Q(S)} {{X_{mr}}} + \sum\limits_{b \in B} {{I_{mb}}{Z_{mb}} = 1} ,\;\forall m \in {A_3}(S)$$ (7) 约束(7)表示如果存在可重部署的保障分队, 且其没有分派执行队列中的保障需求, 则只能将它重部署到最多一个保障基地. 此时决策空间表示为
$$ {D}_{3}=\{\left\{X,Y,Z\right\} \;\; {\rm{s.t}}.\;\;(1)\sim (5),\;(7)\} $$ 情况 4. 如果没有出现以上事件, 也没有发生以上3种情况, 则约束空间${D_4} \ne \emptyset $.
1.3 状态转移
设第$ k $个事件发生时保障系统所处状态为$ {S_k} $, 保障系统通过决策动作dk使得系统状态从$ {S_k} $演进到${S_{k + 1}}$, 并设随机元素$ W({S}_{k}, {d}_{k}) $表示系统处于${S_{k + 1}}$时发生的随机事件信息, 整个保障系统的演进动力模型可以表示为
$$ {S_{k +1 }} = {S^T}( {{S_k},{d_k},w\left( {{S_k},{d_k}} \right)} ) $$ (8) 式中, $ {S^T} $表示状态迁移函数.
1.4 奖励函数
按照MDP模型, 当有保障分队调度 (分派或重规划) 执行保障任务时, 该决策行为将会获得奖励. 奖励值的设计也是影响强化学习能力的重要因素, 本文保障系统中需求优先级、期望保障时间以及需求产生时刻等因素都会影响决策动作的奖励值. 设$ C({S_k},{d_k}) $表示在系统处于状态$ {S_k} $时, 如果采取决策$ {d_k} $将会获得的立即奖励值, 它的计算式设计为
$$\begin{split} C({S_k},{d_k}) =\;& \sum\limits_{m \in {A_1}({S_k})} {\sum\limits_{r \in R} {{\omega _r}\mu(M_m^s - R_r^t){X_{mr}}} }\; + \\ &\sum\limits_{m \in {A_2}({S_k})} {\sum\limits_{r \in R} {({\omega _r}\mu(M_m^s - R_r^t) - M_m^c){Y_{mr}}} } \end{split} $$ (9) 式中, $ {\omega _r} $为权重参数, 用需求优先级加权系统奖励; $ \mu (M_m^s - R_r^t) $为效用函数, 随着需求$ r $的保障时间 (期望服务时间减去发出申请的时间)递减, $ M_m^c $为保障分队$ m $中断执行的保障需求的奖励, 所以式(9)第2项表示重调度保障分队能够获取的奖励 (包括放弃原任务的代价).
1.5 目标函数及优化方程
基于给定策略$ \pi $ (一系列决策的组合) , $ {D^\pi }({S_k}) \in D({S_k}) $为从状态空间到决策空间的决策函数, 用以指导在状态$ {S_k} $下采取策略$ {d_k} $. MDP模型的目的也就是从所有可行策略中计算得到优化策略$ {\pi ^{\text{*}}} $, 从而最大化系统的长远回报. 因此, 系统目标函数为
$$\mathop {\max }\limits_{\pi \in \prod } {{\rm{E}}^\pi }\left[\sum\limits_{k = 1}^\infty {\gamma C({S_k},{D^\pi }({S_k}))} \right]$$ (10) 式中, $ \gamma $为一个固定的折扣因子, 为了便于计算, Bellman优化方程利用迭代方式计算目标函数, 其表达式为
$$V({S_k}) = \mathop {\max }\limits_{{d_k} \in D({S_k})} (C({S_k},{d_k}) + \gamma {\rm{E}}[V({S_{k + 1}})|{S_k},{d_k}])$$ (11) 式中, $ V({S_k}) $为状态$ {S_k} $的值函数.
2. 求解算法
由于维度灾(式(11)的状态空间维度过大)的影响, 利用常规动态规划方法无法取得式(11)的精确解. 为此, 本文采用近似动态规划[20]的方法逼近式(11)的值函数.
2.1 随机事件的计算
另外, 式(11)中还需要对期望值$ {\rm{E}}[V({S_{k + 1}})|{S_k}, {d_k}] $求极值, 不仅计算量巨大而且会带来较大的统计误差, 为此本文采用决策后状态思想[21-22], 将先求期望值后求极值问题转换为先求极值后求期望值问题, 从而降低了计算量和误差. 该思想在前后两个状态之间 $ ({S_k} $和$ {S_{k{\text{ + }}1}} )$引入了一个中间状态, 即决策后状态$ S_k^x $, 该状态在决策发生后事件发生前出现, 属于确定性状态, 因此, 原来式(8)的一步状态转移转换为两步, 即
$$ \begin{array}{l} S_k^x = {S^{T,x}}\left( {{S_k},{d_k}} \right)\\ {S_{k +1 }} = {S^{T,w}}\left( {S_k^x,w\left( {{S_k},{d_k}} \right)} \right) \end{array} $$ 其中, ${S^{T,x} }$为确定性函数, ${S^{T,x}}$和${S^{T,w}}$组合后与式(8)的$ {S^T} $等价. 设决策后状态$ S_k^x $的价值为
$$ V(S_k^x) = {\rm{E}}\left( {V\left( {{S_{k +1 }} } \right)|S_k^x} \right) $$ (12) 将式(12)代入式(11), 优化方程修改为
$$V({S_k}) = \mathop {\max }\limits_{{d_k} \in D({S_k})} (C({S_k},{d_k}) + \gamma V(S_{_k}^x))$$ (13) 下面进一步讨论式(13)决策后状态价值的计算, 由于式(12)为迭代过程, 可以有
$$ V(S_{k - 1}^x) ={\rm{ E}}\left( {V\left( {{S_k}} \right)|S_{k - 1}^x} \right) $$ (14) 式(13)代入式(14)右边, 引入决策后状态价值的优化方程可表示为
$$V(S_{_{k{\rm{ - 1}}}}^x) = {\rm{E}}\left[ {\mathop {\max }\limits_{{d_k} \in D({S_k})} (C({S_k},{d_k}) + \gamma V(S_{_k}^x))|S_{_{k - 1}}^x} \right]$$ (15) 2.2 基函数的设计
尽管式(15)通过引入决策后状态变量减小了随机事件带来的计算复杂性和统计误差, 但是对于式(15)而言, 复杂的状态空间导致的维度灾问题仍然存在. 为此, 本文通过构造基函数捕捉决策后状态的特征, 再以基函数为基础来设计近似函数以便逼近式(15)表示的价值函数. 这里基函数的设计尤为重要[23-24], 关系到最后近似价值函数的求解质量. 为此本文设计了6种基函数, 通过它们的非线性组合(参见第2.3节的神经网络)来表示价值函数. 设$ \varphi f(S_k^x) $表示基函数, $ f $为基函数特征, $ f \in F $.
1)第1种基函数直接表示保障分队状态, 数量为 $ \left| {M'} \right| $, 计算式为
$$ {\varphi _1}(S_k^x) = M_m^s $$ 2)第2种基函数捕捉保障分队执行保障任务(服务−客户对)的期望服务时间, 数量为 $ \left| {M'} \right| $. 设$ {I_{mr}} $为指示函数, 如果保障分队$ m $当前执行的保障任务为$ r $, 则为1, 否则为0, 计算式为
$$ {\varphi _2}(S_k^x) = {I_{mr}}(M_m^\mu - t(S_k^x)) $$ 3)第3种基函数捕捉保障分队执行保障任务的优先级, 数量为 $\left| {M'} \right| $, 计算式为
$$ {\varphi _3}(S_k^x) = {I_{mr}}(M_m^p) $$ 4)第4种基函数捕捉当前在队列中等待处理的保障需求优先级, 数量为 $\left| {R'} \right| $, 计算式为
$$ {\varphi _4}(S_k^x) = R_r^p,\;\;R_r^s = 0 $$ 5)第5种基函数捕捉每一个需求在系统中的逗留时间, 数量为 $\left| {R'} \right| $, 计算式为
$$ {\varphi _5}(S_k^x) = t(S_k^x) - R_r^t $$ 6)第6种基函数捕捉每一个保障分队与保障申请点的距离, 数量为 $ \left| {M'} \right| \times \left| {R'} \right| $, 该基函数结合保障分队的状态$ M_m^d $, 可以知道哪一个保障分队有足够油料分派或重规划到某需求点, 其计算式为
$$ {\varphi _6}(S_k^x) = {d_{mr}} $$ 2.3 神经网络的设计
由于保障系统状态空间和决策空间较为复杂, 常规线性基函数组合的效果将会因此受到较大影响. 所以本文以基函数的输出结果作为神经网络输入, 即利用神经网络对基函数进行非线性组合[25], 从而达到逼近式(15)值函数的目的.
为了使学习后的神经网络能够近似表达值函数, 本文设计了3层神经网络结构: 输入层、隐藏层和输出层. 如图1所示, 输入层包含$ \left| F \right| $个输入, 它的值为基函数的输出, 如图1中${\phi _{1,1}}$表示第1类基函数的第1个函数输出值, 输入节点个数为6类基函数的总个数, 输入层没有激活单元. 为了减小基函数评估值的波动, 帮助神经网络反向传播算法能够快速找到权重矩阵, 在输入到输入层之前, 本文对基函数评估值进行了均值归一化.
隐藏层包括$ H = \{ 1,2,\cdots,\left| H \right|\} $个神经元, 其个数$ \left| H \right| $为超参数, 所以隐藏层的输入表达式为
$${I_h}(S_k^x) = \sum\limits_{f \in F} {{{\boldsymbol{\theta }}_{{{f,h}}}}{\varphi _f}(S_k^x),\;\;\forall h \in H} $$ (16) 式中, $ {I_h} $表示隐藏层中第$ h $个神经元的输入, ${{\boldsymbol{\theta}} _{f,h}}$为$ \left| F \right| \times \left| H \right| $的权重矩阵, 控制输入层到隐藏层的映射关系, 隐藏层神经元的激活函数为sigmoid函数, 表示为
$$\sigma (i) = \frac{1}{{1 - {{\rm{e}}^{ - i}}}}$$ 因此, 隐藏层的输出表达式为
$$ {O_h}(S_k^x) = \sigma ({I_h}(S_k^x)) $$ (17) 其中, $ {O_h} $为第$ h $个神经元的输出, $ \left| H \right| $个隐藏层神经元输出与输出层权重组合生成输出层的输入, 其表达式为
$${I_o}(S_k^x) = \sum\limits_{h \in H} {{{\boldsymbol{\theta }}_{h}}{O_h}(S_k^x)} $$ (18) 式中, ${{\boldsymbol{\theta}} _h}$为$ \left| H \right| \times 1 $的权重矩阵, 控制隐藏层到输出层的映射关系, 输出层只有一个神经元, 激活函数与隐藏层的相同, 也为sigmoid函数, 其表达式为
$$ V(S_k^x|{\boldsymbol{\theta}} ) = \sigma ({I_o}(S_k^x)) $$ (19) 式中, ${\boldsymbol{\theta }}= ({{\boldsymbol{\theta}} _{f,h}},{{\boldsymbol{\theta}} _h})$为神经网络中需要学习的权重参数.
2.4 神经网络权重学习算法的设计
本文设计了基于强化学习策略迭代[26]的神经网络学习算法, 如图2所示, 算法分为2层循环, 第1层循环(内层循环)为策略评估, 利用给定策略(上一次循环更新的神经网络), 在模拟产生的事件驱动下, 生成动态演进的状态价值并作为样本点保存; 第2层循环(外层循环)为策略改进, 利用内层循环保存的样本点改进神经网络的权重矩阵.
策略迭代算法外循环每次进行策略改进时都需要调用神经网络反向传播算法对权重参数进行训练, 为了防止出现过拟合和泛化误差, 本文在神经网络代价函数中加入了惩罚项, 即
$$\begin{split} L( {\boldsymbol{\theta }}) =\;& \frac{1}{{2K}}{\left( {{V_k} - V(S_{k - 1}^x| {\boldsymbol{\theta }})} \right)^2} + \\ &\frac{\eta }{{2K}}\left( {\sum\limits_{f \in F} {\sum\limits_{h \in H} {{{({\theta _{f,h}})}^2} + \sum\limits_{h \in H} {{{({{\boldsymbol{\theta}} _h})}^2}} } } } \right) \\ \end{split} $$ 其中, $ K $个样本点中, $ V(S_{{{k - 1}}}^x|{\boldsymbol{\theta }}) $在步骤2.4中存储, 为神经网络估算值; $ {V_k} $在步骤2.7中存储, 为标签值; 正则化参数$ \eta $用于平衡模型复杂度和边际误差. 本文采用了自适应预估方法来计算合适的$ \eta $值, 计算式为
$$ \eta = \max \{ |v + 3{\sigma _v}\left| , \right|v - 3{\sigma _v}|\} $$ 式中, $ v $为样本数据的均值, $ {\sigma _v} $为样本数据的标准差.
需要计算得到$ {\boldsymbol{\theta}} {\text{*}} $值, 使得代价函数最小, 即${\boldsymbol{ \theta}} {\text{*}} = {\rm{ argmin}}\{ L({\boldsymbol{\theta}} )\}$. 为了提高计算速度, 本文采用拟牛顿法求解, 拟牛顿法需要的梯度信息可以利用神经网络的反向传播算法计算得到.
为了平滑${\boldsymbol{ \theta }}$权重矩阵, 本文采用式(20)来更新$ {\boldsymbol{\theta}} $:
$$ {\boldsymbol{\theta}} = {a_n}{\boldsymbol{\theta}} {\text{*}} + \left( {1 - {a_n}} \right){\boldsymbol{\theta}} $$ (20) 其中, ${a_n}=1/{n^\beta }$, $ \beta \in (0.3,1] $, $a_n $的下标值$ n $与策略改进外循环次数$ n $一致, 通过$ {a_n} $控制$ {\boldsymbol{\theta }}$值, 在历史值 $( {\boldsymbol{\theta}}) $ 与新估计值 $({\boldsymbol{ \theta }}{\text{*}}) $ 之间取得平衡. 随着策略改进迭代次数$ n $的增加, 本算法越来越偏重于过去$ n-1 $次迭代得到的历史值.
在策略迭代算法的每一次外循环 (策略改进) 中, 都会按式(18)对神经网络的权重进行更新, 如果$ n < N $, 则算法开始下一轮循环. 算法中可调节参数包括$ N $、$ K $、$ \left| H \right| $、$ \eta $和$ \beta $, 其中, $ N $为策略改进的迭代次数, $ K $为策略评估的迭代次数, $ \left| H \right| $为隐藏层节点的个数, $ \eta $是样本估计的正则化项, $ \beta $是步长参数.
2.5 调度算法的使用时机及步骤
建立的神经网络模型可以看作一个具有预测能力的调度机. 其使用时机为: 当战场态势变化, 例如出现新的保障申请, 如第1.1节描述的当前系统状态随之改变. 使用步骤如下:
1)在第1.2.2节描述的决策约束下, 生成各种可能的决策动作;
2)按第1.3节状态转移矩阵, 基于当前状态, 采取步骤1)生成的各种可能的决策动作, 形成下一步状态集合$S; $
3)将下一步状态集合中的每一个状态作为第2.2节叙述的基函数输入, 基函数的输出为第1阶段的线性预测值, 用于降低计算复杂性;
4)为了具有非线性预测能力, 如图1所示, 基函数的输出作为神经网络模型的输入, 此时神经网络的输出为下一步状态的价值$V(S) $, 该价值为第2.4节Bellman方程迭代计算的 “期望” 价值;
5)当状态集合S中的每一个状态都经过步骤3)和步骤4), 计算出相应期望价值后(该过程可以并行执行), 导致下一步状态价值最大的决策可看作当前最优决策.
3. 实验验证
本节通过一个分布式战场保障场景来验证动态调度算法的适用性. 由于MDP求解算法超参数较多, 通过实验设计测试了不同参数设置对动态算法的影响, 并比较了动态算法与两个比对策略的性能差异.
3.1 实验参数设置
本文以图3所示的一个典型的分布式作战行动为背景, 当交战区域中我方部队发出保障申请后, 使用上文提出的数学模型及逼近算法计算调度结果, 即决定是否接受该申请, 如果接受该申请, 分派哪一支分队处理. 出于安全考虑, 删除了图3的背景地图, 图3中有2个保障基地和2个前进基地, 与保障基地相比, 前进基地较小, 当没有申请所需物资装备时, 需要从保障基地补充. 图3中还包括54个交战地点, 即保障申请点, 分属12个区域, 由其发出保障申请.
本文使用泊松分布生成保障需求的产生概率, 为了能够接近实战背景, 泊松分布的到达率参数由式(21)生成, 即
$$ {\lambda _{kz}} = \lambda {p_z}{p_{kz}} $$ (21) 式中, $\lambda $为保障申请发生率; $ {p_z} $为条件概率, 表示当发生保障申请时, 该申请是从交战区域$ z $发出的概率; $ {p_{kz}} $为条件概率, 表示当出现保障申请且该申请从交战区域$ z $发出时, 该申请优先级为$ k $的概率. 实验中保障申请发生率$\lambda $设为1/45, 即平均每隔45 min发出一个保障申请, 请求保障分队执行任务. 为了集中反映系统的调度能力, 条件概率$ {p_{kz}} $中紧急保障和一般保障的比例为0.8和0.2. 式(9)中紧急保障的优先级权重为0.9, 一般保障的权重为0.1, 式(10)中折扣因子$ \gamma $在实验中设为0.99, 该设置使得系统重视未来事件的影响.
为了检验动态算法的性能, 实验设计了2个比对策略. 比对策略A采用常规的最近分配原则, 该策略认为当前没有执行任务的保障分队为可用资源, 当出现保障申请时, 分配离该申请点(交战区域)最近的可用分队执行此项保障任务, 比对策略A不具备抢占调度能力. 比对策略B将比对策略A进行了扩展, 当出现优先级更高的保障申请时, 允许其抢占其他保障分队当前执行的低优先级任务. 两个比对策略使用的都是最近分配原则, 该原则实际上只考虑当前的立即奖励进行决策(与式(9)相似), 没有用到预测的未来信息(式(10)). 另外, 由于立即奖励没有考虑重部署决策, 所以这两个比对策略都不具备重部署能力.
3.2 超参数调整
本文采用了全因子实验设计来检验不同的超参数对算法性能的影响, 主要超参数设置如下: 策略改进迭代次数$ N = \{ 1,2,\cdots,40\} $, 策略评估迭代次数$ K = \{ 500,1\,000,2\,000,4\,000\} $, 步长参数$\beta = \{ 0.3, 0.5, 0.7, 0.9\}$, 隐藏层节点数$ \left| H \right| = 7 $, 正则化项$ \eta $采用自适应预估方法计算. 为了能够得到合理的置信度, 每一个组合运行100遍仿真, 每次仿真时长为1000 min以上. 仿真实验结果如表1所示, 其中, 性能相对改进量计算式为
表 1 仿真实验结果Table 1 Simulation resultsN K β Impr1,A Impr1,B Impr2,A Impr2,B 30 500 0.3 8.2±0.2 5.3±0.2 6.9±0.2 3.1±0.1 35 1000 0.3 8.6±0.2 5.6±0.1 7.8±0.1 3.2±0.2 25 2000 0.3 9.5±0.2 6.5±0.2 7.2±0.2 4.2±0.1 18 4000 0.3 9.3±0.2 6.4±0.2 5.1±0.1 2.9±0.1 10 500 0.5 8.3±0.2 5.3±0.1 6.9±0.2 2.7±0.2 9 1000 0.5 8.3±0.2 5.3±0.1 7.4±0.2 2.3±0.2 28 2000 0.5 9.6±0.2 6.6±0.2 6.8±0.1 2.7±0.1 12 4000 0.5 8.2±0.2 5.2±0.1 7.1±0.1 4.2±0.1 10 500 0.7 8.4±0.2 5.4±0.1 5.9±0.2 4.1±0.2 6 1000 0.7 8.0±0.1 5.1±0.1 7.8±0.1 4.5±0.1 25 2000 0.7 9.0±0.2 6.0±0.2 8.1±0.2 4.4±0.2 4 4000 0.7 8.4±0.2 5.4±0.1 6.4±0.2 4.3±0.2 30 500 0.9 8.1±0.2 5.2±0.1 5.9±0.1 2.1±0.1 7 1000 0.9 7.8±0.1 4.9±0.1 7.2±0.1 4.9±0.2 33 2000 0.9 9.4±0.2 6.4±0.2 5.7±0.2 3.4±0.1 25 4000 0.9 8.4±0.1 5.4±0.1 5.3±0.2 2.9±0.2 $$ {{Imp}}{{{r}}_i}_{,j} = \frac{{V_i} - {V_j}}{V_j} $$ (22) 其中, $ {V_i} $为采用$ i $算法计算得到的价值, $ {V_j} $为采用$ j $算法计算得到的价值, 表1中${{Imp{r}}_{1,A}}$和${{Imp{r}}_{1,B}}$分别为本文基于神经网络的动态算法相较于比对策略A和策略B得到的性能相对改进量.
另外, 为了考量神经网络模型的性能, 设计了基函数的线性回归模型作为比较算法, Impr2,A和Impr2,B分别为线性回归模型相较于比对策略A和策略B得到的性能相对改进量. 表1中仿真结果数据的置信度都为95%.
表1中左边3列为仿真实验中设置的算法参数组合, 为了节省篇幅, 其中$ N $值只取$ (K,\beta ) $因子组合中算法性能最大的取值, 其他4列表示动态算法相较于两个比对策略的总奖励回报 (式(15)) 的提高率, 取置信度为95%的置信区间. 从表1中可以看出, 当$ \lambda = 1/45 $时, 无论哪一种参数组合, 重规划动态调度算法生成的方案都要优于比对策略, 特别是当$ N = 28 $, $ K = 2\;000 $, $ \beta = 0.5 $时 (表1中粗体字所示) 效果最好. 另外, 近似函数为神经网络模型时, 调度性能要明显超过基于线性回归模型的近似函数, 这主要是因为调度算法中用基函数表示的影响因素相互交织, 呈非线性关系, 所以用神经网络拟合效果较好.
3.3 性能指标比较测试
图4显示了策略评估迭代次数$ K = 2\;000 $时, 无论步长参数$ \beta $取何值, 相较于比对策略A, 动态调度算法的性能都为最佳值. 当$ K $在增加到2000前, 动态算法的性能逐渐提高; 当大于2000后, 性能开始下降; 在4000次迭代时性能明显下降. 主要原因是在$ K = 4\;000 $时, 本仿真实验的样本数据集增加到一定阈值, 导致神经网络模型过拟合, 从而产生低效率的调度结果. 另外, 从表1和图4都可以看出, $\beta $取较小值 (0.3或0.5) 时, 算法收敛速度较慢, 能够增加算法的调度效果.
表2的第1列为调度策略; 第2列和第3列分别为当$ N = 28 $, $ K = 2\;000 $, $ \beta = 0.5 $时, 不同优先级的保障申请响应时间 (从发出申请至保障分队到达的时间间隔) 的置信区间 (置信度为95%); 第4列为调度方案$ V $值提高百分比的置信区间. 从表2可以看出, 具备抢占调度能力的策略B和动态调度算法都比不具备抢占能力的策略A性能好, 另外还有一个现象也需要引起注意, 随着第4列显示的性能提高, 在紧急保障申请的响应时间减少的同时, 一般保障申请的响应时间却在增加. 估计这与抢占调度特性有关, 它抢占低优先级保障任务转而去执行高优先级任务, 导致低优先级任务服务时间延长.
表 2 动态算法和比对策略的性能比较Table 2 Comparison of the algorithms and policies调度策略 响应时间(min) 性能相对改进量(%) 紧急申请 一般申请 比对策略A 56.3±0.2 56.8±0.2 — 比对策略B 53.4±0.1 57.7±0.2 2.9±0.1 动态调度 48.1±0.1 57.9±0.1 9.6±0.2 为了进一步检验算法的鲁棒性, 在模拟一天24小时的保障仿真中, 对保障申请发生率$\lambda $和交战区域位置进行了数次改变. 从图5中可以看出, 响应时间也相应发生了较大波动, 但是动态调度算法性能还是明显好于比对策略.
保障申请率的变化对调度系统也有较大影响, 为此, 设置保障申请发生率$\lambda $从1/25减小到1/65, 图6反映了动态调度算法和比对策略B相较于策略A的性能相对改进量变化情况. $\lambda $减小意味着保障申请发生率减小, 动态调度算法和策略B的性能相对改进量也逐渐减小, 表示抢占调度和重部署带来的性能优势也在减小, 因此在低强度战场上动态调度算法性能优势不明显, 在保障申请率较高的高强度战场上抢占调度和重部署能力才能取得较明显的效果.
4. 性能定性分析
最后通过4个场景来定性分析重规划能力的优势. 第1个场景状态中, 假设某作战部队申请后装保障, 此时只有离它较远的保障分队空闲, 离它较近的保障分队预测能在较短时间内完成正在执行的任务. 由于比对策略A和B缺乏预测能力, 会把较远的空闲保障分队分派出去, 而动态调度算法需要最大化基于长期回报的奖励函数, 所以先把该次申请放入队列, 等候较近的保障分队空闲后再分派.
在第2个场景的系统状态中, 某保障分队刚被分派执行某高烈度区域的一个低优先级保障任务, 这时同样区域发出了一个高优先级保障申请, 此状态下, 除非指挥员发出新的分派指令, 否则策略A将保持该保障分队的任务不变. 很明显此时好的调度算法应该主动中断保障分队的当前任务, 重新分派它执行高优先级的紧急任务, 从而取得更高的回报价值.
考虑第3个场景的系统状态, 某保障分队刚被分派执行某高烈度区域的一个低优先级保障任务, 这时另一个较远距离的低烈度区域发出高优先级保障申请, 此状态下动态调度算法需要根据神经网络模型的预测结果权衡, 如果 “重规划” 动作产生的状态价值较小, 则不应该实施抢占.
考虑第4个场景的系统状态, 某保障分队快要完成当前任务准备返回基地, 这时一个离它较远(超过剩余油料支持路程)的区域发出保障申请. 该状态下, 比对策略的调度方案是要求该保障分队返回原基地补充后再执行新任务. 而具有重部署能力的动态调度算法会指示保障分队前往距离申请点近的地方补充油料, 从而更快地执行新任务.
综上所述, 与比对策略不同, 动态调度算法的决策基础是通过基函数组合的神经网络模型, 它能够捕捉当前事件和可预测的未来事件带来的影响, 因此能够产生更优的调度结果.
5. 结束语
本文主要研究了战时后装保障中重规划(抢占调度、重分配及重部署)问题, 以便生成高质量的保障资源调度策略, 提高后装保障智能化水平. 针对重规划问题设计了一个无限时域马尔科夫决策过程模型, 其目标是最大化保障调度系统的长期折扣奖励. 为了解决重规划模型的维度灾问题, 利用神经网络对基函数进行非线性组合, 从而达到逼近值函数的目的, 并提出了基于强化学习策略迭代的神经网络学习算法. 最后设计了一个高强度分布作战仿真场景, 检验了不同问题特征及算法参数对调度性能的影响, 验证了动态调度算法的适用性.
本文中MDP模型的描述是对保障调度适用的对象或场景的限制条件, 对于超出该模型描述的保障调度, 也具有一定的借鉴意义. 另外, 如果调度场景与对象变化较大, 如作战规模过大, 保障基地数量位置动态变化时, 由于机器学习能力限制, 逼近函数(本文采用基函数+神经网络)也需要相应调整.
下一步工作需要改进当前研究的一些不足之处, 例如在高强度作战中, 可能某次保障申请需要的资源较大, 超过了一个保障分队或基地的能力, 需要调度多个分队协同保障. 协同保障方面已经有一些相关研究成果, 正在考虑如何与之结合. 另一个重要研究方向是进一步扩展保障分队的类型及相应特性, 这样可以比较不同保障分队的调度性能. 另外, 错误定义的保障需求优先级会影响保障分队的调度, 这也是下一步需要解决的难点.
-
图 7 计算实验系统的运行流程图
Fig. 7 The operation flow chart of the computational experimental system
图 23 使用强化学习的虚拟淘宝架构
Fig. 23 The architecture of virtual Taobao using reinforcement learning
图 25 腾讯TAD Sim仿真系统场景演示
Fig. 25 The scene demonstration of Tencent TAD Sim simulation system
表 1 计算实验与相关概念的区别
Table 1 Differences between computational experiments and similar concepts
概念 实物实验 自然实验 (田野实验) 计算机仿真 计算实验 研究对象 在物理空间中实际进行的实验 在社会空间中实际进行的实验 在虚拟空间中对物理系统进行实验 在虚拟空间中对社会复杂系统进行实验 研究手段 通常在实验室、工厂或农场里进行, 通过控制实验条件, 进行观察实验 将受试群体暴露在自然条件或者某种特定的控制条件下, 通过观察实验组与控制组的指标变化进行实验 基于相似性原理, 采用自上而下、还原分解的方式建立与实际或设想系统之间具有同态关系的数学模型. 计算机以数值计算的方法执行求解过程, 输出与物理系统相同的结果 基于知识与学习机制, 采用自下而上的方式建立实际系统的计算模型, 能够对从未发生过的场景进行模拟推演 研究目标 构建理论与事实的桥梁, 不仅促进了理论到技术方法的转换, 也使得理论研究更加具有目的性 自己无法控制实验条件, 但通过某个意外事件, 正好创造出了符合要求的实验条件, 用以验证社会中的因果关系 关注建模的保真度, 即是否能准确反映物理对象的特性和状态, 从而指导实际物理系统的设计与优化 为实际社会复杂系统的设计、分析、管理、控制和综合提供科学决策和指导 应用领域 广泛应用于如农业、工业、制造业等领域 广泛应用于医学和社会科学的研究中, 也是心理学研究的一种重要方法 已经渗透到了各个领域, 包括交通运输、航空航天、工业制造、气象预测、电子信息产业等 与众多学科交叉融合, 成为诸多领域的重要工具, 例如计算社会学、计算经济学、计算金融学、计算组织学、计算流行病学等 局限性 实验时间较长, 由于伦理、道德、经济、社会等因素有时难以顺利开展 情境上比较真实, 而在干扰变数的处理上则比较差 由于缺乏充分可用的理论和先验知识, 自顶向下的建模方法难于对复杂系统进行准确描述并深入分析 如何证明计算模型的有效性与等价性没有取得共识, 容易遭受实验能否反映现实的质疑 
下载: 导出CSV
表 2 典型的大规模流行病传播模拟系统特征对比
Table 2 Comparison of characteristics of typical large-scale epidemic spread simulation systems
特点 BIoWar[15] EpiSimS[68] GSAM[113] CovidSim[114] ASSOCC[115] SIsaR[116] 疾病类型 飞沫传播、物理
接触传播天花、流感 新型冠状病毒肺炎、
其他呼吸道病毒新型冠状病毒肺炎 新型冠状病毒肺炎 新型冠状病毒肺炎 主要用途 影响评估策略优化 影响评估策略优化 研究传染病的蔓延与控制 影响评估策略优化 影响评估政策权衡 评估不同干预政策的成本和收益 模拟尺度 美国中等城市 美国中等城市 全球 国家 国家 国家 模拟方法 多智能体 多智能体 多智能体 地理空间单元 多智能体 多智能体 开发语言 C++ − Java C++ Netlogo、R语言 Netlogo 可视化 否 是 是 是 是 是 开源 否 否 否 是 是 是 (可在网上运行)
下载: 导出CSV
-
[1] 王飞跃. 人工社会, 计算实验, 平行系统—关于复杂社会经济系统计算研究的讨论. 复杂系统与复杂性科学, 2004(4): 25-35 doi: 10.3969/j.issn.1672-3813.2004.04.002Wang Fei-Yue. Artificial society, computational experiments, parallel systems — a discussion on computational research of complex socio-economic systems. Complex Systems and Complexity Science, 2004(4): 25-35 doi: 10.3969/j.issn.1672-3813.2004.04.002 [2] 王飞跃, 史帝夫 $\cdot $ 兰森. 从人工生命到人工社会: 复杂社会系统研究的现状和展望. 复杂系统与复杂性科学, 2004, 1(1): 33-41 doi: 10.3969/j.issn.1001-9596.2004.05.024Wang Fei-Yue, Lansing J S. From artificial life to artificial societies——new methods for studies of complex social systems. Complex Systems and Complexity Science, 2004, 1(1): 33-41 doi: 10.3969/j.issn.1001-9596.2004.05.024[3] Prigogine I, Stengers I. Order Out of Chaos. New York: Bantam Books Inc, 1984. [4] Xue X, Wang S F, Gui B, Hou Z W. A computational experiment-based evaluation method for context-aware services in complicated environment. Information Sciences, 2016, 373: 269-286 doi: 10.1016/j.ins.2016.09.003 [5] Pearl J, Mackenzie D. Why: The New Science of Cause and Effect. New York: Basic Books, 2018. [6] Boschert S, Rosen R. Mechatronic Futures, Digital Twin: The Simulation Aspect. Cham: Springer, 2016. 59−74 [7] 王飞跃. 情报5.0: 平行时代的平行情报体系. 情报学报, 2015, 34(6): 563-574 doi: 10.3772/j.issn.1000-0135.2015.006.001Wang Fei-Yue. Intelligence 5.0: Parallel intelligence in parallel age. Journal of Information, 2015, 34(6): 563-574 doi: 10.3772/j.issn.1000-0135.2015.006.001 [8] 薛霄. 复杂系统的计算实验方法: 原理、模型与案例. 北京: 科学出版社, 2020.Xue Xiao. Computational Experiment Methods for Complex Systems: Principles, Models and Cases. Beijing: Science Press, 2020. [9] 王飞跃. 计算实验方法与复杂系统行为分析和决策评估. 系统仿真学报, 2004, 16(5): 893-897 doi: 10.3969/j.issn.1004-731X.2004.05.009Wang Fei-Yue. Computational experimental methods and complex system behavior analysis and decision evaluation. Journal of System Simulation, 2004, 16(5): 893-897 doi: 10.3969/j.issn.1004-731X.2004.05.009 [10] Li L, Wang X, Wang K. Parallel testing of vehicle intelligence via virtual-real interaction. Science Robotics, 2019, 4(28): eaaw4106 doi: 10.1126/scirobotics.aaw4106 [11] Li L, Huang W L, Liu Y. Intelligence testing for autonomous vehicles: A new approach. IEEE Transactions on Intelligent Vehicles, 2017, 1(2): 158-166 [12] Hu X F, Li Z Q, Yang J Y, Si G Y, Pi L. Some key issues of war gaming & simulation, Journal of System Simulation. 2010, 22(3): 549-553 [13] 吴江. 社会网络的动态分析与仿真实验. 武汉: 武汉大学出版社, 2012.Wu Jiang. Theory and Application of Social Network Dynamic Analysis and Simulation Experiments. Wuhan: Wuhan University Press, 2012. [14] Acevedo M F, Callicott J B, Monticino M. Models of natural and human dynamics in forest landscapes: Giorgio-site and cross-cultural synthesis. Geoforum, 2008, 39(2): 846-866 doi: 10.1016/j.geoforum.2006.10.008 [15] Carley K M, Fridsma D B, Casman E. BioWar: Scalable agent-based model of bioattacks. IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 2006, 36(2): 252-265 doi: 10.1109/TSMCA.2005.851291 [16] Huang C Y, Sun C T, Hsieh J L, Lin H. Simulating SARS: Small-world epidemiological modeling and public health policy assessments. Journal of Artificial Societies and Social Simulation, 2004, 7(4): 2 [17] Cioffi R C, Rouleau M. Mason rebeland: An agent-based model of politics, environment, and insurgency. International Studies Review, 2010, 12(1): 31-52 doi: 10.1111/j.1468-2486.2009.00911.x [18] Mitchell W. Complexity: The Emerging Science at the Edge of Order and Chaos. New York: Touchstone, 1992. [19] Bertalanffy L V. General System Theory. New York: Braziller, 1968. [20] Bertalanffy L V. Problems of Life: An Evaluation of Modern Biological and Scientific Thought. New York: Harper, 1952. [21] Norbert W. Cybernetics: Or Control and Communication in the Animal and the Machine. Massachusetts: MIT Press, 1961. [22] Shannon C E. A mathematical theory of communication. Bell System Technical Journal, 1948, 27(3): 379-423 doi: 10.1002/j.1538-7305.1948.tb01338.x [23] Prigogine J. Structure, dissipation and life, theoretical physics and biology. Theoretical Physics and Biology, 1969: 23-52 [24] Thom R. Structural Stability and Morphogenesis. Boca Raton: CRC Press, 2018. [25] Haken H P J. Synergetics. IEEE Circuits & Devices Magazine, 1977, 28(9): 412-414 [26] Li T Y, Yorke J A. Period three implies chaos. The American Mathematical Monthly, 1975, 82(10): 985-992 doi: 10.1080/00029890.1975.11994008 [27] Mandelbrot B B. Fractals, form, chance and dimension. The Mathematical Gazette, 1978, 62(420): 130-132 doi: 10.2307/3617679 [28] Bak P, Tang C, Wiesenfeld K. Self-organized criticality: An explanation of noise. Physical Review Letters, 1987, 59(4): 381-384 doi: 10.1103/PhysRevLett.59.381 [29] Holland J H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. New York: MIT press, 1992. [30] Watts D J, Strogatz S H. Collective dynamics of ‘small-world’ networks. Nature, 1998, 393(6684): 440 doi: 10.1038/30918 [31] Barabási A L, Albert R. Emergence of scaling in random networks. Science, 1999, 286(5439): 509-512 doi: 10.1126/science.286.5439.509 [32] Neumann J. Theory of Self-reproducing Automata. Urbana: University of Illinois Press, 1966. [33] John Conway. Conway＇s game of life [Online], available: https://conwaylife.com/wiki/Conway%27s_Game_of_Life, June 25, 2022 [34] Langton C G. Artificial life in 1991 lectures in complex systems. Addison-Wesley Reading, 1992: 189-241 [35] Wolfram S. Random sequence generation by cellular automata. Advances in Applied Mathematics, 1986, 7(2): 123-169 doi: 10.1016/0196-8858(86)90028-X [36] Teruyam, Nakao Z, Chen Y W. A boid-like example of adaptive complex systems. In: Proceedings of the IEEE International Conference on Systems. Hawaii, USA: IEEE, 1999. 1−5 [37] Dorigo M, Birattari M, Stutzle T. Ant colony optimization. IEEE Computational Intelligence Magazine, 2006, 1(4): 28-39 doi: 10.1109/MCI.2006.329691 [38] Gilbert N, Troitzsch K G. Simulation for the Social Scientist 2nd Edition. Berkshire: Open University Press, 2005. [39] Swarm main page [Online], available: http://www.swarm.org, April 3, 2021 [40] Repastsource [Online], available: https://repast.github.io/index.html, April 1, 2021 [41] Parker M T. What is ascape and why should you care. Journal of Artificial Societies and Social Simulation, 2001, 4(1): 5 [42] Tisue S, Wilensky U. Netlogo: A simple environment for modeling complexity. In: Proceedings of the International conference on Complex Systems. Shanghai, China: 2004. 16−21 [43] Carl H, Steven C B. Artificial Societies: A Concept for Basic Research on the Societal Impacts of Information Technology. Santa Monica: RAND Corporation, 1991. [44] Nigel G. Rosaria Conte: Artificial Societies, the Computer Simulation of Social Life. London: University College London Press, 1995. [45] Epstein J M, Axtell R. Growing Artificial Societies: Social Science From the Bottom Up. Washington: Brookings Institution Press, 1996. [46] Arthur W B, Holland J, LeBaron B, Palmer R, Tayler P. Asset pricing under endogenous expectations in an artificial stock market. The Economy as an Evolving Complex System II. 1997: 15−44 [47] Basu N, Pryor R, Quint T. ASPEN: A microsimulation model of the economy. Computational Economics, 1998, 12: 223-241 doi: 10.1023/A:1008691115079 [48] Wang F Y. Shadow Systems: A New Concept for Nested and Embedded Co-simulation for Intelligent Systems. Tucson: University of Arizona, 1994. [49] Grieves M W. Virtually intelligent product systems: Digital and physical twins. Complex Systems Engineering: Theory and Practice, 2019. [50] Farsi M, Daneshkhah A, Hosseinian F A, Jahankhani H. Digital Twin Technologies and Smart Cities. Cham: Springer, 2020. [51] Wang F Y. Parallel system approach and management and control of complex systems. The Journal of Control and Decision, 2004, 19(5): 485-489 [52] Wang F Y. Toward a paradigm shift in social computing: The ACP approach. IEEE Intelligent Systems, 2007, 22(5): 65-67 doi: 10.1109/MIS.2007.4338496 [53] Wang F Y, Li X, Mao W. An ACP-based approach to intelligence and security informatics. Studies in Computational Intelligence, 2015, 563(1): 69-86 [54] Mei H. Understanding ‘software-defined’ from an OS perspective: Technical challenges and research issues. Science China Information Sciences, 2017, 60(12): 126101 doi: 10.1007/s11432-017-9240-4 [55] Busoniu L, Babuska R, Schutter B. A comprehensive survey of multiagent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, 2008, 38(2): 156-172 doi: 10.1109/TSMCC.2007.913919 [56] Xue X, Wang S F, Zhang L J, Feng Z Y, Guo Y D. Social learning evolution (SLE): Computational experiment-based modeling framework of social manufacturing. IEEE Transactions on Industrial Informatics, 2019, 15(6): 3343-3355 doi: 10.1109/TII.2018.2871167 [57] Wilensky U. Netlogo heatbugs model [Online], available: ht-tp://ccl.northwestern.edu/netlogo/models/Heatbugs. Novemb-er 16, 2020 [58] Schelling T C. Dynamic models of segregation. Journal of Mathematical Sociology, 1971, 1(2): 143-186 doi: 10.1080/0022250X.1971.9989794 [59] 张维. 计算实验金融研究. 北京: 科学出版社, 2010.Zhang Wei. Agent-based Computational Finance: An Alternative Way to Understand the Markets. Beijing: Science Press, 2010. [60] Carley K M, Gasser L. Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence. Cambridge: MIT Press, 1999. [61] Marathe M, Vullikanti A K S. Computational epidemiology. Communications of the ACM, 2013, 56(7): 88-96 doi: 10.1145/2483852.2483871 [62] 盛昭瀚. 社会科学计算实验理论与应用. 上海: 上海三联书店, 2009.Sheng Zhao-Han. Experimental Theory and Application of Co-mputing in Social Sciences. Shanghai: Shanghai Sanlian Book-store, 2009. [63] Lazer D, Pentland A, Adamic L. Social science. Computational social science. Science, 2009, 323(5915): 721-723 doi: 10.1126/science.1167742 [64] Lazer D M J, Pentland A, Watts D J. Computational social science: Obstacles and opportunities. Science, 2020, 369(6507): 1060-1062 doi: 10.1126/science.aaz8170 [65] Goodfellow I J, Pouget A J, Mirza M. Generative adversarial networks. Advances in Neural Information Processing Systems, 2014, 3:2672-2680. [66] Nigel G, Rosaria C. Artificial Societies: The Computer Simulation of Social Life. London: University College London Press, 1995. [67] Xue X, Chen F Y, Zhou D Y, Wang X, Lu M, Wang F Y. Computational experiments for complex social systems part I: The customization of computational model, IEEE Transactions on Computational Social Systems, 2021. [68] Mniszewski S M, Del Valle S Y. EpiSimS: Large-scale Agent-based Modeling of the Spread of Disease, LA-UR-13-23236, Los Alamos National Laboratory, United States Department of Energy, USA, 2013 [69] 邱晓刚, 陈彬, 张鹏. 面向应急管理的人工社会构建与计算实验. 北京: 科学出版社, 2017.Qiu Xiao-Gang, Chen Bin, Zhang Peng. Artificial Society Construction and Computational Experiment for Emergency Management. Beijing: Science Press, 2017. [70] Jain A K, Mao J, Mohiuddin K M. Artificial neural networks: A tutorial. Computer, 1996, 29(3): 31-44 doi: 10.1109/2.485891 [71] Whitley D. A genetic algorithm tutorial. Statistics and Computing, 1994, 4(2): 65-85 [72] Alavi M, Henderson J C. An evolutionary strategy for implementing a decision support system. Management Science, 1981, 27(11): 1309-1323 doi: 10.1287/mnsc.27.11.1309 [73] Kennedy J, Eberhart R. Particle swarm optimization. In: Proceedings of the ICNN International Conference on Neural Networks. Perth, Australia: 1995. 1942−1948 [74] Karaboga D, Akay B. A comparative study of artificial bee colony algorithm. Mathematics and Computation, 2009, 214(1), 108-132 doi: 10.1016/j.amc.2009.03.090 [75] Dodds P S, Watts D J. A generalized model of social and biological contagion. Journal of Theoretical Biology, 2005, 232(4): 587-604 doi: 10.1016/j.jtbi.2004.09.006 [76] Chen W, Yuan Y, Zhang L. Scalable influence maximization in social networks under the linear threshold model. In: Proceedings of the IEEE International Conference on Data Mining. Sydney, Australia: IEEE, 2010. 88−97 [77] Hoppitt W, Laland K N. Social Learning: An Introduction to Mechanisms, Methods, and Models. Washington: Princeton Uni-versity Press, 2013. [78] Bachelor G, Brusa E, Ferretto D, Mitschke A. Model-based design of complex aeronautical systems through digital twin and thread concepts. IEEE Systems Journal, 2020, 14(2): 1568-1579 doi: 10.1109/JSYST.2019.2925627 [79] Wang F Y, Zheng N N, Cao D. Parallel driving in CPSS: A unified approach for transport automation and vehicle intelligence. IEEE / CAA Journal of Automatica Sinica, 2017, 4(4): 577-587 doi: 10.1109/JAS.2017.7510598 [80] Li L, Lin Y L, Zheng N N. Artificial intelligence test: A case study of intelligent vehicles. Artificial Intelligence Review, 2018, 50(3): 441-465 doi: 10.1007/s10462-018-9631-5 [81] Montgomery D C. Design and Analysis of Experiments. Hobo-ken: John Wiley & Sons, 2017. [82] 崔凯楠, 郑晓龙, 文丁, 赵学亮. 计算实验研究方法及应用. 自动化学报, 2013, 39(8): 1157-1169Cui Kai-Nan, Zheng Xiao-Long, Wen Ding, Zhao Xue-Liang. Researches and applications of computational experiments. Acta Automatica Sinica, 2013, 39(8): 1157-1169 [83] Fang K T, Lin D K J, Winker P, Zhang Y. Uniform design: Theory and application. Technometrics, 2000, 42(3): 237-248 doi: 10.1080/00401706.2000.10486045 [84] Marcos L P. Machine Learning for Asset Managers. Cambridge: Cambridge University Press, 2020. [85] Xue X, Feng Z Y, Chen S Z, Zhou Z B, Qin C Z, Li B, et al. Service ecosystem: A lens of smart digital society. IEEE International Conference on Services Computing (SCC 2021), p263−273 [86] Xue X, Zhou D Y, Chen F Y, Yu X N, Feng Z Y, Duan Y C, et al. From SOA to VOA: A shift in understanding the operation and evolution of service ecosystem. IEEE Transactions on Services Computing, 2021. [87] Frow P, McColl-Kennedy J R, Hilton T, McColl-Kennedy J, Hilton T, Davidson A, et al. Value propositions-a service ecosystem perspective. Marketing Theory, 2014, 14(3): 327-351 doi: 10.1177/1470593114534346 [88] Vargo, S L, Maglio, P P, Akaka, M A. On value and value co-creation: A service systems and service logic perspective. European Management Journal, 2008, 26: 145-152 [89] Kil H, Oh S, Elmacioglu E, Nam W, Lee D. Graph theoretic topological analysis of web service networks, World Wide Web, 2009, (12): 321-343 [90] Huang K, Fan Y, Tan W. An empirical study of programmable web: A network analysis on a service-mashup system. In: Proceedings of the 19th International Conference on Web Services. Honolulu, USA: IEEE, 2012. 552−559 [91] 马于涛, 何克清, 李兵, 刘婧. 网络化软件的复杂网络特性实证. 软件学报, 2011, 22(3): 381-407 doi: 10.3724/SP.J.1001.2011.03934Ma Yu-Tao, He Ke-Qing, Li Bin, Liu Jing. Empirical evidence of complex network characteristics of networked software. Journal of Software, 2011, 22(3): 381-407 doi: 10.3724/SP.J.1001.2011.03934 [92] Grieves M. Digital twin: Manufacturing excellence through virtual factory replication. White paper, 2014, 1: 1-7 [93] Burt R S. Structural Holes: The Social Structure of Competition. Cambridge: Harvard university press, 2009. [94] Fischer R, Scholten U, Scholten S. A reference architecture for feedback-based control of service ecosystems. In: Proceedings of the 4th IEEE International Conference on Digital Ecosystems and Technologies. Dubai, United Arab Emirates: IEEE, 2010, 1−6 [95] Diao Y. Using control theory to improve productivity of service systems. In: Proceedings of the IEEE International Conference on Services Computing. Salt Lake City, USA: 2007. 435− 442 [96] Kahn H, Wiener A J. The next thirty-three years: A framework for speculation. Daedalus, 1967: 705-732 [97] Douglas H J. Time Series Analysis. Princeton: Princeton University Press, 2020. [98] 李大宇, 米加宁, 徐磊. 公共政策仿真方法: 原理, 应用与前景. 公共管理学报, 2011, 8(4): 8-20Li Da-Yu, Mi Jia-Ning, Xu Lei. Simulation methods for public policy: Principles, applications and prospects. Journal of Public Administration, 2011, 8(4): 8-20 [99] Bar-Yam Y. From big data to important information. Complexity, 2016, 21(S2): 73-98 doi: 10.1002/cplx.21785 [100] Zenil H, Kiani N A, Zea A A, J. Tegnér. Causal deconvolution by algorithmic generative models. Nature Machine Intelligence, 2019, 1(1): 58-66 doi: 10.1038/s42256-018-0005-0 [101] Yang M, Xiong Z J. Model validation – methodological problems in agent-based modeling, System Engineering – Theory & Practice, 2013, 33(6): 1458-1470 [102] Gao J, Zhang Y C, Zhou T. Computational socioeconomics. Physics Reports, 2019, 817: 1-104 doi: 10.1016/j.physrep.2019.05.002 [103] Lu M, Chen S Z, Xue X, Wang X, Zhang Y F, Wang F Y. Computational experiments for complex social system part II: The evaluation of computational model, IEEE Transactions on Computational Social Systems, 2021. [104] Sundberg R. Multivariate calibration-direct and indirect regression methodology. Scandinavian Journal of Statistics, 1999, 26(2): 161-207 doi: 10.1111/1467-9469.00144 [105] Werker C, Brenner T. Empirical Calibration of Simulation Models, Report No.0410. Papers on Economics and Evolution, Philipps University of Marburg, Germany, 2004 [106] Malerba F, Nelson R, Orsenigo L. ‘History-friendly’ models of industry evolution: The computer industry. Industrial and Corporate Change, 1999, 8(1): 3-40 doi: 10.1093/icc/8.1.3 [107] Markisic S, Neumann M, Lotzmann U. Simulation of ethnic conflicts in former jugoslavia. In: Proceedings of the Internati-onal Conference on Energy, Chemical, Materials Science. Kobl-enz, Germany: 2012. 37−43 [108] Ravi B, Miodownik D, Nart J. Rescape: An agent-based framework for modeling resources, ethnicity, and conflict. The Journal of Artificial Societies and Social Simulation, 2008, 11(27) [109] Laver M, Sergenti E. Party Competition: An Agent-based Mo-del. Princetion: Princeton University Press, 2012. [110] Paul E J. Agent-based modeling: What I learned from the artificial stock market. Social Science Computer Review, 2002, 20(2): 174-186 doi: 10.1177/089443930202000207 [111] Yeh C H, Yang C Y. Examining the effectiveness of price limits in an artificial stock market. Journal of Economic Dynamics and Control, 2010, 34(10): 2089-2108 doi: 10.1016/j.jedc.2010.05.015 [112] Xue X, Gao J J, Wang S F, Feng Z Y. Service bridge: Transboundary impact evaluation method of internet. IEEE Transactions on Computational Social Systems, 2018, 5(3): 758-772 doi: 10.1109/TCSS.2018.2858565 [113] Epstein J M. Modelling to contain pandemics. Nature, 2009, 460(7256): 687-687 doi: 10.1038/460687a [114] Schneider K A, Ngwa G A, Schwehm M. The COVID-19 pandemic preparedness simulation tool: CovidSIM. BMC Infectious Diseases, 2020, 20(1): 1-11 doi: 10.1186/s12879-019-4717-5 [115] Ghorbani A, Lorig F, Bruin B. The ASSOCC simulation model: A response to the community call for the Covid-19 pandemic [Online], available: https://rofasss.org/2020/04/25/the-asso-cc-simulation-model, April 1, 2021 [116] Pescarmona G, Terna P, Acquadro A, Pescarmona P, Russo G, Terna S. How can ABM models become part of the policy-making process in times of emergencies — The S.I.S.A.R. epidemic model [Online], available: https://rofasss.org/2020/10/20/sisar/, April 1, 2022 [117] Shi J C, Yu Y, Da Q. Virtual-taobao: Virtualizing real-world online retail environment for reinforcement learning. In: Proce-edings of the AAAI Conference on Artificial Intelligence. Haw-aii, USA: 2019. 4902−4909 [118] Zheng S, Trott A, Srinivasa S. The AI economist: Improving equality and productivity with ai-driven tax policies. arXiv pr-eprint arXiv: 2004.13332v1. 2004 [119] Peter D, Emmanuel S. The case for a progressive tax: From basic research to policy recommendations. Journal of Economic Perspectives, 2011, 25(4): 165-190 doi: 10.1257/jep.25.4.165 [120] Robert E, Kelli L. Decision making in a virtual environment: Effectiveness of a semi-immersive ‘Decision Theater’ in understanding and assessing human-environment interactions. AutoCarto. 2006, 8: 1922 [121] The decision theather. Arizona State University. [Online]. ava-ilable: http://dt.asu.edu/, April 1,2022 期刊类型引用(8)
1. Xiao Xue，Deyu Zhou，Xiangning Yu，Gang Wang，Juanjuan Li，Xia Xie，Lizhen Cui，Fei-Yue Wang. Computational Experiments for Complex Social Systems: Experiment Design and Generative Explanation. IEEE/CAA Journal of Automatica Sinica. 2024(04): 1022-1038 . 
必应学术2. Xiao Xue，Xiangning Yu，Deyu Zhou，Xiao Wang，Chongke Bi，Shufang Wang，Fei-Yue Wang. Computational Experiments for Complex Social Systems: Integrated Design of Experiment System. IEEE/CAA Journal of Automatica Sinica. 2024(05): 1175-1189 . 必应学术3. 林飞，王飞跃，田永林，丁显廷，倪清桦，王静，申乐. 平行药物系统：基于大语言模型和三类人的框架与方法. 智能科学与技术学报. 2024(01): 88-99 . 百度学术4. 赵汗青，葛岩，印闯，秦裕林. 疫情信息怎样影响疫情演化：一个计算实验模型. 国际新闻界. 2024(05): 133-159 . 百度学术5. 吕行，杜莉华，陈阳. “作为方法的时间”：基于过程性时间量化研究的框架重构与方法革新. 新闻与写作. 2024(07): 62-75 . 百度学术6. 张妮，蒲亦非. 基于元宇宙的立法社会实验. 四川大学学报(自然科学版). 2024(06): 250-260 . 百度学术7. Xiao Xue，Xiangning Yu，Fei-Yue Wang. ChatGPT Chats on Computational Experiments: From Interactive Intelligence to Imaginative Intelligence for Design of Artificial Societies and Optimization of Foundational Models. IEEE/CAA Journal of Automatica Sinica. 2023(06): 1357-1360 . 必应学术8. 宫远强，张业鹏，马万鹏，薛霄. 无人机蜂群中的群体智能涌现机理. 兵工学报. 2023(09): 2661-2671 . 百度学术其他类型引用(6)
-
下载:
计量
- 文章访问数: 3137
- HTML全文浏览量: 2311
- PDF下载量: 2038
- 被引次数: 14
