基于回跳层数的SAT求解器学习子句删除策略

目前学习子句删除策略广泛采用的是基于LBD的评估方式,LBD评估方式在每次执行删除时都会删除前一半LBD值大的学习子句,这种方式对LBD值大的学习子句的删除过于激进。针对此问题,提出了一种利用冲突回跳层数（back-jump levels）的评估方式来保留LBD值较大的相关学习子句。以CDCL（conflict driven clause learning）完备算法为框架,在子句删除环节形成了BJL删除算法。通过测试2017年SAT国际竞赛例,对新改进的版本与原版求解器进行了对比实验。实验表明,所提策略可显著提高求解器的求解性能和求解效率。     

基于学习子句删除策略的SAT求解器分支策略

对于SAT求解器,目前流行的分支变量决策策略大多是基于冲突的变量活跃度评估算法,选择具有最大活性的未赋值变量作为决策变量,优先解决最近的冲突.但是,它们都忽略了包含决策变量的子句数目对布尔约束传播(BCP)的影响.针对此问题,提出了 一种基于学习子句删除策略的分支变量决策策略(VDALCD),在删除学习子句的同时减小被删除子句中变量的活跃度.基于VDALCD策略分别对Glucose4.1,MapleLCMDistChronoBT-DL-v2.1进行改进,形成了求解器Glucose4.1_VDALCD和Maple-DL_VDALCD.以2018年、2019年SAT国际竞赛题为基准测试例,将改进版本与原版本求解器进行比较.实验结果表明,在2018年的例子测试中,Gluose4.1_VDALCD比Gluose4.1多求出26个例子,增加了 15.5％.在2019年的例子测试中,Maple-DL_VDALCD 比 MapleLCMDistChronoBT-DL-v2.1 多求出 17个例子,增加了 7.6％.     

基于参与冲突分析次数的动态学习子句评估策略

针对现有学习子句评估策略的单一性,提出一种基于学习子句参与冲突分析次数的评估策略,并将该策略分别与经典的文字块距离评估策略和活跃值评估策略结合,形成两个动态学习子句评估策略。基于2018年SAT国际竞赛部分基准实例,将动态评估策略与原评估策略进行参数适应性对比实验,并通过2018和2017年的基准实例进行评估。结果表明动态评估策略能更好地评估学习子句的质量,由此生成的求解器在求解数量和速度方面表现出较好的求解性能。     

基于动态奖惩的分支策略的SAT完备算法

针对学习子句数量有限或相似度高导致历史信息有限、搜索树不平衡的问题,提出了基于动态奖惩的分支策略。首先,对每次单子句传播的变元进行惩罚,依据变元是否产生冲突和产生冲突的间隔,确立不同的惩罚函数;其次,在学习阶段,利用学习子句确定对构造冲突有益的变元,非线性增加它们的活跃度;最后,选择活跃度最大的变元作为新分支变元。在glucose3.0算法基础上,完成了改进的动态奖惩算法——AP7。实验结果表明,相比glucose3.0算法,AP7算法的剪枝率提高了14.2%~29.3%,少数算例剪枝率的提高可达51%,且改进后的AP7算法相比glucose3.0算法,运行时间缩短了7%以上。所提分支策略可以有效降低搜索树规模,使搜索树更加平衡,减少计算时间。     

RLD演绎及子句蕴含与子句包含关系的非等价性

软件复用的一个主要任务是可复用软件构件的表示与检索，由于一阶逻辑能够描述软件构件的计算语义，因此用一阶逻辑表示构件及用基于归结原理的自动定量证明技术检索构件的研究在软件工程领域得到了足够的重视，为了简化基于演绎的构件检索技术的程序设计结构及提高演绎效率，提出了最右线性演绎RLD（rightmost linear deduction)，并证明了它的完备性，同时，指出了子句蕴含与子句包含关系的非等价性，并给出了由子句蕴含关系推出子句包含关系成立的一个充分条件。     

基于趋势强度的SAT问题学习子句评估算法

针对命题逻辑公式求解过程中难以有效评估学习子句是否有利于后续搜索的问题,提出了一种基于学习子句趋势强度的评估算法。该算法首先通过分析学习子句在生存期内参与冲突分析的时间分布特征,将随机、离散的时间分布转换为连续的累积趋势强度;然后在删除周期达到时,通过设定趋势强度阈值删除在后续搜索过程中“不大可能”被使用的子句,保留“可能”被使用的子句;最后采用2015年、2016年SAT问题国际竞赛实例,将该算法与经典的活跃度评估算法和文字块距离(LBD)评估算法进行对比。实验结果表明,趋势强度评估算法在效率上明显优于活跃度评估算法,且求解的实例更多,同时与LBD算法基本持平。     

