Meta-control of an interacting-particle algorithm for global optimization

A common issue for stochastic global optimization algorithms is how to set the parameters of the sampling distribution (e.g. temperature, mutation/cross-over rates, selection rate, etc.) so that the samplings converge to the optimum effectively and efficiently. We consider an interacting-particle algorithm and develop a meta-control methodology which analytically guides the inverse temperature parameter of the algorithm to achieve desired performance characteristics (e.g. quality of the final outcome, algorithm running time, etc.). The main aspect of our meta-control methodology is to formulate an optimal control problem where the fractional change in the inverse temperature parameter is the control variable. The objectives of the optimal control problem are set according to the desired behavior of the interacting-particle algorithm. The control problem considers particles’ average behavior, rather than treating the behavior of individual particles. The solution to the control problem provides feedback on the inverse temperature parameter of the algorithm.     

Numerical computation of singular control problems with application to optimal heating and cooling by solar energy

The method presented here is an extension of the multiple shooting algorithm in order to handle multipoint boundary-value problems and problems of optimal control in the special situation of singular controls or constraints on the state variables. This generalization allows a direct treatment of (nonlinear) conditions at switching points. As an example a model of optimal heating and cooling by solar energy is considered. The model is given in the form of an optimal control problem with three control functions appearing linearly and a first order constraint on the state variables. Numerical solutions of this problem by multiple shooting techniques are presented.     

A dynamic programming algorithm for dynamic lot size models with piecewise linear costs

We propose a new algorithm for dynamic lot size models (LSM) in which production and inventory cost functions are only assumed to be piecewise linear. In particular, there are no assumptions of convexity, concavity or monotonicity. Arbitrary capacities on both production and inventory may occur, and backlogging is allowed. Thus the algorithm addresses most variants of the LSM appearing in the literature. Computational experience shows it to be very effective on NP-hard versions of the problem. For example, 48 period capacitated problems with production costs defined by eight linear segments are solvable in less than 2.5 minutes of Vax 8600 cpu time.     

A multi-start global minimization algorithm with dynamic search trajectories

A new multi-start algorithm for global unconstrained minimization is presented in which the search trajectories are derived from the equation of motion of a particle in a conservative force field, where the function to be minimized represents the potential energy. The trajectories are modified to increase the probability of convergence to a comparatively low local minimum, thus increasing the region of convergence of the global minimum. A Bayesian argument is adopted by which, under mild assumptions, the confidence level that the global minimum has been attained may be computed. When applied to standard and other test functions, the algorithm never failed to yield the global minimum.The first author wishes to thank Prof. M. Levitt of the Department of Chemical Physics of the Weizmann Institute of Science for suggesting this line of research and also Drs. T. B. Scheffler and E. A. Evangelidis for fruitful discussions regarding Conjecture 2.1. He also acknowledges the exchange agreement award received from the National Council for Research and Development in Israel and the Council for Scientific and Industrial Research in South Africa, which made possible the visit to the Weizmann Institute where this work was initiated.     

A rank based particle swarm optimization algorithm with dynamic adaptation

The particle swarm optimization (PSO) technique is a powerful stochastic evolutionary algorithm that can be used to find the global optimum solution in a complex search space. This paper presents a variation on the standard PSO algorithm called the rank based particle swarm optimizer, or PSO_rank, employing cooperative behavior of the particles to significantly improve the performance of the original algorithm. In this method, in order to efficiently control the local search and convergence to global optimum solution, the γ best particles are taken to contribute to the updating of the position of a candidate particle. The contribution of each particle is proportional to its strength. The strength is a function of three parameters: strivness, immediacy and number of contributed particles. All particles are sorted according to their fitness values, and only the γ best particles will be selected. The value of γ decreases linearly as the iteration increases. A time-varying inertia weight decreasing non-linearly is introduced to improve the performance. PSO_rank is tested on a commonly used set of optimization problems and is compared to other variants of the PSO algorithm presented in the literature. As a real application, PSO_rank is used for neural network training. The PSO_rank strategy outperformed all the methods considered in this investigation for most of the functions. Experimental results show the suitability of the proposed algorithm in terms of effectiveness and robustness.     

Dependence of the acoustic and mechanical properties of polyethylene on temperature and cyclic cooling and heating

