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

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

Steiner树优化问题的算法研究综述

最优Steiner树问题(Steiner tree problem,STP)是一个经典的组合优化问题,许多工程问题都可以归结为最优Steiner树问题。STP被广泛应用于通信网络、电路设计、VLSI设计等领域。然而,STP是典型的NP难问题,还没有多项式时间的精确算法求解该问题。目前,求解该问题的算法主要集中在基于启发式的近似算法、智能优化算法、信息传播算法等,并取得了很好的效果。在不同规模的网络中,基于传统遗传算法给出一种叶交叉机制(leaf crossover,LC),使用该机制的算法性能表现更好。通过对这些算法的原理、性能、精度等方面进行梳理,归纳出算法的优缺点,并指出STP的研究方向和算法设计路径,对于相关问题的研究有指导意义。

融合关联信息与CNN的实体识别研究

引入外部词汇是提升实体识别效果的有效方法,然而现有的方法未能对词汇的关联字符向量进行表征,从而忽略了字符之间的联系。基于此,提出一种融合关联信息与卷积神经网络(convolutional neural network,CNN)的实体识别方法。在使用SoftLexicon引入外部词汇的基础上,根据字符所对应的外部词汇发现关联字符并以词频方式进行归一,从而与字符、词汇向量融合以构建多特征信息来扩充字符特征表示,之后使用CNN与双向长短期记忆网络联合获取深层信息。在Resume、Weibo和CCKS2017数据集上进行实验,结果表明,相比SoftLexicon方法,所提方法能有效提升实体识别效果。

约束可满足性中求解RB模型实例的算法综述

约束满足问题是人工智能领域中最基本的NP完全问题之一。多年来,随着约束满足问题的深入研究,国内外学者提出多种实例模型。其中,RB模型是一种能生成具有精确相变的增长域约束满足问题实例,其求解难度极具挑战性。为了寻找其求解的新型高效算法,促进约束可满足问题的RB模型求解算法领域的研究,首先从约束满足问题的模型发展、求解技术进行分析;其次,对各类求解RB模型实例算法进行梳理,将求解的算法文献划分为回溯启发式类、信息传播类和元启发式类相关改进算法,从算法原理、改进策略、收敛性和精确度等方面进行对比综述;最后给出求解RB模型实例算法的研究趋势和发展方向。

求解可满足性问题的信息传播算法研究综述

信息传播算法来自统计物理,被广泛应用于人工智能各个领域,特别是求解组合优化问题时,具有良好的有效性。通过对信息传播算法的相关文献进行分析,综述了信息传播算法以及其相关应用的发展史,根据信息传播算法的发展,介绍了求解可满足性问题的信息传播算法相关概念,主要涉及到警示传播算法、置信传播算法和调查传播算法,描述了三种算法发展中出现的收敛性、有效性研究,分别综述了各个算法在相关领域的应用情况,并总结了信息传播算法的研究路径和应用方向。

融合词汇信息与GlobalPointer的实体识别

为了提升GlobaiPointer方法的实体边界区分性能,提出一种融合词汇信息与GlobalPointer的实体识别方法。对SoftLexicon提取的词汇特征与字符相结合,采用BiLSTM网络与RoPE编码捕捉时序与相对位置信息构建全面特征,通过实体矩阵实现实体识别。对多个数据集进行试验,本研究提出的模型相较于其他基线模型,精确率、召回率、F_(1)均有一定的提升,Weibo数据集中F_(1)达到71.33%、CMeEE数据集中F_(1)达到63.45%,表明本研究提出的模型架构能够进一步扩充语义表征,增强识别性能。