基于Intranet的知识库系统匹配算法的研究与实现

在分析了知识库和知识库系统概念的基础上,探讨了知识库系统中的应用和方法。在知识库系统中问题匹配是系统的核心问题。围绕问题匹配方法的设计,首先分析了知识库匹配中的各种相关因素,提出了一个基于关键词、关键词权重、问题频度和典型语义词的知识库匹配算法,并给出了基于该算法的知识库系统的实现方案,最后在IBM技术Intranet知识库上进行应用,应用结果表明了该算法的高效性。     

最大团问题降阶算法

最大团问题是找出给定图中的一个最大结点子集合,使得子集合中的任意两点之间都有边相连,最大团问题是一个著名的NP-难题,在很多领域中都有着广泛的应用.本文在研究最大团问题数学性质的基础上给出该问题的一个初步降阶方法;在初步降阶的基础上给出一个求解最大团问题的上、下界方法;最后将降阶方法和上下界方法结合起来形成一个全新的降阶算法,该算法不仅可以单独使用,还可以与其它算法结合起来使用达到更好的效果.在文中还介绍了本算法和其它各类算法的优缺点,最后通过多个示例来进一步说明算法的原理及应用情况.     

集合覆盖问题的启发函数算法

本文给出了求解NP困难问题的完备策略的概念,在此基础上提出了一个求解集合覆盖问题的启发函数算法SCHF(set-covering heuristic function),文中对该算法的合理性、时间复杂性以及解的精度进行了分析,本文的主要创新点是用已知的完备策略建立启发函数,并用该启发函数进行空间搜索求出优化解.该方法具有一定的普遍性,可以应用到其它的NP困难问题.它为求解NP困难问题的近似解提供了一种行之有效的方法.在规则学习中的应用结果表明,本文给出的SCHF算法是非常有效的.     

基于动态状态树的回溯算法

介绍了背包问题及0-1背包问题,阐述了回溯算法(算法设计的基本方法之一)和状态空间的概念,提出一个基于动态状态空间树的回溯算法.以0-1背包问题为例,说明动态树方法对求解线性规划问题等是非常有用的,且该算法所用时间少于静态状态空间树方法,有助于扩大回溯算法的应用.     

函数依赖集在属性子集上投影新算法

分析了分解法分解关系模式在数据库设计应用中存在的问题是函数依赖集在属性子集上投影的计算问题，而后对该问题提出了解决的方法和技术，并设计了具体的算法。该算法为解决此计算问题提供了一个有效途径，给分解法分解关系模式在数据库设计中的应用创造了更有利条件。     

求解VRP问题的混合鱼群遗传优化算法

首先对物流配送中的一般车辆优化调度问题（VRP）进行了分析,并为之建立了相应的数学模型。随后设计了一个人工混合鱼群算法,并研究了如何应用该算法解决车辆优化调度问题,该算法在初期阶段应用人工鱼群算法迅速获得阶段最优解,在后期阶段应用遗传算法寻求最优解。最后通过仿真实验验证了该算法具有求解速度快,性能稳定等优点。     

配送问题的数学模型与遗传算法

配送问题在物流配送业中有着广泛的应用背景,合理进行配送是实现运输规模经济、节省运输费用的重要手段。论文首先在一些模型假设的基础上,建立了客户订单合成配送问题的数学模型,提出并实现了解决该问题的遗传算法。大量仿真结果表明该算法能够在较短的时间内有效求得问题的近优解,该算法的运行时间主要取决于订单数和交货组数。该算法可以有效求得客户订单合成配送问题的近优解,为实现物流配送提供了一个基本方法。     

基于DCMSTP问题的算法综述

DCMSTP （度限制最小生成树问题）是一个NP难问题,具有重要的实际应用价值。对于大规模的DCMSTP问题,至今还没有非常有效的求解方法。为此,本文对讨论了DCMSTP问题的数学模型和求解该问题的精确算法和启发式算法。     

求解多目标优化问题的改进蚁群算法

蚁群算法是一种模拟蚂蚁行为进行优化的启发式优化算法,该算法在许多领域已经得到应用.针对多目标优化问题优化与求解较困难的问题,提出一种嵌入变尺度算法的改进蚁群算法用于求解,为蚁群算法在连续空间中的应用提供了怂一个可行的方案.给出了该算法的详细定义及实现步骤,实例仿真表明,该算法能加快收敛速率,对连续空间的蚁群算法研究具有重要的意义.     

求解运输问题的GAPSO算法

运输问题是一个应用非常广泛的问题,传统方法对于大规模的运输问题求解比较复杂,而一些基于随机搜索算法的方法对于其约束条件的处理又比较困难.基于运输问题约束条件的特殊性,设计了一种产生可行解的方法,将对约束条件的处理转化到了算法设计之中.在此基础上,又设计了基于遗传算法和粒子群优化算法的求解运输问题的GAPSO算法,为避开对非可行解的处理,该算法对迭代过程也进行了特殊设计,从而简化了运用随机搜索算法解决运输问题的过程.最后给出了三个实例验证,通过对验证结果分析和比较,说明该算法在时间复杂度和收敛性方面都具有其优良性,是行之有效的.     

多参数最小支撑树问题的复杂性和算法

建立了多参数最小支撑树问题（ＲＭＳＴ）的模型,并证明该问题是ＮＰ－完全的。利用经典Ｇｒｅｅｄｙ算法,给出了该问题的一个近似算法,并分析了该近似算法的性能比,证明了所给出的界是紧的。     

MSN网络的优化问题研究

