用于Turbo迭代译码的近似Log-MAP算法研究

本文运用逼近论,研究Log-MAP算法的近似算法.本文提出了校正函数的一阶、二阶和三阶逼近多项式,并对近似式的逼近精度进行了分析和比较.本文将近似Log-MAP算法用于WCDMA turbo译码器中,对译码器在AWGN信道和平坦慢衰落信道上的纠错性能进行了仿真.仿真结果表明：一阶近似Log-MAP算法将Max-Log-MAP turbo译码器的纠错性能改进了0.2~0.3dB,二阶及三阶近似Log-MAP算法与原Log-MAP算法性能等价,优于Max-Log-MAP 算法0.3~0.5dB.

采用近似max*运算的Log-MAP译码算法

为有效降低Turbo码译码的硬件存储消耗,提出一种基于近似max*运算的改进的Log-MAP算法。并通过设计合适的数字电路来找出一组数据中最大的两个值嵌入到其相关函数项中,有效实现了低复杂度的Turbo译码器的硬件结构。实验结果表明,所提出的结构比Constant Log-MAP算法结构平均简化了30%,达到了与Log-MAP几乎相同的误码率(BER)性能,降低译码的复杂度,便于实际工程应用。

量子近似优化算法在数字分区问题中的应用

量子近似优化算法(QAOA)是一种近似求解组合优化问题的方法,它通过反复调整电路参数,以获取问题哈密顿量的最大期望值为目的来解决问题,在组合优化问题领域具有广阔的应用前景。将QAOA应用于数字分区问题(二分区问题),通过将问题函数转换成对应的哈密顿量,构造了量子线路,采用线性近似约束优化(COBYLA)方法对电路参数进行了优化,并使用IBMQ模拟平台进行了模拟实验。研究发现量子近似优化算法在数字分区问题中有着良好的性能表现,可在多项式时间内给出问题的解,并且降低了问题的时间复杂度。

基于Contig的单面基因组框架填充2-近似算法

随着基因测序技术的持续发展,基因组框架填充问题受到广泛关注。该文针对基于contig的单面含重复基因的基因组框架填充问题开展研究。通过设计有效的近似算法,完成根据参照基因组,将缺失基因填充至基因测序获得的不完整框架中,提高基因组框架的完整性。前期研究的基因组框架填充问题,缺失基因可以插入到不完整序列的任意两个基因之间,而基于片段重叠群(contig)的基因组框架填充,缺失基因的插入位置被限制在两个contig之间,更具一般性,该问题已被证明是NP完全问题。现有的近似算法中,2-近似算法处理的实例具有特殊性,2.57-近似算法针对一般实例,但近似性能比不够理想。该文以缺失基因、基因位点和断点三者之间的对应关系为基础,采用贪婪策略和最大匹配相结合的方式避免在填充过程中出现冗余公共邻接,并通过生成新的contig增加外邻接的数量,将针对一般实例的算法近似性能比提高到2,完成了基于Python的可视化程序开发,进一步验证了算法的有效性。

k-center问题的算法研究综述

k-center问题是设施选址的基础问题,同样是NP难问题,在分配、紧急服务等领域也有着实际的应用。随着问题规模的扩大,原有的算法已不再适用,需要进一步优化或者改进。为了找到求解该问题的高效算法,对现有算法进行研究。对各类求解k-center问题的算法进行梳理,将求解算法划分为精确算法、启发式算法、元启发式算法、近似算法等,从算法原理、改进思路、性能和精度等方面进行对比综述。精确算法在求解小规模k-center问题时可在多项式时间内得到最优解,但是算法效率低,不适用于大规模问题;启发式算法可以在多项式时间内给出相对最优解,但是没有理论保证,无法衡量与最优解的关系;元启发式算法可对目前存在的智能优化算法进行改进,给出相对最优解,但是解的质量无法保证;利用近似算法得到的解具有近似比保证,有较大的理论研究价值,但是实用价值较弱。目前求解k-center问题的元启发式算法已取得一定的研究成果,但是在求解时间、求解规模、算法效率等方面仍待突破,这将是未来k-center问题的研究重点。

基于FPGA的分段近似双边滤波算法设计与实现

