Cyclic best first search: Using contours to guide branch‐and‐bound algorithms

The cyclic best‐first search (CBFS) strategy is a recent search strategy that has been successfully applied to branch‐and‐bound algorithms in a number of different settings. CBFS is a modification of best‐first search (BFS) that places search tree subproblems into contours which are collections of subproblems grouped in some way, and repeatedly cycles through all non‐empty contours, selecting one subproblem to explore from each. In this article, the theoretical properties of CBFS are analyzed for the first time. CBFS is proved to be a generalization of all other search strategies by using a contour definition that explores the same sequence of subproblems as any other search strategy. Further, a bound is proved between the number of subproblems explored by BFS and the number of children generated by CBFS, given a fixed branching strategy and set of pruning rules. Finally, a discussion of heuristic contour‐labeling functions is provided, and proof‐of‐concept computational results for mixed‐integer programming problems from the MIPLIB 2010 database are shown. © 2017 Wiley Periodicals, Inc. Naval Research Logistics, 64: 64–82, 2017     

Augmented nested sampling for stochastic programs with recourse and endogenous uncertainty

We propose a novel simulation‐based approach for solving two‐stage stochastic programs with recourse and endogenous (decision dependent) uncertainty. The proposed augmented nested sampling approach recasts the stochastic optimization problem as a simulation problem by treating the decision variables as random. The optimal decision is obtained via the mode of the augmented probability model. We illustrate our methodology on a newsvendor problem with stock‐dependent uncertain demand both in single and multi‐item (news‐stand) cases. We provide performance comparisons with Markov chain Monte Carlo and traditional Monte Carlo simulation‐based optimization schemes. Finally, we conclude with directions for future research.     

Exact algorithms and bounds for the dynamic assignment interdiction problem

We study a multi‐stage dynamic assignment interdiction (DAI) game in which two agents, a user and an attacker, compete in the underlying bipartite assignment graph. The user wishes to assign a set of tasks at the minimum cost, and the attacker seeks to interdict a subset of arcs to maximize the user's objective. The user assigns exactly one task per stage, and the assignment costs and interdiction impacts vary across stages. Before any stage commences in the game, the attacker can interdict arcs subject to a cardinality constraint. An interdicted arc can still be used by the user, but at an increased assignment cost. The goal is to find an optimal sequence of assignments, coupled with the attacker's optimal interdiction strategy. We prove that this problem is strongly NP‐hard, even when the attacker can interdict only one arc. We propose an exact exponential‐state dynamic‐programming algorithm for this problem as well as lower and upper bounds on the optimal objective function value. Our bounds are based on classical interdiction and robust optimization models, and on variations of the DAI game. We examine the efficiency of our algorithms and the quality of our bounds on a set of randomly generated instances. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 373–387, 2017     

基于线加速度计卫星平台颤振测量下的高分辨率光学遥感影像重建方法

卫星平台颤振条件下,推扫式高分辨率光学影像成像往往产生扭曲,从而影响影像的定位及信息提取精度。针对当前颤振下影像成像扭曲补偿的问题,本文提出一种基于线加速度计测量平台颤振下的稳态重成像模型实现高分辨率卫星颤振扭曲影像的重建。本文采用受平台颤振影响而扭曲变形的高分某型号卫星全色影像数据进行验证。分析结果表明：本文提出的线加速度计可以有效检测并测量出平台的颤振,设计的颤振影像地面重建模型可以有效改善平台颤振下推扫式光学影像扭曲成像的影响,补偿后的影像扭曲变形现象明显消除。     

舰艇防空反导自适应干扰HDP算法分析与仿真

为干扰来袭的多波次、多方向反舰导弹,提高舰艇防空反导能力,分析了自适应干扰HDP算法模型,并通过实例进行仿真。通过对结果进行分析,验证了启发式动态规划(HDP)算法在自适应电子干扰策略最优组合的生成过程中的时效性、预测精度以及适用性,为该算法的后续研究提供支持。     

导弹自动驾驶仪控制算法鲁棒性研究

以某型轴对称导弹为研究对象,在解耦和线性化的情况下,得到简化的数学模型。通过求解线性矩阵不等式(LMI)设计了状态反馈H∞控制导弹自动驾驶仪,采用模糊和变论域理论设计了变论域模糊PID控制自动驾驶仪。考虑飞行过程中的干扰、气动参数摄动,对两种自动驾驶仪的控制性能进行对比研究,仿真结果表明,二者皆能实现对导弹制导指令的有效跟踪,其中状态反馈H∞控制设计的自动驾驶仪在指令跟踪的快速性、准确性和抗干扰性上具有明显的优越性。     

一种结构化的编译型 PROLOG数据库及其管理策略

PROLOG数据库存放着构成PROLOG程序的子句以及表示成子句的全局数据,它的组织与管理是实用PROLOG系统的关键,这一点在提高执行效率的编译型PROLOG系统中尤为如此。本文以YH-SIM——一个扩充了的WAM模型为基础,提出一种新颖的编译型PROLOG数据库结构形式,其中·过程中的子句索引与子句彼此分离; ·子句索引块分成多个专门的子索引块; ·一个子句按两种形式存放,子句代码和子句项(源子句形式)。二者分离且共享同一索引,因此代码库和项库的管理是一体化的。这些结构化的特征,有力地支持PROLOG数据库的操作及管理(子句的插入删除,以及空间分配与回收)。文中还介绍了一种简明有效的管理方法。     

向量巨型机高效程序设计技术

本文着重研究适应向量巨型机体系结构的高效程序设计技术。围绕减少指令流水线阻塞,提高多功能部件并行度,数据调度与局部化技术三个方面进行了深入的讨论,给出了一系列设计高效程序的方法和技巧。     

程序进化器

研究用模拟进化方法进行程序设计的途径。构造了以形式文法为遗传表示的程序进化器,提出了这个进化器使用的有关算法。本文用程序进化器解决了人工蚁问题。     

恒定应力加速寿命试验的非参数统计方法

在恒定应力加速寿命试验 (简称恒加试验 )的统计分析中 ,非参数统计方法具有一定的实际价值 .在一定的假定下 ,文中给出了两种新估计 ,并证明了它们的优良性