基于进化规划的运动估计算法

本文将进化规划引入了运动估计问题的求解中,在算法中还引入了像素疏值法,从而使得算法的运算量大为减少,而运动估计的精度没有明显下降。实验表明,本文算法的运算量甚至少于三步搜索法（3SS）,而获得的图像质量优于三步搜索法,接近全搜索算法（FS）。     

基于进化编程的改进GLA算法

文中提出的矢量量化算法以种群为基础,通过变异算子提高种群的平均适应值,使其逃离局部最小点。降低了该算法对初始码书的敏感程度,然后使用选择算子对种群进行有针对性地操作。高斯－马尔可夫序列实验表明,该算法较好地实现了全局最优,并有助于克服对初始码本较为敏感的缺点。     

An improved quantum-inspired evolutionary algorithm for coding resource optimization based network coding multicast scheme

This paper investigates how to minimize the required coding resources in network-coding-based multicast scenarios. An evolutionary algorithm (MEQEA) is proposed to address the above problem. Based on quantum-inspired evolutionary algorithm (QEA), MEQEA introduces multi-granularity evolution mechanism which allows different chromosomes, at each generation, to have different rotation angle step values for update. In virtue of this mechanism, MEQEA significantly improves its capability of exploration and exploitation, since its optimization performance is no longer overly dependant upon the single rotation angle step scheme shared by all chromosomes. MEQEA also presents an adaptive quantum mutation operation which is able to prevent local search efficiently. Simulations are carried out over a number of network topologies. The results show that MEQEA outperforms other heuristic algorithms and is characterized by high success ratio, fast convergence, and excellent global-search capability.     

一种基于进化模型的聚类算法

对于模糊聚类算法对初值或者隶属度矩阵敏感,不能保证收敛到全局最优解的问题,文中提出了一种新的进化聚类算法遗传模拟退火聚类算法SAGA-FCM。利用模拟退火算法较强的局部搜索能力和遗传算法较强的全局搜索能力,以避免模糊聚类算法收敛到局部极值或鞍点。实验对不同的人工数据集进行测试,结果分析表明SAGA-FCM算法有比较好的收敛值和收敛速率,具有良好的聚类效果。     

An algorithm for compression of bilevel images

This paper presents the block arithmetic coding for image compression (BACIC) algorithm: a new method for lossless bilevel image compression which can replace JBIG, the current standard for bilevel image compression. BACIC uses the block arithmetic coder (BAC): a simple, efficient, easy-to-implement, variable-to-fixed arithmetic coder, to encode images. BACIC models its probability estimates adaptively based on a 12-bit context of previous pixel values; the 12-bit context serves as an index into a probability table whose entries are used to compute p(1) (the probability of a bit equaling one), the probability measure BAC needs to compute a codeword. In contrast, the Joint Bilevel Image Experts Group (JBIG) uses a patented arithmetic coder, the IBM QM-coder, to compress image data and a predetermined probability table to estimate its probability measures. JBIG, though, has not get been commercially implemented; instead, JBIG's predecessor, the Group 3 fax (G3), continues to be used. BACIC achieves compression ratios comparable to JBIG's and is introduced as an alternative to the JBIG and G3 algorithms. BACIC's overall compression ratio is 19.0 for the eight CCITT test images (compared to JBIG's 19.6 and G3's 7.7), is 16.0 for 20 additional business-type documents (compared to JBIG's 16.0 and G3's 6.74), and is 3.07 for halftone images (compared to JBIG's 2.75 and G3's 0.50).     

An algorithm for solving discrete-time Wiener-Hopf equations based upon Euclid's algorithm

An algorithm for solving a discrete-time Wiener-Hopf equation is presented based upon Euclid's algorithm. The discrete-time Wiener-Hopf equation is a system of linear inhomogeneous equations with a given Toeplitz matrix M, a given vector b, and an unknown vectorlambdasuch thatMlambda = b. The algorithm is able to find a solution of the discrete-time Wiener-Hopf equation for any type of Toeplitz matrices except for the all-zero matrix, while the Levinson algorithm and the Trench algorithm are not available when at least one of the principal submatrices of the Toeplitz matrixMis singular. The algorithm gives a solution, if one exists, even when the Toeplitz matrixMis singular, while the Brent-Gustavson-Yun algorithm only states that the Toeplitz matrixMis singular. The algorithm requiresO(t^{2})arithmetic operations fortunknowns, in the sense that the number of multiplications or divisions is directly proportional tot^{2}, like the Levinson and Trench algorithms. Furthermore, a faster algorithm is also presented based upon the half greatest common divisor algorithm, and hence it requiresO(t log^{2} t)arithmetic operations, like the Brent-Gustavson-Yun algorithm.     

A dynamic programming algorithm for nonlinear smoothing

