正弦曲线拟合若干问题探讨

研究了测量噪声较小情况下正弦曲线的最小二乘多项式拟合误差与拟合阶数的关系,分别采用均方误差和误差平方和分析了测量噪声以及测量数据有效位数对拟合误差的影响,对多周期正弦曲线拟合以及正弦曲线的外推存在的问题进行了探讨,指出了正弦曲线的最小二乘多项式拟合方法的局限性.最后,提出了一种基于傅利叶变换的频率已知正弦曲线拟合方法,仿真结果表明其性能优于最小二乘多项式拟合方法.     

基于随机Hough变换的零基线正弦曲线检测

研究零基线正弦曲线的随机Hough变换的最小点集、收敛映射和动态链接表结构3个基本问题,提出改进的三点拟合零基线正弦曲线的方法,给出零基线正弦曲线的随机Hough变换检测算法,并分析算法的计算性能和存储量性能。仿真实验表明该方法的有效性。     

一种传播模型无关的快速WiFi访问点定位算法

在一个未知环境中定位无线WiFi访问点(AP),由于传播介质的衰减参数是时变的,导致传统三点定位方法会产生较大的定位误差.但定位AP与常见的终端定位相比具有其特殊性,即信号源是单一的,因此信号源的功率变化在多个终端处可以通过差分计算消除.基于信号源定位的特殊性,研究实现了一种与传播模型参数无关的定位算法,对多个观测点的测量数据,定义了一个与无线信号传播模型无关的评价函数,从而将定位问题转换为对该评价函数的最小化问题,因此可利用已有的数值计算方法优化计算效率,最终实现基于信号强度的快速WiFi AP定位.     

基于支持向量回归的非线性多功能传感器信号重构

在多功能传感器信号重构中,通常采用经验风险最小化准则实现函数回归,在小样本情况下,该方法易导致泛化性差和过拟合问题.本文利用支持向量回归方法实现非线性多功能传感器信号重构,支持向量机是基于结构风险最小化准则的新型机器学习方法,可有效抑制过拟合问题并改善泛化性能.仿真结果表明经该算法重构后的信号重构误差率在0.4%以下,重构效果较好,验证了该算法的有效性.     

调幅信号的数字化解调

介绍一种用三参数正弦波拟合算法实现的、绝对收敛的四参数最小二乘正弦波拟合算法,给出了其收敛区间、绝对收敛判据以及实现过程.在此基础上讨论实现正弦载波的调幅信号的精确解调问题.使用一个周期的正弦波曲线模型的滑动拟合法,实现了幅度调制信号波形的精确解调.在调制信号也是正弦波的情况下,仿真评价了幅度解调效果,并给出了解调失真的计算方法和结果.同时,在一个实测调幅曲线波形上进行的解调分析,获得了非常明确的波形测量结果.本方法是评价载波为正弦波的调幅信号的一种优良方法,准确度高、分辨力高,可用于调幅信号源及其解调设备的指标评价和计量.     

麦克劳林级数法求取光电编码器转子位置算法

由于制作工艺使得光栅线数受到限制,增量式光电编码器每转一周输出的脉冲数量有限,已无法满足高精度伺服系统的控制性能要求.根据正余弦编码器输出的正弦信号,将一个周期分为八个小区间,继而根据麦克劳林近似公式,提出反向数据拟合方法直接拟合出正弦信号对应的相位值,进一步得到转子的精确位置,使得计算精度高、运行速度快,解决了电机极低速运行时角度精度低的问题.搭建了实际电路及测试平台,得到了与理论分析相一致的效果.     

基于TDLAS技术气体浓度测量的快速拟合方法

基于可调谐二极管激光吸收光谱(Tunable Diode Laser Absorption Spectroscopy,TDLAS)技术的气体浓度测量系统通常以吸收光谱的归一化二次谐波信号反演气体浓度。然而以常用的数字锁相技术提取归一化二次谐波信号的方法消耗资源多、计算量大。为简化计算量,一种基于广义级数展开快速拟合的方法被提出,首先测量激光器的入射平均光强,结合光强调制系数计算线型函数及其平方项的傅里叶展开系数,即可拟合出归一化二次谐波信号。构建了CO2气体吸收光谱检测实验,实验测试及仿真计算结果表明采用本文方法拟合的结果与通过数字锁相技术实测的信号之间最大相对误差仅为2‰,计算消耗的时间却远小于后者,简化了系统资源,有利于TDLAS技术气体浓度测量系统的小型化、数字化。     

基于二元多项式拟合法的压力传感器输入信号重构

