基于深度蒙特卡洛树搜索的拱坝仓面排序研究

合理的仓面排序方案对于加快工程进度和优化资源配置有着重要影响。然而,现有仓面排序方法将这一序贯决策问题简化,多数采用多属性决策方法,存在仅对大坝实时施工状态进行分析以及未考虑未来仓面浇筑方案对当前排序策略影响的问题;部分采用多目标优化方法进行仓面排序多目标优化问题分析,但主要是采用静态权重,存在忽略了仓面排序策略随环境动态变化的不足。针对以上问题,本文提出基于深度蒙特卡洛树搜索的拱坝仓面排序方法。首先,分析仓面排序问题的约束条件和目标函数,建立仓面排序强化学习模型;其次,针对仓面排序强化学习模型具有复杂且庞大的离散状态空间,为提高搜索效率,提出融合深度学习的蒙特卡洛树搜索方法,分别利用深度神经网络进行先验动作概率分布预测和策略函数评估;最后,以乌东德拱坝工程为例进行研究,结果表明本文方法可以有效地分析拱坝仓面排序问题,且相比于粒子群方法、证据理论方法,本文方法分析的施工工期可分别提前6天、14天,平均机械利用率分别提高1.19%、1.35%。本研究为拱坝仓面排序分析与优化提供了新思路。

基于蒙特卡洛树搜索的数值目标子群发现算法

MonteCloPi算法是一种基于蒙特卡洛树搜索(Monte Carlo tree search,MCTS)的任意时间子群发现算法,旨在使用MCTS策略构建非对称的最佳优先搜索树来发现高质量的多样性模式集,但是限制了目标为二值变量.为此,本文结合了数值目标的特点,通过为置信度上界(upper confidence bound,UCB)公式选取合适的C值、动态调整各个样本的拓展权重并对搜索树进行剪枝、使用自适应top-k均值更新策略,将MonteCloPi算法拓展到了数值目标.最后,在UCI数据集、全国健康与营养调查(national health and nutrition examination survey,NHANES)听力测试数据集上的实验结果表明本文的算法相比其他算法可以发现更高质量的多样性模式集,并且最优子群的可解释性也更好.

基于蒙特卡洛树搜索的视频异常场景监测方法

通过视频监控可以更快速地发现异常场景,并尽快制止违法暴力行动。为保证监测精度,文中设计一种基于蒙特卡洛树搜索的视频异常场景监测方法。首先对行人轨迹特征进行提取,计算目标预测位置与实际位置的空间距离,判定二者的相对位置,建立三级异常图像;再基于蒙特卡洛树搜索算法设计行人行为判别方法,构建不确定判别网络,标记残差函数,对数据进行归一化处理,同时获得激活函数以及函数的输出值;最后,设计视频异常场景监测算法,基于协方差矩阵将多个判别结果汇总成一个整体,并以此得到监控视频内异常场景的监测结果。该方法能够通过目标提取得到视频内的异常目标。目标识别精度的测试结果表明,所提方法在简单场景与复杂场景内的AUC值分别为0.952和0.886,说明其监测精度较高,在简单场景与复杂场景下均可正常使用。

给定预算下基于相对熵置信区间的蒙特卡洛树搜索最优动作识别算法

蒙特卡洛树搜索(Monte Carlo tree search, MCTS)将强化学习的反馈优化与生长树的动态规划相结合,在输出当前状态的最佳动作的同时极大地减少了计算量,因此成为开放环境下众多领域智能系统的关键通用方法.但由于计算资源匮乏或者计算成本昂贵等原因,完全充分地对树结构进行搜索是难以实现的,因此在有限的预算下高效合理地分配计算资源从而获得当前状态下的最优动作是目前研究的一个重要问题.现有大多数算法仅以识别准确率作为性能指标,通过实验对比验证算法性能,缺少对算法的识别误差和影响因素的分析,从而降低了算法的可信性和可解释性.针对该问题,选择基础核心的2名玩家、完全信息、零和博弈场景,提出了固定预算设定下MCTS抽象模型的最优行动识别算法DLU——基于相对熵置信区间的纯探索(relative entropy confidence interval based pure exploration).首先提出了基于相对熵置信区间的估值方法对叶子节点胜率进行估计,其可以从底层提高树节点估值准确性;其次给出了第1层节点值估计、最优节点选择策略以形成完整算法流程;然后推导了DLU算法的识别误差上界,并分析了算法性能的影响因素;最后在人造树模型和井字棋2种场景下验证算法性能.实验结果表明,在人造树模型上基于相对熵的算法类具有更高的准确度,且模型越复杂识别难度越高时,该算法类的性能优势越显著.在井字棋场景下,DLU算法能有效地识别最优动作.