The low-temperature stability of polyethylene is confirmed by acoustic and mechanical investigations. Data are given on the dependence of the acoustic and mechanical properties of polyethylene on temperature and repeated cyclic cooling to –50° and heating to +60°C, together with information on the change in Poisson's ratio and volume during deformation.Mekhanika Polimerov, Vol. 1, No. 3, pp. 145–150, 1965     

An algorithm for minimal dynamic flow

FORD and FULKERSON have shown that a stationary maximal dynamic flow can be obtained by solving a transhipment problem associated with the static network and thereby finding the maximal temporally repeated dynamic flow. This flow is known to be an optimal dynamic flow. This paper presents the remark that temporally repeated flows may be not optimal for a minimal dynamic flow and an algorithm for such a flow. A numerical example is presented.     

A parallel variable-metric dynamic programming algorithm

This paper presents a potentially parallel iterative algorithm for the solution of the unconstrainedN-stage decision problem of dynamic programming. The basis of the algorithm is the use of variable-metric minimization techniques to develop a quadratic approximation to the cost function at each stage. The algorithm is applied to various problems, and comparisons with other algorithms are made.This research forms part of the author's PhD program, and is supported by the Department of Scientific and Industrial Research of the New Zealand Government. The author is indebted to Dr. B. A. Murtagh, PhD supervisor, for his encouragement and support during the preparation of this paper.     

Exergoeconomic optimal performance of an irreversible closed Brayton cycle combined cooling,heating and power plant

A combined cooling, heating and power (CCHP) plant model composed of an irreversible closed Brayton cycle and an endoreversible four-heat-reservoir absorption refrigeration cycle is established by using finite time thermodynamics. The irreversibilities considered in the CCHP plant include heat-resistance losses in the hot-, cold-, thermal consumer-, generator-, absorber-, condenser- and evaporator-side heat exchangers as well as non-isentropic losses in the compression and expansion processes. Equations of exergy efficiency and profit rate of the CCHP plant are derived. Based on the finite time exergoeconomic analysis method, profit rate optimization is carried out by searching the optimal compressor pressure ratio and the optimal heat conductance distributions of the seven heat exchangers for a fixed total heat exchanger inventory and with the help of Powell arithmetic. The effects of some design parameters, including compressor and gas turbine efficiencies, ratio of heat demanded by the thermal consumer to power output, heat reservoir temperature ratios and price ratios on the optimal heat conductance distributions, optimal compressor pressure ratio, maximum profit rate and finite time exergoeconomic performance bound of the CCHP plant are discussed by numerical examples. The results obtained may provide some theoretical guidelines for the designs and operations of the practical CCHP plants.     

The value iteration algorithm is not strongly polynomial for discounted dynamic programming

This note provides a simple example demonstrating that, if exact computations are allowed, the number of iterations required for the value iteration algorithm to find an optimal policy for discounted dynamic programming problems may grow arbitrarily quickly with the size of the problem. In particular, the number of iterations can be exponential in the number of actions. Thus, unlike policy iterations, the value iteration algorithm is not strongly polynomial for discounted dynamic programming.     

Optimization algorithm based on densification and dynamic canonical descent

Stochastic methods have gained some popularity in global optimization in that most of them do not assume the cost functions to be differentiable. They have capabilities to avoid being trapped by local optima, and may converge even faster than gradient-based optimization methods on some problems. The present paper proposes an optimization method, which reduces the search space by means of densification curves, coupled with the dynamic canonical descent algorithm. The performances of the new method are shown on several known problems classically used for testing optimization algorithms, and proved to outperform competitive algorithms such as simulated annealing and genetic algorithms.     

Fully dynamic recognition algorithm and certificate for directed cographs

This paper presents an optimal fully dynamic recognition algorithm for directed cographs. Given the modular decomposition tree of a directed cograph G, the algorithm supports arc and vertex modification (insertion or deletion) in O(d) time where d is the number of arcs involved in the operation. Moreover, if the modified graph remains a directed cograph, the modular decomposition tree is updated; otherwise, a certificate is returned within the same complexity.     

An approximation algorithm for the dynamic facility location problem with submodular penalties

In this paper, we study the dynamic facility location problem with submodular penalties （DFLPSP）. We present a combinatorial primal-dual 3-approximation algorithm for the DFLPSP.     

