利用近似解加速求解SAT问题的启发式完全算法 被引量：5

1

作者 荆明娥 周电 +1 位作者 唐璞山 周晓方 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 2007年第9期1184-1189,共6页

结合DPLL完全算法能够证明可满足性(SAT)问题的不可满足性和局部搜索算法快速的优点,提出利用近似解加速求解SAT问题的启发式完全算法.首先利用局部搜索算法快速地得到一个近似解,并将该近似解作为完全算法的初始输入,用于其中分支变量... 结合DPLL完全算法能够证明可满足性(SAT)问题的不可满足性和局部搜索算法快速的优点,提出利用近似解加速求解SAT问题的启发式完全算法.首先利用局部搜索算法快速地得到一个近似解,并将该近似解作为完全算法的初始输入,用于其中分支变量的相位决策.该算法引导完全算法优先搜索近似解所在的子空间,加速解决器找到可满足解的过程,为SAT问题的求解提供了一种新的有效途径.实验结果表明,该算法有效地提高了决策的精度和SAT解决器的效率,对很多实例非常有效. 展开更多

关键词 SAT问题 完全算法 局部搜索 变量决策

下载PDF 职称材料

利用逻辑演绎求解SAT问题的启发式完全算法 被引量：6

2

作者 陈青山 徐扬 何星星 《西南交通大学学报》 EI CSCD 北大核心 2017年第6期1224-1232,共9页

为解决可满足性(satisfiability problem,SAT)问题求解过程中分支决策效率不高的问题,提出了一种基于逻辑演绎分组(logical deduction group,LDG)的启发式完全算法.该算法通过选择剩余未满足子句参与逻辑演绎,得到一组局部可满足赋值序... 为解决可满足性(satisfiability problem,SAT)问题求解过程中分支决策效率不高的问题,提出了一种基于逻辑演绎分组(logical deduction group,LDG)的启发式完全算法.该算法通过选择剩余未满足子句参与逻辑演绎,得到一组局部可满足赋值序列,并引导求解器优先搜索赋值序列所在解空间;对于可满足问题,可以通过迭代调用演绎过程,将局部可满足解成组地扩充为全局可满足解,对于不可满足问题,如果演绎结果出现空子句,则可以直接判定.采用SAT国际竞赛的实例,与具有代表性的指数级变元状态独立下降和(exponential variable state independent decaying sum,EVSIDS)变量决策算法进行了对比测试,结果表明:在求解总问题数方面,LDG比EVSIDS多出42个;在求解速度方面,LDG对可满足问题的求解时间相较EVSIDS平均减少了22.8%,对不可满足问题的求解时间平均减少了17.8%,总平均时间减少了20.1%. 展开更多

关键词 SAT问题 启发式算法 搜索算法 变量决策 演绎推理

下载PDF 职称材料

基于自适应变异遗传算法的多无人机航迹协同 被引量：3

3

作者 张劼 李宁洲 +1 位作者 张晓娟 卫晓娟 《火力与指挥控制》 CSCD 北大核心 2022年第11期18-23,共6页

为了降低多无人机协同的威胁代价,提高无人机群的环境生存率和任务成功率,以多无人任务机和无人支援机航迹协同为研究对象,描述时间与空间协同叠加、航程与威胁变量决策寻优的多无人机航迹协同实现过程。考虑任务航程与任务威胁的综合影... 为了降低多无人机协同的威胁代价,提高无人机群的环境生存率和任务成功率,以多无人任务机和无人支援机航迹协同为研究对象,描述时间与空间协同叠加、航程与威胁变量决策寻优的多无人机航迹协同实现过程。考虑任务航程与任务威胁的综合影响,提出多无人机航迹分段时序协同方法与协同模型。引入航程与威胁决策变量定义航迹代价协同函数,并构建基于近点与远点决策变量的协同函数模型,通过优化决策变量,实现多无人机最小航迹代价的路径寻优过程。为了满足航迹协同的实时性需求,提出利用自适应交叉率和变异率相结合的自适应变异遗传算法模型,实现航迹寻优过程的快速求解。通过半物理仿真试验,验证基于决策变量与改进遗传算法的多无人机航迹协同模型的有效性和实时性,可指导实际系统的构建与实现。 展开更多

