演化硬件中变异概率对进化算法首次命中时间的影响

在(1+1)EAs中,采用马尔可夫链推移时间分析法,推导出了平均首次命中时间的表达式。从理论上分析了变异概率对平均首次命中时间的影响。结果表明适当的变异概率会缩短平均首次命中时间,加快进化算法的寻优时间。     

Single batch machine scheduling with deliveries

We consider the problem of scheduling a set of n jobs on a single batch machine, where several jobs can be processed simultaneously. Each job j has a processing time p_j and a size s_j. All jobs are available for processing at time 0. The batch machine has a capacity D. Several jobs can be batched together and processed simultaneously, provided that the total size of the jobs in the batch does not exceed D. The processing time of a batch is the largest processing time among all jobs in the batch. There is a single vehicle available for delivery of the finished products to the customer, and the vehicle has capacity K. We assume that K = rD, where and r is an integer. The travel time of the vehicle is T; that is, T is the time from the manufacturer to the customer. Our goal is to find a schedule of the jobs and a delivery plan so that the service span is minimized, where the service span is the time that the last job is delivered to the customer. We show that if the jobs have identical sizes, then we can find a schedule and delivery plan in time such that the service span is minimum. If the jobs have identical processing times, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most 11/9 times the optimal service span. When the jobs have arbitrary processing times and arbitrary sizes, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most twice the optimal service span. We also derive upper bounds of the absolute worst‐case ratios in both cases. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 470–482, 2015     

Approximation algorithms for capacitated stochastic inventory systems with setup costs

We develop the first approximation algorithm with worst‐case performance guarantee for capacitated stochastic periodic‐review inventory systems with setup costs. The structure of the optimal control policy for such systems is extremely complicated, and indeed, only some partial characterization is available. Thus, finding provably near‐optimal control policies has been an open challenge. In this article, we construct computationally efficient approximate optimal policies for these systems whose demands can be nonstationary and/or correlated over time, and show that these policies have a worst‐case performance guarantee of 4. We demonstrate through extensive numerical studies that the policies empirically perform well, and they are significantly better than the theoretical worst‐case guarantees. We also extend the analyses and results to the case with batch ordering constraints, where the order size has to be an integer multiple of a base load. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 304–319, 2014     

一类修正的和积分型算子的点态逼近

研究以Beta为基函数的一类修正的和积分型算子,利用统一光滑模。ω^2φ^λ（f,t）（0≤λ≤1）,得到该算子点态逼近的等价定理．     

基于数据压缩的LSP参数高效量化算法

文中为解决超长帧编码系统中联合帧数过多导致LSP参数量化性能下降这个问题,将多项式拟合引入超长帧编码系统中,利用多项式拟合压缩LSP参数矩阵,以降低量化时实际联合的帧数。再用分裂矩阵量化器进行量化。仿真结果表明,在120 bps的参数量化速率下,此算法的量化性能优于矩阵量化算法(MQ),平均谱失真比MQ算法降低了0.0719 dB,平均分段信噪比提高了0.1971 dB。     

Approximation results for min‐max path cover problems in vehicle routing

This article studies a min‐max path cover problem, which is to determine a set of paths for k capacitated vehicles to service all the customers in a given weighted graph so that the largest path cost is minimized. The problem has wide applications in vehicle routing, especially when the minimization of the latest service completion time is a critical performance measure. We have analyzed four typical variants of this problem, where the vehicles have either unlimited or limited capacities, and they start from either a given depot or any depot of a given depot set. We have developed approximation algorithms for these four variants, which achieve approximation ratios of max{3 ‐ 2/k,2}, 5, max{5 ‐ 2/k,4}, and 7, respectively. We have also analyzed the approximation hardness of these variants by showing that, unless P = NP , it is impossible for them to achieve approximation ratios less than 4/3, 3/2, 3/2, and 2, respectively. We have further extended the techniques and results developed for this problem to other min‐max vehicle routing problems.© 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

On efficient algorithms for finding efficient salvo policies

We consider the salvo policy problem, in which there are k moments, called salvos, at which we can fire multiple missiles simultaneously at an incoming object. Each salvo is characterized by a probability p_i: the hit probability of a single missile. After each salvo, we can assess whether the incoming object is still active. If it is, we fire the missiles assigned to the next salvo. In the salvo policy problem, the goal is to assign at most n missiles to salvos in order to minimize the expected number of missiles used. We consider three problem versions. In Gould's version, we have to assign all n missiles to salvos. In the Big Bomb version, a cost of B is incurred when all salvo's are unsuccessful. Finally, we consider the Quota version in which the kill probability should exceed some quota Q. We discuss the computational complexity and the approximability of these problem versions. In particular, we show that Gould's version and the Big Bomb version admit pseudopolynomial time exact algorithms and fully polynomial time approximation schemes. We also present an iterative approximation algorithm for the Quota version, and show that a related problem is NP-complete.     

Technical note: Finite-time regret analysis of Kiefer-Wolfowitz stochastic approximation algorithm and nonparametric multi-product dynamic pricing with unknown demand

We consider the problem of nonparametric multi-product dynamic pricing with unknown demand and show that the problem may be formulated as an online model-free stochastic program, which can be solved by the classical Kiefer-Wolfowitz stochastic approximation (KWSA) algorithm. We prove that the expected cumulative regret of the KWSA algorithm is bounded above by where κ₁, κ₂ are positive constants and T is the number of periods for any T = 1, 2, … . Therefore, the regret of the KWSA algorithm grows in the order of , which achieves the lower bounds known for parametric dynamic pricing problems and shows that the nonparametric problems are not necessarily more difficult to solve than the parametric ones. Numerical experiments further demonstrate the effectiveness and efficiency of our proposed KW pricing policy by comparing with some pricing policies in the literature.     

A multi‐stage stochastic programming approach for network capacity expansion with multiple sources of capacity

In networks, there are often more than one sources of capacity. The capacities can be permanently or temporarily owned by the decision maker. Depending on the nature of sources, we identify the permanent capacity, spot market capacity, and contract capacity. We use a scenario tree to model the uncertainty, and build a multi‐stage stochastic integer program that can incorporate multiple sources and multiple types of capacities in a general network. We propose two solution methodologies for the problem. Firstly, we design an asymptotically convergent approximation algorithm. Secondly, we design a cutting plane algorithm based on Benders decomposition to find tight bounds for the problem. The numerical experiments show superb performance of the proposed algorithms compared with commercial software. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 600–614, 2017     

新算法在划船和伪划船效应中的应用

划船效应补偿是高精度捷联惯导系统解算的重要环节。通过研究其误差特性,推导了新的通用划船效应补偿公式。同时提出了角振动环境中伪划船效应的存在,对伪划船效应的产生原因、表达方式以及对捷联惯导系统的影响进行了分析。对新的补偿算法在划船效应和伪划船效应下进行了仿真试验。