Modified Newton integration algorithm with noise suppression for online dynamic nonlinear optimization

Numerical Algorithms - The solution of nonlinear optimization is usually encountered in many fields of scientific researches and engineering applications, which spawns a large number of...     

A dynamic global and local combined particle swarm optimization algorithm

Particle swarm optimization (PSO) algorithm has been developing rapidly and many results have been reported. PSO algorithm has shown some important advantages by providing high speed of convergence in specific problems, but it has a tendency to get stuck in a near optimal solution and one may find it difficult to improve solution accuracy by fine tuning. This paper presents a dynamic global and local combined particle swarm optimization (DGLCPSO) algorithm to improve the performance of original PSO, in which all particles dynamically share the best information of the local particle, global particle and group particles. It is tested with a set of eight benchmark functions with different dimensions and compared with original PSO. Experimental results indicate that the DGLCPSO algorithm improves the search performance on the benchmark functions significantly, and shows the effectiveness of the algorithm to solve optimization problems.     

Using genetic algorithm for dynamic and multiple criteria web-site optimizations

In today’s competitive electronic marketplace, companies try to create long-lasting relations with their online customers. Log files and registration forms generate millions of online transactions. Companies use new techniques to “mine” these data and establish optimal online storefronts to maximize their web presence. Several criteria, such as minimization of download time, maximization of web-site visualization and product association level, can be used for the optimization of virtual storefronts. This paper introduces a genetic algorithm, to be used in a model-driven decision-support system for web-site optimizations. The algorithm ensures multiple criteria web-site optimizations, and the genetic search provides dynamic and timely solutions independent of the number of objects to be arranged.     

Solving the dynamic capacitated location-routing problem with fuzzy demands by hybrid heuristic algorithm

In this paper, the dynamic capacitated location-routing problem with fuzzy demands (DCLRP-FD) is considered. In the DCLRP-FD, facility location problem and vehicle routing problem are solved on a time horizon. Decisions concerning facility locations are permitted to be made only in the first time period of the planning horizon but, the routing decisions may be changed in each time period. Furthermore, the vehicles and depots have a predefined capacity to serve the customers with altering demands during the time horizon. It is assumed that the demands of customers are fuzzy variables. To model the DCLRP-FD, a fuzzy chance-constrained programming is designed based upon the fuzzy credibility theory. To solve this problem, a hybrid heuristic algorithm (HHA) with four phases including the stochastic simulation and a local search method are proposed. To achieve the best value of two parameters of the model, the dispatcher preference index (DPI) and the assignment preference index (API), and to analyze their influences on the final solution, numerical experiments are carried out. Moreover, the efficiency of the HHA is demonstrated via comparing with the lower bound of solutions and by using a standard benchmark set of test problems. The numerical examples show that the proposed algorithm is robust and could be used in real world problems.     

A new algorithm for multi-dimensional dynamic programming problems

The new algorithm presented here solves medium size multi-dimensional dynamic programming problems in a relatively short computational time with no fast-memory restraints. The algorithm converges to the global optimal solution under some differentiability and convexity assumptions.The procedure is to solve a succession of dynamic programming problems, the state sets of which are limited to only a very small subset of the original state space. The interrelated definition of state sets for successive subproblems facilitates an algorithmic convergence while moving the subsets to contain the optimal states at the end.     

On the analysis of a dynamic evolutionary algorithm

Evolutionary algorithms are applied as problem-independent optimization algorithms. They are quite efficient in many situations. However, it is difficult to analyze even the behavior of simple variants of evolutionary algorithms like the (1+1) EA on rather simple functions. Nevertheless, only the analysis of the expected run time and the success probability within a given number of steps can guide the choice of the free parameters of the algorithms. Here static (1+1) EAs with a fixed mutation probability are compared with dynamic (1+1) EAs with a simple schedule for the variation of the mutation probability. The dynamic variant is first analyzed for functions typically chosen as example-functions for evolutionary algorithms. Afterwards, it is shown that it can be essential to choose the suitable variant of the (1+1) EA. More precisely, functions are presented where each static (1+1) EA has exponential expected run time while the dynamic variant has polynomial expected run time. For other functions it is shown that the dynamic (1+1) EA has exponential expected run time while a static (1+1) EA with a good choice of the mutation probability has polynomial run time with overwhelming probability.