无约束最大子序列求和改进算法

给出了无约束最大子序列求和的一种改进算法,在不增加复杂性的前提下,突破了美国Mark A llen W eiss教授在约束条件下对该问题求解的算法,即该算法不能计算所有整数为负数情况下的最大子序列和(否则,结果视为0),从而解决了针对所有整数的无条件约束最大子序列的求和问题.

一种实现偏序约束条件下的序列模式挖掘算法

在序列模式挖掘应用中,约束是非常重要的。本文提出了一种新的约束-偏序约束,允许事务之间的间隔可以是无穷大。但是,本文间隔约束中事务之间的间隔只能是整数,所以可以把偏序约束看成是间隔约束的扩展。针对这个问题,提出了一种新颖的算法SPM(Sequential Pattern Maintenance,简称SPM)算法来解决偏序约束,采用含蓄分割技术把不满足偏序约束的数据序列分割出去,充分利用已挖掘出来的信息来解决由于数据序列数目变小使得支持度值变小的复杂情况。实验表明,SPM算法能够快速可扩展地挖掘出所有满足约束的频繁序列模式。

带约束最长公共子序列快速算法

带约束最长公共子序列(CLCS)问题有很深的生物学应用背景,常被用来表示同源基因序列相似性的度量,但计算CLCS时间代价很高,最早的CLCS算法的时间复杂度为O(rn4),目前,最快的CLCS算法的时间复杂性为O(rn2).运用对偶原理将带约束最长公共子序列问题转换为带约束最小覆盖集问题,并建立带权的ref树结构,构造包含约束序列的约束覆盖子集,约简带约束覆盖子集并从中搜索关键路径,再通过关键路径构造CLCS,该算法将算法时间复杂度提升到O(nlogn+(q+r)L),r是约束序列的长度,q是两序列序偶的个数,L是两序列的最长公共子序列(LCS)长度.

大规模过程系统优化的序列界约束方法

基于非线性约束极小化的序列无约束方法,对大规模过程系统稳态优化的序列界约束方法进行了研究。该约束方法的罚函数只包含对等式和/或不等式约束的惩罚项,不包含对界约束的惩罚项,通过迭代求解一系列界约束极小化子问题而非无约束极小化子问题获得原问题的解;算法按2层结构实现,内层结构中主要求解界约束极小化子问题得到下一个迭代点,外层迭代主要修改乘子向量和罚向量以及检查收敛准则是否满足,重构下次迭代的界约束子问题,或在收敛准则满足时终止算法。此外,给出了求解界约束极小化子问题的修改截断Newton法,并用一类规模可变的约束优化问题和一类最优控制问题对所给方法进行了数值试验,试验结果表明,所给序列界约束方法是非常稳定和有效的。

一种带匹配路径约束的最长公共子序列长度算法

在带约束的最长公共子序列问题中提出一种特殊的新问题:假设有两序列Q和C,Q中指定的匹配位置序列I,计算两序列Q和C的最长公共子序列,且这个最长公共子序列的匹配路径必须经过位置序列I。针对此问题,该文提出一种带匹配路径约束的最长公共子序列算法。首先定义带匹配路径约束的最长公共子序列模型,其次推出该序列的性质,最后求出带匹配路径约束的最长公共子序列长度的基础算法和快速算法。基础算法和快速算法时间复杂度分别为O(mnt)和O(mn),m,n,t分别为序列Q,C,I的长度。

序列无约束极小化技术和遗传算法在非线性规划中的应用

本文提出了一种求解带约束非线性规划问题的一般方法。与现有的方法相比 ,它不受可导性 ,单峰性和是否病态等因素的限制 ,适用范围广。

一种基于非均匀惩罚因子的序列无约束最优化外点新算法

增广拉格朗日乘子方法(Augmented Lagrange multiplier method)是拉格朗日乘子方法(Lagrange multiplier method)的推广,它是一种序列无约束的最小化技术,包括内点法和外点法,内点法适用于仅有不等式约束的情形,其主要思想是对违背可行性的约束给予一个惩罚。传统的做法是:对所有约束以相同的罚因子,自适应调整Lagrange乘子。提出了一种非均匀惩罚的自适应更新罚因子的方法,即根据近似解对约束违反的严重程度施行不同惩罚的新方法。算例表明,本方法是有效的。

间隙约束序列模式挖掘的对比研究

本文首先描述了间隙约束序列挖掘的分类及研究现状,最后给出了间隙约束的序列模式挖掘在实际生活中的发展趋势。在未来的研究领域中,具有间隙约束的序列模式挖掘仍是一个重要的研究方向。

自适应跳频受约束的信令跳变序列设计

信令能否安全可靠地传输是自适应跳频电台性能好坏的关键。为了提高自适应跳频电台信令传输的安全可靠性,该文在分析了无约束信令跳变序列与宽间隔信令跳变序列抗部分频带干扰的性能与局限性的基础上,提出了一种受约束的信令跳变序列,并给出了其详细的构造过程。理论分析与计算机模拟结果均表明所设计的受约束的信令跳变序列与前两种信令跳变序列相比在抗部分频带干扰方面有一定的性能增益。

序列无约束极小化技术和遗传算法在非线性规划中的应用

提出了一种求解带约束非线性规划问题的一般方法，与现有的方法相比，它不受可导性，单峰性和是否病态等因素的限制，适用范围广，实例说明该算法的对带约束非线性规划问题的求解十分有效。

序列无约束极小化技术和遗传算法在非线性规划中的应用

提出了一种求解带约束非线性规划问题的一般方法。与现有的方法相比,它不受可导性、单峰性和是否病态等因素的限制,适用范围广。实例说明该算法对带约束非线性规划问题的求解十分有效。

