Adaptive random search for continuous simulation optimization

We present, analyze, and compare three random search methods for solving stochastic optimization problems with uncountable feasible regions. Our adaptive search with resampling (ASR) approach is a framework for designing provably convergent algorithms that are adaptive and may consequently involve local search. The deterministic and stochastic shrinking ball (DSB and SSB) approaches are also convergent, but they are based on pure random search with the only difference being the estimator of the optimal solution [the DSB method was originally proposed and analyzed by Baumert and Smith]. The three methods use different techniques to reduce the effects of noise in the estimated objective function values. Our ASR method achieves this goal through resampling of already sampled points, whereas the DSB and SSB approaches address it by averaging observations in balls that shrink with time. We present conditions under which the three methods are convergent, both in probability and almost surely, and provide a limited computational study aimed at comparing the methods. Although further investigation is needed, our numerical results suggest that the ASR approach is promising, especially for difficult problems where the probability of identifying good solutions using pure random search is small. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Discrete stochastic optimization using variants of the stochastic ruler method

We present two random search methods for solving discrete stochastic optimization problems. Both of these methods are variants of the stochastic ruler algorithm. They differ from our earlier modification of the stochastic ruler algorithm in that they use different approaches for estimating the optimal solution. Our new methods are guaranteed to converge almost surely to the set of global optimal solutions under mild conditions. We discuss under what conditions these new methods are expected to converge faster than the modified stochastic ruler algorithm. We also discuss how these methods can be used for solving discrete optimization problems when the values of the objective function are estimated using either transient or steady‐state simulation. Finally, we present numerical results that compare the performance of our new methods with that of the modified stochastic ruler algorithm when applied to solve buffer allocation problems. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Annealing adaptive search,cross‐entropy,and stochastic approximation in global optimization

The Annealing Adaptive Search (AAS) algorithm for global optimization searches the solution space by sampling from a sequence of Boltzmann distributions. For a class of optimization problems, it has been shown that the complexity of AAS increases at most linearly in the problem dimension. However, despite its desirable property, sampling from a Boltzmann distribution at each iteration of the algorithm remains a practical challenge. Prior work to address this issue has focused on embedding Markov chain‐based sampling techniques within the AAS framework. In this article, based on ideas from the recent Cross‐Entropy method and Model Reference Adaptive Search, we propose an algorithm, called Model‐based Annealing Random Search (MARS), that complements prior work by sampling solutions from a sequence of surrogate distributions that iteratively approximate the target Boltzmann distributions. We establish a novel connection between MARS and the well‐known Stochastic Approximation method. By exploiting this connection, we prove the global convergence of MARS and characterize its asymptotic convergence rate behavior. Our empirical results indicate promising performance of the algorithm in comparison with some of the existing methods. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Algorithms for the multi‐item multi‐vehicles dynamic lot sizing problem

We consider a two‐stage supply chain, in which multi‐items are shipped from a manufacturing facility or a central warehouse to a downstream retailer that faces deterministic external demand for each of the items over a finite planning horizon. The items are shipped through identical capacitated vehicles, each incurring a fixed cost per trip. In addition, there exist item‐dependent variable shipping costs and inventory holding costs at the retailer for items stored at the end of the period; these costs are constant over time. The sum of all costs must be minimized while satisfying the external demand without backlogging. In this paper we develop a search algorithm to solve the problem optimally. Our search algorithm, although exponential in the worst case, is very efficient empirically due to new properties of the optimal solution that we found, which allow us to restrict the number of solutions examined. Second, we perform a computational study that compares the empirical running time of our search methods to other available exact solution methods to the problem. Finally, we characterize the conditions under which each of the solution methods is likely to be faster than the others and suggest efficient heuristic solutions that we recommend using when the problem is large in all dimensions. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006.     

面向多平台多目标协同跟踪的指派问题

