一个基于最小冲突修补的动态约束满足求解算法

约束满足问题是人工智能中一个重要的研究方向,近年来,对动态变化的约束满足问题的研究逐渐成为该领域的热点.在目前该领域最流行的LC算法基础上,引入禁忌搜索策略,提出了一个基于最小冲突修补的算法Tabu-LC.算法在每次冲突调整时将所有冲突变量看成一个整体,并采用分支定界搜索策略求解冲突变量组成的子问题,极大地提高了求解效率.同时,在约束求解系统"明月1.0"架构下给出了算法的具体实现,并针对大量随机问题进行了对比实验.结果表明,Tabu-LC算法在求解效率和解的质量上都明显优于LC算法.

一种识别最小冲突集的实用方法

应用Ｒｅｉｔｅｒ提出的基于第一原理的诊断方法解决连续系统多故障诊断问题的难点是有效地识别最小冲突集合组。文章针对工业过程控制系统的特点，提出一种实用算法。首先根据系统的结构和传感器分布等不变知识，离线识别最小冲突集候选；然后根据测量数据，使用约束悬挂和约束传播技术，在线确定最小冲突集合组。算法是完备的，且大大节省时间资源。

基于源树的MPLS最小冲突路径多播算法

维护多播信息需要额外的硬件开销,多播体系结构缺乏可扩展性,限制了多播业务的发展。本文在多播中应用MPLS最小冲突路径算法,在分支节点的MPLS中加入多播信息表,实现基于源树的多播树构建,从而解决了MPLS多播中数据转发的标签分配问题,具有良好的扩展性。实验表明,利用MPLS最小冲突路径算法,起到了节约带宽和提高多播性能的作用。

混洗交换网络中最小无冲突路由分组的生成方法

为了解决混洗交换网络中冲突路由的分组问题,定义了路由的无冲突极大组、最小无冲突分组、特征函数及覆盖函数等概念,并基于这些概念提出了应用布尔代数计算最小无冲突分组的理论和方法。同时,为提高冲突路由分组的效率,提出了计算最小无冲突分组的近似算法。理论分析和实验表明,近似算法不仅具有良好的时间性能,而且具有较高的准确度,它为在大规模信息交换中实施分批路由策略提供了强有力的支撑。

用布尔代数方法计算最小碰集

在基于模型的诊断中 ,模型一般都是用布尔代数来表示 ,而计算碰集 (hittingsets)则采用HS 树或图 ,这就使得诊断系统采用多种不同的数据结构 ,给编程实现带来了不便 .本文用布尔代数变量表示待诊断系统的部件 ,并给出了用布尔代数直接计算最小碰集的算法 .数据结构更为简单 ,只需要布尔表达式 ,相当于字符串 ,效率上比其他的一些研究结果也要好 ,同时可克服丢失正确解的问题 。

用对分HS-树计算最小碰集

在基于模型的诊断中,利用冲突集计算最小碰集是其关键的步骤,因为所有冲突集的最小碰集就是所考察系统的诊断.在Reiter的方法中,要用HS-树(图)来计算最小冲突集的最小碰集.HS-树的计算量比较大,且又会因为剪枝的问题而剪掉真实解.提出了用对分HS-树(binary hitting set-树,简称BHS-树)计算最小碰集的方法.这种方法的优点是:(1)产生的树的节点数明显少于HS-树,因而效率较高;(2)解决了因为剪枝而产生的最小碰集丢失的问题;(3)在新增加冲突集时不必完全重新计算,只需在原BHS-树的基础上增加新的分支即可,这种性质对实际诊断问题是特别有用的.对利用BHS-树的算法从理论上进行了分析和论证,并通过实际编写程序进行了检验.

两种高效局部搜索算法求解RB模型实例

