Augmenting Trees to Meet Biconnectivity and Diameter Constraints

Given a graph G=(V,E) and a positive integer D , we consider the problem of finding a minimum number of new edges E' such that the augmented graph G'=(V,E\cup E') is biconnected and has diameter no greater than D. In this note we show that this problem is NP-hard for all fixed D , by employing a reduction from the DOMINATING SET problem. We prove that the problem remains NP-hard even for forests and trees, but in this case we present approximation algorithms with worst-case bounds 3 (for even D ) and 6 (for odd D ). A closely related problem of finding a minimum number of edges such that the augmented graph has diameter no greater than D has been shown to be NP-hard by Schoone et al. [21] when D=3 , and by Li et al. [17] when D=2. Received April 19, 1999; revised June 5, 2001.     

Specification methods for material-handling control algorithms in flexible manufacturing systems

Good methods are needed to specify, test, and debug material-handling control logic. This article surveys a number of representative methods for defining and describing control algorithms for programmable material-handling equipment used in flexible manufacturing systems. The methods are evaluated with regard to their suitability for communication between people and as bases for interfaces to automatic program generators. It is concluded that no single method is entirely satisfactory. Three methods (position diagrams, function block diagrams, and operation networks) have potential to be combined into an effective hybrid approach that minimizes the need for the user to switch between various conceptual models.     

Semiparametric Estimation in Time‐Series Regression with Long‐Range Dependence

Abstract. We consider semiparametric estimation in time‐series regression in the presence of long‐range dependence in both the errors and the stochastic regressors. A central limit theorem is established for a class of semiparametric frequency domain‐weighted least squares estimates, which includes both narrow‐band ordinary least squares and narrow‐band generalized least squares as special cases. The estimates are semiparametric in the sense that focus is on the neighbourhood of the origin, and only periodogram ordinates in a degenerating band around the origin are used. This setting differs from earlier studies on time‐series regression with long‐range dependence, where a fully parametric approach has been employed. The generalized least squares estimate is infeasible when the degree of long‐range dependence is unknown and must be estimated in an initial step. In that case, we show that a feasible estimate which has the same asymptotic properties as the infeasible estimate, exists. By Monte Carlo simulation, we evaluate the finite‐sample performance of the generalized least squares estimate and the feasible estimate.     

Evaluating part designs for automatic feeding in robotic assembly systems: A geometric analysis of the nesting of polyhedral objects

One of the problems encountered by automatic feeding devices, such as vibratory bowl feeders, in robotic assembly systems is nesting which leads to inseparability of parts and jamming. In this paper, we describe a design evaluation procedure to determine whether a part is prone to nesting and to quantify the degree of nesting. The proposed methodology reduces the 3-D protrusion-hole polyhedral containment problem of nesting to a 2-D polygon containment problem by employing a loop-based feature recognition scheme. Subsequently, the 3-D containment configuration is reconstructed from that of the 2-D by using a strategy calleddrop, pull and push. In this context, we introduce the notion of axis as a characteristic direction of a feature that facilitates the analysis of generalized 3-D polyhedral containment. The algorithms are applicable to generic B-Rep CAD data, and their time and space complexities are polynomial.     

基于遗传算法的土钉支护结构优化设计研究

通过建立三维有限元模型,对土钉支护的变形和受力性能进行分析,得出土钉力的合理分布。在此基础上,考虑土钉支护的水平位移,采用遗传算法,对土钉支护的结构优化设计进行研究,建立了土钉支护结构的优化设计数学模型,并编制了相应的计算程序。通过算例分析,并与基于极限平衡分析的优化结果相比较,得出合理的土钉支护结构设计的参考结论。     

Self-adjusting the intensity of assortative mating in genetic algorithms

Mate selection plays a crucial role in both natural and artificial systems. While traditional Evolutionary Algorithms (EA) usually engage in random mating strategies, that is, mating chance is independent of genotypic or phenotypic distance between individuals, in natural systems non-random mating is common, which means that somehow this mechanism has been favored during the evolutionary process. In non-random mating, the individuals mate according to their parenthood or likeness. Previous studies indicate that negative assortative mating (AM)—also known as dissortative mating—, which is a specific type of non-random mating, may improve EAs performance by maintaining the genetic diversity of the population at a higher level during the search process. In this paper we present the Variable Dissortative Mating Genetic Algorithm (VDMGA). The algorithm holds a mechanism that varies the GA’s mating restrictions during the run by means of simple rule based on the number of chromosomes created in each generation and indirectly influenced by the genetic diversity of the population. We compare VDMGA not only with traditional Genetic Algorithms (GA) but also with two preceding non-random mating EAs: the CHC algorithm and the negative Assortative Mating Genetic Algorithm (nAMGA). We intend to study the effects of the different methods in the performance of GAs and verify the reliability of the proposed algorithm when facing an heterogeneous set of landscapes. In addition, we include the positive Assortative Mating Genetic Algorithm (pAMGA) in the experiments in order test both negative and positive AM mechanisms, and try to understand if and when negative AM (or DM) speeds up the search process or enables the GAs to escape local optima traps. For these purposes, an extensive set of optimization test problems was chosen to cover a variety of search landscapes with different characteristics. Our results confirm that negative AM is effective in leading EAs out of local optima traps, and show that the proposed VDMGA is at least as efficient as nAMGA when applied to the range of our problems, being more efficient in very hard functions were traditional GAs usually fail to escape local optima. Also, scalability tests have been made that show VDMGA ability to decrease optimal population size, thus reducing the amount of evaluations needed to attain global optima. We like to stress that only two parameters need to be hand-tuned in VDMGA, thus reducing the tuning effort present in traditional GAs and nAMGA.     

Cycle detection using a stack

We present an algorithm for detecting periodicity in sequences produced by repeated application of a given function. Our algorithm uses logarithmic memory with high probability, runs in linear time, and is guaranteed to stop within the second loop through the cycle. We also present a partitioning technique that offers a time/memory tradeoff. Our algorithm is especially well suited for sequences where the cycle length is typically small compared to the length of the acyclic prefix.     

基于频率采样技术的FIR数字滤波器优化设计

本文提出了一种FIR数字滤波器满意优化设计方法，将滤波器过渡带样本值作为优化变量，通过设计通带、过渡带和阻带性能指标满意度函数和综合满意度函数，构造出满意优化模型，并用本文提出的新量子遗传算法搜索满意解，FIR高通和带阻数字滤波器的设计结果表明，采用满意优化方法设计的FIR滤波器的性能优于传统方法。     

A simple approximation algorithm for the weighted matching problem

We present a linear time approximation algorithm with a performance ratio of 1/2 for finding a maximum weight matching in an arbitrary graph. Such a result is already known and is due to Preis [STACS'99, Lecture Notes in Comput. Sci., Vol. 1563, 1999, pp. 259-269]. Our algorithm uses a new approach which is much simpler than the one given by Preis and needs no amortized analysis for its running time.