研究了由MSN节点组成的应用层组播网络,讨论了度约束最小直径生成树(D-MDST)问题,并给出了求解该问题的BCT算法。提出了一种新的生成树编码方法——过程控制编码,该编码将启发式算法与遗传算法结合起来且具有编码简单、译码方便、适用常规遗传算子等优点。给出了基于该种编码的遗传算法,并将BCT算法作为过程控制编码的译码器。仿真结果表明了该遗传算法的有效性。     

节点加权的Steiner树问题的降阶回溯算法

节点加权的Steiner树问题是组合优化中一个经典的NP-hard问题,现有算法研究该问题时存在时间复杂性高或无法得到最优解的缺点。针对现有算法的不足,提出了一个基于降阶技术的回溯算法。首先研究该问题的数学性质,利用数学性质对该问题进行降阶以缩小问题的规模;接着提出上界子算法和下界子算法,利用上下界子算法对该问题的解空间树进行剪枝,提高搜索效率;最后利用上下界子算法和数学性质设计了一个回溯算法求解该问题。示例分析以及实验的结果表明,该算法不仅时间复杂性较低而且可以得到问题的最优解。     

基于最小树权矩阵法的改进算法

针对最小树权矩阵法在大型网络应用中的不足，从提高算法效率方面对其进行了改进，并给出了新的算法。新算法减少了运算量，达到了快速寻找最小树的目的。通过对新算法和权矩阵法的比较，结果表明新算法具有较低的复杂度，是一种更为有效的算法。     

最坏情况下Min-2SAT问题的上界

最坏情况下MaxSAT问题上界的研究已成为一个热门的研究领域.与MaxSAT问题相对的是MinSAT问题,在求解某些组合优化问题时,将其转化为MinSAT问题比转化为MaxSAT问题有着更快的速度,因此对MinSAT问题进行研究.针对Min-2SAT问题提出算法MinSATAlg,该算法首先利用化简算法Simplify对公式进行化简,然后通过分支树的方法对不同情况的子句进行分支.从子句数目的角度分析算法的时间复杂度并证明Min-2SAT问题可在O(1.134 3m)时间内求解,对于每个变量至多出现在3个2-子句中的情况,得到最坏情况下的上界为O(1.122 5n),其中n为变量的数目.     

物流网络中节点带权的Steiner最小树的参数算法

通过优化物流的运输网络,可以有效地降低物流成本。集中配送的物流网络优化问题可以转换成求解节点带权的Steiner最小树问题,这是一个NP-hard问题。运用参数理论,提出一种新的启发式解决算法P-NSMT。算法的思想是：首先尽可能只利用终端节点构造一棵连通的最小生成树,然后逐步向树中添加能减少生成树总权值的Steiner节点,最终生成一棵节点总数不超过参数k的Steiner最小树。实验表明,与同类型其他算法相比,P-NSMT算法具有更好的准确性和时间效率,特别适应于网络规模大、终端配送节点数目较少的物流网络。     

A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem

We consider the version of prize collecting Steiner tree problem (PCSTP) where each node of a given weighted graph is associated with a prize and where the objective is to find a minimum weight tree spanning a subset of nodes and collecting a total prize not less that a given quota Q.$Q.$ We present a lower bound and a genetic algorithm for the PCSTP. The lower bound is based on a Lagrangian decomposition of a minimum spanning tree formulation of the problem. The volume algorithm is used to solve the Lagrangian dual. The genetic algorithm incorporates several enhancements. In particular, it fully exploits both primal and dual information produced by Lagrangian decomposition. The proposed lower and upper bounds are assessed through computational experiments on randomly generated instances with up to 500 nodes and 5000 edges. For these instances, the proposed lower and upper bounds exhibit consistently a tight gap: in 76% of the cases the gap is strictly less than 2%.     

最小费用充电站选址问题的分支定界算法

电动汽车的充电站选址问题是当前社会的热点问题,其实质是组合优化中经典的NP-hard问题。基于最小开设费用对充电站选址问题进行研究,首先对该问题进行了数学建模,进而研究了该问题的数学性质并给予相应的证明,利用这些性质减小问题的规模,从而降低问题的求解难度;然后设计了上下界子算法以及降阶子算法,基于这些子算法提出了一种可以快速缩小问题规模同时得到最优解的分支定界算法,降低了时间复杂度,同时可以对解空间进行大量剪枝加快求解速度;最后通过分析和求解一个示例来进一步阐述所提算法的原理和执行过程。     

奖励收集斯坦利最小树的混合拉格朗日与分散搜索算法

针对PCSTP问题，提出了HLGSS混合算法．通过拉格朗日松弛策略，将PCSTP问题转化为简单的CMST问题；然后由Volume算法求解PCSTP的拉格朗日对偶问题并获得其下界．用SS算法优化原问题的可行解，利用求解拉格朗日对偶问题过程中获得的原始一对偶信息来指导SS算法的搜索．仿真结果表明，HLGSS比SS降低了算法的搜索空间，加速了算法的收敛性．     

最小比率生成树的竞争决策算法

最小比率生成树是找出目标函数形式为两个线性函数比值最小的生成树,例如总代价与总收益比值最小的生成树。当不限制分母的符号时,这是一个NP-hard问题。在分析最小比率生成树数学性质的基础上,提出了最小比率生成树的竞争决策算法。为了防止算法陷入局部最优,采用edge_exchange操作来增加算法的搜索范围。为了验证算法的有效性,采用无关和相关两种策略产生测试数据,并使用Delphi 7.0实现了算法的具体步骤。