为了同时解决压力传感器输出特性的非线性和温度漂移问题,提出利用二元多项式根据传感器输出信号及其内部温度来重构被测压力.给出了被测压力重构模型的具体形式,以传感器静态特性标定试验数据为依据,利用最小二乘法求解模型系数矩阵,利用单点最大拟合误差、误差平方和模型阶次三项指标进行模型择优.基于重构模型给出了测量电路检测精度估算方法.本方法在传感器静态特性标定数据范围内得到了便于工程计算的一致表达式,同时解决了传感器的非线性和温度漂移两个主要问题,计算所用数据量大大小于插值法.某型硅谐振压力传感器的应用验证了本方法的合理性和有效性.     

一种旋转变压器误差分析和校正方法

针对旋转变压器输出信号存在误差影响其测角精度的问题,文中从旋转变压器自身结构、励磁信号的谐波干扰、噪声干扰三个主要方面出发,分析建立出被测角度的误差模型,通过采用24面棱体和白准直仪标定的方法获得角度实际误差值,结合通用全局优化算法的曲线拟合方法计算出误差模型参数。通过与其他三个模型的拟合误差进行比较,该模型的拟合误差最小,平均拟合误差小于0．05”。实验结果证明该模型具有很好的拟合效果,可以提高误差补偿校正精度。     

GPS高程拟合在水利测量中的应用研究

常见高程系统包括大地高、正高及正常高系统,由于 GPS 测量的大地高在实际测量中的应用十分有限,须采用高程拟合技术,将大地高转换成为正常高,但转换过程中会出现高程异常,因此采用拟合方程对已知高程进行异常处理。高程拟合方法包括多项式与多面函数拟合法,在 GPS 拟合原理基础上,对二次多项式、 三次多项式、多面函数 3 种拟合方法的高程异常及拟合差值进行分析计算,并将拟合方法应用于地形起伏差异不同的 2 个测区,对 3 种拟合方法的精度评定进行比较分析。结果表明：三次多项式拟合方法的精度要优于二次多项式和多面函数的拟合精度,说明三次多项式拟合更适用于水利测绘工程,且通过三次多项式拟合方法可减少水利测量工作,提高测量精度和工作效率。     

一种可重构阵列的最小瑕点覆盖算法

关于可重构阵列的瑕点覆盖问题受到了很多文献的关注，特别地，关于可重构阵列的最小瑕点覆盖问题等价于二分图的受约束最小点覆盖问题，并被证明是NP-完全问题。针对本问题提出的算法运行时间为O(1．19^k kn)，这里k为可替换行与列的数目，改进了原有的最好结果，其运行时间为0(1．266k kn)，较好地组合并扩展了研究参数计算的最新技术与经典匹配理论，且具有较好的实用价值。这是关于可重构阵列的最小瑕点覆盖问题算法又一较大的改进，也是目前最小点覆盖问题相关参数算法的较有意义的改进。     

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

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

基于双标签集的标签匹配集成学习算法

当标识示例的两个标签分别来源于两个标签集时,这种多标签分类问题称之为标签匹配问题,目前还没有针对标签匹配问题的学习算法。 尽管可以用传统的多标签分类学习算法来解决标签匹配问题,但显然标签匹配问题有其自身特殊性。 通过对标签匹配问题进行深入的研究,在连续AdaBoost(real Adaptive Boosting)算法的基础上,基于整体优化的思想,采用算法适应的方法,提出了基于双标签集的标签匹配集成学习算法,该算法能够较好地学习到标签匹配规律从而完成标签匹配。 实验结果表明,与传统的多标签学习算法用于解决标签匹配问题相比,提出的新算法不仅缩小了搜索的标签空间的范围,而且最小化学习误差可以随着分类器个数的增加而降低,进而使得标签匹配分类更加快速、准确。     

求解含非线性参数的QoS路由的启发式算法

具有非线性参数的QoS路由分为含有非线性约束条件的QoS路由和含有非线性优化目标的QoS路由两类，它们都是NP问题．提出了两种启发式算法求解这两类QOS路由优化问题问题．对第一类问题，求解去掉非线性约束条件后的优化问题．如果找到的解满足非线性约束条件，则该解是最优解；否则在优化问题中添加一个新的线性约束，将已得到的解去掉，反复下去就可得到最终解．对第二类问题，将非线性优化目标换为约束条件中的线性参数，求解此优化模型，如果有解，则记录此时对应的非线性目标值．而后增加一个新的线性约束，去掉刚才得到的解，比较两次得到的非线性目标值，保留最小值．如果得到的解不满足该线性参数的约束条件，则算法结束；否则继续迭代．证明了两种算法的收敛性，并且时间复杂性为近似多项式时间．计算实例表明了算法的有效性．     

Design and Performance Evaluation of Sequence Partition Algorithms

