A search game taking account of attributes of searching resources

This article deals with a two‐person zero‐sum game called a search allocation game (SAG), in which a searcher and a target participate as players. The searcher distributes his searching resources in a search space to detect the target. The effect of resources lasts a certain period of time and extends to some areas at a distance from the resources' dropped points. On the other hand, the target moves around in the search space to evade the searcher. In the history of search games, there has been little research covering the durability and reachability of searching resources. This article proposes two linear programming formulations to solve the SAG with durable and reachable resources, and at the same time provide an optimal strategy of distributing searching resources for the searcher and an optimal moving strategy for the target. Using examples, we will analyze the influences of two attributes of resources on optimal strategies. © 2007 Wiley Periodicals, Inc. Naval Research Logistics 2008     

Adjacency‐based local top‐down search method for finding maximal efficient faces in multiple objective linear programming

It is well‐known that the efficient set of a multiobjective linear programming (MOLP) problem can be represented as a union of the maximal efficient faces of the feasible region. In this paper, we propose a method for finding all maximal efficient faces for an MOLP. The new method is based on a condition that all efficient vertices (short for the efficient extreme points and rays) for the MOLP have been found and it relies on the adjacency, affine independence and convexity results of efficient sets. The method uses a local top‐down search strategy to determine maximal efficient faces incident to every efficient vertex for finding maximal efficient faces of an MOLP problem. To our knowledge, the proposed method is the first top‐down search method that uses the adjacency property of the efficient set to find all maximal efficient faces. We discuss this and other advantages and disadvantages of the algorithm. We also discuss some computational experience we have had with our computer code for implementing the algorithm. This computational experience involved solving several MOLP problems with the code.     

基于禁忌退火算法的巡航导弹航迹规划

针对巡航导弹航迹规划这个复杂的优化问题,一个禁忌退火混合优化算法被提出.首先,该算法是以基本模拟退火算法为基础.其次,为了加快该模拟退火算法的收敛速度,在恶化解的接受判断过程中,增加了一定动态的约束条件.最后,为了使最优解能够跳出局部最优的陷阱,使用了一个动态的禁忌表.仿真结果验证了该禁忌退火混合优化算法能够取得目标函数更优的航迹规划路径,从而有效提高巡航导弹的作战效能.     

Neighborhood search heuristics for selecting hierarchically well‐formulated subsets in polynomial regression

The importance of subset selection in multiple regression has been recognized for more than 40 years and, not surprisingly, a variety of exact and heuristic procedures have been proposed for choosing subsets of variables. In the case of polynomial regression, the subset selection problem is complicated by two issues: (1) the substantial growth in the number of candidate predictors, and (2) the desire to obtain hierarchically well‐formulated subsets that facilitate proper interpretation of the regression parameter estimates. The first of these issues creates the need for heuristic methods that can provide solutions in reasonable computation time; whereas the second requires innovative neighborhood search approaches that accommodate the hierarchical constraints. We developed tabu search and variable neighborhood search heuristics for subset selection in polynomial regression. These heuristics are applied to a classic data set from the literature and, subsequently, evaluated in a simulation study using synthetic data sets. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

LFM脉冲雷达距离维快速搜索处理算法

针对脉冲雷达近距离目标遮挡问题,从理论上分析了雷达最小作用距离不受限于脉冲宽度.在此基础上,以Chirp脉冲为例,提出了一种适合远近距离全程目标的快速搜索处理算法.该算法只需发射一种宽脉冲波形,而不必根据距离的变化改变脉宽,从而有效缩短了搜索时间,大大提高了搜索效率.仿真结果表明了理论分析的正确性和算法的有效性.     

A learning tabu search for a truck allocation problem with linear and nonlinear cost components