关键词 多无人机 时序协同 航迹协同 变量决策 自适应变异算法

下载PDF 职称材料

启发式极性决策算法解SAT问题 被引量：3

4

作者 荆明娥 周电 +2 位作者 唐璞山 周晓方 张华 《中国科学（E辑）》 CSCD 北大核心 2007年第12期1597-1606,共10页

提出了一种启发式极性决策的可满足性问题(SAT)新算法.该算法继承了当前SAT解决器的许多策略:快速BCP、子句记录、重启动搜索等.同时,该算法通过预先根据Karnaugh图的覆盖分布计算变量极性,将其加入到DPLL的决策过程中,大大降低了搜索... 提出了一种启发式极性决策的可满足性问题(SAT)新算法.该算法继承了当前SAT解决器的许多策略:快速BCP、子句记录、重启动搜索等.同时,该算法通过预先根据Karnaugh图的覆盖分布计算变量极性,将其加入到DPLL的决策过程中,大大降低了搜索过程中的冲突次数.实验表明采用该算法的解决器——DiffSat,能够解决许多目前最有效的解决器Zchaff和MiniSat所不能解决的实例.尤其是对于Bart基准系列中的每个实例,DiffSat都能够在0.03s内解决,而Zchaff和MiniSat在给定的900s内不能够解决大部分实例.而且,DiffSat解决器在某些实例上的特性远远优于具有代表性的基于不完全随机算法的解决器DLM. 展开更多

关键词 可满足性问题 DPLL 完全算法 变量决策

原文传递

基于变量决策层的启发式变量选择策略

5

作者 刘姚 宋振明 《计算机与现代化》 2019年第7期20-24,96,共6页

启发式分支策略是SAT求解器中不可或缺的一部分,直接影响求解器的效率。早期的启发式分支决策需要遍历整个子句数据库,效率比较低。随着独立变量状态衰减和(Variable State Independent Decaying Sum,VSIDS)分支策略的出现,SAT求解器的... 启发式分支策略是SAT求解器中不可或缺的一部分,直接影响求解器的效率。早期的启发式分支决策需要遍历整个子句数据库,效率比较低。随着独立变量状态衰减和(Variable State Independent Decaying Sum,VSIDS)分支策略的出现,SAT求解器的效率有所提高,但VSIDS策略以及它的延伸策略中变量的增量都只是与变量的冲突次数有关,没有考虑变量的决策层在分支策略中的影响。因此当发生冲突时,如果与冲突有关的变量的得分相同而决策层不同时,对于变量的选择就具有随机性。基于此,本文在阐述变量的决策层的重要性之后在VSIDS策略的基础上,提出一种基于变量决策层的启发式变量选择策略--HSVDL策略。然后通过实例显示HSVDL策略在变量决策阶段选择决策层低的变量的可能性比选择决策层高的变量的可能性要大,而且得分比较小,减少了内存的占用。最后通过实验表明HSVDL策略能够求解出更多的实例,求解器的效率也有所提高,说明该策略有一定的优势。 展开更多

关键词 启发式分支策略 SAT求解器 VSIDS策略 HSVDL策略 变量决策

下载PDF 职称材料

基于粗糙集的多变量决策树构造方法 被引量：120

6

作者 苗夺谦 王珏 《软件学报》 EI CSCD 北大核心 1997年第6期425-431,共7页

本文利用粗糙集理论中条件属性相对于决策属性的核，解决多变量检验中属性的选择问题．另外，定义了２个等价关系相对泛化的概念，并将它用于解决多变量检验的构造问题．通过一个例子，对本文提出的多变量决策树方法与著名的单变量决策... 本文利用粗糙集理论中条件属性相对于决策属性的核，解决多变量检验中属性的选择问题．另外，定义了２个等价关系相对泛化的概念，并将它用于解决多变量检验的构造问题．通过一个例子，对本文提出的多变量决策树方法与著名的单变量决策树（ＩＤ３）方法进行了比较，结果表明前者比后者更简单．同时，对几种多变量决策树方法做了初步的对比分析． 展开更多