Tradeoffs between time complexities and solution optimalities are important when selecting algorithms for an NP-hard problem in different applications. Also, the distinction between theoretical upper bound and actual solution optimality for realistic instances of an NP-hard problem is a factor in selecting algorithms in practice. We consider the problem of partitioning a sequence of n distinct numbers into minimum number of monotone （increasing or decreasing） subsequences. This problem is NP-hard and the number of monotone subsequences can reach [√2n＋1/1-1/2]in the worst case. We introduce a new algorithm, the modified version of the Yehuda-Fogel algorithm, that computes a solution of no more than [√2n＋1/1-1/2]monotone subsequences in O（n^1.5） time. Then we perform a comparative experimental study on three algorithms, a known approximation algorithm of approximation ratio 1.71 and time complexity O（n^3）, a known greedy algorithm of time complexity O（n^1.5 log n）, and our new modified Yehuda-Fogel algorithm. Our results show that the solutions computed by the greedy algorithm and the modified Yehuda-Fogel algorithm are close to that computed by the approximation algorithm even though the theoretical worst-case error bounds of these two algorithms are not proved to be within a constant time of the optimal solution. Our study indicates that for practical use the greedy algorithm and the modified Yehuda-Fogel algorithm can be good choices if the running time is a major concern.     

Restoration of images degraded by motion blur and noise

This paper considers the restoration of images degraded by a motion blur in the presence of noise. Based on a two-dimensional separable autoregressive image model, a one-dimensional horizontally causal vector state space model with multiple delays is derived. By the discrete sine transform, the one-dimensional vector state space model is decomposed into a set of nearly uncorrelated scalar subsystems, to which the Kalman filter is applied to obtain an approximate recursive computationally efficient restoration algorithm for motion degraded images. The same technique is also applied to a semicausal minimum variance image model in order to derive a related recursive restoration algorithm. The computational efficiency is accomplished by the discrete sine transform and the transform data compression technique. Numerical results are presented to show the applicability of the algorithms developed. Finally, the possible extension of the present method to the case of general blur is suggested.     

一种解决TSP的改进遗传算法

旅行推销员问题TSP(Traveling Salesman Problem)问题是组合优化中的经典NP难题,一些典型的遗传算法(GA)在求解TSP问题时的性能并不理想.提出基于"最小邻域接入法"CBMC(Connecting Based on Minimum Circle)思想的改进的遗传算法,并在算法中增加一些控制策略,与其他算法相比,获得了更好的性能和收敛速度.通过用中国33个省会的TSP问题对提出算法进行实验验证,结果证明了改进后的算法在收敛速度和收敛到最优解的概率都优于其他遗传算法.     

Application of heuristic and hybrid-GASA algorithms to tool-path optimization problem for minimizing airtime during machining

In this paper, heuristic algorithms such as simulated annealing (SA), genetic algorithm (GA) and hybrid algorithm (hybrid-GASA) were applied to tool-path optimization problem for minimizing airtime during machining. Many forms of SA rely on random starting points that often give poor solutions. The problem of how to efficiently provide good initial estimates of solution sets automatically is still an ongoing research topic. This paper proposes a hybrid approach in which GA provides a good initial solution for SA runs. These three algorithms were tested on three-axis-cartesian robot during milling of wood materials. Their performances were compared based on minimum path and consequently minimum airtime. In order to make a comparison between these algorithms, two cases among the several milling operations were given here. According to results obtained from these examples, hybrid algorithm gives better results than other heuristic algorithms alone. Due to combined global search feature of GA and local search feature of SA, hybrid approach using GA and SA produces about 1.5% better minimum path solutions than standard GA and 47% better minimum path solutions than standard SA.     

求解度约束最小生成树的一种改进算法

度约束最小生成树问题是网络设计和优化中的一个NP-hard问题。提出一种求解网络G关于指定节点的最大度约束最小生成树的改进算法。算法在保证指定节点最大度的前提下,通过选取剩余边中权最小的边加入当前网络,得到网络G关于指定节点的最大度最小生成树,同时对算法的复杂度进行了分析。最后通过与其他算法的仿真比较,表明新算法的有效性和通用性。     

Deadline guaranteed packet scheduling for overloaded traffic in input-queued switches

Many applications need to solve the deadline guaranteed packet scheduling problem. However, it is a very difficult problem if three or more deadlines are present in a set of packets to be scheduled. The traditional approach to dealing with this problem is to use EDF (Earliest Deadline First) or similar methods. Recently, a non-EDF based algorithm was proposed that constantly produces a higher throughput than EDF-based algorithms by repeatedly finding an optimal scheduling for two classes. However, this new method requires the two classes be non-overloaded, which greatly restricts its applications. Since the overloaded situation is not avoidable from one iteration to the next in dealing with multiple classes, it is compelling to answer the open question: Can we find an optimal schedule for two overloaded classes efficiently? This paper first proves that this problem is NP-complete. Then, this paper proposes an optimal preprocessing algorithm that guarantees to drop a minimum number of packets from the two classes such that the remaining set is non-overloaded. This result directly improves on the new method.