基于遗传算法的二层线性规划问题的求解算法

本研究了下层以最优解返回上层的二层线性规划问题的遗传算法。在提出可行度概念的基础上，构造了二层线性规划上层规划问题的适应度函数，由此设计了求解二层线性规划问题遗传算法。为了提高遗传算法处理约束的能力，在产生初始种群时将随机产生的初始种群变为满足约束的初始种群，从而避免了使用罚函数处理约束带来的困难，最后用实例验证了本提出的二层线性规划的遗传算法的有效性。     

Asymptotic analysis of the effect of arrival model uncertainties in some optimal routing problems

We study the effect of arrival model uncertainties on the optimal routing in a system of parallel queues. For exponential service time distributions and Bernoulli routing, the optimal mean system delay generally depends on the interarrival time distribution. Any error in modeling the arriving process will cause a model-based optimal routing algorithm to produce a mean system delay higher than the true optimum. In this paper, we present an asymptotic analysis of the behavior of this error under heavy traffic conditions for a general renewal arrival process. An asymptotic analysis of the error in optimal mean delay due to uncertainties in the service time distribution for Poisson arrivals was reported in Ref. 6, where it was shown that, when the first moment of the service time distribution is known, this error in performance vanishes asymptotically as the traffic load approaches the system capacity. In contrast, this paper establishes the somewhat surprising result that, when only the first moment of the arrival distribution is known, the error in optimal mean delay due to uncertainties in the arrival model is unbounded as the traffic approaches the system capacity. However, when both first and second moments are known, the error vanishes asymptotically. Numerical examples corroborating the theoretical results are also presented.This work was supported by the National Science Foundation under Grants ECS-88-01912 and EID-92-12122 and by NASA under Contract NAG 2-595.The authors wish to thank an anonymous referee for pointing out Ref. 20, thus avoiding the need for an explicit proof of convexity of the cost function considered in the paper.     

Polynomial-time approximation schemes for packing and piercing fat objects

We consider two problems: given a collection of n fat objects in a fixed dimension, (1) ( packing) find the maximum subcollection of pairwise disjoint objects, and (2) ( piercing) find the minimum point set that intersects every object. Recently, Erlebach, Jansen, and Seidel gave a polynomial-time approximation scheme (PTAS) for the packing problem, based on a shifted hierarchical subdivision method. Using shifted quadtrees, we describe a similar algorithm for packing but with a smaller time bound. Erlebach et al.'s algorithm requires polynomial space. We describe a different algorithm, based on geometric separators, that requires only linear space. This algorithm can also be applied to piercing, yielding the first PTAS for that problem.     

A Comparative Study on Dynamic and Static Sparsity Patterns in Parallel Sparse Approximate Inverse Preconditioning

Sparse approximate inverse (SAI) techniques have recently emerged as a new class of parallel preconditioning techniques for solving large sparse linear systems on high performance computers. The choice of the sparsity pattern of the SAI matrix is probably the most important step in constructing an SAI preconditioner. Both dynamic and static sparsity pattern selection approaches have been proposed by researchers. Through a few numerical experiments, we conduct a comparable study on the properties and performance of the SAI preconditioners using the different sparsity patterns for solving some sparse linear systems. This revised version was published online in July 2006 with corrections to the Cover Date.     

A projection method for solving incompressible viscous flows on domains with moving boundaries

In this paper, a projection method is presented for solving the flow problems in domains with moving boundaries. In order to track the movement of the domain boundaries, arbitrary‐Lagrangian–Eulerian (ALE) co‐ordinates are used. The unsteady incompressible Navier–Stokes equations on the ALE co‐ordinates are solved by using a projection method developed in this paper. This projection method is based on the Bell's Godunov‐projection method. However, substantial changes are made so that this algorithm is capable of solving the ALE form of incompressible Navier–Stokes equations. Multi‐block structured grids are used to discretize the flow domains. The grid velocity is not explicitly computed; instead the volume change is used to account for the effect of grid movement. A new method is also proposed to compute the freestream capturing metrics so that the geometric conservation law (GCL) can be satisfied exactly in this algorithm. This projection method is also parallelized so that the state of the art high performance computers can be used to match the computation cost associated with the moving grid calculations. Several test cases are solved to verify the performance of this moving‐grid projection method. Copyright © 2004 John Wiley Sons, Ltd.     

Phase Measurement Algorithm in Wavelength Scanned Fizeau Interferometer

Wavelength scanned interferometry allows the simultaneous measurement of top surface shape and optical thickness variation of a transparent object consisting of several parallel surfaces. Interference signals from these surfaces can be separated in frequency space, and their phases are detected by discrete Fourier analysis. However, these signal frequencies are shifted from the detection frequency by the refractive index dispersion of the object and a nonlinearity of the wavelength scanning. The Fourier analysis is sensitive to the detuning of the signal frequency and suffers from the multiple-beam interference noise. Conventional error-compensating algorithms cannot be applied to an object consisting of more than three reflecting surfaces. We derive a new 2N-1 sample error-compensating algorithm, which allows the phase detection of any order of harmonic frequency among the interference signals. The new algorithm suppresses the effect of signal frequency detuning as well as the multiple-beam interference noise and can be applied to the measurement of complex objects consisting of more than three reflecting surfaces.     

旋转带电体磁矩计算的若干法则与算例

本文在文献 [1]、[2 ]等的基础上给出关于旋转带电体的磁矩计算的若干法则 ,均以定理形式表达 ,并列表枚举其相关算例     

Five-step phase-shifting algorithms with unknown values of phase shift

The presented work offers new algorithms for phase evaluation in interferometric measurements. Several phase-shifting algorithms with an arbitrary but constant phase-shift between captured intensity frames are proposed. These phase calculation algorithms need to measure five frames of the intensity of the interference field. The algorithms are similarly derived as so called Carré algorithm. The phase evaluation process then does not depend on the linear phase shift errors. Furthermore, the detailed analysis of the algorithms with respect to most important factors, which affect interferometric measurements, is carried out. It is also studied the dependency of the evaluation algorithms on the phase shift values, and the proposed phase calculation algorithms are compared with respect to the resulting phase errors. The influence of most important factors in the measurement and evaluation process was simulated as systematic and random errors using a proposed mathematical model.     

Convergent Algorithm Based on Progressive Regularization for Solving Pseudomonotone Variational Inequalities

In this paper, we extend the Moreau-Yosida regularization of monotone variational inequalities to the case of weakly monotone and pseudomonotone operators. With these properties, the regularized operator satisfies the pseudo-Dunn property with respect to any solution of the variational inequality problem. As a consequence, the regularized version of the auxiliary problem algorithm converges. In this case, when the operator involved in the variational inequality problem is Lipschitz continuous (a property stronger than weak monotonicity) and pseudomonotone, we prove the convergence of the progressive regularization introduced in Refs. 1, 2.