检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

基于格局检测的并行模型计数方法

吉林大学学报（工学版） 2020年第4期50卷 1443-1448页

作者：李壮刘磊张桐搏吕帅吉林大学计算机科学与技术学院长春130012

在经典的可满足性问题求解中,针对处理模型数较少的实例,SWcc迭代法和SWcc优化增量法与完备的模型计数方法相比,求解适用性更高,但SWcc迭代法和SWcc优化增量法均为串行求解方法,没有对解空间进行剪枝、化简等处理。本文基于此设计了基... 详细信息

在经典的可满足性问题求解中,针对处理模型数较少的实例,SWcc迭代法和SWcc优化增量法与完备的模型计数方法相比,求解适用性更高,但SWcc迭代法和SWcc优化增量法均为串行求解方法,没有对解空间进行剪枝、化简等处理。本文基于此设计了基于格局检测的并行模型计数算法。该算法以化简解空间和启发式为核心,将原解空间分解成为若干子空间并对原子句集进行化简后,并行处理各个子空间。实验结果表明:对于模型个数较少、公式规模较大的问题,该算法比原算法更具有适用性。

关键词：自动推理局部搜索模型计数格局检测并行框架

在线全文

学校读者我要写书评

暂无评论

结合格局检测与局部搜索的故障数据缩减方法

吉林大学学报（工学版） 2021年第6期51卷 2144-2153页

作者：欧阳丹彤张必歌田乃予张立明吉林大学计算机科学与技术学院长春130012 吉林大学符号计算与知识工程教育部重点实验室长春130012

针对集成电路故障诊断中故障数据缩减方法 N-cover存在冗余故障数据的问题,提出了结合格局检测与局部搜索的故障数据缩减方法。通过分析故障数据与端口覆盖次数的逻辑关系,提出了故障频率和故障覆盖度的概念以指导局部搜索。同时,结合... 详细信息

针对集成电路故障诊断中故障数据缩减方法 N-cover存在冗余故障数据的问题,提出了结合格局检测与局部搜索的故障数据缩减方法。通过分析故障数据与端口覆盖次数的逻辑关系,提出了故障频率和故障覆盖度的概念以指导局部搜索。同时,结合格局检测策略以避免重复搜索,进而通过减少冗余迭代来增加搜索广度。在标准测试用例上的实验结果表明,与现有方法相比,本文方法可有效缩减故障数据数目并提高求解效率。

关键词：人工智能故障诊断电路测试故障数据局部搜索格局检测

在线全文

学校读者我要写书评

暂无评论

基于格局检测的模型计数方法

软件学报 2020年第2期31卷 395-405页

作者：贺甫霖刘磊吕帅牛当当王强吉林大学计算机科学与技术学院吉林长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 吉林长春130012 西北农林科技大学信息工程学院陕西杨凌712100

模型计数是指求出给定命题公式的模型数,是SAT问题的泛化.模型计数在人工智能领域取得了广泛应用,很多现实问题都可以规约为模型计数进行求解.目前,常用的模型计数求解器主要有Cachet与sharp SAT,它们均采用完备方法且具有高效的求解能... 详细信息

模型计数是指求出给定命题公式的模型数,是SAT问题的泛化.模型计数在人工智能领域取得了广泛应用,很多现实问题都可以规约为模型计数进行求解.目前,常用的模型计数求解器主要有Cachet与sharp SAT,它们均采用完备方法且具有高效的求解能力,但其求解效率对模型数不敏感.有理由猜测:当给定问题的模型较少时,不完备算法可能发挥其效率优势而更适合模型计数.局部搜索是求解SAT问题的高效不完备方法,Cai等人提出了格局检测策略,并将其应用到局部搜索方法中,提出了SWcc算法,具有很高的求解效率.对SWcc算法进行扩充,分别得到了迭代法与优化后的增量法两种效率较高的不完备模型计数方法,给出了两种方法的思路和具体实现.最后给出了大量测试样例的实验结果,以验证当给定合取范式的模型较少时,该迭代法与优化后的增量法的求解效率有所提升.

关键词：模型计数局部搜索格局检测

在线全文

学校读者我要写书评

暂无评论

最优摄像头放置问题的局部搜索算法研究

最优摄像头放置问题的局部搜索算法研究

作者：王楷东北师范大学

学位级别：硕士

随着消费电子产品日新月异的发展以及社会对公共安全的迫切需求,摄像头网络已经从提供静态监视的早期角色,演变为当前的能够获取大量视频信息以进行智能处理的复杂网络系统,而且功能也不再是简单的监控用途,可以为后续的研究提供资源基... 详细信息