RB(revised B)模型是一种在约束可满足问题中具备精确相变增长域的随机实例模型,提出两种高效的启发式局部搜索算法用于解决RB模型生成的大值域约束可满足问题。首先为基于权重指导搜索的W-MCH算法,该算法通过约束判断和违反约束数计分来进行搜索,并引入了基于约束违反概率的权重计算公式,根据其关联的约束权重进行修正,再对变量进行迭代调整。然后提出最小化值域的MDMCH算法,该算法通过记录违反约束和逐步消除已违反约束变量的启发式策略来减少搜索空间,并在最小化后的变量域内重新校准变量赋值,进而有效提高算法的收敛速度。此外,还提出了融入模拟退火策略的WSCH和MDSCH算法,这两种算法都能根据变量的表征特点对变量域进行针对性的搜索。实验结果表明,与多种启发式算法相比,这两种算法在精度与时间效率方面均呈现明显提升,在复杂难解的实例中能够提供高效的求解效率,验证了算法的有效性和优越性。

基于模型诊断中用逻辑数组计算最小碰集

在基于模型诊断中 ,冲突集的最小碰集就是诊断目标 .提出用二维逻辑型数组计算冲突集的最小碰集的一种新的算法 .

递归建立HS-树计算最小碰集

在基于模型的诊断中,广泛地使用冲突集来计算最小碰集的算法诊断。现有的HS-树,HST-树,BHS-树等算法普遍存在实现的困难。文章提出用递归算法建立平衡的二叉HS-树(Recursivehittingset-树,简记为RHS-树)计算最小碰集的方法,在空间复杂性与时间复杂性上能够满足大多数诊断系统中的要求。

冲突网络驱动的反向迭代创新设计过程模型

提出了一种冲突网络驱动下的反向迭代产品创新设计过程模型。通过产品需求分析和TRIZ进化理论建立产品的理想解(IFR)集合,确定对应于IFR的最小冲突集合C,之后运用TRIZ的问题解决工具解决C中的冲突及新衍生的冲突,反复迭代的结果可以获得产品完整的概念设计方案。通过一个工程实例对该过程模型进行了验证和说明。

侦讯双方人际和谐关系定位及其实现路径

在侦查讯问场域中,侦讯双方人际关系如何定位,直接关涉讯问中的互动方式及讯问目的的实现。传统理论下侦讯双方是对抗关系,现行相关研究中存在相对兼相容关系论、相容关系论、谈判关系论、平等协作关系论、融洽关系论、沟通关系论等不同主张,但都未能精准把握讯问人际交往的特殊性,应转向定位于构建和维持人际和谐关系。讯问场域中的人际和谐,归属低等级良好人际关系和工具型和谐的范畴,其心理结构由致同性、相容性和参与性构成。转向人际和谐关系将有助于规范讯问方式,预防和减少人际冲突,提升收集案件信息质效;并且侦讯双方也具有人际和谐的关系基础。为此,需要实现讯问理念转向,特别是从强化天然对抗性转向人际冲突最小化;优化讯问法律规则,降低因制度弊病而引发人际冲突可能性;定制包括接纳讯问对象、调节立场差距、适度自我披露、建立共性基础、增权自主陈述、说服转变态度在内的相配套的讯问策略。

基于集合递推运算的最小hitting集算法

提出一种最小hitting集算法,以满足基于模型故障诊断中诊断解的计算.采用集合递推运算计算了最小hitting集合,并证明了该算法可得到最小冲突集合组的全部最小hitting集合.实验表明,该算法程序容易编制、运算迅速快,可以明显地提高诊断效率,对于复杂的被诊断对象系统可以满足实时性要求.

基于模型诊断的集合逻辑运算法计算最小碰集

在基于模型的故障诊断仿真系统的诊断流程中,由最小冲突集计算最小碰集是整个流程中的关键步骤。针对现有计算最小碰集方法中存在的缺陷,提出了运用集合逻辑运算法计算最小碰集,将冲突集表示为集合的逻辑"与"、逻辑"或"运算,通过其运算法则进行运算简化,可得到全部的最小碰集。该方法具有简单有效、数据结构简单、计算简便快捷和易于程序实现等优点。最后通过实例计算,验证了该算法的正确性、简单性和高效性。

离散二进制粒子群算法在基于模型配电网故障诊断中的应用