关键词 粗糙集 单变量决策树 多变量决策树 归纳学习

下载PDF 职称材料

一种多变量决策树方法研究 被引量：13

7

作者 梁道雷 黄国兴 金健 《计算机科学》 CSCD 北大核心 2008年第1期211-212,共2页

单变量的决策树算法造成树的规模庞大,规则复杂,不易理解。本文结合粗糙集原理中的相对核及加权粗糙度的方法,提出了一种新的多变量决策树算法。通过实例表明,本文的多变量决策树方法产生的决策树比传统的ID3算法构造的决策树更简单,具... 单变量的决策树算法造成树的规模庞大,规则复杂,不易理解。本文结合粗糙集原理中的相对核及加权粗糙度的方法,提出了一种新的多变量决策树算法。通过实例表明,本文的多变量决策树方法产生的决策树比传统的ID3算法构造的决策树更简单,具有较好的分类效果。 展开更多

关键词 多变量决策树 粗糙集 相对核 加权粗糙度

下载PDF 职称材料

一种可用于分类型属性数据的多变量决策树算法 被引量：17

8

作者 刘振宇 宋晓莹 《东北大学学报（自然科学版）》 EI CAS CSCD 北大核心 2020年第11期1521-1527,共7页

针对绝大部分多变量决策树只能联合数值型属性,而不能直接为带有分类型属性数据集进行分类的问题,提出一种可联合多种类型属性的多变量决策树算法(CMDT).该算法通过统计各个分类型属性的属性值在各个类别或各个簇中的频率分布,来定义样... 针对绝大部分多变量决策树只能联合数值型属性,而不能直接为带有分类型属性数据集进行分类的问题,提出一种可联合多种类型属性的多变量决策树算法(CMDT).该算法通过统计各个分类型属性的属性值在各个类别或各个簇中的频率分布,来定义样本集合在分类型属性上的中心,以及样本到中心的距离.然后,使用加权k-means算法划分决策树中的非终端结点.使用这种结点划分方法构建的决策树可用于数值型数据、分类型数据以及混合型数据.实验结果表明,该算法建立的分类模型在各种类型的数据集上均获得比经典决策树算法更好的泛化正确率和更简洁的树结构. 展开更多

关键词 决策树 分类型属性 多变量决策树 结点划分 K-均值

下载PDF 职称材料

面向分布式数据流大数据分类的多变量决策树 被引量：17

9

作者 张宇 包研科 +1 位作者 邵良杉 刘威 《自动化学报》 EI CSCD 北大核心 2018年第6期1115-1127,共13页

分布式数据流大数据中的类别边界不规则且易变,因此基于单变量决策树的集成分类器需要较大数量的基分类器才能准确地近似表达类别边界,这将降低集成分类器的学习与分类性能.因而,本文提出了基于几何轮廓相似度的多变量决策树.在最优基... 分布式数据流大数据中的类别边界不规则且易变,因此基于单变量决策树的集成分类器需要较大数量的基分类器才能准确地近似表达类别边界,这将降低集成分类器的学习与分类性能.因而,本文提出了基于几何轮廓相似度的多变量决策树.在最优基准向量的引导下将n维空间样本点投影到一维空间以建立有序投影点集合,然后通过类别投影边界将有序投影点集合划分为多个子集,接着分别对不同类别集合的交集递归投影分裂,最终生成决策树.实验表明,本文提出的多变量决策树GODT具有很高的分类精度和较低的训练时间,有效结合了单变量决策树学习效率高与多变量决策树表示能力强的优点. 展开更多

关键词 分布式数据流 大数据 分类 几何轮廓相似度 多变量决策树

下载PDF 职称材料

一类加权连续属性的多变量决策树构造方法 被引量：8

10

作者 黄定轩 武振业 《系统工程理论方法应用》 北大核心 2005年第1期80-83,96,共5页