基于改进蒙特卡洛树搜索的无人机目标分配与突防决策方法

针对多无人机任务规划问题,在多种约束与机动动作下,进行目标分配和突防决策统一建模与优化求解方法研究。首先,基于无人机自身优势、目标威胁以及突防概率分别建立目标分配优化函数和突防决策优化函数;然后,利用线性加权法将两者融合,形成多无人机协同任务规划统一目标函数;其次,在强化学习框架下,分阶段构建协同任务规划的状态空间和动作空间,并根据统一目标函数设计奖励函数;提出一种改进的蒙特卡洛树搜索强化学习算法,在统一目标函数最大收益下实现对无人机目标分配和突防决策问题的求解;最后,通过对比仿真实验验证所提出的方法的时效性和最优性。研究结果表明:相较于传统方法,所提出的方法在提升收敛程度的同时,将训练时间减少了15%。

基于蒙特卡洛树搜索算法实现轨道交通车辆多功能车辆总线周期调度表优化

目的:为改善轨道车辆MVB(多功能车辆总线)周期调度表的负载均衡度,提高MVB带宽利用率和车辆的通信系统实时性,需要对MVB周期调度表进行优化。方法:简述了MVB周期信息通信原理,明确了MVB调度表的2个约束条件,建立将MCTS(蒙特卡洛树搜索)算法应用于MVB调度表优化的理论方法,并通过Python软件编程实现该算法。明确了MCTS算法的优化目标,结合MVB调度表的约束条件设计了优化MCTS算法的预剪枝策略。选取了RMS(单调速率调度)算法、MCTS算法和GA(遗传算法)三种算法进行仿真试验,并对各算法的结果进行对比分析。结果及结论:优化后的MCTS算法有效避免了大量无效的搜索,搜索效率非常高。与RMS算法、GA相比,优化后的MCTS算法能在相同的搜索时间内获得更均衡的解。如果车辆通信设备增加,需要生成包含更多变量的调度表时,MCTS算法更能凸显其搜索优势。

基于蒙特卡洛树搜索的土石方动态调配算法及验证

针对堆石坝填筑进度控制以及土石方动态调运问题,受AlphaGo-Zero的启发,本文提出了一个基于蒙特卡洛树搜索(Monte Carlo tree search,MCTS)的土石方智能动态调配模型。该模型以当前累计填筑工程量、紧邻前一月份完成工程量以及当前月份为状态,用各月填筑工作面对应的填筑可达强度约束动作空间,综合考虑节点工期、总工期、坝面施工机械费用和土石方调运费用等因素构造奖励函数。此外,结合本文研究问题的特点,对MCTS迭代中的上限置信区间算法(upper confidence bound apply to tree,UCT)进行了改进和比较分析,最后以一个工程实例对本文提出模型的有效性进行了验证分析。结果表明,与施工仿真相比,以MCTS为框架的土石方动态调配模型的计算分析时间大大减少,为土石方动态调配问题提供了新的模型与手段。

基于蒙特卡洛树搜索的符号回归算法

为克服符号回归问题经典算法具有搜索时间过长和容易陷入局部最优的缺点,提出一种基于蒙特卡洛树搜索的符号回归算法。将符号空间划分为模型空间和系数空间;在深度策略网络指导下通过蒙特卡洛树搜索实现在模型空间内寻找合适数据集特征的公式模型;在此基础上,使用粒子群算法搜索公式模型下的系数空间,得到适应度最高的公式。实验结果表明,与GP算法相比,该算法具有适应度值更低、不易陷入局部最优的特点。

蒙特卡洛树搜索下的整合多目标可持续闭环供应链网络优化

针对现有可持续供应链网络中指标陈旧,且未能充分利用最新可持续指标对网络进行准确衡量与优化的问题,基于《CITI评价指南7.0》,提出一种将经济成本、合规整改与节能减排、绿色供应链、推动公众绿色选择、供应链沟通与透明5项指标进行层次分析加权整合的五位一体可持续闭环供应链网络模型,并设计了一种采用蒙特卡洛树搜索改进的分支定界算法MCTS_BB进行高效求解。首先,对5项指标按相互关联影响及隶属度关系进行归一化并构造多目标决策矩阵。然后,使用决策矩阵中最大特征值对应的特征向量对多目标函数进行线性组合,建立混合整数线性规划模型。最后,通过MCTS_BB中的分支选择、随机模拟搜索和剪枝策略求解模型。通过不同规模算例验证了模型和算法的有效性,实验结果表明,五位一体模型实现了多目标函数间的有效最优平衡,为各层级决策者对模型指标与参数进行统筹管理提供决策指导。

