A novel stochastic optimization algorithm

This paper presents a new stochastic approach SAGACIA based on proper integration of simulated annealing algorithm (SAA), genetic algorithm (GA), and chemotaxis algorithm (CA) for solving complex optimization problems. SAGACIA combines the advantages of SAA, GA, and CA together. It has the following features: (1) it is not the simple mix of SAA, GA, and CA; (2) it works from a population; (3) it can be easily used to solve optimization problems either with continuous variables or with discrete variables, and it does not need coding and decoding,; and (4) it can easily escape from local minima and converge quickly. Good solutions can be obtained in a very short time. The search process of SAGACIA can be explained with Markov chains. In this paper, it is proved that SAGACIA has the property of global asymptotical convergence. SAGACIA has been applied to solve such problems as scheduling, the training of artificial neural networks, and the optimizing of complex functions. In all the test cases, the performance of SAGACIA is better than that of SAA, GA, and CA.     

Sampling average approximation method for a class of stochastic Nash equilibrium problems

We consider a class of stochastic Nash equilibrium problems (SNEP). Under some mild conditions, we reformulate the SNEP as a stochastic mixed complementarity problem (SMCP). We apply the well-known sample average approximation (SAA) method to solve the SMCP. We further introduce a semismooth Newton method to solve the SAA problems. The comprehensive convergence analysis is given as well. In addition, we demonstrate the proposed approach on a stochastic Nash equilibrium model in the wholesale gas–oil markets.     

Optimal and suboptimal solutions to stochastically uncertain problems of quintile optimization

In this paper, problems of stochastic optimization under incomplete information on distribution of random perturbations with the quintile and probability criteria are considered. The minimax approach is used when optimal solutions are chosen. Conditions for equivalency of direct and inverse problems of stochastic optimization under incomplete statistical information are studied. The solution method for statistically uncertain problems of optimization with the quintile criterion basing on the use of generalized confidence sets for statistically uncertain random quantities is proposed. The use of confidence sets for finding suboptimal solutions to the problem of stochastic optimization under incomplete information is considered. Examples of the application of obtained relations are represented.     

一种新的求解ATSP问题的PBIL算法

该文将二进制的人口增量学习算法(PBIL)改进为整数(集值)形式(multiplePBIL),并提出了一种新的基于城市间连接关系的非对称旅行商问题(ATSP)的解法。这种解法结合了集值人口增量学习算法和TSP问题的启发式搜索3-opt加强方法。混沌定位,分布式随机遍历构架和判断进化结束条件的可能性分布的熵的确定是该解法的三大创新之处。     

Sequential optimization approach for nesting and cutting sequence in laser cutting

The economy of the laser cutting process depends on two productivity issues: (i) nesting, a classic problem of finding the most efficient layout for cutting parts with minimum material waste; (ii) cutting sequence, which targets the optimal sequence of edges of the parts to be cut for minimum cycle time. This paper presents a two stage sequential optimization procedure for nesting and cutting sequence for the objectives of maximizing material utilization and minimization of ideal (non-cut) travel distance of laser cut tool. However, the focus of this paper is the development of solution technique for optimal cutting sequence to any given layout. Simulated annealing algorithm (SAA) is considered to evolve the optimal cutting sequence. The proposed SAA is illustrated with the optimal material utilization layout obtained using sheet cutting suite software, a professional rectangular nesting software package. The robust test carried out with five typical problems shows that the SAA proposed for cutting sequence is capable of providing near optimal solutions. The performance comparison with two literature problems reveals that the proposed SAA is able to give improved result than GA and ACO algorithms.     

Optimal Deterministic and Stochastic Macroeconomic Policies for Slovenia: An Application of the OPTCON Algorithm