提出一种基于模型的配电网故障诊断方案,该方案首先根据配电网原理模型的仿真数据和实际观测值存在的差异得到极小冲突集,然后由离散二进制粒子群优化算法推出可能的故障元件和故障形式,最后由贝叶斯方法确定概率最高的诊断结论。通过实际建模、编程和实验证明了该方案的可靠性和有效性。仿真结果表明,与HS-Tree、Boolean Algebra方法、遗传算法等算法相比,离散二进制粒子群算法搜索效率更高,可节约1/3～1/2的搜索时间,并且可以避免当问题规模较大时出现内存溢出问题。

基于模型的配电网故障诊断关键问题研究

现有配电网故障诊断方法主要是根据故障后保护装置产生的报警信息,断路器的状态变化信息来推断可能故障位置和类型,属于后验故障诊断方法。基于模型诊断方法(Model-based diagnosis,MBD)则直接利用电压电流等量测量来判断故障元件,可以在保护装置和断路器动作前进行故障定位,具有一定的故障预警功能。给出一个完整的基于模型的配电网诊断方案,采用优化的离散二进制粒子群算法(BPSO,Binary Particle Swarm Optimization)求取冲突集的最小碰集,诊断识别过程中以贝叶斯后验概率形式量化了候选诊断的衡量标准,从而降低诊断过程中的不确定度。最后以某10kV配电网为诊断实例,通过实际建模、编程和实验,取得了良好的效果。

基于模型诊断的贝叶斯解释及应用

在基于模型诊断的基础上 ,建立了贝叶斯模型 .该模型首先假设系统的所有状态都是可能发生的 ,并对系统中的各个元件设定一个先验概率 .当系统的观测与预期不符合时 ,利用最小冲突集的概念得到系统可能的状态 .之后根据各个系统状态的对应概率计算出元件发生故障的后验概率 ,该后验概率本质上是一个边缘概率分布 ,它在数值上表示了元件发生故障的可能性 ,确定了故障查找顺序 .用一个数字故障电路的实例验证了该方法的有效性 。

牵引变电站故障的基于模型诊断方法

现有牵引变电站所应用的故障诊断系统多是基于专家经验的专家系统,但是基于经验的专家系统不能诊断经验之外的故障,系统的移植和维护也比较困难。提出一种牵引变电站故障的基于模型诊断方法。该方法的系统模型知识在牵引变电站设计阶段就可获得,通过引用候选最小冲突集概念,将基于模型的诊断方法应用于牵引变电站主要电气设备的故障诊断,可以直接利用量测量来判断故障元件。最后,以一个实际自耦牵引变电站诊断为实例,通过对该系统的建模、编程和实验,取得了良好的效果,验证和讨论了该方法的可行性和有效性。

基于实例和CSP的产品配置方法

采用基于实例和约束满足问题(constraint satisfaction problem,CSP)的方法进行大规模定制下的产品配置,将产品配置问题表示为CSP,并对产品族内的实例进行形式化描述,利用基于实例的方法检索出与客户需求匹配的产品实例,使系统将当前的新配置问题直接定位到某一历史案例,为CSP中变量提供初始解信息,避免了CSP系统不管任何问题都从头到尾进行推理的弊病,减少了不必要的搜索空间和时间。然后利用最小冲突修改算法求解CSP,产品实例的调整过程就以求解CSP的形式独立完成,使不清楚的产品实例调整过程形式化,可以确保产品实例调整过程的一致性同时减轻客户配置产品的负担。

基于值序的二元约束满足问题粒子群算法

提出了一个基于最小冲突启发式值序的二元约束满足问题粒子群算法,利用值序对值的选取方式代替随机选择的盲目搜索方式,使群体在探索解空间的时候,选择有希望能找到全局解的地方搜索。使用随机约束满足问题的实验表明,改进后的算法比原算法能以更快的速度收敛到全局解,无论在迭代次数还是运行时间上均能数倍提高算法的效率。

支持MPLS流量工程的选播路由

对选播服务的网络负载均衡做了研究,提出一种支持多协议标签交换(MPLS)流量工程的选播路由算法(ART).ART基于最小冲突路由机制,通过MPLS约束路由的标记分发协议(CR-LDP)建立1条从选播服务器到客户方向的标记交换路径(LSP),并预留带宽资源.仿真结果表明,ART能平衡网络的负载,在选播服务中实现网络资源的优化利用,并且在传输服务数据流时,能减少时延及数据包的丢失.