检索结果-南通市图书馆

基于子句权重学习的求解sat问题的遗传算法

在线全文

学校读者我要写书评

暂无评论

计算机学报 2005年第9期28卷 1476-1482页

作者：凌应标吴向军姜云飞中山大学信息科学与技术学院广州510275

该文提出了一种求解sat问题的改进遗传算法(satWAGA).satWAGA算法有多个改进性特点:将sat问题的结构信息量化为子句权重,增加了学习算子和判定早熟参数,学习算子能根据求解过程中的动态信息对子句权重进行调整,以便防止遗传进程的早熟,... 详细信息

该文提出了一种求解sat问题的改进遗传算法(satWAGA).satWAGA算法有多个改进性特点:将sat问题的结构信息量化为子句权重,增加了学习算子和判定早熟参数,学习算子能根据求解过程中的动态信息对子句权重进行调整,以便防止遗传进程的早熟,同时,算法还采用了最优染色体保存策略,防止进化过程的发散.该文最后描述了实现包括satWAGA等多个算法的实验系统,对选择最佳早熟判定参数值给出了一些有效的建议.实验结果表明:与一般遗传算法相比,satWAGA算法在求解速度、成功率和求解问题的规模等方面都有明显的改善.

关键词： sat问题遗传算法子句权重早熟

在线全文

学校读者我要写书评

暂无评论

求解sat问题的分级重排搜索算法

软件学报 1996年第4期7卷 201-210页

作者：刘涛李国杰国家智能计算机研究开发中心

局部搜索法在ＳＡＴ问题上的成功运用已引起越来越广泛的重视，然而，它在面对不可满足问题例时的局限性不能不被考虑．分级重排搜索算法ＭＳＲＡ（ｍｕｌｔｉ－ｓｔａｇｅｓｅａｒｃｈｒｅａｒｒａｎｇｅ－ｍｅｎｔａｌｇｏｒｉｔｈｍ... 详细信息

局部搜索法在ＳＡＴ问题上的成功运用已引起越来越广泛的重视，然而，它在面对不可满足问题例时的局限性不能不被考虑．分级重排搜索算法ＭＳＲＡ（ｍｕｌｔｉ－ｓｔａｇｅｓｅａｒｃｈｒｅａｒｒａｎｇｅ－ｍｅｎｔａｌｇｏｒｉｔｈｍ）正是为克服局部搜索法的不完备性而提出的，准确地讲，它是几种算法在思想上的集成，但为明确起见，把其最典型的分级重排过程作为名称．分级重排搜索算法在求解ＳＡＴ问题时，能表现出优于单一求解策略（如局部搜索法或回溯算法）的明显特性．由于可根据约束条件的强弱来估计ＳＡＴ问题例的可满足性，因此能够以此来确定更有效的求解策略．

关键词： sat问题局部搜索法 MSRA 算法

在线全文

学校读者我要写书评

暂无评论

O(m^2)时间求解sat问题的随机算法

计算机学报 2001年第11期24卷 1136-1141页

作者：徐云陈国良许胤龙顾钧中国科学技术大学计算机科学与技术系合肥230027 香港科技大学计算机系香港

传统的求解 sat问题的随机算法主要是对满足解进行搜索 ,在找不到满足解的情况下 ,则无法正确判断问题的可满足性 .该文提出了两个时间复杂度为 O( m2 )求解 sat问题的随机算法 sat Test1和 sat Test2 ,这里 m为CNF公式中的子句数 .这... 详细信息

传统的求解 sat问题的随机算法主要是对满足解进行搜索 ,在找不到满足解的情况下 ,则无法正确判断问题的可满足性 .该文提出了两个时间复杂度为 O( m2 )求解 sat问题的随机算法 sat Test1和 sat Test2 ,这里 m为CNF公式中的子句数 .这两个随机算法是通过对不满足解数的估计来判断 sat问题的可满足性 ,不同于传统的随机算法 .其中第二个算法 sat Test2在搜索满足解的同时又可以对不满足解数进行估计 ,是对传统随机算法的重要改进 .试验结果表明 ,文中提出的算法对相变区域的难 sat实例有较好的求解能力 .