This paper reports about applications of optimal control theory to the analysis of macroeconomic policies for Slovenia during its way into the Euro Area. For this purpose, the model SLOPOL4, a macroeconometric model for Slovenia, is used. Optimal policies are calculated using the OPTCON algorithm, an algorithm for determining (approximately) optimal solutions to deterministic and stochastic control problems. We determine optimal exchange rate and fiscal policies for Slovenia as solutions to optimum control problems with a quadratic objective function and the model SLOPOL4 as constraint. Several optimization experiments under different assumptions about the exchange rate regime are carried out. The sensitivity of the results with respect to several assumptions is investigated; in particular, the reaction of the optimal paths on varying the stochastic character of the model parameters is examined. If the stochastic nature of more parameters is taken into consideration, the resulting policies are closer to the deterministic solution than with only a few stochastic parameters.     

OPTIMIZING COMPLEX FUNCTIONS BY CHAOS SEARCH

During past decades, the role of optimization has steadily increased in many fields. It is a hot problem in research on control theory. In practice, optimization problems become more and more complex. Traditional algorithms cannot solve them satisfactorily. Either they are trapped to local minima or they need much more search time. Chaos often exists in nonlinear systems. It has many good properties such as ergodicity, stochastic properties, and ''regularity.'' A chaotic motion can go nonrepeatedly through every state in a certain domain. By use of these properties of chaos, an effective optimization method is proposed: the chaos optimization algorithm COA . With chaos search, some complex optimization problems are solved very well. The test results illustrate that the efficiency of COA is much higher than that of some stochastic algorithms such as the simulated annealing algorithm SAA and chemotaxis algorithm CA , which are often used to optimize complex problems. The chaos optimization method provides a new and efficient way to optimize kinds of complex problems with continuous variables.     

A two-stage stochastic programming model for the parallel machine scheduling problem with machine capacity

This paper proposes a two-stage stochastic programming model for the parallel machine scheduling problem where the objective is to determine the machines' capacities that maximize the expected net profit of on-time jobs when the due dates are uncertain. The stochastic model decomposes the problem into two stages: The first (FS) determines the optimal capacities of the machines whereas the second (SS) computes an estimate of the expected profit of the on-time jobs for given machines' capacities. For a given sample of due dates, SS reduces to the deterministic parallel weighted number of on-time jobs problem which can be solved using the efficient branch and bound of M’Hallah and Bulfin [16]. FS is tackled using a sample average approximation (SAA) sampling approach which iteratively solves the problem for a number of random samples of due dates. SAA converges to the optimum in the expected sense as the sample size increases. In this implementation, SAA applies a ranking and selection procedure to obtain a good estimate of the expected profit with a reduced number of random samples. Extensive computational experiments show the efficacy of the stochastic model.     

多智能体系统跟踪领导节点的随机一致性问题研究

针对一阶连续时间多智能体系统,研究了在带有通信噪声情况下跟踪领导节点的随机一致性问题。将代数图理论、矩阵理论和随机Lyapunov方法相结合,给出了在领导节点状态的一阶导数有界的情况下,系统达到随机一致的条件,并给出了误差均方期望上界的表达式。通过研究该误差上界表达式,可以找到控制误差上界的关键参数。其中分别研究了系统中所有个体都可以获取领导节点信息和只有一部分个体可以获取领导节点信息的两种情形。第二种情形更接近实际情况,也有更大的研究价值。最后通过仿真实验证明:理论推导与仿真结果相一致。     

On solutions to fuzzy stochastic differential equations with local martingales

This paper deals with a class of fuzzy stochastic differential equations (FSDEs) driven by a continuous local martingale under the Lipschitzian condition. Such equations can be useful in modeling hybrid systems, where the phenomena are simultaneously subjected to two kinds of uncertainties: randomness and fuzziness. The solutions of the FSDEs are the fuzzy stochastic processes, and their uniqueness is considered to be in a strong sense. Thus, the existence and uniqueness of solutions to the FSDEs under the Lipschitzian condition is first proven. Moreover, some asymptotic properties of the solutions to the FSDEs are investigated. Finally, an illustrating example on the interest term model is provided.     

On asymmetric stochastic bang-bang control†

Three stochastic bang-bang control problems, the predicted miss, the linear regulator, and a complete observation model, are shown to have formally similar solutions under an asymmetric boundedness condition on the control u(t), 0<t<T.     

Stochastic algorithms for robustness of control performances