首先利用粗集理论和模糊聚类理论确定连续多变量属性的选择问题,然后利用聚类中心算法建立等级标准中心以解决连续变量的区间划分问题,其次将等价关系相对泛化的概念用于决策树中多变量检验的构造。最后通过实例说明了本方法是可行的。

关键词 连续属性 多变量决策树 粗糙集 模糊聚类

原文传递

粗糙集用于建立基于多变量决策树的变压器故障诊断模型 被引量：5

11

作者 王楠 律方成 李和明 《电工电能新技术》 CSCD 2004年第1期21-24,33,共5页

采用决策树方法建立变压器故障诊断模型,可以方便地处理含有非数值特征的故障样本,且能够从样本中学习知识并简化知识,具有较好的适应性。但是采用单变量决策树描述复杂关系仍存在一定的局限性,本文提出基于多变量决策树的变压器故障诊... 采用决策树方法建立变压器故障诊断模型,可以方便地处理含有非数值特征的故障样本,且能够从样本中学习知识并简化知识,具有较好的适应性。但是采用单变量决策树描述复杂关系仍存在一定的局限性,本文提出基于多变量决策树的变压器故障诊断方法。并通过粗糙集辨识矩阵确定多变量检测特征选取,来实现多变量决策树的建立,能有效地约简知识,直观且易于理解。最后通过实例比较验证了方法的有效性。 展开更多

关键词 变压器 故障诊断 多变量决策树 粗糙集

下载PDF 职称材料

基于知识粗糙度的多变量决策树在变压器故障诊断系统中的应用 被引量：8

12

作者 黎静华 栗然 《电力自动化设备》 EI CSCD 北大核心 2005年第10期40-43,共4页

详细介绍了利用粗糙集的基本理论构造变压器的多变量故障决策树的具体过程,考虑了属性间的关联性,避免了生成决策树时故障特征的重复检测,适用于大量样本的自动处理,具有较好的自组织性和自适应性。通过粗糙集分辨矩阵确定多变量检测特... 详细介绍了利用粗糙集的基本理论构造变压器的多变量故障决策树的具体过程,考虑了属性间的关联性,避免了生成决策树时故障特征的重复检测,适用于大量样本的自动处理,具有较好的自组织性和自适应性。通过粗糙集分辨矩阵确定多变量检测特征的选取,将相对泛化的概念用于构造多变量检验,采用知识粗糙度作为选择决策树属性的度量,方便有效地解决了构造多变量故障决策树的关键问题。与传统的信息熵算法相比,基于知识粗糙度的决策树计算量大大减少,且可能得到最优的故障树。故障实例分析表明,该方法有效地简化了决策树,减少了故障信息的冗余性,诊断效率高,结果易于被人理解。 展开更多

关键词 电力变压器 故障诊断 粗糙集理论 知识粗糙度 多变量决策树

下载PDF 职称材料

基于粗集和熵的多变量决策树的构造算法 被引量：5

13

作者 罗秋瑾 马锐 《计算机应用》 CSCD 北大核心 2007年第7期1708-1710,共3页

多变量决策树是一种有效用于分类的数据挖掘方法,构造的关键是根据属性之间的相关性选择合适的属性组合作为节点。针对传统方法中用相对核进行多变量检验中属性选择存在的不足,首先对每个节点包含的属性个数加以限制,然后由重新定义的... 多变量决策树是一种有效用于分类的数据挖掘方法,构造的关键是根据属性之间的相关性选择合适的属性组合作为节点。针对传统方法中用相对核进行多变量检验中属性选择存在的不足,首先对每个节点包含的属性个数加以限制,然后由重新定义的属性依赖度和基于条件熵的距离函数选择相关的属性组合作为节点,从而提出一种新的构造算法。实例说明,该算法不仅有效降低了树的高度,而且还兼顾了分类的可读性。 展开更多

关键词 粗糙集 多变量决策 属性依赖度 条件熵 距离函数

下载PDF 职称材料

基于粗集的混合变量决策树构造算法研究 被引量：5

14

作者 胡学钢 张冬艳 《合肥工业大学学报（自然科学版）》 CAS CSCD 北大核心 2007年第3期257-260,共4页