为了增强图像显示的质量以及减少基于现场可编程逻辑器件(FPGA)双边滤波算法中硬件资源的消耗,设计了一种分段近似的双边滤波算法。通过分段近似计算减少了双边滤波中值域的存储容量以及输出的数据位宽,从而降低了计算复杂度和硬件资源消耗。在Zynq-7000和Sparten-7的FPGA平台上实现了分段近似的双边滤波算法,研究了不同高斯噪声及在其最佳的值域标准差下的滤波和边缘保持性能。结果表明,本文算法在性能上与传统的双边滤波算法相当,并且与传统的双边滤波算法相比,其查找表(LUT)和数字信号处理模块(DSP)的使用量减少了9.9%和71.1%,且功耗仅为0.128 W。本文算法适合用于硬件资源有限的图像滤波应用场景。

基于近似测量算法Sketch的高精度区块链异常检测机制

区块链存在网络动态性强和其管理困难等问题,使得区块链普遍存在DDoS攻击和账户接管等异常现象.现有区块链异常检测方法多从所有区块链账户中提取历史交易信息和交易频率等特征加以分析以甄别异常.然而,随着区块链数据规模的不断扩大,现有方法在提取特征时面临内存消耗高、检测精度低的挑战.为此,提出了一种高检测精度、低内存开销的区块链异常检测机制,该机制采用近似测量算法将区块链异常检测转化为异常交易账户检测,包括区块内异常账户和跨区块异常账户.对于区块内异常账户,即仅存在于单个区块内的异常账户,使用Sketch算法进行账户识别,精度高.而对于存在于多个区块且难以通过单个区块信息检测到的跨区块异常账户,则通过聚合和分析多区块信息进行账户的准确检测.使用包含88847个区块的真实区块链数据评估上述机制.实验结果表明,与现有代表性方法对比,所提出的机制将区块链异常检测的召回率最高提升了6.3倍,F1分数最高提升了4.4倍.因此,提出的高精度区块链异常检测机制对于规范区块链交易行为、维护系统安全性具有意义.

近似图引导的演化贝叶斯网络结构学习算法

贝叶斯网络结构学习是贝叶斯网络推理及应用的基础.搜索高质量的节点序是贝叶斯网络结构学习的一类重要方法.针对在节点序空间中,搜索高质量节点序存在的难以高效、准确评估解的问题,本文提出了一种近似图引导的演化贝叶斯网络结构学习算法.首先,该算法利用互信息构建无向近似图;其次,该算法通过结合节点序和无向近似图构造有向图结构,将其贝叶斯信息准则评分作为节点序的适应度来高效评估节点序,并在演化优化的框架下,使用提出的基于Kendall Tau Distance的交叉算子和基于逆度的变异算子搜索最优节点序;最后,将搜索到的最优节点序输入K2算法得到其对应的贝叶斯网络结构.在4种不同规模网络上的实验结果表明,该算法在收敛时间和准确度之间取得了较好的平衡,其评分相较于对比算法中的次优解分别提升了10.91%、12.28%、53.96%、10.87%.

带次模惩罚的部分命中集问题的近似算法

研究了带次模惩罚的部分命中集问题.给定一个超图H=(V,E),一个定义在V上的费用函数,一个定义在2~E上的次模惩罚函数,和一个非负整数k.问题的目标是找一个顶点子集S?V,使得S至少覆盖k条超边,且S的总费用加上未被S覆盖的超边集的惩罚费用之和最小.设计了一个基于原始-对偶的两阶段组合算法来解决该问题.当次模惩罚函数是正规化的且非减时,得到算法的近似因子为l+1,其中l是超边所含的顶点数的最大值.

量子近似优化算法在精确覆盖问题中的应用

