用于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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

优先级k-中心问题的FPT近似算法

优先级k-中心问题是聚类领域中1个经典的NP-难问题。给定度量空间中的1个集合X和参数k∈N+,其中,集合X中每个点v都被赋予1个优先级参数r(v)∈R+,求解1个大小为k的子集S■X,考虑集合X中任意数据点到集合S的距离与r(v)之间比值,找到最大比值,目标是最小化该比值。对于优先级k-中心问题,目前最好的结近似算法是多项式时间内的2-近似算法,该问题不存在1个(2-ε)-近似算法,(其中,ε为用于控制算法近似比的参数)。本文研究优先级k-中心问题的固定参数可解(fixed-parameter tractability,FPT)时间内的近似算法。基于k-中心问题的贪心策略,提出新的中心点选取方法。研究结果表明:该方法通过贪心策略选取一定规模的候选中心点集,利用加倍度量维度的性质去限制该集合的大小,实现了FPT时间内的(1+ε)-近似算法,降低了目前该问题的近似比。

发射台站智能化任务分配算法研究

基于发射台站智能化管理系统的数据处理模型,研究任务分配算法。以分支定界算法代表精确算法、贪心算法代表近似算法、遗传算法代表智能算法,进行算法性能测试,并对计算数据进行分析,总结不同算法的优缺点和应用场景。

量子近似优化算法在投资组合优化中的应用

讨论了量子近似优化算法(QAOA)在投资组合优化问题上的应用,而后者在离散的约束条件下是NP难的;介绍了QAOA的基本框架以及相应的投资组合优化问题的建模;阐述了数个可用于解决投资组合优化问题的QAOA方法。通过数值模拟及假设检验比较这些方法与经典方法的表现,各量子算法在平均近似比上相较经典方法均有7%以上的提升。

量子近似优化算法在最大独立集中的应用

最大独立集问题是著名的NP问题,并且在许多场景中都有应用。传统的精确算法解决最大独立集问题需要指数级的时间复杂度。为更高效地解决最大独立集问题,提出了一种基于量子近似优化算法的量子线路解决方案。该方案由最大独立集的数学模型,推导出最大独立集问题的哈密顿量表达式;设计了基于量子近似优化算法的量子线路,采用COBYLA经典优化算法对参数量子门中的参数进行优化,并使用IBM提供的量子开发框架Qiskit进行仿真实验。仿真结果表明,使用量子近似优化算法可以在多项式时间内以高概率获得最大独立集问题的解,实现了指数加速。量子近似优化算法对解决最大独立集问题有一定的可行性和有效性。

平方度量的设施租赁问题的近似算法

作为设施租赁问题的推广,首次提出平方度量的设施租赁问题,平方度量侧重于突出距离对连接费用的影响,具有广泛的实际应用背景。在平方度量的设施租赁问题中,每个时间段都有顾客到达,每个到达的顾客都需要被连接到某个其到达时正在租赁的设施上。租赁设施产生租赁费用,连接顾客到设施产生连接费用,连接费用是顾客与设施之间距离的平方,通常假设距离是度量的。目标是租赁一些设施,连接每个顾客,使得租赁费用与连接费用之和最小。基于原始对偶技巧,给出平方度量的设施租赁问题的9-近似算法。

基于变可信度近似模型的BGA焊点可靠性预测与优化方法

焊点可靠性预测研究多采用有限元仿真与单一精度近似模型相结合的模式,存在仿真时间长、效率低、准确性差等问题,为此,提出了一种基于变可信度近似模型的球栅阵列(ball grid array,BGA)焊点可靠性预测与优化方法.首先,对不同网格细化方案进行收敛性验证,分别设计高/低精度样本点进行有限元仿真;其次,基于CoKriging模型融合高/低精度仿真数据进行焊点可靠性预测;最后,将预测结果与单一精度近似模型进行对比分析,并采用遗传算法优化模型获得对应结构参数.结果表明,在更少的仿真成本下,变可信度模型的预测效果更好,在同等预测精度下,变可信度模型高精度样本点数量仅为单一精度模型的1/4,相比高精度神经网络预测模型,在寻优过程中收敛更快.

最小负载受限k-中位问题的近似方案

给定度量空间中的用户集合C和带有最小负载τ:F→(O,|C|]的设施集合F以及正整数k,最小负载受限k中位问题的一个可行解(H,σ)由满足|H|≤k的开设设施集合H⊆F和满足|σ^(-1)(f)|≥τ(f)∀(f)∈H的映射σ:C→H组成。(H,σ)的费用为∑_(c∈c)^(σ)(c,σ(c))其中,(σ)(c,σ(c)为c与σ(c)之间的距离.最小负载受限k-中位问题的目标是找到费用最低的可行解.本文以k作为固定参数研究最小负载受限k-中位问题的求解算法.本文首先利用D采样方法寻找与最优解中的开设设施较为接近的用户,然后围绕这些用户划分空间并选取开设设施.给定满足C∪F⊂R^(d)的实例(C,F,k,τ)和常数ε∈(0,1),本文结合上述思路和降维方法提出了时间复杂度为o(ndk+(kε-1)^(kε)^(-o(1)))n^(o(1)))的(1+ε)-近似算法,其中,n=|C∪F|.此前,人们在固定参数时间内得到的关于该问题的最好近似结果为3+ε;只有在设施可以被开设在欧几里得空间中的任意位置且所有设施最小负载都相等的实例中,存在固定参数时间的(1+ε)-近似算法.