In recent years, there has been a growing interest in developing statistical learning methods to provide approximate solutions to “difficult” control problems. In particular, randomized algorithms have become a very popular tool used for stability and performance analysis as well as for design of control systems. However, as randomized algorithms provide an efficient solution procedure to the “intractable” problems, stochastic methods bring closer to understanding the properties of the real systems. The topic of this paper is the use of stochastic methods in order to solve the problem of control robustness: the case of parametric stochastic uncertainty is considered. Necessary concepts regarding stochastic control theory and stochastic differential equations are introduced. Then a convergence analysis is provided by means of the Chernoff bounds, which guarantees robustness in mean and in probability. As an illustration, the robustness of control performances of example control systems is computed.     

A Computational Method for Stochastic Optimal Control Problems in Financial Mathematics

Principle of optimality or dynamic programming leads to derivation of a partial differential equation (PDE) for solving optimal control problems, namely the Hamilton‐Jacobi‐Bellman (HJB) equation. In general, this equation cannot be solved analytically; thus many computing strategies have been developed for optimal control problems. Many problems in financial mathematics involve the solution of stochastic optimal control (SOC) problems. In this work, the variational iteration method (VIM) is applied for solving SOC problems. In fact, solutions for the value function and the corresponding optimal strategies are obtained numerically. We solve a stochastic linear regulator problem to investigate the applicability and simplicity of the presented method and prove its convergence. In particular, for Merton's portfolio selection model as a problem of portfolio optimization, the proposed numerical method is applied for the first time and its usefulness is demonstrated. For the nonlinear case, we investigate its convergence using Banach's fixed point theorem. The numerical results confirm the simplicity and efficiency of our method.     

Stability of stochastic dynamic random-structure systems with aftereffect and Markov switchings

Using the second Lyapunov–Krasovskii method, sufficient conditions are obtained for the asymptotic stochastic global stability, for the global stability, and mean-square stability of trivial solutions to systems of diffusion stochastic functional–differential equations with Markov switchings, and the theory is illustrated by two model problems.     

The effect of few historical data on the performance of sample average approximation method for operating room scheduling

We model the scheduling problem of a single operating room for outpatient surgery, with uncertain case durations and an objective function comprising waiting time, idle time, and overtime costs. This stochastic scheduling problem has been studied in diverse forms. One of the most common approaches used is the sample average approximation (SAA). Our contribution is to study the use of SAA to solve this problem under few historical data using families of log t distributions with varying degrees of freedom. We analyze the results of the SAA method in terms of optimality convergence, the effect of the number of scenarios, and average computational time. Given the case sequence, computational results demonstrate that SAA with an adequate number of scenarios performs close to the exact method. For example, we find that the optimality gap, in units of proportional weighted time, is relatively small when 500 scenarios are used: 99% of the instances have an optimality gap of less than 2.6 7% (1.74%, 1.23%) when there are 3 (9, many) historical samples. Increasing the number of SAA scenarios improves performance, but is not critical when the case sequence is given. However, choosing the number of SAA scenarios becomes critical when the same method is used to choose among sequencing heuristics when there are few historical data. For example, when there are only three (nine, many) historical samples, 99% of the instances have less than 25.38% (13.15%, 6.87%) penalty in using SAA with 500 scenarios to choose the best sequencing heuristic.     

Remarks on the cellular automaton global synchronisation problem: deterministic versus stochastic models

In the global synchronisation problem, one is asked to find a cellular automaton which has the property that every initial condition evolves into a homogeneous blinking state. We study this simple inverse problem for the case of one-dimensional systems with periodic boundary conditions. Two paradoxical observations are made: (a) despite the apparent simplicity of finding rules with good statistical results, there exist no perfect deterministic solutions to this problem, (b) if we allow the use of randomness in the local rule, constructing “perfect” stochastic solutions is easy. For the stochastic case, we give some rules for which the mean time of synchronisation varies quadratically with the number of cells and ask if this result can be improved. To explore more deeply the deterministic rules, we code our problem as a SAT problem and use SAT solvers to find rules that synchronise a large set of initial conditions (in appendix).

     

A hybrid approach based on stochastic competitive Hopfield neural network and efficient genetic algorithm for frequency assignment problem