精确覆盖问题属于组合优化中的NP完全问题,使用经典算法难以在多项式时间范围内求解。为解决该问题,在开源量子计算框架qiskit上,提出基于量子近似优化算法(QAOA)的量子线路求解方案,并采用基于单纯形法的线性近似约束优化(COBYLA)算法对量子逻辑门中的参数进行优化。首先,通过精确覆盖问题的数学模型建立经典伊辛模型;其次,利用量子理论中的旋转变量对经典伊辛模型进行量子化,再用泡利旋转算子代替旋转变量,得到量子伊辛模型和问题哈密顿量,提高QAOA寻找最优的速度;最后,以混合哈密顿量为生成元的酉变换和问题哈密顿量为生成元的酉变换乘积的累积,得到问题哈密顿量期望的表达式,并由此设计生成量子线路。另外,通过经典处理器对两个酉变换中的参数进行优化,调整问题哈密顿量的期望值,从而提高求解的概率。该线路在IBM的开源量子计算框架qiskit上进行仿真实验,实验结果表明,所提方案能够在多项式时间内以95.6%的概率获得问题的解,验证了所提量子线路能够以较高的概率求得精确覆盖问题的解。

一种求解图分割问题的量子近似优化算法

量子近似优化算法(Quantum Approximate Optimization Algorithm,QAOA)是求解组合优化问题的算法框架,是近期最有可能展示量子计算优势的算法之一.在QAOA框架内,表征解的量子态采取的二进制编码方案导致的对称性限制了QAOA的性能.为了克服这一局限性,本文受Dicke态制备算法的启发,给出了一种新的解编码方案,消除了现有编码方案中的对称性.本文还设计了新的演化算子——星图(Star Graph,SG)算子,及其对应的SG算法,给出了算法求解图分割问题时的量子电路.在IBM Q上的实验结果显示,星图算法比标准QAO算法平均约有25.3%的性能提升.

基于多点触摸的协作机器人近似最优人机交互控制算法

针对人机交互系统中现有方法无法准确捕捉用户的操作意图,动态环境适应性较差,导致人机交互精准性不佳的问题,为提高协作机器人在作业过程中的人机交互精准性,提出一种基于多点触摸的近似最优人机交互控制方法.首先,基于人机交互的多点触摸动作匹配,建立交互手势动作序列图像传导函数,提取交互手势特征,分析图像相似度特征分量,根据像素值得出动作判断的模糊度集合,以实现对多点触摸动作的匹配,从而准确捕捉用户的操作意图;其次,考虑机器人运动条件和摩擦力因素,建立摩擦力近似最优约束方程,以保证机器人移动交互的平衡性和稳定性;最后,获取交互手臂的期望响应,利用Lagrange方程描述多点触摸条件下的人机交互状态,建立交互动作动力学方程,引入交互控制变量,利用自适应模糊控制体系输出近似最优控制结果,以提高动态环境适应性,并根据实际情况调整控制策略,更好地满足人机交互的需求.实验结果表明,该方法能有效完成人机交互控制,识别率高达94%以上,控制时延误差较小,为0.03×10^(-3)s,且迭代收敛速度快,具有更好的控制效果.

基于硬约束热启动的量子投资组合优化算法

针对金融领域的投资组合优化问题中普遍存在的整数约束难题,提出了一种基于量子近似优化算法的新解法。该算法通过将经典算法得到的连续解编码为量子电路的初始态,从而将连续优化问题转化为离散的马科维茨模型。同时,引入硬约束来严格满足投资组合中的整数约束,确保解的质量。通过热启动技术,进一步提升了算法的成功率。数值模拟实验表明,该算法在求解大规模整数约束投资组合问题时,相较于传统方法具有显著的计算效率优势,且所得解的质量更优。

基于量子近似优化算法的旅行商问题研究

用量子近似优化方法对旅行商问题的一个变种进行算法设计和实现,并在模拟器上进行了仿真。结果表明,在量子比特足够的情况下,该算法能在量子计算机上以多项式时间进行旅行商问题变种的求解,并达到近似比1.5之内的近似程度,为利用量子计算机求解NP难问题提供了一种思路。

基于连续凸近似的多阶段弹道重规划求解算法

运载火箭弹道重规划问题是航天工程中至关重要的问题之一。目前运载火箭弹道重规划方法尚未对特定的多阶段弹道优化模型的特殊结构进行深入挖掘,计算效率有待进一步提升。通过建立多阶段弹道重规划问题模型,开展模型结构特性分析,最终在连续凸优化近似框架下构建了高效的定制化内点算法,以实现高精度、高鲁棒性的多阶段弹道重规划问题在线求解。仿真实验的结果表明,对典型火箭发射的SSO和GTO弹道,定制化内点算法的运行时间与传统算法相比分别减少了37.41%和47.86%,大幅提升了计算效率。

