启发式算法设计中的骨架分析与应用

骨架是指一个NP-难解问题实例的所有全局最优解的相同部分, 因其在启发式算法设计中的重要作用而成为该领域的研究热点. 本文对目前骨架及相关概念的研究成果进行了全面综述, 将骨架本身的研究工作归纳为三个层面: 理论基础层面主要考虑骨架与计算复杂性的关系问题; 应用基础层面主要考虑如何高效地获取骨架; 应用层面主要考虑如何利用骨架进行高效启发式算法设计. 在此基础上, 本文详细讨论了骨架研究亟待解决的难题, 并指出了解决这些问题的努力方向.     

AE1: An extension matrix approximate method for the general covering problem

A new approach, the extension matrix approach, is introduced and used to show that some optimization problems in general covering problem areNP-hard. Approximate solutions for these problems are given. Combining these approximate solutions, this paper presents an approximately optimal covering algorithm,AE1. Implementation shows thatAE1 is efficient and gives optimal or near optimal results.This research was supported in part by the National Science Foundation under Grant DCR 84-06801, Office of Naval Research under Grant N00014-82-K-0186, Defense Advanced Research Project Agency under Grant N00014-K-85-0878, and Education Ministry of the People's Republic of China.On leave from Harbin Institute of Technology, Harbin, China.     

求解QAP问题的近似骨架导向快速蚁群算法

QAP(quadratic assignment problem)问题是经典的组合优化问题之一,广泛应用于许多领域中.针对QAP问题,提出了一种新的蚁群算法--近似骨架导向的快速蚁群算法(ABFANT).该算法的基本原理是通过对局部最优解的简单相交操作得到QAP问题实例的近似骨架(approximate-backbone),利用这些近似骨架可以极大地缩小QAP问题的搜索空间,而同时不降低搜索的性能,最后对这个缩小后的搜索空间,直接用当前求解QAP问题最好的启发式算法之一-快速蚁群算法(FANT)求解得到问题的解.在QAPLIB中的典型实例上的实验结果表明,近似骨架导向的快速蚁群算法明显优于快速蚁群算法.此外,指出基于近似骨架的算法思想可以很容易地被移植到其他求解QAP问题的启发式算法中.     

Neural Network Algorithm for Designing FIR Filters Utilizing Frequency-Response Masking Technique

This paper presents a new joint optimization method for the design of sharp linear-phase finite-impulse response (FIR) digital filters which are synthesized by using basic and multistage frequency-response-masking(FRM) techniques.The method is based on a batch back-propagation neural network algorithm with a variable learning rate mode.We propose the following two-step optimization technique in order to reduce the complexity.At the first step,an initial FRM filter is designed by alternately optimizing th...     

旅行商问题优化解之间关系的分析

旅行商问题是经典的组合优化NP难题之一,学术界一直致力于建立在合理的计算时间内精确或近似求解问题的算法.近似算法常求得的高质量近似优化解与全局最优解之间边交集不为空,建立了两者之间及与全局最优解之间的特定关系,通过数学分析建立量化关系模型,利用实验确立模型中相关参数的先验概率.据此建立的随机TSP裁减过程大幅度裁减问题的求解规模;在求解过程中亦能高概率确定属于全局最优解的边,以提高问题求解效率和质量.     

Coding-based Join Algorithms for Structural Queries on Graph-Structured XML Document

In many applications, XML documents need to be modelled as graphs. The query processing of graph-structured XML documents brings new challenges. In this paper, we design a method based on labelling scheme for structural queries processing on graph-structured XML documents. We give each node some labels, the reachability labelling scheme. By extending an interval-based reachability labelling scheme for DAG by Rakesh et al., we design labelling schemes to support the judgements of reachability relationships for general graphs. Based on the labelling schemes, we design graph structural join algorithms to answer the structural queries with only ancestor-descendant relationship efficiently. For the processing of subgraph query, we design a subgraph join algorithm. With efficient data structure, the subgraph join algorithm can process subgraph queries with various structures efficiently. Experimental results show that our algorithms have good performance and scalability. Support by the Key Program of the National Natural Science Foundation of China under Grant No.60533110; the National Grand Fundamental Research 973 Program of China under Grant No. 2006CB303000; the National Natural Science Foundation of China under Grant No. 60773068 and No. 60773063.     

Adaptive blind separation of underdetermined mixtures based on sparse component analysis