随着消费电子产品日新月异的发展以及社会对公共安全的迫切需求,摄像头网络已经从提供静态监视的早期角色,演变为当前的能够获取大量视频信息以进行智能处理的复杂网络系统,而且功能也不再是简单的监控用途,可以为后续的研究提供资源基础,例如目标识别、目标跟踪、姿态估计等。由于摄像头网络的规模逐渐庞大,需要覆盖的区域也更加复杂,如何降低摄像头网络的组网成本及如何提升目标空间的覆盖率已成为迫切需要解决的问题。因为摄像头放置问题的优化版本属于NP-hard,因此随着问题规模增大,求解耗时呈指数级增加。为了提高求解效率,本文设计了两个高效的局部搜索算法来求解该问题即ES-CCLS算法和MLSES-CC算法。首先,在第一个算法ES-CCLS中,本文通过分析研究问题的实例,使用离散数学中的知识总结出两条约简规则:（1）根据原问题建模形成的采样点被某一摄像头唯一覆盖,则该摄像头代表的集合一定在最优解中;（2）某一摄像头所能覆盖的采样点同时都在另一摄像头的监视视野中,即该摄像头代表的集合是另一摄像头代表的集合的子集,则该摄像头代表的集合一定不在最优解中。约简规则能在一定程度上降低原问题规模,进而提升求解时间。此外,ES-CCLS中采用了改进的格局检测技术。区别于传统的格局检测技术,针对该问题提出了基于集合元素覆盖状态的格局检测,可以使候选解在筛选的过程中速度更快更精确。其次,本文在ES-CCLS算法的基础上提出了改进版本的MLSES-CC算法。MLSES-CC算法新增了多层评价函数和动态多管线搜索。多层评价函数增加了对集合中覆盖超过1次的元素考虑,通过加权累加进评价函数。并且在此基础上提出了一种在单次局部搜索中进行多次交换的扰动方法。另外,MLSES-CC算法包含两条搜索管线,快速搜索管线使用单层评价函数用于快速收敛到局部最优解,动态多层搜索管线用于处理算法在一定的迭代周期内无法继续优化解时切换搜索空间即变邻域搜索。动态多管线搜索就是局部搜索迭代中动态选择合适的搜索管线。最后,本文针对所提出的两个算法分别在常见的基准测试集上进行验证,并选择与当前最好的几个算法对比。ES-CCLS算法在问题集求解数量上表现出优势,而MLSES-CC算法在问题集求解数量和效率上表现都更好。

关键词：最优摄像头放置问题集合覆盖问题组合问题优化局部搜索格局检测

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于个体稳定度博弈的动态社区发现算法研究

电子与信息学报 2017年第4期39卷 763-769页

作者：许宇光蒋飞朱恩强潘惊治谢惠扬北京大学信息科学技术学院北京100871 北京林业大学理学院北京100083

在动态网络中发现社区结构是一个复杂而又有重要意义的课题。该文针对动态网络中的社区发现问题,提出一种基于个体稳定度的博弈论方法(PDG)。在该博弈方法中,网络中的每个节点都是一个独立个体。个体会根据网络中的其他个体的状态,使用... 详细信息

在动态网络中发现社区结构是一个复杂而又有重要意义的课题。该文针对动态网络中的社区发现问题,提出一种基于个体稳定度的博弈论方法(PDG)。在该博弈方法中,网络中的每个节点都是一个独立个体。个体会根据网络中的其他个体的状态,使用最佳应对策略进行社区的选择。针对网络演化过程中的社区更新问题,该文提出了格局检测(Configuration checking)等优化策略,从而大大提高了演化网络的社区发现的效率。最后,在真实演化网络的实验中,与最新的静态和动态社区发现方法进行对比,验证了PDG方法的效率和效果。

关键词：动态社区发现稳定度模块度博弈论格局检测

在线全文

学校读者我要写书评

暂无评论

基于局部搜索的并行扩展规则推理方法

软件学报 2021年第9期32卷 2744-2754页

作者：李壮刘磊张桐搏周文博吕帅吉林大学计算机科学与技术学院吉林长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 吉林长春130012

扩展规则推理方法在经典的可满足性问题求解中已得到广泛应用,若干个基于扩展规则的推理方法已被提出,皆得到国内外的认可,例如完备的NER,IMOMH_IER,PPSER算法以及基于局部搜索的不完备算法ERACC等,都具有良好的求解效果.其中,ERACC算... 详细信息