关键词： sat问题随机算法数学期望 NP问题计算机

d-正则(k,s)-sat问题的NP完全性

在线全文

学校读者我要写书评

暂无评论

软件学报 2020年第4期31卷 1113-1123页

作者：符祖峰许道云贵州大学计算机科学与技术学院贵州贵阳550025 安顺学院电子与信息工程学院贵州安顺561000

研究具有正则结构的sat问题是否是NP完全问题,具有重要的理论价值.(k,s)-CNF公式类和正则(k,s)-CNF公式类已被证明存在一个临界函数f(k),使得当s≤f(k)时,所有实例都可满足;当s≥f(k)+1时,对应的sat问题是NP完全问题.研究具有更强正则... 详细信息

研究具有正则结构的sat问题是否是NP完全问题,具有重要的理论价值.(k,s)-CNF公式类和正则(k,s)-CNF公式类已被证明存在一个临界函数f(k),使得当s≤f(k)时,所有实例都可满足;当s≥f(k)+1时,对应的sat问题是NP完全问题.研究具有更强正则约束的d-正则(k,s)-sat问题,其要求实例中每个变元的正负出现次数之差不超过给定的自然数d.通过设计一种多项式时间的归约方法,证明d-正则(k,s)-sat问题存在一个临界函数f(k,d),使得当s≤f(k,d)时,所有实例都可满足;当s≥f(k,d)+1时,d-正则(k,s)-sat问题是NP完全问题.这种多项式时间的归约变换方法通过添加新的变元和新的子句,可以更改公式的子句约束密度,并约束每个变元正负出现次数的差值.这进一步说明,只用子句约束密度不足以刻画CNF公式结构的特点,对临界函数f(k,d)的研究有助于在更强正则约束条件下构造难解实例.

关键词： d-正则(k,s)-CNF公式 sat问题 NP完全性

利用逻辑演绎求解sat问题的启发式完全算法

在线全文

学校读者我要写书评

暂无评论

西南交通大学学报 2017年第6期52卷 1224-1232页

作者：陈青山徐扬何星星西南交通大学信息科学与技术学院四川成都610031 西南交通大学系统可信性自动验证国家地方联合工程实验室四川成都610031

