基于有效实例的改进U树算法

计算机工程与科学

• 人工智能与数据挖掘 • 上一篇

基于有效实例的改进U树算法

宋佳佳，王作为

(天津工业大学计算机与软件学院，天津 300387）

收稿日期:2017-09-12 修回日期:2018-03-12 出版日期:2019-01-25 发布日期:2019-01-25

A modified U-tree algorithm

based on effective instances

SONG Jiajia,WANG Zuowei

(School of Computer Science and Software Engineering,Tianjin Polytechnic University,Tianjin 300387,China)

Received:2017-09-12 Revised:2018-03-12 Online:2019-01-25 Published:2019-01-25

摘要/Abstract

摘要：

传统U-Tree算法对于部分观测马尔可夫决策过程POMDP问题的解决已取得较为显著的成效，但是由于边缘节点生长过于随意,所以仍存在树的规模庞大、内存需求比较大、计算复杂度过高的问题。在原U-Tree算法的基础上，通过得到下一步观测值，来划分同一个叶子节点中做相同动作的实例，提出了一种基于有效实例来扩展边缘节点的EIU-Tree算法，大大缩减了计算规模,以此来帮助智能体更好更快地学习，并且在4×3经典栅格问题中做了仿真实验，对比于原有的U-Tree算法，该算法运行效果更好。

关键词: 部分观测马尔可夫决策过程, 强化学习, U-树, Q-学习算法

Abstract:

The traditional U-tree algorithm has achieved remarkable results in solving the problem of partially observable Markov decision process (POMDP), however, because of excessive random growth of fringe nodes, some problems such as large scale trees, large memory requirement and high computational complexity, still remain. Based on the original U-Tree algorithm, we classify the instances of the same leaf node which do the same action after obtaining the observation value, and propose an effective instance U-tree algorithm which extends fringe nodes based on effective instances. It greatly reduces computational scale to help the agent to learn faster and better. Simulation experiments are carried out on the classic 4×3 grid problem, and experimental results show that the algorithm outperforms the original u-Tree algorithm.

Key words: partially observable Markov decision process；reinforcement learning ；U-tree, Q-learning algorithm

宋佳佳，王作为. 基于有效实例的改进U树算法[J]. 计算机工程与科学.

SONG Jiajia,WANG Zuowei.

A modified U-tree algorithm

based on effective instances

[J]. Computer Engineering & Science.

[1]	庄述鑫, 陈永红, 郝一行, 吴巍炜, 徐学永, 王万元. 对抗环境中基于种群多样性的鲁棒策略生成方法[J]. 计算机工程与科学, 2024, 46(06): 1081-1091.
[2]	曾凡锋, 王春真, 李琛. 基于深浅层特征融合的无监督视频摘要算法研究[J]. 计算机工程与科学, 2023, 45(09): 1602-1610.
[3]	王扬, 陈智斌. 一种求解CVRP的动态图转换模型[J]. 计算机工程与科学, 2023, 45(05): 859-868.
[4]	彭坤彦, 尹翔, 刘笑竹, 李恒宇. 基于粒子群优化和深度强化学习的策略搜索方法[J]. 计算机工程与科学, 2023, 45(04): 718-725.
[5]	童钊, 叶锋, 刘碧篮, 邓小妹, 梅晶, 刘宏. 移动边缘计算中多约束下的任务卸载和资源分配算法[J]. 计算机工程与科学, 2020, 42(10高性能专刊): 1869-1879.
[6]	蔡钺, 游进国, 丁家满. 基于近端策略优化与对抗学习的对话生成[J]. 计算机工程与科学, 2020, 42(09): 1680-1689.
[7]	官蕊, 丁家满, 贾连印, 游进国, 姜瑛, . 基于强化学习的多样性文档排序算法[J]. 计算机工程与科学, 2020, 42(09): 1697-1703.
[8]	韩虎, 孙天岳, 赵启涛. 引入自编码机制对抗网络的文本生成模型[J]. 计算机工程与科学, 2020, 42(09): 1704-1710.
[9]	周碧莹1，王爱平1，费长江2，虞万荣2，赵宝康2. 基于强化学习的卫星网络资源调度机制[J]. 计算机工程与科学, 2019, 41(12): 2134-2142.
[10]	万谦1,2，刘玮1,2，徐龙龙1,2，郭竞知1,2. 基于Q-learning的不确定环境BDI Agent最优策略规划研究[J]. 计算机工程与科学, 2019, 41(01): 166-172.
[11]	闫雪飞,李新明,刘东,刘德生,李强. 基于强化学习的体系对抗仿真战役层次指控算法[J]. 计算机工程与科学, 2018, 40(08): 1511-1520.
[12]	王建军,刘玉林. 基于强化学习的自适应中间件在线更新机制研究[J]. J4, 2014, 36(08): 1462-1468.
[13]	黄晗文1，2，郑宇3. 强化学习中基于定性模型的知识传递方法[J]. J4, 2011, 33(6): 118-124.
[14]	沈〓乐，毛新军，董孟高. 基于强化学习的自适应多Agent系统的构造[J]. J4, 2011, 33(12): 72-77.
[15]	李琼，郭御风，蒋艳凰. 基于强化学习的智能I/O调度算法[J]. J4, 2010, 32(7): 58-61.

基于有效实例的改进U树算法

A modified U-tree algorithm

based on effective instances

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 15

编辑推荐

Metrics

本文评价