The two‐level problem studied in this article consists of optimizing the refueling costs of a fleet of locomotives over a railway network. The goal consists of determining: (1) the number of refueling trucks contracted for each yard (truck assignment problem denoted TAP) and (2) the refueling plan of each locomotive (fuel distribution problem denoted FDP). As the FDP can be solved efficiently with existing methods, the focus is put on the TAP only. In a first version of the problem (denoted (P1)), various linear costs (e.g., fuel, fixed cost associated with each refueling, weekly operating costs of trucks) have to be minimized while satisfying a set of constraints (e.g., limited capacities of the locomotives and the trucks). In contrast with the existing literature on this problem, two types of nonlinear cost components will also be considered, based on the following ideas: (1) if several trucks from the same fuel supplier are contracted for the same yard, the supplier is likely to propose discounted prices for that yard (Problem (P2)); (2) if a train stops too often on its route, a penalty is incurred, which represents the dissatisfaction of the clients (Problem (P3)). Even if exact methods based on a mixed integer linear program formulation are available for (P1), they are not appropriate anymore to tackle (P2) and (P3). Various methods are proposed for the TAP: a descent local search, a tabu search, and a learning tabu search (LTS). The latter is a new type of local search algorithm. It involves a learning process relying on a trail system, and it can be applied to any combinatorial optimization problem. Results are reported and discussed for a large set of instances (for (P1), (P2), and (P3)), and show the good performance of LTS. © 2014 Wiley Periodicals, Inc. 62:32–45, 2015     

远程制导火箭子母弹对机场跑道毁伤研究

对机场跑道毁伤封锁是远程制导武器的重要任务,其毁伤判断的依据是最小升降窗口存在与否。采用Monte-Carlo方法对远程制导火箭子母弹打击机场跑道的炸点分布进行仿真模拟,提出了一种改进的搜索飞机起降最小升降窗口算法,并用该算法计算分析了远程制导火箭子母弹相关战技术因素对机场跑道毁伤的影响程度。计算结果表明改进算法计算封锁概率的值相对于区域搜索算法更加精确,研究结果对远程制导火箭子母弹的作战运用及进一步优化设计具有参考与实用价值。     

一种基于部分搜索的GNSS模糊度解算方法

为解决LAMBDA算法搜索策略效率不高的问题,提出了一种基于部分搜索的模糊度解算新方法。该方法的解算成功率接近LAMBDA算法,且只需对最后3维模糊度元素采取搜索策略。同时,通过合理设定搜索椭球的大小和搜索策略;大大提高了搜索效率。通过实验对该新算法与Bootraping算法、LAMBDA算法进行了比较分析,进一步验证了该新算法的有效性。     

求解CVRP问题的一种改进启发式蚁群算法

针对蚁群算法求解CVRP问题时收敛速度慢、求解质量不高的缺点,提出了一种改进启发式蚁群算法。该算法借鉴蚁群系统和基于排列的蚂蚁系统的优点设计信息素更新策略,既加强了对每次迭代最好解的利用,又避免了陷入局部最优;按一定比例使用基本方法和基于PFIH方法构造路径,扩大了算法的搜索空间;采用一种混合局部搜索算子,增强了算法局部寻优能力。实验结果表明,改进启发式蚁群算法可以大幅度减少车辆运行成本,具有较快的收敛速度。     

智能搜救机器人在障碍地形的自主构型规划

为了解决带有辅助摆臂的智能搜救机器人自动规划构型以实现自主越障的难题,提出一种能够适应复杂地面形状的搜救机器人越障构型规划新方法,其核心是一种高适应性、高效率的机器人姿态预测算法。通过将地形表示为离散的点集,建立了搜救机器人的单侧姿态预测数学模型;进一步提出了快速求解该问题的算法,每秒可预测1 000～1 500个姿态。基于此,设计了机器人越障过程中状态、动作的评价指标,运用动态规划算法与滚动优化思想构建了具有优化能力的、能够实时运行的构型规划器。仿真与实物实验的结果表明,该方法能够使机器人自主调整构型穿越复杂地形,且相较强化学习算法和人工操作具有更平稳的越障效果。