针对多平台多目标协同跟踪中要求多个无人地面平台尽可能均匀地协同跟踪多个目标的特点,提出了改进的离散粒子群优化算法。首先采用连续型粒子群优化算法中的速度和位置迭代公式,然后对粒子位置进行离散编码,使粒子编码对应于可行的指派方案;其次,在优化算法中引入局部搜索,提高算法寻优性能。最后将所提算法应用于多平台多目标协同跟踪中的指派问题,并与未加入局部搜索的粒子群优化算法比较,仿真结果表明,加入局部搜索后的离散粒子群优化算法具有较好的寻优性能。     

自适应人工蜂群优化的混沌系统参数估计

为了对混沌系统未知参数进行准确估计,改进了人工蜂群优化算法,提出自适应人工蜂群算法的混沌系统参数估计方法。将混沌系统参数估计问题转化为多维变量数值优化问题,利用人工蜂群算法对未知参数进行导向随机搜索。在搜索过程中,通过种群优化程度和解的质量自适应地调整更新步长和解的尝试次数。以Lorenz混沌系统为例进行的仿真实验表明,该方法在无噪声和噪声强度较大的情况下均能够获得较好的估计结果,表现出较强的鲁棒性。     

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.     

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     

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

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

优化多星协同观测的改进广义模式搜索算法

多星协同观测可以最大化卫星的整体效能,如何对多星进行部署是一个设计空间大、设计变量多的优化问题.对此,提出了基于Kriging模型的改进广义模式搜索算法.在算法的搜索步,通过代理模型最优和最大期望提高在当前网格内进行选点,避免选择的盲目性;在筛选步,利用代理模型预测筛选集中各点提高的比例并排序,减少不必要的仿真分析.最后,采用该算法对多星部署方案进行优化,通过对比发现,算法性能优于STK-Analyzer,证明了算法的可行性和有效性.     

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.     

声纳浮标搜潜优化布放技术研究

在航空搜潜中为了提高搜索概率,需要优化声纳浮标群的布放位置。首先建立目标运动模型和累积搜索概率的计算方法,然后采用多点随机搜索、分区&分支界定和遗传算法对规则阵形和不规则阵形的声纳浮标群的布放位置进行优化,相应地建构了三种声纳浮标搜潜优化布放方法。仿真结果表明：在简单环境下搜潜,用前两种方法优化规则浮标阵的阵形参数,其搜索概率高而且运算时间短;在复杂环境下搜潜,利用遗传算法优化不规则浮标阵的布放位置,具有最高的搜索概率但运算时间较长。     

基于族群机制的花朵授粉算法

针对花朵授粉算法易陷入局部极值、收敛速度慢等不足,提出一种具有族群机制的花朵授粉算法。该算法把种群分成多个族群,各族群的最优个体再组成新的种群,进而促进种群间的信息交流,有效地协调种群进化过程中的全局搜索和局部搜索能力,避免个体的早熟收敛,提高算法的全局寻优能力及收敛速度。通过8个CEC2005benchmark测试函数进行测试比较,仿真结果表明,改进算法的寻优性能明显优于基本的花朵授粉算法、粒子群算法和蝙蝠算法,其收敛精度、收敛速度、鲁棒性均较对比算法有较大提高。     

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

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

基于静止标量磁强计的运动舰船定位问题的研究

建立了静止标量磁强计对运动舰船定位的模型,并给出了用遗传算法求全局较优解、然后用单纯形法进行精确局部搜索的求解参数的方法.仿真实验表明这种方法有效、可行.     

Subspace dynamic‐simplex linear interpolation search for mixed‐integer black‐box optimization problems