基于蒙特卡洛树搜索的众包概率规划

概率规划问题描述的是一个马尔科夫决策过程,其中的动作具有并行性和不确定性,从而导致概率规划问题的状态空间产生组合爆炸。过大的状态空间会降低规划器的效率,同时也会提高求解的难度。基于蒙特卡洛树搜索的众包概率规划可以将规划任务动态分配给多个规划器,由多个规划器共同对规划问题进行求解;同时使用蒙特卡洛树搜索算法构建前瞻树,通过前瞻树评估不同规划器返回的动作的质量。实验结果表明,随着时间限制放宽,该方法所求得的解的质量呈上升趋势;即使在相同条件下,该方法在求解效率和标准差上都有优势。

基于蒙特卡洛树搜索方法的空战机动决策

针对空战中双方的机动决策问题,考虑角度、距离、速度变化以及高度优势函数,以赢取最大空战优势期望为目标,建立了空战双方机动决策模型,并引入蒙特卡洛树搜索方法进行求解,搜索策略采取极大极小搜索算法。针对双机对抗,通过仿真给出空战态势及空战优势变化曲线,结果表明:我机在整个空战过程中绝大部分是处于优势地位的,验证了使用蒙特卡洛树搜索方法进行空战机动决策的可行性,同时对算法的实时性进行了仿真,计算机动动作所用时间众数位于50~100ms区间内,达到了实时性要求。

基于蒙特卡洛树搜索方法的空战机动决策

针对空战中双方的机动决策问题,考虑角度、距离、速度变化以及高度优势函数,以赢取最大空战优势期望为目标,建立空战双方机动决策模型,并引入蒙特卡洛树搜索方法进行求解,搜索策略采取极大极小搜索算法。针对双机对抗,通过仿真给出空战态势及空战优势变化曲线,结果表明我机在整个空战过程中绝大部分是处于优势地位的,验证了使用蒙特卡洛树搜索方法进行空战机动决策的可行性,同时对算法的实时性进行了仿真,结果表明算法计算机动动作所用时较短,达到了算法的实时性要求。

基于深度学习和蒙特卡洛树搜索的机组恢复在线决策

针对大停电后电力系统初始状态和恢复过程中线路恢复状况的不确定性,提出一种基于深度学习和蒙特卡洛树搜索(MCTS)的机组恢复在线决策方法。采用一种深度学习算法——稀疏自动编码器(SAE)对自动生成的训练集进行训练,建立估值网络;根据系统状态,利用改进的上限置信区间(UCT)算法、支路修剪技术和估值网络对机组恢复措施进行MCTS;汇总并行的多次MCTS结果,以加权机组发电量为决策指标确定最终的恢复措施。以新英格兰10机39节点系统和山东西部电网为例验证了所提方法的可行性和有效性;相比于传统方法,所提方法能够获得具有较高鲁棒性的恢复方案,并有效应对机组恢复过程中的多种不确定性状况。

双人博弈问题中的蒙特卡洛树搜索算法的改进

蒙特卡洛树搜索(MCTS)是一种针对决策类博弈游戏,运用蒙特卡洛模拟方法进行评估博弈策略的启发式搜索算法。但是,在面对计算机围棋这种复杂的决策过程时,简单的蒙特卡洛树搜索过程往往由于计算量大,收敛速度非常慢。由于双人博弈游戏中的蒙特卡洛树搜索不能收敛于双人博弈的最佳决策策略,因此提出蒙特卡洛树搜索结合极大极小值算法的改进算法,使得搜索结果不会因为蒙特卡洛方法的随机性而失真。为了进一步提高复杂双人博弈游戏中搜索算法的计算效率,还结合了几种常见的剪枝策略。实验结果说明,所提算法显著改进了蒙特卡洛树搜索的准确性和效率。

基于手牌拆分的“斗地主”蒙特卡洛树搜索

“斗地主”是典型的多人合作非完全信息博弈,蒙特卡洛树搜索是求解博弈(围棋、国际象棋等)问题的重要工具.本文首先提出基于“斗地主”规则的手牌拆分算法,通过选择较小拆分以解决其动作空间较大问题;其次,通过蒙特卡洛抽样法,对“斗地主”非完全合作博弈进行不断抽样模拟,在满足一定预设条件后,选择收益最佳的节点作为本次最佳决策.实验结果表明,基于手牌拆分的“斗地主”蒙特卡洛树搜索能较好地实现“斗地主”自动博弈.

面向多智能体博弈的并行蒙特卡洛树搜索算法研究