The independence priori is very often used in the conventional blind source separation （BSS）. Naturally, independent component analysis （ICA） is also employed to perform BSS very often. However, ICA is difficult to use in some challenging cases, such as underdetermined BSS or blind separation of dependent sources. Recently, sparse component analysis （SCA） has attained much attention because it is theoretically available for underdetermined BSS and even for blind dependent source separation sometimes. However, SCA has not been developed very sufficiently. Up to now, there are only few existing algorithms and they are also not perfect as well in practice. For example, although Lewicki-Sejnowski＇s natural gradient for SCA is superior to K-mean clustering, it is just an approximation without rigorously theoretical basis. To overcome these problems, a new natural gradient formula is proposed in this paper. This formula is derived directly from the cost function of SCA through matrix theory. Mathematically, it is more rigorous. In addition, a new and robust adaptive BSS algorithm is developed based on the new natural gradient. Simulations illustrate that this natural gradient formula is more robust and reliable than Lewicki-Sejnowski＇s gradient.     

A pure quasi-human algorithm for solving the cuboid packing problem

We excavate the wisdom from an old Chinese proverb “gold corner, silver side and strawy void”, and further improve it into “maximum value in diamond cave” for solving the NP-hard cuboid packing problem. We extract, integrate and formalize the idea by west modern mathematical tools, and propose a pure quasi-human algorithm. The performance of the algorithm is evaluated on two sets of public benchmarks. For 100 strongly heterogeneous difficult benchmarks, experiments show an average packing utilization of 87.31%, which surpasses current best record reported in the literature by 1.83%. For 47 difficult benchmarks without orientation constraint, experiments show an average volume utilization of 92.05%, which improves current best record reported in the literature by 1.05%. Supported by the National Natural Science Foundation of China (Grant No. 60773194), the National Basic Research Program of China (Grant No. 2004CB318000), and Postdoctoral Science Foundation of China (Grant No. 20070420174)     

Parity conditions in homotopic knock-knee routing

We examine the impact ofevenness (all cuts having even free capacity) andlocal evenness (cuts that separate a single vertex having even free capacity) on homotopic knock-knee routing. Kaufmann and Mehlhorn have presented a linear-time algorithm for routing even instances. We show that routing locally even instances is NP-hard. If we are permitted to move modules slightly, however, then we can efficiently route any locally even instance in which the free capacity of every cut is nonnegative. This fact implies that locally even instances can be one-dimensionally compacted in polynomial time. But when the assumption of local evenness is dropped, routing again becomes NP-hard, whether or not modules may move.This work was supported in part by the Deutsche Forschungsgemeinschaft, Sonderforschungsbereich 124, Teilprojekt B2 (VLSI Entwurf und Parallelität), and in part by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, Grant NSF-STC88-09648. Miller Maley was also supported by a Mathematical Sciences Postdoctoral Research Fellowship from the National Science Foundation, Grant DMS-8705835.     

A moving object segmentation algorithm for static camera via active contours and GMM

Moving object segmentation is one of the most challenging issues in computer vision. In this paper, we propose a new algorithm for static camera foreground segmentation. It combines Gaussian mixture model (GMM) and active contours method, and produces much better results than conventional background subtraction methods. It formulates foreground segmentation as an energy minimization problem and minimizes the energy function using curve evolution method. Our algorithm integrates the GMM background model, shadow elimination term and curve evolution edge stopping term into energy function. It achieves more accurate segmentation than existing methods of the same type. Promising results on real images demonstrate the potential of the presented method. Supported by National Basic Research Program of China (Grant No. 2006CB303105), the Chinese Ministry of Education Innovation Team Fund Project (Grant No. IRT0707), the National Natural Science Foundation of China (Grant Nos. 60673109 and 60801053), Beijing Excellent Doctoral Thesis Program (Grant No. YB20081000401), Beijing Municipal Natural Science Foundation (Grant No. 4082025), and Doctoral Foundation of China (Grant No. 20070004037)     

Steady-state performance analysis of HOS-based blind adaptive multiuser detection

The blind adaptive multiuser detections based on higher-order statistics (HOS) can obtain higher steady-state decorrelating performance than the conventional linear algorithm under the high SNR condition. However, the closed-form analysis for this steady-state performance is scarce due to the complication of analyzing the nonlinear updates of the adaptive algorithm. An analysis approach based on ordinary differential equation (ODE) method is proposed to get the closed-form excess mean-square error (EMSE) expression of the HOS-based multiuser detections. The simulation and the comparison verify the results of the analysis. Supported by the National Natural Science Foundation of China (Grant No. 60432040), and the Guangxi Natural Science Foundation (Grant Nos. 0731026, 0731025)     

Multivariable direct adaptive decoupling controller using multiple models and a case study