为解决可满足性(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问题启发式算法搜索算法变量决策演绎推理

基于OpenMP的并行遗传算法求解sat问题

在线全文

学校读者我要写书评

暂无评论

西南交通大学学报 2019年第2期54卷 428-435页

作者：吴贯锋徐扬常文静陈树伟徐鹏西南交通大学信息科学与技术学院四川成都610031 西南交通大学系统可信性自动验证国家地方联合工程实验室四川成都610031 西南交通大学数学学院四川成都610031

为了提高sat (boolean satisfiability)问题求解效率,在OpenMP (open multi-processing)编程框架下,将遗传算法与局部搜索算法结合,改进了混合遗传算法中的选择算法,将原有选择操作的时间复杂度降低到O(N)级别.算法采用OpenMP中的编译... 详细信息

为了提高sat (boolean satisfiability)问题求解效率,在OpenMP (open multi-processing)编程框架下,将遗传算法与局部搜索算法结合,改进了混合遗传算法中的选择算法,将原有选择操作的时间复杂度降低到O(N)级别.算法采用OpenMP中的编译制导语句#pragma omp parallel粗粒度并行化驱动混合遗传算法,采用#pragma omp single语句块实现了子种群间个体的同步迁移操作.与同类算法HCGA (hybrid cloud genetic algorithm)比较分析表明:改进算法HGA (hybrid genetic algorithm)以及并行后的混合遗传算法CGPHGA(coarse-grained parallel hybrid genetic algorithm)在求解成功率和求解效率上都有显著提高,部分问题求解成功率提高达5倍.

关键词： sat问题 OpenMP 并行混合遗传算法粗粒度模型

在线全文

学校读者我要写书评

暂无评论

求解sat问题的量子免疫克隆算法

计算机学报 2007年第2期30卷 176-183页

作者：李阳阳焦李成西安电子科技大学智能信息处理研究所西安710071

将量子计算应用于人工免疫系统中的克隆算子,提出了一种基于量子编码的免疫克隆算法(Quantum-InspiredImmuneClonalAlgorithm,QICA)来求解sat问题,并从理论上证明了算法的全局收敛性.算法中采用量子位的编码方式来表达种群中的抗体,针... 详细信息

将量子计算应用于人工免疫系统中的克隆算子,提出了一种基于量子编码的免疫克隆算法(Quantum-InspiredImmuneClonalAlgorithm,QICA)来求解sat问题,并从理论上证明了算法的全局收敛性.算法中采用量子位的编码方式来表达种群中的抗体,针对这种编码方式采用量子旋转门和动态调整旋转角度策略对抗体进行演化,加速原有克隆算子的收敛;利用克隆算子的局部寻优能力强的特点,在各个子群体间采用量子交叉操作来增强信息交流,提高种群的多样性防止早熟.实验中,用标准satLIB库中的3700个不同规模的标准sat问题对QICA的性能作了全面的测试,并与单纯的量子遗传算法和简单免疫克隆算法以及著名的Walksat和PFEA2算法进行比较,仿真实验表明:QICA具有更高的成功率和运算效率.对于具有250个变量、1065个子句的sat问题,QICA也仅用了1.357s,显示出了优越的性能.

关键词：量子编码遗传算法人工免疫系统克隆算子 sat问题

在线全文

学校读者我要写书评

暂无评论

求解sat问题的多智能体社会进化算法

计算机学报 2014年第9期37卷 2011-2020页

作者：潘晓英焦李成刘芳西安邮电大学计算机学院西安710121 西安电子科技大学智能感知与图像理解教育部重点实验室西安710071 西安电子科技大学计算机学院西安710071

基于Agent社会合作机制以及智能体对环境的感知和反作用能力提出了一种新的求解sat问题的多智能体社会进化方法MASEA（Multi-AgentSocialEvolutionaryAlgorithm）。该方法在多智能体进化思想的基础上，引入人类社会“关系网模型”的概... 详细信息

基于Agent社会合作机制以及智能体对环境的感知和反作用能力提出了一种新的求解sat问题的多智能体社会进化方法MASEA（Multi-AgentSocialEvolutionaryAlgorithm）。该方法在多智能体进化思想的基础上，引入人类社会“关系网模型”的概念来建立智能体所能感知的邻域环境；同时在保留原有的竞争算子和自学习算子前提下，根据智能体具有竞争协作的特性，设计了一个新的算子---协作算子来共同完成整个进化过程。以标准satLIB库中变量个数从20～250的3700个不同规模的标准sat问题以及基于RB模型所产生的随机实例对MASEA的性能进行了全面的测试，并与其他一些具有较高性能算法的结果进行了比较。结果表明，MASEA具有更高的成功率和更高的运算效率。

关键词：多智能体系统进化算法关系网模型 sat问题协作算子

在线全文

学校读者我要写书评

暂无评论

量子协同免疫算法用于sat问题的求解

系统工程与电子技术 2009年第6期31卷 1441-1445页

作者：吴秋逸李阳阳焦李成西安电子科技大学智能信息处理研究所和智能感知与图像理解教育部重点实验室陕西西安710071

根据协同策略和量子免疫计算理论,提出一种求解sat问题的量子协同免疫算法。该算法在将sat问题转化为函数优化问题的基础上,采用多个子种群。分别采用量子比特编码来表达个体,采用通用的量子旋转门策略演化个体,采用量子交叉操作阻止早... 详细信息

根据协同策略和量子免疫计算理论,提出一种求解sat问题的量子协同免疫算法。该算法在将sat问题转化为函数优化问题的基础上,采用多个子种群。分别采用量子比特编码来表达个体,采用通用的量子旋转门策略演化个体,采用量子交叉操作阻止早熟收敛;各种群独立演化,同时引入量子协同理论,采用协同算子使得算法的搜索效率更高。实验采用标准satLAB库中的3 700个不同规模的问题对算法进行测试,并与简单克隆选择算法、量子遗传算法、量子免疫克隆选择算法进行比较。结果表明,量子协同免疫算法的平均成功率最高,平均运行时间和平均评价次数最少。

关键词： sat问题量子编码人工免疫系统协同理论