云资源调度的回答集程序描述性求解

针对求解难度为NP完全的基础设施即服务(IaaS)模式云资源调度问题,本文提出一种基于回答集程序(ASP)的描述性优化求解方法,并对其正确性进行分析。首先,把满足虚拟机CPU使用的情况下关闭尽可能多的主机做为减少云平台能耗的方法,将云资源调度问题形式化表述;其次,结合形式化描述以及减少云平台能耗的策略,将云资源调度问题用ASP编码为描述性(优化)问题,并分析其正确性;最后,在公开的PlanetLab数据集上进行实验,结果显示,ASP方法可在保障服务质量的同时减少集群能耗,最高可节能13%以上。这表明ASP方法在云资源调度问题上是有效的,从而提供一种易理解、易修改并能充分利用ASP最新工具成果的有效云资源调度新方法。

析取回答集程序设计结构化测试方法

针对析取回答集程序的结构化测试基础理论匮乏的问题,系统化地提出析取回答集程序结构化测试覆盖的概念。首先,定义针对析取回答集程序的测试用例,确立析取回答集程序的主要测试实体为程序中的逻辑规则;其次,通过对规则的头、规则的体、规则的集合等不同测试目标构建了规则覆盖、定义覆盖、环覆盖等基本概念来模拟结构化测试中的语句覆盖、分支覆盖等概念;最后,提出了析取回答集程序的测试覆盖率计算公式,并举例说明各种覆盖下的覆盖率计算方法,并讨论了析取回答集程序的部分特殊性质和关键指标。

E-R模型的回答集编程表示

作为一种广为接受的语义数据模型,E-R模型被广泛地应用于数据库设计阶段.但是E-R模型自身却存在某些缺陷,这些缺陷制约了对其进一步的应用.针对E-R模型的改进,目前主要存在基于图形表示和描述性逻辑表示两种途径.但是,前者仍然不具有自动推理能力,而后者却存在表示能力弱、与数据库兼容性不足等缺陷.为克服以上缺陷,提出一种利用回答集编程(answer set programming)表示E-R模型的新方法.首先,对应于数据库的E-R模式被区分为基本和扩展两种类型,并分别完成它们的语法与语义定义.其次,利用回答集编程完成以上两类模式的逻辑编程表示.最后,完成表示的正确性证明.提出的方法不仅为E-R模型提供了一种新的逻辑表示途径,而且相对原有的两种E-R模型改进途径具有明显的优势.更为重要的是该研究成果使得应用E-R模型实现异构数据库之间的语义协作成为可能.

一种基于回答集程序的三方协商新机制

提出了一种基于回答集程序的三方协商新机制,该机制采用回答集程序作为协商背景知识的表示工具.参与协商的两方在达成某些初步协议的基础上,通过从第三方获得利益补偿而选择放弃自己原先的一些需求,最终三方达成最优交易.证明了三方达成最优交易所采取的策略组合是纳什均衡的.

基于回答集编程的UML模型不一致性修正

为支持大规模工业应用的设计,研究统一建模语言(UML)中的不一致性修正问题,提出基于回答集编程的修正方法,处理类图和序列图之间的不一致性。采用逻辑程序表示UML图和固有约束规则,借助推理机求解得到回答集,该回答集能使UML图保持一致性,实例验证了该方法的有效性。

基于回答集编程的Banks选举求解方法

采用启发式算法的Banks选举在进行求解时执行效率较低。为解决该问题,提出一种基于回答集编程(ASP)的求解方法。通过建立Banks选举问题到ASP问题的映射,编写相对应的ASP,调用回答集求解器进行求解,得到的每一个ASP模型就是Banks选举问题的一个解。实验结果表明,当问题规模为200时,该方法的求解时间为4.196 s,求解效率高于手工启发式方法。

正规逻辑程序回答集存在性研究

判断逻辑程序的回答集是否存在是回答集程序设计的一个重要问题,也是NP完全问题。当前利用否定圈边数的奇偶性来判断回答集存在性的方法还具有一定的局限性,即:对于非分层逻辑程序,现有方法并不能准确判断其回答集存在性。针对该问题,提出了一种新的基于否定圈的判断方法,给出了该判断方法的算法框架,证明了算法的正确性,并以实例分析说明了方法的有效性。