基于近似算法的分布参数对机电系统动态响应的频时域研究

文章针对具有机械部分分布参数的机电系统进行了频时域实验研究。文章强调了考虑参数分布的重要性,并分析了影响其分布特性的重要元素。在验证阶段开发了实验装置,并采用StrimServer和CANMonitor程序用于数据采集和分析;同时开发了控制系统,描述了最简单校正装置的创建过程,突出了用于开发控制程序的编程环境,并提供了一组编程控制器的程序。在频域实验中,在模拟机电系统行为的条件下,展示了合成控制系统的有效性。通过与理论计算的比较发现,其与实际值最大相对误差不超过10%,证实了理论计算的可靠性。在时域分析中,通过CANMonitor程序绘制电流图,发现在共振频率下电流幅值增加到1.83倍,这与在谐振频率处应有的情况相符。期望本文能对理解和设计具有分布参数的机电系统带来启发。

基于分段聚合近似与Shapelet算法的户变关系异常识别方法

在电力系统运营中,准确地监测和识别户变关系异常是保证系统安全和提高运营效率的关键。本文基于分段聚合近似(piecewise aggregate approximation, PAA)和Shapelet算法提出了一种新的户变关系异常识别方法。首先,利用PAA算法对电力消费数据进行降维处理,其次,通过Shapelet算法从简化后的数据中提取关键模式,以准确识别和分类异常情况。最后,将本文方法与传统支持向量机算法进行性能比较,结果表明:本方法在准确率和召回率方面均显著优于支持向量机算法。

一种基于编辑距离的中文字符串近似匹配算法

字符串近似匹配是模式匹配领域中的一个重要研究方向。在中文字符串近似匹配中,基于字符操作的编辑距离不能准确衡量由复制、剪贴等操作导致的相似关系。基于此,在传统编辑距离的基础上引入了字符串的平移和复制操作,给出了一种在贪心算法基础上进行动态规划搜索的计算方法,能有效计算改进的编辑距离,在真实数据集上的实验结果和分析显示了对文本检索的有效性。

图像特征点匹配算法下车辆行驶主动防撞预警

对于车辆行驶过程中的防撞预警,如果无法识别前车的具体行驶状态,可能使系统反应速度较慢,而不能动态变化调整本车行驶策略,导致无法有效规避潜在碰撞的危险。为了提高车辆在行驶过程中对周围环境的感知能力,防止车辆碰撞事故的发生,提出了图像特征点匹配算法下车辆行驶主动防撞预警方法。通过尺度不变特征转换(Scale-Invariant Feature Transform,SIFT)对采集到的前车图像中的特征点展开提取;利用近似最近邻搜索算法完成特征点的匹配,并将匹配点对从像素坐标系转换到图像坐标系中,以完成对前车的定位;基于单帧静态图像测距方法获得车距,并将前车的行驶状态分为静止、减速、匀速或加速三种状态,计算不同状态下的提醒报警距离和危险报警距离,动态调整本车行驶策略。当车距达到提醒报警距离或危险报警距离时,发出报警,以此实现车辆行驶过程中的主动防撞预警。试验结果表明:利用图像特征点匹配算法下车辆行驶主动防撞预警方法对前车车距展开测量,测量结果与实际车距基本一致,准确度误差在5 cm以内,相较于差异化预警方法和车联网数据预警方法而言可以更精准地测量车距;此外,所提方法的风险系数最大值为0.12,远小于差异化预警方法和车联网数据预警方法的风险系数,证实了该方法的车辆定位准确度高、防撞预警性能强。

近似熵、互近似熵的性质、快速算法及其在脑电与认知研究中的初步应用

本文从信号处理的角度介绍了近似嫡、互近似熵的概念、性质与应用，并给出了一种计算近似熵、互近似熵的实用快速算法．本文还通过实际算例说明了近似烟在表征信号的复杂性、互近似熵在表征信号的模式相似性方面的能力及其在脑电与认知研究中的初步应用。