In this paper, a multivariable direct adaptive controller using multiple models without minimum phase assumption is presented to improve the transient response when the parameters of the system jump abruptly. The controller is composed of multiple fixed controller models, a free-running adaptive controller model and a re-initialized adaptive controller model. The fixed controller models are derived from the corresponding fixed system models directly. The adaptive controller models adopt the direct adaptive algorithm to reduce the design calculation. At every instant, the optimal controller is chosen out according to the switching index. The interaction of the system is viewed as the measured disturbance which is eliminated by the choice of the weighing polynomial matrix. The global convergence is obtained. Finally, several simulation examples in a wind tunnel experiment are given to show both effectiveness and practicality of the proposed method. The significance of the proposed method is that it is applicable to a non-minimum phase system, adopting direct adaptive algorithm to overcome the singularity problem during the matrix calculation and realizing decoupling control for a multivariable system. Supported by the National Natural Science Foundation of China (Grant Nos. 60504010, 60864004), the National High-Tech Research and Development Program of China (Grant No. 2008AA04Z129), the Key Project of Chinese Ministry of Education (Grant No. 208071), and the Natural Science Foundation of Jiangxi Province (Grant No. 0611006)     

SNR estimation algorithm based on the preamble for wireless OFDM systems

Based on the analysis of the performance of Boumard＇s SNR method for wireless orthogonal frequency division multiplexing （OFDM） systems, a new estimation algorithm of the noise variance is proposed by only using the data samples of the two training symbols in the preamble, and the second order moment of these data samples is employed to estimate the signal power. The average SNR and the SNRs on the subchannels can all be estimated by the proposed algorithm, and its performance is independent of the channel＇s frequency selectivity. Simulation results show that the performance of the proposed method is highly improved and much better than that of Boumard＇s method.     

Analysis and side peaks identification of Chinese DTTB signal ambiguity functions for passive radar

Passive radar is one of the current research focuses. The implementation of the Chinese standard digital television terrestrial broadcasting (DTTB) creates a new opportunity for passive radar. DTTB system contains single-carrier and multicarrier application modes. In this paper, ambiguity functions of the DTTB signals in the single-carrier and multicarrier application modes are analyzed. Ambiguity function of the DTTB signal contains one main peak and many side peaks. The relative positions and amplitudes of the side peaks are derived and the reasons for the occurrence of the side peaks are obtained. The side peaks identification (SPI) algorithm is proposed for avoiding the false alarms caused by the side peaks. Experimental results show that the SPI algorithm can indentify all the side peaks without the power loss. This research provides the foundation for designing the DTTB based passive radar. Supported by the National Natural Science Foundation of China (Grant No. 60232010), the Ministerial Foundation of China (Grant No. A2220060039) and the National Natural Science Foundation of China for Distinguished Young Scholars (Grant No. 60625104)     

Demand-Driven Memory Leak Detection Based on Flow- and Context-Sensitive Pointer Analysis

We present a demand-driven approach to memory leak detection algorithm based on flow- and context-sensitive pointer analysis. The detection algorithm firstly assumes the presence of a memory leak at some program point and then runs a backward analysis to see if this assumption can be disproved. Our algorithm computes the memory abstraction of programs based on points-to graph resulting from flow- and context-sensitive pointer analysis. We have implemented the algorithm in the SUIF2 compiler infrastructure and used the implementation to analyze a set of C benchmark programs. The experimental results show that the approach has better precision with satisfied scalability as expected. This work is supported by the National Natural Science Foundation of China under Grant Nos. 60725206, 60673118, and 90612009, the National High-Tech Research and Development 863 Program of China under Grant No. 2006AA01Z429, the National Basic Research 973 Program of China under Grant No. 2005CB321802, the Program for New Century Excellent Talents in University under Grant No. NCET-04-0996, and the Hunan Natural Science Foundation under Grant No. 07JJ1011.     

Observer-based optimal output tracking for discrete-time systems with multiple state and input delays

The optimal output tracking control (OOTC) problem for a class of discrete-time systems with state and input delays is addressed. An augmented system is constructed such that the OOTC problem can be transformed into a two-point boundary value (TPBV) problem with both advance and delay terms from the necessary optimality conditions. The successive approximating method recently developed is extended to obtain an approximate solution of the TPBV problem, which is then used to obtain a feedforward and feedback tracking controller. An observer is designed for the uncertain reference input such that the feedforward controller is physically realizable. Simulations show the results are effective even with long time-delays. Recommended by Editorial Board member Poo Gyeon Park under the direction of Editor Young Il Lee. This research was supported by the National Natural Science Foundation of China (Grant No. 40776051), the Key Natural Science Foundation of Shandong Province (Grant No. Z2005G01), the Natural Science Foundation of Qingdao City (Grant No. 05-1-JC-94) and the research funds of QingDao University of Science and Technology. Hai-Hong Wang received the Ph.D. degree in Computer Science in July 2007 from Ocean University of China. She presently works in QingDao University of Science and Technology, Qingdao, P.R. China. Her current research interests include analysis and control for time-delay systems and nonlinear systems. Gong-You Tang received the Ph.D. degree in Control Theory and Applications from the South China University of Technology, P. R. China in 1991. He is a Professor at the College of Information Science and Engineering at the Ocean University of China, Qingdao, P. R. China. He is the Editor of the Journal of the Ocean University of China and Control and the Instruments in Chemical Industry. His research interests are in the areas of nonlinear systems, delay systems, large-scale systems, and networked control systems, with emphasis in optimal control, robust control, fault diagnosis and stability analysis.     