文章提出混合变量决策树结构,并在此基础上提出基于粗集理论的混合变量决策树构造算法RSH2,算法在每个结点选择尽可能少的属性明确划分尽可能多的实例,减小了决策树规模,且易于理解。将RSH2算法与ID3算法及基于粗集的单变量决策树算法HA... 文章提出混合变量决策树结构,并在此基础上提出基于粗集理论的混合变量决策树构造算法RSH2,算法在每个结点选择尽可能少的属性明确划分尽可能多的实例,减小了决策树规模,且易于理解。将RSH2算法与ID3算法及基于粗集的单变量决策树算法HACRs进行实验比较,结果表明该算法有良好性能。 展开更多

关键词 单变量决策树 多变量决策树 粗糙集合 归纳学习

下载PDF 职称材料

基于知识粗糙度的多变量决策树的构建 被引量：6

15

作者 沙慧新 叶东毅 《福州大学学报（自然科学版）》 CAS CSCD 2004年第2期138-141,共4页

提出了一种基于粗糙集中知识粗糙度的构建多变量决策树的算法.基本思想是,在选择了核属性作为决策树的根节点后,将选择知识粗糙度最小的那个条件属性作为下一个分枝结点的检验属性.

关键词 知识粗糙度 核 多变量决策树 信息熵

原文传递

基于GIS和多变量决策树的地震滑坡道路中断风险应急评估模型 被引量：3

16

作者 白仙富 杨志全 +3 位作者 罗伟东 王杰 田鹏 戴雨芡 《地震研究》 CSCD 北大核心 2023年第3期343-353,共11页

在地震应急阶段,如何定量评估地震滑坡道路中断风险是一项亟待完善的关键技术。为解决这一难题,以2008年汶川M_(S)8.0地震、2014年鲁甸M_(S)6.5地震及2012年彝良M_(S)5.7、5.6地震为案例开展地震滑坡道路中断风险应急评估模型的构建和... 在地震应急阶段,如何定量评估地震滑坡道路中断风险是一项亟待完善的关键技术。为解决这一难题,以2008年汶川M_(S)8.0地震、2014年鲁甸M_(S)6.5地震及2012年彝良M_(S)5.7、5.6地震为案例开展地震滑坡道路中断风险应急评估模型的构建和检验。汶川研究区用来建立地震滑坡道路中断风险多变量决策树的应急评估模型,并对模型作有效性评价,鲁甸和彝良研究区用来对所建模型开展相似区域外延适用性的评价。通过P值检验模型统计学的显著性,使用Kappa值评价模型推断结果与实际情况的一致性。汶川研究区的P值为2.52×10^(-203),Kappa系数为0.91。说明使用模型计算出的道路中断风险是地震滑坡道路是否中断的良好指标。鲁甸和彝良研究区的P值为9.7×10^(-107),Kappa系数为0.81。这表明在允许一定误差的情况下,本研究建立的地震滑坡道路中断风险多变量决策树应急评估模型可以推广应用到其它类似地区。 展开更多

关键词 道路中断风险 地震滑坡 多变量决策树 应急评估

下载PDF 职称材料

基于决策类划分新型多变量决策树算法实例分析 被引量：5

17

作者 黄俊南 《齐齐哈尔大学学报（自然科学版）》 2015年第1期4-9,共6页

利用"基于决策类划分的新型多变量决策树算法"中的五大步骤,以"气象信息系统表"为实例构造多变量决策树,取得的结果与著名的单变量决策树(ID3)方法和粗糙集多变量决策树方法所获得的结果相同,证明本算法有效。其决... 利用"基于决策类划分的新型多变量决策树算法"中的五大步骤,以"气象信息系统表"为实例构造多变量决策树,取得的结果与著名的单变量决策树(ID3)方法和粗糙集多变量决策树方法所获得的结果相同,证明本算法有效。其决策树构造过程简单,易于理解。通过时间复杂度的比较,证明本算法优于粗糙集算法速度更优和ID3算法。 展开更多

