计算机科学中几个算法及建模应用的探究

模型是将实际问题数学化,算法是将其中所蕴含的数学问题进行求解.算法即计算方法,是求解数学模型用的,就是将模型解出的方法.计算机科学中算法的选择、应用好坏,对建模具有非常重要的意义.本文简要论述了计算机科学中几个算法及建模应用具体内容,仅供交流.     

基于自组装的N皇后问题DNA计算算法

N皇后问题是理论计算机科学中一个经典的NP难问题.自Adleman首次运用DNA计算来解决NP问题以来,DNA计算已成为计算机科学的研究热点之一,现有N皇后问题的DNA计算机算法多基于粘贴和剪接模型,存在生化操作复杂度和实验误差较高等问题.本文提出了一种基于DNA自组装模型来求解N皇后问题的DNA计算方法.算法通过减少实验操作步骤数,降低了生化解的错误率.算法使用的tiles分子块种类为O（n²）,生化操作复杂性为O（1）,其中n为皇后的个数.与求解N皇后问题的其它DNA算法的对比分析表明,本算法可提高生化解的准确性,降低算法生化实验的复杂度,具有良好的易操作性.     

一种求解随机期望值模型的改进差分进化算法

针对随机期望值模型的特点,将随机模拟技术和松弛选择策略相结合,提出了一种改进的差分进化算法.并将该算法用于求解报童问题等模型,数值结果表明了算法的有效性和可行性.     

生物地理学算法求解一类非线性线性双层规划

用生物地理学优化算法的实数编码来求解下层为凸规划的非线性双层规划问题。基于上层目标函数设置了一种新的适宜度函数,可以简单区分不同类型的解;对下层问题先用坐标轮换法求解,然后利用基于下层问题的KKT最优性等价条件来检验求解结果。分别运用4种不同的迁移率模型来求解问题,实验结果表明,生物地理学优化算法求解这类双层问题是稳定、有效的。     

一种求解最小割的警示传播算法

最小割问题（minimum cut problem）是NP（Non-deterministic Polynomial）难问题,警示传播算法（warning propagation）是一种基于因子图的消息传递算法,可用于求解组合优化问题.首先,本文借助隐马尔可夫模型将无向图转换为因子图,将求解最小割映射为求解因子图的相应问题.进而设计一种求解最小割的警示传播算法.最后,选取了几组随机无向图实例进行数值实验,实验结果表明,该算法在求解速度上优于同类算法.     

基于树核度的社交网络影响最大化问题

社交网络中的影响最大化问题是指对于给定的k值,寻找k个在特定传播模型下能够使得传播范围达到最大的节点.此问题在常用的几种传播模型中都是NP-难的.目前虽然已经有很多近似求解的算法,但如何在较低的算法时间复杂度下,保证较大的传播范围仍然是求解该问题的一个挑战.为此,本文提出了一种新颖的基于图的树核度理论的方法来求解社交网络影响最大化问题,并相应地给出了一个多项式时间的算法.所提算法综合考虑了网络的结构特征和传播特征.另外,我们将该算法与传统的随机、度以及贪心算法进行了比较.实验结果表明,所提算法可以较快地找到能够使得传播范围较大的节点集合.     

基于粒子群优化算法的Logistic模型参数估计

将Logistic模型的参数估计问题转化为一个多维无约束函数优化问题,然后利用粒子群优化算法(PSO)的全局搜索能力对此问题求解.仿真实验中所使用的数据包括真实数据和随机采样数据.实验结果表明,在这两种数据条件下PSO算法均能够较准确地估计获得Logistic模型的参数,证实了PSO算法是Logistic模型参数估计的一种可靠有效的算法.同时也分析了参数维数和噪声对PSO算法的收敛性和稳定性的影响.     

求解随机线性互补问题的Barzilai-Borwein算法

随机线性互补是一类特殊的互补问题。常用的求解方法是先将其转化为约束极小化模型,然后用优化算法求解该模型。文中针对随机线性互补问题的期望残差极小化模型,通过使用Barzilai-Borwein步和有效集策略,提出了求解该模型的Barzilai-Borwein算法。实验结果表明,该算法与光滑投影梯度法相比,能在更短的时间内得到相应的数值结果。     