提高回答集编程在家庭机器人仿真上求解效率初探

家庭机器人仿真比赛是由中科大发起的一项基于简单机器人模型在一定范围内实现任务规划的比赛.Answer Set Programming(回答集编程)是一种非单调逻辑编程技术,是在融合逻辑编程理论基础上发展而来的.独创性的提出合并关联原子动作来提高回答集编程的求解效率,并在家庭机器人仿真比赛中实现较高效率的自动规划.

带模理论的回答集程序设计（英文）

基于回答集语义的逻辑程序(ASP)是一种描述性问题求解的典范,目前人们提出了各种ASP的扩张。本文提出带背景理论的回答集程序设计框架,它不仅是正规逻辑程序的一般化,对带聚合函数的ASP而言,也与SPT-PDB的回答集语义一致。经证明,当背景理论是命题逻辑时,该框架与Shen和You提出的方法一致。

基于回答集语义复杂信息系统表单驱动需求规约的描述与验证

高品质的复杂信息系统软件设计与开发源自合理的、完整的和准确的软件需求.为了描述需求领域的非确定问题,并在需求获取不完全的情况下对需求规约进行非单调推理,本文将回答集逻辑程序和基于因果关系的动作理论应用于需求描述与验证.针对复杂信息系统需求问题空间规模较大的特点,将动作描述语言C与动作查询语言Q结合形成动作语言Lo,作为需求描述的基础;通过分析需求领域各个元素及其相互关系,以表单驱动引导需求,并作为需求描述依据与核心,提出了描述需求问题空间静态关系和动态行为关系的"主谓宾状"需求模型MRspoa.利用回答集逻辑程序求解器SMODELS,可以对需求规约进行多层次规划与检测.本文的研究来自工程项目实践的总结与提高,研究成果得到具体应用.

基于回答集程序的Slater选举求解方法

Slater选举是最优化问题,也是NP-hard问题,此类问题一般被认为不存在多项式时间的算法。考虑到其求解的复杂度与回答集求解的复杂度是一致的,为此,提出一种利用回答集程序(Answer Set Programming,ASP)求解Slater选举的新方法。首先,使用饱和技术为Slater选举建立逻辑上等价的ASP模型;其次,对模型进行正确性证明;最后,调用回答集求解器DLV求解Slater选举的具体实例,并在实验结果中说明其可行性。该方法不仅可求解Slater选举问题,而且在ASP中所使用的饱和技术还为其他同类的最优化问题提供了一种新的逻辑表示途径。

有序逻辑程序的回答集语义

为了统一并扩充回答集语义,在带有规则序的逻辑程序中,基于不动点原理,采用了处理优先序的新方法———直接在规则迭代过程中考虑规则序的作用.用此方法得到了9种不同的回答集语义,并讨论了各种语义之间的关系;证明了它们在包含意义下不是构成线序结构,而是一般的格结构;在层次逻辑程序中,该类回答集语义都退化为普通的回答集语义.

基于回答集程序的排课系统设计与实现

排课问题是典型的组合优化和NP完全问题。一个好的排课系统既需要能高效地求解排课问题,也需要能提供灵活的定义各种用户约束的方式,但现有的排课系统通常不能同时兼顾这两点。通过实现一个基于回答集程序的排课系统,较好地解决了这一问题。系统的前端接受用户的各种约束条件,并将其转换为回答集程序,后端调用回答集求解器实现排课问题的求解。实验表明,这种实现方式能适应排课条件的变化,具有灵活和可扩展的特点,并在可接受的时间内能排出教师满意度较高的课表。

回答集程序在语义网中的应用研究

语义网是一种能理解人类语言的智能网络,目的是完成基于语义的知识表示和推理。回答集程序(Answer Set Programming,简称ASP)是一种具有回答集语义的逻辑程序,因具有丰富的知识表达和推理能力,使其在语义网领域得到了广泛的研究和应用。本文对回答集程序在语义网中的应用研究情况作出简要的分析和总结,并对其应用前景进行展望。

一个带破圈启发方法的回答集编程系统(英文)