两种带约束的序列比对算法

通过理论证明,得出了当距离函数中惩罚因子φ=0时的解应满足的条件,并在此基础上改进两种最长公共子序列的优化算法,使之能够求解出带约束的序列比对问题。这两种改进算法的时间复杂度分别为O(nmr)和O(nm(r+1)),空间复杂度分别为O(nmr)和O((n+m)(r+1))。推导出算法应满足在两序列中插入的空位符数目分别为(m-l)和(n-l),使比对结果中不会出现错配,保证了比对的质量。实现了基于回溯的改进算法,验证了其求解带约束的序列比对问题的有效性。

过程间引发约束变化的最小高级修改序列识别

鉴于引发约束变化的最小高级修改序列在实现数据感知过程转换、合并、版本控制等方面具有重要作用,提出一种识别数据感知过程间引发约束变化的最小高级修改序列的方法。该方法定义了数据感知过程的活动约束图,然后基于活动约束图构建两个数据感知过程的约束矩阵,最后利用约束矩阵和数字逻辑识别一个数据感知过程间转换所需引发约束变化的最小修改序列。大量实验评估了所提方法和现有方法的准确性与时效性。结果表明,所提方法比现有方法具有更高的准确性,其平均准确率达到89.89%。

正负序列模式中的约束条件研究

合理的约束条件对于高效挖掘数量适中且满足用户需求的正负序列模式有着重要意义。本文对正序列模式中的约束条件进行了讨论并归纳为早期约束、零散类约束和系统性约束,对4种典型的负序列模式挖掘方法中的约束条件进行了详细讨论。这些讨论对更好地掌握已有的约束并在此基础上提出更合理的约束有着重要意义。

带重要点约束的经典轨迹相似度量新算法

在经典轨迹的相似度量问题中提出一个新问题:假设有待相似度量的经典轨迹和实时轨迹,在经典轨迹中存在部分点为重要点,实时轨迹受这些重要点约束。针对此问题,将经典轨迹和实时轨迹作为相似度量的两序列,重要点作为实时轨迹的约束序列,利用带约束的最长公共子序列理论提出带重要点约束的经典轨迹相似度量基础算法和快速算法。实验结果表明,快速算法比基础算法的计算时间减少了36%以上。

路网环境下访问序列受限的多标签路线查询算法

随着移动互联网、地理定位技术和智能终端设备的迅速普及,产生了大量的位置信息和其对应的标签(tag)描述信息.路线搜索是人们出行时经常进行的活动,但面临多个任务需求时,寻找最佳路线是一项极为耗时的工作.此外空间对象本身的访问权限和用户指定的限制一定程度上制约了对象的访问次序.针对上述情况,文中提出了一种路网环境下访问序列受限的多标签路线(MTROC)查询,该查询的目标是找出一条从源点到目标点、经由与查询中给定的tag相匹配的空间对象且满足序列约束的最短线路.文中证明了MTROC查询问题是NP-hard,并基于增强的路线叠置-关联目录(EROAD)索引提出了3种近似算法.路线扩展RE-Greedy算法和路线渐增插入RII-Greedy算法通过局部更新获得满足需求的路线,而全局路线优化算法GROA为MTROC查询提供一个全局近似最优解.使用真实和合成数据集对文中提出的算法的有效性和可扩展性进行分析评估,实验结果表明3种算法都能有效地完成MTROC查询,其中GROA算法可扩展性最好,而RII-Greedy算法返回的路线质量最高.

多目标规划问题的约束度分析

对于多目标规划问题 ,提出了约束度的概念 ,基于此概念利用各个约束度序列可以刻划该规划系统的相容性。决策者可根据约束优化原则把原问题转化为弱约束的规划问题来求其非劣解。最后 ,用一个算例说明了这种方法的应用。

约束Chebyshev逼近及在FIR滤波器设计中的应用

考虑了一类约束Chebyshev逼近问题 ,应用序列无约束优化技术证明了最佳逼近三角多项式具有的特征性质 ,并提出求解最佳逼近多项式的一种具有良好数字特性的实用算法 .作为约束Chebyshev逼近的应用 ,考虑了一类约束FIR滤波器的设计问题 ,设计例子表明了最佳逼近三角多项式求解算法的有效性 .

约束优化问题强次可行方向法的研究

本文旨在对简金宝教授及其研究团队(简称为简优化团队)建立的约束优化问题强次可行方向法与拟强次可行方向法(统称(拟)强次可行方向法)的思想及其研究作一个概述.本综述包括:(1)(拟)强次可行方向法的思想与内涵;(2)广义梯度投影型强次可行方向法;(3)序列二次规划(SQP)型强次可行方向法;(4)序列线性方程组(SSLE)型强次可行方向法;(5)序列二次约束二次规划(SQCQP)型强次可行方向法;(6)拟强次可行方向法.本综述最后对(拟)强次可行方向法的深入与拓展研究作一个展望,与读者分享.

可行方向SUMT外点法的研究及应用

针对序列无约束极小化技术(sequential unconstrained minimization technology,SUMT)外点法中由于设计变量越界而导致优化失败的问题,分析了设计变量越界的原因,将SUMT外点法和可行方向法相结合,提出了一种可行方向SUMT(feasible direction SUMT,FD-SUMT)外点法。用可行方向法的思想处理设计变量的约束,将搜索空间限定在设计变量可行域内。与传统的SUMT外点法相比,该方法除实现简单外,更具有鲁棒性高、收敛快等优点。通过数值算例和工程应用实例验证了FD-SUMT外点法的性能。优化结果表明,该方法消除了设计变量越界的情况,收敛速度和鲁棒性明显高于传统的SUMT外点法,而且初值选取容易,具有工程实用性。