线性逆问题求解的多尺度降阶模型

基于相对误差协方差矩阵信息,该文给出线性逆问题求解的多尺度降阶模型,把高阶模型的求解问题转化为一个近似的低阶模型再进行求解．利用该降阶模型可以得到与完全模型相当的估计效果,同时又能大大降低逆算法的计算量,从而有效地解决逆问题求解中计算复杂度过高的难题,增强逆问题求解算法的可实施性,采用降阶模型进行求解还可以增加那些提供显著信息的点的估计精度。     

深亚微米HCI模型参数多目标全域提取方法

研究了一种建立在退化栅电流物理解析模型基础上的深亚微米pMOS器件HCI(hot carrier injection)退化模型.提出了一种基于L-M(Levenberg-Marquardt)算法的多目标响应全域优化提取策略,并对可靠性模型参数进行优化提取.分析了优化过程中由于参数灵敏度过低产生的问题并提出采用递归算法求解不同时刻栅电流注入电荷量的加速计算方法.最后,给出了最优化参数提取的结果,并且将测量值与理论值进行了比较,得到很好的一致性.     

应用改进自蛇模型和L-R算法恢复毫米波图像

在毫米波的图像恢复中,L-R算法是一种简单而有效的非线性方法,但当噪声不可忽略时,L-R算法难以获得较好的复原结果。针对毫米波图像数据量少和图像分辨率低的特点,提出基于改进自蛇模型和L-R算法毫米波图像恢复方法,以局部方差构造自蛇模型的边缘停止函数,其改进自蛇模型在消除噪声的同时更能够保留图像中的边缘和细节特征,然后使用L-R算法进行图像恢复,这种改进算法通过使用基于改进自蛇模型去噪能有效地减少噪声对L-R算法的影响。实验结果表明:在信噪比和相关度方面本文算法提高了L-R算法的性能,可用于含噪声的图像复原。     

多站测向定位中递归加权最小二乘法的技术分析

最小二乘法常用于多站测向定位,文章在现有最小二乘法模型基础上,推导了一种递归加权的最小二乘法模型,并与非递归的最小二乘法模型在运算量上进行了比较,发现在测向站较多的情况下（多于6站）,递归的最小二乘法模型比非递归的最小二乘法模型在运算量上要小,最后绘出了不同数量测向站的GDOP图,发现在一定误差条件下,随着测向站的增加,定位精度的提高并不是很明显。     

IEEE 802.11 DCF差错帧模型的分析与仿真算法改进

该文提出了IEEE802.11DCF差错帧模型的概念,并在详细分析这一模型的基础上,指出了GloMoSim仿真环境中现有的DCF差错帧模型仿真算法存在的问题,然后严格按照DCF差错帧模型中的相关规约改进了该仿真算法。仿真与分析表明,与GloMoSim中现有的仿真算法相比,改进后的仿真算法能正确地模拟IEEE802.11DCF协议处理差错帧的相关规约,为仿真实验提供了更加可靠的结果。     

Recursive blind identification of non-Gaussian time-varying ARmodel and application to blind equalisation of time-varying channel

A novel method for the blind identification of a non-Gaussian time-varying autoregressive model is presented. By approximating the non-Gaussian probability density function of the model driving noise sequence with a Gaussian-mixture density, a pseudo maximum-likelihood estimation algorithm is proposed for model parameter estimation. The real model identification is then converted to a recursive least squares estimation of the model time-varying parameters and an inference of the Gaussian-mixture parameters, so that the entire identification algorithm can be recursively performed. As an important application, the proposed algorithm is applied to the problem of blind equalisation of a time-varying AR communication channel online. Simulation results show that the new blind equalisation algorithm can achieve accurate channel estimation and input symbol recovery     

色噪声环境下GTD模型的参数估计

本文将能够精确描述高频电磁散射的GTD信号模型引入MUSIC算法,并对MUSIC算法做了相应改进。提出利用特征分析方法中信号与噪声子空间正交特性,使改进后的MUSIC算法既能够精确估计目标散射中心位置,又能估计散射中心类型。本文采用基于四阶累量的MUSIC算法,在一定程度上克服了高斯色噪声对MUSIC算法的影响,拓宽了GTD 模型参数求解的条件。     