命题逻辑的子句集中文字的分类

检测和消除命题逻辑公式中的冗余文字,是人工智能领域广泛研究的基本问题。针对命题逻辑的子句集中子句的划分,结合冗余子句和冗余文字的概念,将命题逻辑的子句集中的文字分为必需文字、有用文字和无用文字3类,并分别给出其定义。讨论3种文字与无冗余等价子集的性质,给出其等价子集的等价描述方法。得到题逻辑的子句集中必需文字、有用文字和无用文字的判定方法,借助子句集的可满足性得到3种文字与子句集的可满足性的等价条件。上述结果对命题逻辑中文字属性的判断提供了多种可选择方法,同时为命题逻辑公式的化简奠定了理论基础。     

基于长度约束区分矩阵的约简算法研究

粗糙集理论是机器学习和数据挖掘领域的重要课题之一,其中属性约简算法是该理论实现应用的主要算法。提出了一种基于长度约束区分矩阵的约简算法（RABDMLC算法）,通过抽样数据集计算平均区分矩阵项长,构造区分矩阵时不构造长于平均区分矩阵项长的项,在一定程度上提高了约简的效率。与基于属性频度函数的约简算法进行对比试验分析后,验证了该算法是有效和可行的。     

基于排队长度均衡的交叉口信号配时优化策略

城市交通的快速发展和交通需求的不断增长,使得城市交通拥堵日益严重,由此造成的时间延误和经济损失越来越大.鉴于此,提出了基于排队长度均衡的交叉口信号配时优化策略,根据排队长度均衡的控制思想,实时动态调整各相位绿灯时间,以达到排队长度均衡的控制目标,保证了绿灯时间的充分利用.通过近似动态规划方法的引入,使得该算法具有自学习和自适应的特性,不依赖于交通流模型.仿真结果验证了算法的有效性.     

基于变量混合特征的分支启发式策略

先进的SAT求解器能够通过有效的分支启发式策略解决大型应用实例.目前VSIDS策略是最具有代表性的基于冲突分析的分支策略,它因其稳健性而被广泛使用,但在每次冲突分析中其判定变量活性的增量方式过于单一.针对此问题,本文提出了一种基于变量混合特征的分支启发式算法,目的是充分地利用参与冲突分析的变量所携带的不同信息特征来区分变量,来进一步指导变量活性增长.并将所提出的分支策略算法嵌入到Glucose4.1中形成求解器Glucose4.1+MFBS,通过对比测试,实验结果表明改进的分支算法比原本的VSIDS策略,具有一定的优势,求解明显个数增加.     

基于前景理论和统计推断的区间数多准则决策方法

针对准则权重不完全确定且准则值为区间数的多准则群决策问题,提出一种基于前景理论的多准则决策方法。基于统计推断原理,以各准则下的方案值为样本推断其发生的概率,进而确定期望值参考点。基于区间数可能度确定价值函数,以方案区分度最大为目标构建非线性优化模型并确定方案排序。最后,通过实例分析表明了所提出方法的有效性和可行性。     

面向简化规则的集成学习模型及规则约简策略

随着机器学习模型的广泛应用,研究者们逐渐认识到这类方法的局限之处。这些模型大多数为黑盒模型,导致其可解释性较差。为了解决这一问题,以集成学习模型为基础,提出了一种基于规则的可解释模型以及规则约简方法,包括生成优化的随机森林模型、冗余规则的发现和约简等步骤。首先,提出了一种随机森林模型的评价方法,并基于强化学习的思想对随机森林模型的关键参数进行了优化,得到了更具可解释性的随机森林模型。其次,对随机森林模型中提取的规则集进行了冗余消除,得到了更加精简的规则集。在公开数据集上的实验结果表明,生成的规则集在预测准确率和可解释性方面均表现优秀。     

Heston模型中具有保费退回的确定缴费型养老金均衡投资策略

本文基于均方差准则研究了Heston模型中确定缴费型养老金(defined contribution,DC)计划的最优投资策略.假定养老金计划可投资于一种无风险资产和一种风险资产(股票),风险资产的价格服从收益率和波动率均为随机的Heston模型.此外,为了保护在基金积累阶段意外死亡的投保人的利益,假定保费可退回(给其继承人).本文在博弈论框架下给出了相应的HJB方程系统,并通过求解相应的HJB方程系统,得到了最优"时间一致"均衡投资策略以及均衡有效前沿的解析式.据我们所知,这是首次在具有保费退回的情形中研究Heston模型中DC计划的均方差均衡投资问题.文章最后分析了最优均衡投资策略和有效前沿的相关性质.