回答集编程(answer set programming,ASP)是一种回答集语义下的逻辑编程范例,可应用于非单调推理,叙述式问题求解等领域.本文为ASP提出并实现了一种破圈启发方法与一种基部限制式前向搜索过程,所得到的系统称为LPS.实验结果显示,相对于其他经典的ASP系统,LPS能够有效地解决处于相变难区域中的逻辑程序,通常这些程序被认为是计算困难的.除此以外,通过使用被称为动态变元过滤(dynamic variable filtering,DVF)的技术,LPS可以在计算过程中极大地缩小搜索树的尺寸.

一种改进的处理不一致的回答集程序的方法

回答集程序设计是一种描述性的程序设计范例,目前成为逻辑程序设计领域中一个很重要、很活跃的研究课题。在实际应用中,由于知识的不一致性,使得程序没有回答集。为解决该问题,朱涛等人提出了基于最小原理的思想,它可以很好地处理不一致的回答集程序,但是该方法会删除对用户来说很重要的知识,并且无法根据用户自己的偏好找到最满意的解。针对该问题,以加权逻辑程序为基础,使用加权定量的方法来处理不一致的回答集程序。通过为每一个规则分配权值,权值表示废除该规则所需的代价,废除规则代价之和最小的作为最优解,方便而简洁地解决了在无解情况下求解最满意解的问题。最后,与相关工作进行比较。

一种改进的回答集程序更新方法

回答集程序设计是一种描述性的程序设计范例,目前已经成为知识表示和推理的一个有力工具。在实际应用中,知识库中的信息可能发生动态改变,因此需要及时对知识进行更新。通过回答集程序的更新可以实现知识库的更新,并确保更新结果的一致性。J.P.Delgrande的程序修正方法可以实现回答集程序的更新,然而该方法中存在对原程序过度修正的问题。针对该问题,提出一种新的方法来更新回答集程序,该方法通过引入优先级和惯性规则的机制,实现了回答集程序的更新。实验结果表明,该方法克服了过度修正的问题,效果良好。最后,以一个实例说明了该方法的应用。

基于可能回答集程序的多Agent信念协调

多Agent系统(Multi-Agent System,MAS)是人工智能领域的一个非常活跃的研究方向。在多Agent系统中,由于Agent之间信念的差异,会不可避免地造成行动冲突。Sakama等提出的严格协调方法只适用于各Agent之间有共同信念的情境,当不存在共同信念时,此协调方法无解。针对该问题,文中提出了一种基于可能回答集程序(Possibilistic Answer Set Programming,PASP)的信念协调方法。首先,针对各Agent的不同信念集,基于加权定量的方法计算PASP的回答集相对Agent信念的满足度,以此来弱化某些信念,并且引入缺省决策理论推理得到Agent信念协调的一致解。然后,根据一致解建立一致的协调程序,将其作为Agent共同认同的背景知识库。最后,以dlv求解器为基础实现了多Agent信念协调算法,使Agent之间可以自主完成信念协调。文中以旅游推荐系统为例,说明该算法能够打破严格协调方法的局限,有效解决各Agent之间无共同信念时的协调问题。

回答集编程在RoboCup中型组的应用

在RoboCup MSL足球机器人中,教练机程序负责对机器人的单机任务和机器人之间的协作进行规划。在多机协作的过程中,由教练机导致的机器人之间的协作冲突会导致任务的失败。如何消解教练机中存在的冲突问题成为中型组研究的一个重点。回答集编程(ASP)作为逻辑编程的一种,近年来逐渐在RoboCup家庭组中得到应用。通过将ASP引入到中型组,某些特定情况下的协作冲突被有效消解,并且通过Matlab仿真,将原程序所产生的结果与ASP方法产生的结果进行比对,可以看到冲突被有效解决。

一类扩展的模糊描述逻辑回答集程序研究

本文介绍了模糊描述逻辑与回答集程序的发展现状和所遇到的挑战,讨论了模糊DL程序的语法和语义,给出了在模糊背景下扩展的Gelfond-Lifschitz变换,并进一步提出了一种面向语义Web的扩展模糊DL答集程序(efdl程序),给出该类程序的具体语法并用代数不等式约束来描述其语义。通过扩展的Gelfond-Lifschitz变换,定义了efdl程序的回答集,并且讨论了求解回答集的计算方法。