This paper presents a smoothness optimization approach to the nonlinear smoothing problem. Linear smoothing techniques fail to provide adequate results for curves which exhibit both sharp discontinuities to be preserved and, due to measurement or processing errors, outliers and noise to be filtered out. The nonlinear algorithm is based on a criterion for the overall smoothness of the curve. The smoothness criterion is optimized by a dynamic programming strategy. The resulting algorithm turns out to be computationally attractive. The computation time grows proportionally to N² and the storage requirements are 2N locations where N is the number of samples to be smoothed. The algorithm is applied to smoothing pitch contours.     

一种基于动态规划的雷达合批新算法

针对信号分选结果增批现象严重、影响识别准确度的问题,通过分析实际侦收信号的特点,并借鉴生物信息学中动态规划比对算法的思想,提出了对脉冲重复周期（PRI）信号在载频维和脉宽维进行合批的方法,并结合该方法设计了动态合批处理流程。该算法通过比较两批数据在PRI值及其排列顺序上的相似性来进行合批,利用PRI周期性这一很稳定的特征较好地解决了批信号在载频和脉宽维上的增批问题。仿真结果表明,该算法在存在脉冲丢失和干扰脉冲的情况下仍能准确合批。     

An architectural level test generator based on nonlinear equation solving

It has been shown that the hierarchy of large VLSI circuits can be exploited to speed up the test generation process. However, severe problems remain in most of the published literature which were based on a high level branch-and-bound approach. When the circuit module diagram is complex, it is very difficult to formalize the high level knowledge derived from the circuit hierarchy to make successful decisions in searching. Whenever a global path conflict or value conflict happens, it is unlikely that the backtracking scheme is able to solve this conflict through high level knowledge manipulation. In this article, a new architectural level test generation algorithm based on a nonlinear equation-solving methodology is proposed to solve conflicts and avoid making high level decisions when the tests are computed. For each pattern to be justified at a high level, an instruction sequence and the under-determined system of nonlinear equations are derived based on preprocessing information. The solution of the system of equations are calculated by a signal-driven discrete relaxation algorithm without making any high level decision. The test generation is performed by recursively assembling the instruction sequence and solving the system of equations. This new test generation approach has been implemented, and the tests of several microprocessors have been generated successfully. The results show that this approach is effective and promising.This research was supported by the Semiconductor Research Corporation under Contract SRC 91-DP-109. A preliminary version of this paper appeared in ICCAD-91.     

FWM aware evolutionary programming algorithm for transparent optical networks

This paper proposes and evaluates a four-wave mixing (FWM) aware evolutionary programming algorithm for dynamically setting up lightpaths in an optical wavelength division multiplexed network (WDM network). The proposed algorithm also considers the effect of amplified spontaneous emission noise (ASE noise) on a lightpath during propagation of the optical signal from any source to the intended destination. As crosstalk due to FWM and ASE noise are two transmission impairments that degrade the quality of optical signal even at low to medium data rates, it is mandatory for an algorithm for dynamic routing and wavelength assignment in a WDM network to consider the effect of these two impairments on the lightpath to be established. The distinguishing feature of the proposed algorithm is that it is based on an initial population of a single individual and uses a fitness function that is expressed in terms of the number of hops, path cost, variance contributions due to FWM crosstalk, amplifier noise, and different beat noises at the receiver. The performance of a newly introduced FWM aware priority-based wavelength assignment technique is compared with few of the existing wavelength assignment techniques in the present work.     

Ant colony algorithm of partially optimal programming based on dynamic convex hull guidance for solving TSP problem

To solve basic ant colony algorithm’s drawbacks of large search space,low convergence rate and easiness of trapping in local optimal solution,an ant colony algorithm of partially optimal programming based on dynamic convex hull guidance was proposed.The improved algorithm dynamically controlled the urban selection range of the ants,which could reduce the search space of ants on basis of helping the algorithm to jump out of local optimal solution to global optimal solution.Meanwhile,the delayed drift factor and the convex hull constructed by the cities to be chosen were introduced to intervene the current ants’ urban choice,it could increase the diversity of the early solution of the algorithm and improve the ability of ants’ partially optimal programming.Then the pheromone updating was coordinated by using construction information of convex hull and the complete path information that combined local with whole,it could improve the accuracy of the algorithm by guiding the subsequent ants to partially optimal programming.The pheromone maximum and minimum limit strategy with convergence was designed to avoid the algorithm’s premature stagnation and accelerate the solving speed of the algorithm.Finally,the proposed algorithm was applied to four classic TSP models.Simulation results show that the algorithm has better optimal solution,higher convergence rate and better applicability.     

一种基于二阶锥规划的新时差定位算法

针对传统时差定位算法在量测噪声较大情况下定位性能不佳的缺点,提出了一种基于二阶锥规划的新时差定位算法.该算法通过凸松弛和引入惩罚项,将难以求解的用户位置最大似然估计问题转换为一个易于求解的二阶锥规划问题,并将松弛问题的最优解作为用户位置的初始估计,利用传统的泰勒级数展开法得到最终定位结果.仿真给出了不同基站数目及量测噪声下算法的定位性能.仿真结果表明,在量测噪声较大的情况下,新算法的定位精度仍可以逼近理论克拉美罗下限,而且算法中惩罚因子的选取范围易于确定.     