High performance word level sequential and parallel coding methods and architectures for bit plane coding

This paper introduced a novel high performance algorithm and VLSI architectures for achieving bit plane coding （BPC） in word level sequential and parallel mode. The proposed BPC algorithm adopts the techniques of coding pass prediction and parallel ＆ pipeline to reduce the number of accessing memory and to increase the ability of concurrently processing of the system, where all the coefficient bits of a code block could be coded by only one scan. A new parallel bit plane architecture （PA） was proposed to achieve word-level sequential coding. Moreover, an efficient high-speed architecture （HA） was presented to achieve multi-word parallel coding. Compared to the state of the art, the proposed PA could reduce the hardware cost more efficiently, though the throughput retains one coefficient coded per clock. While the proposed HA could perform coding for 4 coefficients belonging to a stripe column at one intra-clock cycle, so that coding for an NxN code-block could be completed in approximate N2/4 intra-clock cycles. Theoretical analysis and experimental results demonstrate that the proposed designs have high throughput rate with good performance in terms of speedup to cost, which can be good alternatives for low power applications.     

求解TSP问题的多级归约算法

TSP(traveling salesman problem)问题是最经典的NP-hard组合优化问题之一.长期以来,人们一直在寻求快速、高效的近似算法,以便在合理的计算时间内解决大规模问题.由于对较大规模的问题,目前的近似算法尚不能在较短的时间内给出高质量的解,因此提出了多重归约算法.该算法的基本原理是通过对TSP问题的局部最优解与全局最优解之间关系的分析,发现对局部最优解的简单的相交操作能以很高的概率得到全局最优解的部分解.利用这些部分解可以大大缩小原问题的搜索空间,同时也不会降低搜索的性能.这就是所谓的归约原理.再通过多次归约使问题的规模降到足够小,然后对这个较小规模的实例直接用已有的算法求解,最后通过相反的次序拼接部分解,最终得到一个合法的解.在TSPLIB(traveling salesman problem library)中,典型实例上的实验结果表明,此算法在求解质量和求解速度上与目前已知的算法相比有较大的改进.     

Orthogonal Methods Based Ant Colony Search for Solving Continuous Optimization Problems

Research into ant colony algorithms for solving continuous optimization problems forms one of the most significant and promising areas in swarm computation. Although traditional ant algorithms are designed for combinatorial optimization, they have shown great potential in solving a wide range of optimization problems, including continuous optimization. Aimed at solving continuous problems effectively, this paper develops a novel ant algorithm termed ＂continuous orthogonal ant colony＂ （COAC）, whose pheromone deposit mechanisms would enable ants to search for solutions collaboratively and effectively. By using the orthogonal design method, ants in the feasible domain can explore their chosen regions rapidly and efficiently. By implementing an ＂adaptive regional radius＂ method, the proposed algorithm can reduce the probability of being trapped in local optima and therefore enhance the global search capability and accuracy. An elitist strategy is also employed to reserve the most valuable points. The performance of the COAC is compared with two other ant algorithms for continuous optimization -API and CACO by testing seventeen functions in the continuous domain. The results demonstrate that the proposed COAC algorithm outperforms the others.     

A novel algorithm for explicit optimal multi-degree reduction of triangular surfaces

This paper introduces the algebraic property of bivariate orthonormal Jacobi polynomials into geometric approximation. Based on the latest results on the transformation formulae between bivariate Bernstein polynomials and Jacobi polynomials, we naturally deduce a novel algorithm for multi-degree reduction of triangular B~zier surfaces. This algorithm possesses four characteristics： ability of error forecast, explicit expression, less time consumption, and best precision. That is, firstly, whether there exists a multi-degree reduced surface within a prescribed tolerance is judged beforehand; secondly, all the operations of multi-degree reduction are just to multiply the column vector generated by sorting the series of the control points of the original surface in lexicographic order by a matrix; thirdly, this matrix can be computed at one time and stored in an array before processing degree reduction; fourthly, the multi-degree reduced surface achieves an optimal approximation in the norm L2. Some numerical experiments are presented to validate the effectiveness of this algorithm, and to show that the algorithm is applicable to information processing of products in CAD system.