扩展规则推理方法在经典的可满足性问题求解中已得到广泛应用,若干个基于扩展规则的推理方法已被提出,皆得到国内外的认可,例如完备的NER,IMOMH_IER,PPSER算法以及基于局部搜索的不完备算法ERACC等,都具有良好的求解效果.其中,ERACC算法是当前扩展规则求解器中求解效率最高、能力最强的算法.但是,串行的ERACC算法在启发式和预处理上仍然具有可提升的空间.基于此,设计了相应的并行框架,提出了PERACC算法.该算法基于格局检测的局部搜索方法,从变量赋初始值、化简解空间和启发式这3个阶段出发,将原极大项空间分解成为若干极大项子空间,并对原子句集进行化简后,并行处理各个子空间.通过实验显示:该算法与原算法相比,不仅在求解效率方面有较大提高,而且可以求解规模更大的测试用例,使扩展规则方法再次突破公式规模的限制.

关键词：自动推理局部搜索扩展规则格局检测并行框架

在线全文

学校读者我要写书评

暂无评论

基于IAPS的扩展规则局部搜索算法

电子学报 2020年第5期48卷 899-905页

作者：王金艳胡春牛当当李先贤广西多源信息挖掘与安全重点实验室(广西师范大学) 广西桂林541004 广西师范大学计算机科学与信息工程学院广西桂林541004 西北农林科技大学信息工程学院陕西杨凌712100

ERACC(Extension Rule Based on Accurate Configuration Checking)算法由杨洋等人基于扩展规则和格局检测提出,具有较高的推理效率.为进一步提高ERACC算法在大规模SAT(Satisfiability)问题求解上的性能,本文在搜索由极大项组成的空间时... 详细信息

ERACC(Extension Rule Based on Accurate Configuration Checking)算法由杨洋等人基于扩展规则和格局检测提出,具有较高的推理效率.为进一步提高ERACC算法在大规模SAT(Satisfiability)问题求解上的性能,本文在搜索由极大项组成的空间时,首先利用IMOM(Improved Maximum Occurrences on Clauses of Maximum Size)思想生成初始极大项,接着设计了适用于扩展规则推理的CCA_ER(Configuration Checking with Aspiration for Extension Rule-Based Reasoning)启发式策略,为极大项中格局信息未发生变化的变量对应文字提供一定的翻转机会.同时,为进一步提高扩展规则推理算法在k-SAT问题求解上的性能,设计了适用于扩展规则推理的PAWS_ER(Pure Additive Weighting Scheme for Extension Rule-Based Reasoning)策略,并且给出变量的Subscore_ER(Subscore for Extension Rule-Based Reasoning),CScore_ER(Comprehensive Score for Extension Rule-Based Reasoning)和HScore_ER(Hybrid Score for Extension Rule-Based Reasoning)属性.在此基础上,提出了ERACC_IAPS(ERACC with IMOM,CCA_ER,PAWS_ER and Subscore_ER)和CERACC_IAPS(ERACC with IMOM,CCA_ER,PAWS_ER,CScore_ER and HScore_ER)算法.实验结果表明:ERACC_IAPS和CERACC_IAPS算法的效率明显优于ERACC算法,最高可将其求解效率提高1000多倍.

关键词：扩展规则自动推理局部搜索格局检测

在线全文

学校读者我要写书评

暂无评论

基于局部搜索的模型计数方法研究

基于局部搜索的模型计数方法研究

作者：贺甫霖吉林大学

学位级别：硕士

模型计数问题是指求解出给定命题公式的模型数,是自动推理领域的重要难题。模型计数在人工智能领域取得了广泛应用,许多现实问题都可以规约为模型计数问题进行求解。目前常用的完备的模型计数求解器具有高效的求解能力,但其求解效率对... 详细信息