关键词 单变量决策树 多变量决策树 决策表 集合运算 逻辑运算

下载PDF 职称材料

基于主成分分析的多变量决策树构造方法 被引量：5

18

作者 赵翔 刘同明 《计算机应用研究》 CSCD 北大核心 2005年第9期37-38,共2页

大多数决策树构造方法在每个节点上只检验单个属性,这种单变量决策树忽视了信息系统中广泛存在的属性间的关联作用,而且修剪时往往代价很大。针对以上两点,提出了一种基于主成分分析的多变量决策树构造方法,提取信息系统中的若干主成分... 大多数决策树构造方法在每个节点上只检验单个属性,这种单变量决策树忽视了信息系统中广泛存在的属性间的关联作用,而且修剪时往往代价很大。针对以上两点,提出了一种基于主成分分析的多变量决策树构造方法,提取信息系统中的若干主成分来构造决策树。实验结果表明,这是一种操作简单,效率很高的决策树生成方法。 展开更多

关键词 数据挖掘 单变量决策树 多变量决策树 主成分分析

下载PDF 职称材料

基于决策树的电网重要用户供电路径决策方法

19

作者 郭挺 杨悦荣 +5 位作者 徐良德 陈中豪 董红 杨梓晴 林舜江 刘明波 《电力科学与技术学报》 CAS CSCD 北大核心 2024年第2期53-63,共11页

广州等超大城市电网中110kV网架接线主要为3T接线,其运行方式多变,对电网的规划和运行有很大影响。超大城市电网中存在着大量的重要用户,其供电可靠性是安排电网运行方式的一个重要考虑因素。若安排的运行方式使得某些重要用户的供电路... 广州等超大城市电网中110kV网架接线主要为3T接线,其运行方式多变,对电网的规划和运行有很大影响。超大城市电网中存在着大量的重要用户,其供电可靠性是安排电网运行方式的一个重要考虑因素。若安排的运行方式使得某些重要用户的供电路径汇集在同一元件,就会大大降低重要用户的供电可靠性。基于此,建立超大城市电网重要用户供电路径优化决策模型,以最小化电网中220kV线路的平均负载率为目标,要求系统的每个重要用户都要满足多个供电路径来自最少2个不同的220kV变电站。为了快速求解此混合整数非线性规划模型,引入多变量决策树将模型转化成一个整数非线性规划问题,再通过变量代换将其转化为一个整数线性规划问题,实现快速准确求解。最后,以广州电网实际数据为例,验证所提优化决策模型和求解方法的可行性与有效性。 展开更多

关键词 重要用户 供电路径 3T接线 多变量决策树 线路负载率

下载PDF 职称材料

基于代价敏感支持向量机和多变量决策树的分级自适应暂态电压稳定评估

20

作者 甄永赞 阮程 《电网技术》 EI CSCD 北大核心 2024年第2期778-788,共11页

为解决暂态电压稳定评估中失稳工况漏判率高的问题、提升多变量决策树(multivariate decision tree,MDT)应用能力,提出一种分级代价敏感多变量决策树(hierarchical cost sensitive multivariate decision tree,HCS-MDT)评估方法。基于... 为解决暂态电压稳定评估中失稳工况漏判率高的问题、提升多变量决策树(multivariate decision tree,MDT)应用能力,提出一种分级代价敏感多变量决策树(hierarchical cost sensitive multivariate decision tree,HCS-MDT)评估方法。基于可量测电气量时空联合拓展构建特征,利用改进经验风险的代价敏感支持向量机(cost sensitive support vector machines,CS-SVM)作为MDT内部节点分类器,生成解析式组合特征判稳规则作为可视化决策依据,并能有效减少失稳漏判;将分级自适应(hierarchical self-adaptation,HSA)准则融入CS-MDT中进行暂态电压稳定评估,在提升早期评估能力的同时有效保障评估准确率。暂态电压稳定仿真算例验证了所提方法的有效性。 展开更多

关键词 暂态电压稳定 时空特征 代价敏感支持向量机 多变量决策树 分级自适应

下载PDF 职称材料