基于SSA-BP近似模型的湿式制动器带排转矩参数CSO智能优化

针对湿式制动器在非制动工况下功率损失的工程问题,考虑摩擦副间隙内部的润滑油对摩擦副带排转矩的影响,运用麻雀搜索算法-反向传播(Sparrow Search Algorithm-Back Propagation,SSABP)神经网络的强大非线性拟合能力,以制动器空载工况为输入量、带排转矩为输出量,建立了湿式制动器近似模型;与传统的BP模型对比,该模型预测精度明显提高,更能满足实际工程的需要;同时,为获取最小带排转矩,采用鸡群优化(Chicken Swarm Optimization,CSO)智能算法对工况参数进行搜索寻优,得到湿式制动器的最佳工况。经试验测试验证,与优化前相比,优化后摩擦副间的带排转矩和功率损失有着明显降低。研究为湿式制动器结构的进一步优化提供了理论基础和工程实践经验。

基于改进近似共轭梯度追踪的轴承故障诊断方法

在确保机械系统的可靠性和功能性、生产效率和安全性方面,滚动轴承的状态监测和故障诊断极其重要。然而,故障特征通常总是被背景噪音和其他不稳定的干扰成分所掩盖,这使得这项工作变得非常困难。为了更好地提取轴承故障特征,提出了结合改进的正余弦优化算法(improved sine cosine algorithm, ISCA)的弱选择近似共轭梯度追踪(weak selection approximate conjugate gradient pursuit, WACGP)算法。将惯性权重和非线性参数更新策略引入正余弦优化算法(sine cosine algorithm, SCA)中,提高了信号稀疏表示的效率和精度,以便用字典原子最大限度地逼近原始信号,并且将弱选择策略引入近似共轭梯度追踪(approximate conjugate gradient pursuit, ACGP)中,提高了提取轴承故障特征的速度和能力。通过对轴承的故障仿真信号和实际轴承内、外圈和滚动体振动信号的分析,验证了该方法的有效性。详细说明了与基于正余弦优化的梯度追踪算法的比较,突出了所提出的方法的优点。

基于近似模型的弹性背腔穿孔管消声器声学性能优化

弹性背腔穿孔管消声器利用声波和弹性管壁的耦合作用,相比于穿孔管消声器具有更好的低频消声性能。为了进一步提高该消声器的低频、宽频消声能力,采用遗传算法对其进行优化。首先,利用COMSOL有限元软件建立该消声器的传递损失计算模型。其次,分析弹性管壁材料对消声器低频消声性能的影响,并选取橡胶复合材料作为弹性管壁材料。再次,由于所采用的有限元模型计算耗时长,为节约时间资源,利用径向基函数(Radial Basis Function,RBF)神经网络方法建立近似模型代替有限元计算模型。最后,利用近似模型结合遗传算法进行全局寻优,获得该消声器结构参数的优化结果,并利用有限元模型验证优化的准确性。结果表明:优化后在100~1000 Hz低频段范围内弹性背腔穿孔管消声器消声带宽增加62%,且平均传递损失提高3.6 dB。

多子阵合成孔径声纳距离-多普勒成像算法

基于相位中心近似(PCA)的传统多子阵合成孔径声纳(SAS)成像方法忽略了近似误差的方位空变性,使得分布式目标的聚焦结果发生畸变。为解决这个问题,该文从收发阵元空间分置采样与相位中心近似采样的几何模型出发推导了一种考虑近似误差方位空变性的双程斜距历程,并将多子阵合成孔径声纳2维频域系统函数分解为收发分置畸变项和类收发合置项。在此基础上,采用复数相乘、插值实现收发分置畸变项的补偿,并利用距离-多普勒算法进行成像处理。相对传统方法,该文方法在整个测绘带内的近似误差更小,不会带来方位向上的位置偏移,能得到与真实目标位置一致的成像结果。

基于响应面近似模型的车门轻量化仿真分析与研究

为实现车门的轻量化,首先对车门的刚度与模态进行分析,确保各项性能满足要求,利用质量和模态频率的灵敏度分析结果筛选出车门部分部件的板厚作为设计变量,通过最优拉丁超立方的试验设计方法结合有限元仿真模型求解数据采集用来构建二阶响应面模型的基本数据,在二阶响应面模型的基础上结合第二代非支配遗传算法进行多目标优化。结果表明:车门质量降低4.45%。