This paper presents a hybrid efficient genetic algorithm (EGA) for the stochastic competitive Hopfield (SCH) neural network, which is named SCH–EGA. This approach aims to tackle the frequency assignment problem (FAP). The objective of the FAP in satellite communication system is to minimize the co-channel interference between satellite communication systems by rearranging the frequency assignment so that they can accommodate increasing demands. Our hybrid algorithm involves a stochastic competitive Hopfield neural network (SCHNN) which manages the problem constraints, when a genetic algorithm searches for high quality solutions with the minimum possible cost. Our hybrid algorithm, reflecting a special type of algorithm hybrid thought, owns good adaptability which cannot only deal with the FAP, but also cope with other problems including the clustering, classification, and the maximum clique problem, etc. In this paper, we first propose five optimal strategies to build an efficient genetic algorithm. Then we explore three hybridizations between SCHNN and EGA to discover the best hybrid algorithm. We believe that the comparison can also be helpful for hybridizations between neural networks and other evolutionary algorithms such as the particle swarm optimization algorithm, the artificial bee colony algorithm, etc. In the experiments, our hybrid algorithm obtains better or comparable performance than other algorithms on 5 benchmark problems and 12 large problems randomly generated. Finally, we show that our hybrid algorithm can obtain good results with a small size population.     

Step decision rules for multistage stochastic programming: A heuristic approach

Stochastic programming with step decision rules (SPSDR) aims to produce efficient solutions to multistage stochastic optimization problems. SPSDR, like plain multistage Stochastic Programming (SP), operates on a Monte Carlo “computing sample” of moderate size that approximates the stochastic process. Unlike SP, SPSDR does not strive to build a balanced event tree out of that sample. Rather, it defines a solution as a special type of decision rule, with the property that the decisions at each stage are piecewise constant functions on the sample of scenarios. Those pieces define a partition of the set of scenarios at each stage t, but the partition at t+1 need not be refinement of the partition at t. However, the rule is constructed so that the non-anticipativity condition is met, a necessary condition to make the rules operational. To validate the method we show how to extend a non-anticipatory decision rule to arbitrary scenarios within a very large validation sample of scenarios. We apply three methods, SPSDR, SP and Robust Optimization, to the same 12-stage problem in supply chain management, and compare them relatively to different objectives and performance criteria. It appears that SPSDR performs better than SP in that it produces a more accurate estimate (prediction) of the value achieved by its solution on the validation sample, and also that the achieved value is better.     

Hierarchical stochastic modeling and optimization for petroleum field development under geological uncertainty

Real-world simulation optimization (SO) problems entail complex system modeling and expensive stochastic simulation. Existing SO algorithms may not be applicable for such SO problems because they often evaluate a large number of solutions with many simulation calls. We propose an integrated solution method for practical SO problems based on a hierarchical stochastic modeling and optimization (HSMO) approach. This method models and optimizes the studied system at increasing levels of accuracy by hierarchical sampling with a selected set of principal parameters. We demonstrate the efficiency of HSMO using the example problem of Brugge oil field development under geological uncertainty.     

Estimation of the Pareto front in stochastic simulation through stochastic Kriging

Multi-objective optimization of simulated stochastic systems aims at estimating a representative set of Pareto optimal solutions and a common approach is to rely on metamodels to alleviate computational costs of the optimization process. In this article, both the objective and constraint functions are assumed to be smooth, highly non-linear and computationally expensive and are emulated by stochastic Kriging models. Then a novel global optimization algorithm, combing the expected hypervolume improvement of approximated Pareto front and the probability of feasibility of new points, is proposed to identify the Pareto front (set) with a minimal number of expensive simulations. The algorithm is suitable for the situations of having disconnected feasible regions and of having no feasible solution in initial design. Then, we also quantify the variability of estimated Pareto front caused by the intrinsic uncertainty of stochastic simulation using nonparametric bootstrapping method to better support decision making. One test function and an (s, S) inventory system experiment illustrate the potential and efficiency of the proposed sequential optimization algorithm for constrained multi-objective optimization problems in stochastic simulation, which is especially useful in Operations Research and Management Science.