马尔可夫链最优停止的值函数

本文讨论了时间无限的马尔可夫链的最优停止问题。对于无限状态情况,给出了其最优停止变量以及值函数存在的一个充分条件;对于有限状态情况,这个充分条件以及问题的计算等价于解一个线性规划问题。     

求解不确定型车辆路径问题的弱鲁棒优化方法

为降低鲁棒优化模型最优解的保守性,以最小化违约车辆数和总惩罚成本为目标,建立针对旅行时间不确定的开放式车辆路径问题的弱鲁棒优化模型。对于不确定数据集的每个取值,该模型的最优解可以使其目标函数值始终不超过某数值,进而改善最优解的保守性。为提高启发式算法发现最优解的概率,提出一种自设计遗传算法对模型进行求解,其主要思想是利用粒子群算法搜索出可使遗传算法预期产生最好解的算法要素,并将其进行组合,从而产生新的遗传算法。采用新产生的遗传算法对模型继续求解,输出最好解。计算结果表明:与以往的鲁棒优化方法相比,弱鲁棒优化方法的最优解的保守性显著降低。     

天基光学短弧观测约束域的粒子群优化定轨方法

针对空间目标定轨问题,提出一种利用两段天基光学短弧观测数据的粒子群优化定轨新算法。在介绍天基光学短弧观测测量帧集、测量约束域及目标函数构造的基础上,为解决已有的基于网格搜索思想寻优的算法存在的多解、局部最优解及运算量过大等问题,提出了一种利用粒子群优化算法在约束域内对目标函数值寻优达到定轨目的的新算法。对算法的性能进行了仿真验证。多次仿真结果表明:该算法大大降低了计算量,且有效地解决了目标函数多解和局部最优解问题,对目标定轨的精度与定轨算法的克拉美罗下限接近。     

一种利用精英保留改进的量子遗传算法

针对量子遗传算法的"早熟"现象,在多峰值函数的寻优中,提出了基于精英的量子遗传算法。该算法不仅考虑函数值与当前最优值的关系,还考虑函数值所对应的自变量与当前最优值所对应自变量的关系。仿真实验表明,该算法对于多峰值函数具有很好的寻优能力。     

具有适应值预测机制的遗传算法

针对适应值计算费时的优化问题,提出一种具有适应值预测机制的遗传算法:为了有效控制预测适应值的准确度和预测频率,建立了一个基于可信度概念的适应值预测模型,引入可信度流失机制以减少预测误差的传播和累积,引入冗余个体剔除机制以减少计算消耗。利用3个基准函数对算法进行收敛性和有效性的测试,测试结果表明算法对于3个测试函数均能获得满意的最优解,并且都能减少60%以上的真实适应值计算次数。     

多基线InSAR图割相位解缠算法研究

提出了一种基于迭代的多基线In SAR图割相位解缠算法。该算法将一阶马尔可夫模型作为先验信息,通过构建能量函数,将相位解缠问题转化为最大后验概率问题下的能量最优化问题,接着依据改进的Ishikawa图网络模型,通过分段图割迭代的方法逐步逼近最优的相位值。与Ishikawa图割方法相比,该迭代算法能够减少相位解缠所需的内存和处理时间。仿真数据验证了方法的有效性。     

水雷气动不平衡式发射轴向受力优化分析

基于水雷气动不平衡式发射内弹道数学模型,建立了轴向受力和出管速度的泛函表达式,以基本可行解为基准,对可行解区间进行了仿真计算,通过将轴向受力和出管速度函数在基本可行解处一阶泰勒展开,并采用分段函数表示可行解各分量的变化律,从而将非线性问题转化为线性规划问题,运用单纯形法进行优化求解,得到了最优发射条件.     

线性规划优化分析的元模型方法及其比较

线性规划优化分析在经济管理等领域有着广泛的应用。当线性规划约束条件的右端向量在一定范围内变化时,目标函数的最优值是右端向量的一个复杂的分片线性函数,但通常难以给出分析表达式。应用多项式回归、径向基函数、Kriging法及多项式回归 Kriging法这四种元模型方法,能快速预测最优值函数。通过仿真实验,对这四种形式的元模型作较全面的比较分析。数值实验的结果表明,用次数较少的实验设计,后三种方法都具有较高的拟合精度;特别地,多项式回归 Kriging法不仅拟合精度高,而且还能用一个二阶多项式给出最优值函数的一个简明的近似描述。结果表明,元模型方法是研究线性规划优化分析问题的有效途径。     

神经网络最小二乘估计器

Hopfield和Tank证明几种最优化问题能用Hopfield网络快速求解,而Hopfield网络是简单的类似神经元模拟处理机的递推网络。使用Hopfield网络时,目标函数的自变量收敛于超立方体的顶点。因此,它们的应用严格地限于决策最优化问题。在本文中,我们将研究目标函数自变量是实数的问题。基于Hopfield网络的概念,推导了求解最小二乘估计问题的神经网络。用这个网络,目标函数可能收敛于超立方体内的任何点,给出一个具有极大速度的实值解。由于所选择的能量函数的凸状性质,不会出现收敛到局部最小值的问题。我们还介绍了空间迭代搜索方法,以便找到可能存在于空间内任意点的最优解。最后,给出了求解线性系统和参数估计问题的模拟结果。     

基于改进自适应遗传算法的阵列优化