蒙特卡洛树搜索算法是一种常用的强化学习算法,博弈过程中动态空间的指数级增长是制约该算法学习效率的因素。基于并行方法对蒙特卡洛树搜索算法进行优化,提出基于胜率估值传递的并行蒙特卡洛树搜索算法。改进后的并行博弈搜索策略框架包含一个主进程和多个子进程,其中子进程用于探索,主进程根据子进程传递的胜率估值数据进行决策。结合多智能体博弈平台Pommerman进行实验验证,与传统的蒙特卡罗树搜索算法相比,并行蒙特卡罗树搜索算法有效提高了资源利用率、博弈胜率及决策效率。

基于蒙特卡洛树搜索的全域指挥控制协同

面向未来全域联合作战概念下的智能化指挥控制协同需求,重点研究针对具体作战任务的作战单元协同,通过利用复杂网络建模方法,构建指挥控制协同网络模型,并设计3种指挥控制协同模式.在此基础上,借鉴强化学习思想,提出基于蒙特卡洛树搜索的指挥控制协同算法,来实现指挥控制协同决策过程的最佳策略选择,最终生成面向具体任务的最优作战簇,降低指挥控制协同网络的搜索代价,提高全域指挥控制协同的智能化水平.以联合反舰作战为背景,通过仿真实验,构建不同指挥控制协同模式下的指挥控制协同网络,并验证基于蒙特卡洛树搜索的指挥控制协同算法的有效性.

基于蒙特卡洛树搜索的电缆线径控制

针对具有滞后特性的线径控制系统,提出一种基于蒙特卡洛树搜索(MCTS)的线径控制器。采用改进型最小二乘法对线径控制系统的输入输出数据进行拟合得到预测模型,在此基础上,利用蒙特卡洛树搜索算法对系统进行寻优控制。将该控制器与传统控制器(PID、模糊PID和动态矩阵)进行仿真对比实验,实验结果表明,该控制器在牺牲一定训练学习时间的代价下,控制效果明显优于传统控制器。采用该控制器的线径控制系统,响应速度和收敛速度更快,几乎没有超调,有一定的实用性。

基于蒙特卡洛树搜索的通用博弈系统的构建与优化研究

【背景】作为人工智能的主要研究领域,通用博弈策略(General Game Playing,简称GGP)旨在构建具有通用智能的博弈系统。这些系统能够基于给定的博弈规则在没有人为干涉的情况下成功地进行多个甚至是全新构造的博弈。【目的】与专门的博弈系统不同,通用博弈系统所使用的策略生成算法并不针对特定博弈,而是能够根据给定的博弈规则自动生成博弈策略的具有通用性的算法。GGP发展至今已成为检测人工智能水平,特别是通用智能发展的重要研究领域。如何构建高效的通用博弈系统是GGP研究的主要问题。【文献范围】通用博弈策略的生成算法是构建通用博弈系统的关键技术。目前所使用的主流算法是蒙特卡洛树搜索算法及其变种。这类算法在工作过程中并不依赖特定的博弈信息,因而被广泛地应用于GGP领域。然而,由博弈规则推导出来的关于博弈的专门信息,往往对建立针对这一博弈的有效决策算法具有重要的作用。【方法】为此,本文通过在蒙特卡洛树搜索算法上增加记忆结构来存储在线博弈过程中的实时信息,用记忆结构中博弈状态的相似状态来估计该状态的好坏,以提高状态评估的准确性。【结果】本文基于这一方法构建了通用博弈系统并对其性能进行了全面地评估。实验结果表明,与原始的蒙特卡洛方法相比,本文所构建的通用博弈系统在决策水平和效率上都有显著提升,特别在双人信息对称的零和回合制博弈中胜率保持在55%以上,且其性能随着博弈规模的增大而显著提升,在Connect 5、Breakthrough等大规模的游戏上有着绝对优势,即达到100%胜率。【结论】这表明本文所提出的方法通过利用博弈的专门信息能够有效地提升蒙特卡洛树搜索算法的性能。

基于蒙特卡洛树搜索的仿真足球防守策略研究

针对Robocup仿真足球比赛中本位点区域化跑位的局限性,在三角剖分的阵型设计基础上将蒙特卡洛树搜索算法引入2D仿真中,将球员智能体在球场上的状态定义为博弈树节点,将双方球员的动作选择视为节点间的状态转移,对于球队的防守任务建立蒙特卡洛树模型。利用极坐标方式对球场进行区域分割,结合Q学习与蒙特卡洛树搜索中的信心上限树算法(Upper Confidence Bound Apply to Tree of Monte Carlo)进行球队训练,将训练结果的动作评估值用于优化比赛代码,使得球队的防守能力得到了较大程度的提升。