Design and management of complex systems with both integer and continuous decision variables can be guided using mixed‐integer optimization models and analysis. We propose a new mixed‐integer black‐box optimization (MIBO) method, subspace dynamic‐simplex linear interpolation search (SD‐SLIS), for decision making problems in which system performance can only be evaluated with a computer black‐box model. Through a sequence of gradient‐type local searches in subspaces of solution space, SD‐SLIS is particularly efficient for such MIBO problems with scaling issues. We discuss the convergence conditions and properties of SD‐SLIS algorithms for a class of MIBO problems. Under mild conditions, SD‐SLIS is proved to converge to a stationary solution asymptotically. We apply SD‐SLIS to six example problems including two MIBO problems associated with petroleum field development projects. The algorithm performance of SD‐SLIS is compared with that of a state‐of‐the‐art direct‐search method, NOMAD, and that of a full space simplex interpolation search, Full‐SLIS. The numerical results suggest that SD‐SLIS solves the example problems efficiently and outperforms the compared methods for most of the example cases. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 305–322, 2017     

Modeling and solution for the ship stowage planning problem of coils in the steel industry

We consider a ship stowage planning problem where steel coils with known destination ports are to be loaded onto a ship. The coils are to be stowed on the ship in rows. Due to their heavy weight and cylindrical shape, coils can be stowed in at most two levels. Different from stowage problems in previous studies, in this problem there are no fixed positions on the ship for the coils due to their different sizes. At a destination port, if a coil to be unloaded is not at a top position, those blocking it need to be shuffled. In addition, the stability of ship has to be maintained after unloading at each destination port. The objective for the stowage planning problem is to minimize a combination of ship instability throughout the entire voyage, the shuffles needed for unloading at the destination ports, and the dispersion of coils to be unloaded at the same destination port. We formulate the problem as a novel mixed integer linear programming model. Several valid inequalities are derived to help reducing solution time. A tabu search (TS) algorithm is developed for the problem with the initial solution generated using a construction heuristic. To evaluate the proposed TS algorithm, numerical experiments are carried out on problem instances of three different scales by comparing it with a model‐based decomposition heuristic, the classic TS algorithm, the particle swarm optimization algorithm, and the manual method used in practice. The results show that for small problems, the proposed algorithm can generate optimal solutions. For medium and large practical problems, the proposed algorithm outperforms other methods. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 564–581, 2015     

A New Chaotic Genetic Hybrid Algorithm and Its Applications in Mechanical Optimization Design

A new chaotic genetic hybrid algorithm(CGHA) based on float point coding was put forward in this paper.Firstly,it used chaos optimization to search coarsely and produced a better initial population.Then,a power function carrier was adopted to improve the ergodicity and the sufficiency of the chaos optimization.Secondly,the genetic algorithm(GA) was used to search finely and guaranteed the population's evolution.To avoid the search being trapped in local minimum,a chaos degenerate mutation operator was designed to make the search converge to a global optimum quickly.Finally,CGHA was used to solve a typical mechanical optimization problem of shear stress checking for a cylinder helix spring.Compared with traditional penalty function method,chaos-Powell hybrid algorithm and standard GA,CGHA shows better performance in solution precision and convergence speed than those of the algorithms.Therefore,CGHA is a new effective way to solve the problems in mechanical optimization design.     

调运问题中基于栅格模型的快速路径规划方法

针对调运路径规划这一问题,采用栅格模型表示环境地图,通过设定路径搜索方向权重,剔除不必要的搜索区域,提高了搜索效率.仿真结果表明,该算法能有效地提高路径搜索效率,并能搜索到最优路径.     

基于混合粒子群优化的多目标决策新方法

多目标优化问题中的一个关键在于合理地评判各有效解的优劣。通过引入灰色系统理论中灰色关联度的概念作为评判准则,结合粒子群优化算法进行有约束多目标规划问题的研究。提出了一种新的不可行解的保留策略,进化过程中以此策略保留适量的不可行解,有利于增强对约束边界附近可能的最优解的搜索,同时,针对粒子群优化算法的容易陷入局部最优的缺点,实现了以粒子群优化为载体的混合算法:即对全局极值邻域进一步混沌搜索寻优。仿真结果表明改进的算法对多目标决策问题是有效的。