卡尔曼滤波算法在单站无源定位中的应用

针对传统卡尔曼滤波算法在单站无源定位中的不足,提出了一种基于CV模型的卡尔曼滤波算法,阐述了卡尔曼滤波算法和CV模型,对基于CV模型的卡尔曼滤波算法在单站无源定位中的应用进行了仿真分析。仿真结果表明改进卡尔曼滤波算法能有效提高定位精度。     

基于最小模型组最优模型扩展的机动目标跟踪方法

针对变结构多模型算法中模型集自适应较复杂,且模型扩展受模型结构限制等问题,提出了一种最小模型组最优模型扩展的机动目标跟踪算法。该算法以最小模型组作为基础有效模型集,采用模型组切换方法进行模型组自适应;并根据Kullback-Leibler距离准则在连续的模型空间中对基础模型组进行最优模型扩展。因此,该算法具有模型集自适应简单、模型激活不受模型结构的限制等优点。多组实验仿真结果表明:该算法既可以对相同结构的模型进行激活,也可以对不同结构的模型进行激活;在没有明显增加计算量的同时,提高了目标的跟踪精度,具有较好的跟踪效果。     

改进的“当前”统计模型变采样率目标跟踪算法

为满足实际雷达系统对高精度和高实时性的要求,提出了一种改进的"当前"统计模型变采样率机动目标跟踪算法。该算法针对"当前"统计模型必须预设加速度极值和机动频率的问题,提出一种加速度方差和机动频率在线同步自适应方法,建立改进的"当前"统计模型机动目标跟踪算法;针对在线自适应方法计算量大的问题,结合采样周期的大小与目标机动特性的关系,引入变采样率方法。仿真结果表明,与传统"当前"统计模型相比,改进的"当前"统计模型机动目标跟踪算法能显著提高对不同机动强度目标的跟踪精度;变采样率方法通过减少采样点数,节省了系统资源,提高了跟踪实时性;所提算法将两者结合,用传统的"当前"统计模型1.5~2倍的平均采样周期得到了更小的位置均方根误差,实现了用单模型方法同时改善跟踪精度和实时性的目的。     

基于模糊逻辑的改进自适应IMM跟踪算法

交互式多模型算法（IMM）和基于模糊控制的交互多模型算法（FIMM）是实际中常用的目标跟踪算法,然而其模型集合固定,当需要大量模型覆盖目标机动时,会导致计算量激增,且过多模型可能带来不必要的模型竞争,降低跟踪性能。针对这一缺陷,提出了一种基于模糊控制的改进自适应IMM算法（FAIMM）,采用一种模型概率的非线性映射处理方法实时筛选模型子集,剔除无用模型,增加有用模型的权重,并通过模糊推理机制自动调整过程噪声水平,使得算法对不同的目标机动模式具有更强的自适应能力。仿真结果表明,提出的算法跟踪性能优于IMM算法以及FIMM算法,能够更好地匹配目标的机动模式。      

区间量测下自适应交互多模型箱粒子滤波机动目标跟踪

针对现有交互多模型箱粒子滤波(Interacting Multiple Model Box Particle Filter,IMMBPF)算法在区间量测目标跟踪过程中模型切换和跟踪精度方面的不足,结合自适应交互多模型算法,提出了一种自适应交互多模型箱粒子滤波(Adaptive IMMBPF,AIMMBPF)算法。该算法利用模型似然后验信息构建修正因子,并结合阈值对马尔可夫转移概率矩阵进行自适应修正,使得匹配模型的概率快速增大,并且可以减小非匹配模型的影响,即使在目标运动模型先验信息不足或者不准确情况下,也能对模型转移概率进行自适应更新。对于量测常受到未知分布和偏差的区间误差所影响而呈现区间形式的问题,将箱粒子代替普通粒子,拟合后验概率密度从而进行滤波。仿真结果表明,相比于原有算法,该算法在区间量测机动目标跟踪的应用中,拥有更优的模型匹配度和目标跟踪精度。