模型计数问题是指求解出给定命题公式的模型数,是自动推理领域的重要难题。模型计数在人工智能领域取得了广泛应用,许多现实问题都可以规约为模型计数问题进行求解。目前常用的完备的模型计数求解器具有高效的求解能力,但其求解效率对模型数不敏感。有理由猜测:当给定问题的模型较少时,不完备算法可能发挥其效率优势而更适合模型计数。本文旨在利用不完备方法的求解优势,设计出新的求解能力更强的模型计数求解方法。其中求解能力以正确求出给定合取范式模型的求解时间长短来衡量。局部搜索是求解SAT问题的高效的不完备方法,Cai等人提出了格局检测策略,并将其应用到局部搜索方法中提出了SWcc算法。格局检测策略定义了邻居变量,很好地解决了变量翻转过程中容易遇到的局部最优问题,具有很高的求解效率。本文对SWcc算法进行扩充分别得到了迭代法与增量法两种效率较高的不完备模型计数方法,给出了两种方法的思路和具体实现。SWcc算法每完成一次局部搜索的迭代计算过程,便可以得到一个可满足的全值指派。迭代法采用添加子句的方法,将刚刚得到的可满足指派的否定形式添加到原合取范式,解决了解的重复性问题,使得算法在每次迭代过程中都可以得到一个不同的可满足指派,并记录下可满足指派数目。增量法同样采用添加子句的方法,与迭代法不同的是,增量法在每次迭代结束后会计算相关变量的邻居信息,下一次翻转操作仍在当前指派上进行,从而减少了许多变量的初始化计算过程。为了进一步提升不完备算法的求解能力,本文提出了两种启发式策略,并将他们分别应用于迭代法与增量法。在迭代法的基础上添加了加速求解策略,给出了该策略的详细描述,理论上该算法适用于求解模型数目较多的合取范式,并且当求解可满足指派中有部分文字正负形式相同的合取范式时,求解效率会进一步提升。在增量法的基础上添加了解的优化策略,尽可能减少添加子句的变量数目,从而发挥了格局检测的优越性。最后,给出了大量测试样例的实验结果,实验结果表明,当给定合取范式的模型较少时,本文提出的迭代法与增量法的求解效率有所提升。本文提出的两种启发式策略在求解部分特定实例时,也会得到较好的求解效果。

关键词：模型计数局部搜索格局检测启发式策略自动推理

一种求解组合拍卖胜者决定问题的局部搜索算法

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

一种求解组合拍卖胜者决定问题的局部搜索算法

作者：张皓辰东北师范大学

学位级别：硕士

拍卖是一种竞价的买卖方式。传统的拍卖是将特定物品或财产权利转让给最高应价者。组合拍卖与传统拍卖不同,组合拍卖允许投标人在多个拍卖品中自由组合,给出总价格作为出价进行竞标,而不对其中物品单独给出价格。组合拍卖在电子商务、... 详细信息

拍卖是一种竞价的买卖方式。传统的拍卖是将特定物品或财产权利转让给最高应价者。组合拍卖与传统拍卖不同,组合拍卖允许投标人在多个拍卖品中自由组合,给出总价格作为出价进行竞标,而不对其中物品单独给出价格。组合拍卖在电子商务、空间分配、云计算等领域均有应用。而胜者决定问题又是组合拍卖领域的核心问题之一,有着重要的理论意义和实际应用价值。然而,胜者决定问题已经在理论上被证明是NP难问题,目前找不到多项式时间内求解的精确算法。精确算法虽然能证明输出解的最优性,但随着问题规模的扩大,它需要的求解时间将呈指数型增长,难以在可接受的时间里应对复杂的大规模实例。这类NP问题通常都需要依靠启发式算法进行近似求解,以达到可以在实际中应用的目的。局部搜索作为一类重要的启发式算法,具有简洁和高效的特点。局部搜索算法在多种NP问题求解中都有极好的表现。尽管它无法像精确算法一样给出最优解并证明其最优性,但在大规模实例上,局部搜索算法通常可以在更短时间内给出高质量的近似解。胜者决定问题在实际应用中十分重要,受到了很多关注。本文将设计和实现一种求解胜者决定问题的局部搜索算法,用于在短时间内求解较大规模的实例并使解质量尽可能提高。本文中提出的算法名为WDPLS。WDPLS基于一种高效且简明的局部搜索框架,并配有三种技术,分别为格局检测技术、自由出价技术和伪并列技术。格局检测技术是一种十分高效的用于局部搜索算法的防回溯策略。针对胜者决定问题,我们为WDPLS设计了适合该问题的格局定义,阻止算法贪婪搜索时发生回溯。在算法进行搜索时,可能会出现自由出价。这是一种特殊的出价,WDPLS优先选择自由出价以快速提升解质量。此外,在搜索过程中可能会遇到质量(得分)非常相似的落败出价。对于这些出价,伪并列技术阻止了算法过度贪婪地选择最高得分出价,从而为其他高质量出价提供了被选可能,进一步增加了解的多样性。在LG数据集上的大量实验表明,WDPLS在求解质量和求解时间上均领先于已发表的先进算法。特别地,尽管WDPLS在本文实验中被实现为单线程程序,但其在与多线程实现的算法CARA及商业求解器CPLEX相比时仍具有明显优势。同时,实验也展示出,以上三种主要技术都对WDPLS的性能有正面影响,证明了它们的有效性。

关键词：胜者决定问题局部搜索格局检测