在基于模型诊断中,诊断解通常是根据极小冲突集合簇进行相应的计算得到所有的极小碰集,所以提高极小碰集的求解效率是模型诊断的核心问题.因此提出结合基于元素覆盖集合度(degree of element coverage,DOEC)极小化策略的SAT求解极小碰...
详细信息
在基于模型诊断中,诊断解通常是根据极小冲突集合簇进行相应的计算得到所有的极小碰集,所以提高极小碰集的求解效率是模型诊断的核心问题.因此提出结合基于元素覆盖集合度(degree of element coverage,DOEC)极小化策略的SAT求解极小碰集的方法 SAT-MHS(satisfiability problemminimal hitting sets).首先,方法SAT-MHS将碰集求解问题转换成SAT问题,即把所有的冲突集合以子句形式表示成SAT的输入CNF进行迭代求解.其次,提出比现有的基于子超集检测极小化策略(sub-superset detecting minimization,SSDM)更为高效的DOEC极小化策略进行极小化处理.由实验数据可见,与SSDM极小化策略相比,其优点是缩减了求解空间和迭代求解次数,尤其当求解规模较大问题时,其极小化效率越高.主要是因为其极小化不会随着待求解问题规模的增加而增加,而是只与冲突集合簇的大小相关,因此时间复杂度较低.实验结果表明,对于一些较大的实例,与目前效率最好的Boolean方法相比,SAT-MHS方法高效且易于实现,求解速度能提高10～20倍,DOEC极小化策略对比传统SSDM极小化策略能达到40倍左右.
行动器评判器(Actor Critic,简称AC)算法是强化学习连续动作领域的一类重要算法,其采用独立的结构表示策略,但更新策略时需要大量样本导致样本效率不高.为了解决该问题,提出了基于模型学习和经验回放加速的正则化自然AC算法(Regularized Natural AC with Model Learning and Experience Replay,简称RNAC-ML-ER).RNAC-ML-ER将Agent与环境在线交互产生的样本用于学习系统动态性对应的线性模型和填充经验回放存储器.将线性模型产生的模拟样本和经验回放存储器中存储的样本作为在线样本的补充,实现值函数、优势函数和策略的更新.为了提高更新的效率,在每个时间步,仅当模型的预测误差未超过阈值时才利用该模型进行规划,同时根据TD-error从大到小的顺序对经验回放存储器中的样本进行回放.为了降低策略梯度估计的方差,引入优势函数参数向量对优势函数进行线性近似,在优势函数的目标函数中加入2-范数进行正则化,并通过优势函数参数向量来对策略梯度更新,以促进优势函数和策略的收敛.在指定的两个假设成立的条件下,通过理论分析证明了所提算法RNAC-ML-ER的收敛性.在4个强化学习的经典问题即平衡杆、小车上山、倒立摆和体操机器人中对RNACML-ER算法进行实验,结果表明所提算法能在大幅提高样本效率和学习速率的同时保持较高的稳定性.
暂无评论