提出了一种改进的自适应遗传算法,对约束了阵列孔径、阵元数目和最小阵元间距的非均匀稀布阵列进行优化布阵。该算法采用实值编码,改进了适应度函数,避免了不可行解的产生。同时选取新的选择算子和改进的双重最佳保留策略,对传统自适应遗传算法的交叉、变异概率进行了动态改进。仿真结果表明,该方法能较好地抑制"早熟",增加了获取全局最优解的概率,获得了更低的峰值旁瓣电平。     

最优停止理论中离散化方法的应用

离散化方法是研究连续参数最优停止理论和马尔可夫过程最优停止理论的有效方法。本文对这一方法进行了阐述，并用此方法解决了两个实际问题。     

An iterative procedure for nondiscounted discrete-time markov decisions

This paper considers the problem of computing, by iterative methods, optimal policies for Markov decision processes. The policies computed are optimal for all sufficiently small interest rates.     

一类扩散过程的最优停止

金融数学中关于美式期权的定价理论最后归结为一个对扩散过程的最优停止问题,扩散过程是特殊的马氏过程,本文讨论了当报酬函数非负时的值函数性质及其最优停时的表示。特别对带折扣的报酬的讨论,更加符合金融数学的需要     

Continuous-time markov decision processes with nonzero terminal reward

In this article we consider a continuous-time Markov decision process with a denumerable state space and nonzero terminal rewards. We first establish the necessary and sufficient optimality condition without any restriction on the cost functions. The necessary condition is derived through the Pontryagin maximum principle and the sufficient condition, by the inherent structure of the problem. We introduce a dynamic programming approximation algorithm for the finite-horizon problem. As the time between discrete points decreases, the optimal policy of the discretized problem converges to that of the continuous-time problem in the sense of weak convergence. For the infinite-horizon problem, a successive approximation method is introduced as an alternative to a policy iteration method.     

Scheduling jobs,with exponentially distributed processing times,on two machines of a flow shop

This paper treats the problem of sequencing n jobs on two machines in a “flow shop.” (That is, each job in the shop is required to flow through the same sequence of the machines.) The processing time of a given job on a given machine is assumed to be distributed exponentially, with a known mean. The objective is to minimize the expected job completion time. This paper proves an optimal ordering rule, previously conjectured by Talwar [10]. A formula is also derived through Markov Chain analysis, which evaluates the expected job completion time for any given sequence of the jobs. In addition, the performance of a heuristic rule is discussed in the light of the optimal solution.     

The discrete max-min problem

The historic max-min problem is examined as a discrete process rather than in its more usual continuous mode. Since the practical application of the max-min model usually involves discrete objects such as ballistic missiles, the discrete formulation of the problem seems quite appropriate. This paper uses an illegal modification to the dynamic programming process to obtain an upper bound to the max-min value. Then a second but legal application of dynamic programming to the minimization part of the problem for a fixed maximizing vector will give a lower bound to the max-min value. Concepts of optimal stopping rules may be applied to indicate when sufficiently near optimal solutions have been obtained.     

Computing the discounted return in markov and semi-markov chains

This paper addresses the problem of computing the expected discounted return in finite Markov and semi-Markov chains. The objective is to reveal insights into two questions. First, which iterative methods hold the most promise? Second, when are interative methods preferred to Gaussian elimination? A set of twenty-seven randomly generated problems is used to compare the performance of the methods considered. The observations that apply to the problems generated here are as follows: Gauss-Seidel is not preferred to Pre-Jacobi in general. However, if the matrix is reordered in a certain way and the author's row sum extrapolation is used, then Gauss-Seidel is preferred. Transforming a semi-Markov problem into a Markov one using a transformation that comes from Schweitzer does not yield improved performance. A method analogous to symmetric successive overrelaxation (SSOR) in numerical analysis yields improved performance, especially when the row-sum extrapolation is used only sparingly. This method is then compared to Gaussian elimination and is found to be superior for most of the problems generated.     

Optimal and suboptimal procedures in group sequential sampling

This paper investigates the problem of choosing between two simple hypothesis, H₀ and H₁, in terms of independent, identically distributed random variables, when observations can be taken in groups. At any stage in the decision process it must be decided whether to stop and take action now or to continue, in which case the size of the next group of observations must be decided upon. The problem is to find an optimal procedure incorporating a stopping, group size (batch) and terminal action rule. It is proven, in general, that the optimal stopping and terminal action rule is of the sequential probability ratio type (SPRT). Fixed stopping rules of the SPRT type are studied and an iterative procedure of the policy improvement type, both with and without a value determination step, is developed. It is shown, for the general situation, that both the average risk and scheduling rule converge to the optima. Also, six suboptimal scheduling rules are considered with respect to the average risks they achieve. Numerical results are presented to illustrate the effectiveness of the procedures.     

Limiting behavior of the stochastic sequential assignment problem

The stochastic sequential assignment problem (SSAP) considers how to allocate available distinct workers to sequentially arriving tasks with stochastic parameters such that the expected total reward obtained from the sequential assignments is maximized. Implementing the optimal assignment policy for the SSAP involves calculating a new set of breakpoints upon the arrival of each task (i.e., for every time period), which is impractical for large‐scale problems. This article studies two problems that are concerned with obtaining stationary policies, which achieve the optimal expected reward per task as the number of tasks approaches infinity. The first problem considers independent and identically distributed (IID) tasks with a known distribution function, whereas in the second problem tasks are derived from r different unobservable distributions governed by an ergodic Markov chain. The convergence rate of the expected reward per task to the optimal value is also obtained for both problems. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013