Hybrid social cognitive optimization algorithm for constrained nonlinear programming

To improve the global convergence speed of social cognitive optimization (SCO) algorithm,a hybrid social cognitive optimization (HSCO) algorithm based on elitist strategy and chaotic optimization is pr...     

基于禁止搜索的非线性时间匹配优化算法

动态时间规整算法DTW(Dynamic Time Warping)作为一种非线性时间匹配技术已成功地应用于语音识别系统中。DTW算法使用动态规划技术来搜索两个时间序列的最优规整路径,虽然这种算法计算量小,运算时间较短,但只是一种局部优化算法。禁止搜索TS(Tabu Search)算法是一种具有短期记忆的广义启发式全局搜索技术,适用于解决许多非线性优化问题。本文将该技术用于语音识别系统中,提出了基于禁止搜索的非线性时间规整的优化算法TSTW,使得时间规整函数尽可能逼近全局最优。仿真结果表明,TSTW比DTW有更高的识别率,且运行时间比遗传时间规整算法GTW大大减少。     

基于进化规划求解最优通信生成树

本文分析了使用遗传算法求解最优通信生成树的缺陷,提出了基于进化规划求解最优通信生成树的新方法,并将这一方法扩展到有约束最优通信生成树问题。仿真结果验证了算法的有效性。     

一种病态线性系统求解的新算法

本文提出了一种病态线性系统求解的新算法,该算法将原线性系统求解的问题转化为极小值点的最优化问题,借助不对分寻优法进行迭代求解,并结合引入的伪误差来解决当方程组阶数非常大时出现的误差积累问题。文末算例实验表明,本文算法对于良态线性系统、病态线性系统均有较好的求解效果。该算法为病态线性系统利用计算机迭代求解提供了直接的参考方法。     

求解DEC-POMDP问题的改进遗传算法

分布式部分可观测马尔科夫模型(Decentralized partially observable Markov decision progress,DEC-POMDP)是研究不确定性情况下多主体协同决策的重要模型。由于其求解难度是NEXP-complete,所以迄今为止尚没有有效的算法能求出其最优解。但是存在一部分近似求解的算法可以解决规模较小的问题。针对此问题,在遗传算法的基础上,通过引入最佳起始状态和最佳收益状态提出改进的遗传算法(Improved Genetic Algorithms,IGA),算法将问题的求解分为两个步骤,首先求解从给定起始状态到最佳起始状态的近似最优策略,然后求解在最佳收益状态之间转换的策略。通过实验可以看出IGA压缩了要搜索的策略空间,减小了编码长度,是求解DEC-POMDP的有效算法。     

An efficient algorithm for solving general periodic Toeplitzsystems

An efficient algorithm is presented for inverting matrices which are periodically Toeplitz, i.e., whose diagonal and subdiagonal entries exhibit periodic repetitions. Such matrices are not per symmetric and thus cannot be inverted by Trench's (1964) method. An alternative approach based on appropriate matrix factorization and partitioning is suggested. The algorithm provides certain insight on the formation of the inverse matrix, is implementable on a set of circularly pipelined processors and, as a special case, can be used for inverting a set of block Toeplitz matrices without requiring any matrix operation     

An efficient algorithm for solving Zakharov-Shabat inversescattering problem

An efficient numerical method for solving Zakharov-Shabat (ZS) inverse scattering problem is presented. In this method, instead of equivalent second-order differential equations to the Gel'fand-Levitan-Marchenko (GLM)-type integral equations, equivalent first-order differential equations are adopted and sufficiently accurate solutions to Zakharov-Shabat inverse problem can be achieved without iterations. Examples for applying it to design nonuniform transmission line (NTL) filters are also provided     

Unconditionally-stable FDTD method based on Crank-Nicolson scheme for solving three-dimensional Maxwell equations

The approximate-factorisation-splitting (CNAFS) method as an efficient implementation of the Crank-Nicolson scheme for solving the three-dimensional Maxwell equations in the time domain, using much less CPU time and memory than a direct implementation, is presented. At each time step, the CNAFS method solves tridiagonal matrices successively instead of solving a huge sparse matrix. It is shown that CNAFS is unconditionally stable and has much smaller anisotropy than the alternating-direction implicit (ADI) method, though the numerical dispersion is the same as in the ADI method along the axes. In addition, for a given mesh density, there will be one value of the Courant number at which the CNAFS method has zero anisotropy, whereas the Crank-Nicolson scheme always has anisotropy. Analysis shows that both ADI and CNAFS have time step-size limits to avoid numerical attenuation, although both are still unconditionally stable beyond their limit.