Optimal patrol to uncover threats in time when detection is imperfect

Consider a patrol problem, where a patroller traverses a graph through edges to detect potential attacks at nodes. An attack takes a random amount of time to complete. The patroller takes one time unit to move to and inspect an adjacent node, and will detect an ongoing attack with some probability. If an attack completes before it is detected, a cost is incurred. The attack time distribution, the cost due to a successful attack, and the detection probability all depend on the attack node. The patroller seeks a patrol policy that minimizes the expected cost incurred when, and if, an attack eventually happens. We consider two cases. A random attacker chooses where to attack according to predetermined probabilities, while a strategic attacker chooses where to attack to incur the maximal expected cost. In each case, computing the optimal solution, although possible, quickly becomes intractable for problems of practical sizes. Our main contribution is to develop efficient index policies—based on Lagrangian relaxation methodology, and also on approximate dynamic programming—which typically achieve within 1% of optimality with computation time orders of magnitude less than what is required to compute the optimal policy for problems of practical sizes. © 2014 Wiley Periodicals, Inc. Naval Research Logistics, 61: 557–576, 2014     

基于空间几何法的目视探测地面目标模型

通过模仿对地攻击机上飞行员的目视搜索发现地面可视目标的过程,建立了其空间几何模型;通过该几何模型得到目视搜索发现目标的数学模型;根据实际情况对模型进行简化,得到简化模型.该模型可信度高,能有效地提高作战效能评估的准确性,对于指挥决策部门和设计单位有一定的参考意义.     

The solution to an open problem for a caching game

In a caching game introduced by Alpern et al. (Alpern et al., Lecture notes in computer science (2010) 220–233) a Hider who can dig to a total fixed depth normalized to 1 buries a fixed number of objects among n discrete locations. A Searcher who can dig to a total depth of h searches the locations with the aim of finding all of the hidden objects. If he does so, he wins, otherwise the Hider wins. This zero‐sum game is complicated to analyze even for small values of its parameters, and for the case of 2 hidden objects has been completely solved only when the game is played in up to 3 locations. For some values of h the solution of the game with 2 objects hidden in 4 locations is known, but the solution in the remaining cases was an open question recently highlighted by Fokkink et al. (Fokkink et al., Search theory: A game theoretic perspective (2014) 85–104). Here we solve the remaining cases of the game with 2 objects hidden in 4 locations. We also give some more general results for the game, in particular using a geometrical argument to show that when there are 2 objects hidden in n locations and n→∞, the value of the game is asymptotically equal to h/n for h≥n/2. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 23–31, 2016     

求解面向进攻的武器-目标分配问题的蚁群算法

面向进攻的武器-目标分配问题是军事运筹学研究中的重要课题,旨在制定合理的打击策略以最大程度摧毁敌方目标。采用一种融合局部搜索和信息素控制的蚁群算法,兼顾控制解的局部收敛速度和全局收敛质量。在解的构造过程中直接处理约束条件,提高生成解的可行性,并大大缩小了搜索空间,提高了算法效率。通过采用多种算法对不同规模的武器-目标分配问题进行实验,结果表明改进的蚁群算法在收敛速度和求解质量上表现优异。     

基于代理模型的卫星系统仿真优化平台

针对既定目标,采用卫星系统进行协同观测可以最大化卫星系统的整体效能,如何对卫星系统的轨道或载荷参数设计是一个设计空间大、设计变量多的优化问题。对此,采用基于代理模型的仿真优化,通过改进广义模式搜索算法在设计空间中搜索最优解,并以此为核心设计开发卫星系统仿真优化平台。该平台集成问题建模、仿真优化和结果评估显示,为用户提供设计和改进卫星系统方案的方法和依据。采用该平台对卫星系统设计实例进行优化,通过对比发现,平台的优化结果稳定性和优化效率优于STK-Analyzer。     

A note on the optimality of index priority rules for search and sequencing problems

We show that the linear objective function of a search problem can be generalized to a power function and/or a logarithmic function and still be minimized by an index priority rule. We prove our result by solving the differential equation resulting from the required invariance condition, therefore, we also prove that any other generalization of this linear objective function will not lead to an index priority rule. We also demonstrate the full equivalence between two related search problems in the sense that a solution to either one can be used to solve the other one and vice versa. Finally, we show that the linear function is the only function leading to an index priority rule for the single‐machine makespan minimization problem with deteriorating jobs and an additive job deterioration function. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

互联网中文搜索引擎存在的问题与发展趋势探析

搜索引擎是互联网信息检索技术的核心,中文搜索引擎与国外相比存在着搜索引擎覆盖率低、查准率不高、检索精度差、更新速度慢、无法控制网络信息的动态变化、对信息内容难于控制和管理等问题。对此,提出了中文搜索引擎从单一查询工具向综合化、全功能服务发展;分类主题一体化,检索语言向自然语言发展;查询智能化,向多国化和多语种化发展;搜索引擎集成化、网络资源著录标准化及利用智能代理技术的信息检索等对策。     

Discrete search allocation game with false contacts

This paper deals with a two‐person zero‐sum game called a search allocation game, where a searcher and a target participate, taking account of false contacts. The searcher distributes his search effort in a search space in order to detect the target. On the other hand, the target moves to avoid the searcher. As a payoff of the game, we take the cumulative amount of search effort weighted by the target distribution, which can be derived as an approximation of the detection probability of the target. The searcher's strategy is a plan of distributing search effort and the target's is a movement represented by a path or transition probability across the search space. In the search, there are false contacts caused by environmental noises, signal processing noises, or real objects resembling true targets. If they happen, the searcher must take some time for their investigation, which interrupts the search for a while. There have been few researches dealing with search games with false contacts. In this paper, we formulate the game into a mathematical programming problem to obtain its equilibrium point. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

基于遗传算法的湿陷性黄土地基灰土挤密桩优化设计

利用Visual C＋＋语言,定义了一个面向对象的基于实数编码遗传算法类。运用可最大限度保证遗传算法搜索到问题的全局最优解的深度搜索策略,编制了灰土挤密桩的优化设计和造价估算遗传算法程序,并针对兰州某地灰土挤密桩复合地基进行了计算分析,并与原有方案比较,结果表明：两种优化方案在满足承载力和变形的条件下,在降低造价成本方面优势非常明显。     

Network design for time‐constrained delivery

To meet customer demand, delivery companies are offering an increasing number of time‐definite services. In this article, we examine the strategic design of delivery networks which can efficiently provide these services. Because of the high cost of direct connections, we focus on tree‐structured networks. As it may not be possible to identify a tree‐structured network that satisfies all of the delivery guarantees, we allow these guarantees to be violated but seek to minimize the sum of the violations. We establish the complexity of the problem and exploit an empirically identified solution structure to create new neighborhoods which improve solution values over more general neighborhood structures. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008