Theoretical analysis of steady state genetic algorithms

Evolutionary Algorithms, also known as Genetic Algorithms in a former terminology, are probabilistic algorithms for optimization, which mimic operators from natural selection and genetics. The paper analyses the convergence of the heuristic associated to a special type of Genetic Algorithm, namely the Steady State Genetic Algorithm (SSGA), considered as a discrete-time dynamical system non-generational model. Inspired by the Markov chain results in finite Evolutionary Algorithms, conditions are given under which the SSGA heuristic converges to the population consisting of copies of the best chromosome.     

Local and global robustness at steady state

We study the robustness of the steady states of a class of systems of autonomous ordinary differential equations (ODEs), having as a central example those arising from (bio)chemical reaction networks. More precisely, we study under what conditions the steady states of the system are contained in a parallel translate of a coordinate hyperplane. To this end, we focus mainly on ODEs consisting of generalized polynomials and make use of algebraic and geometric tools to relate the local and global structure of the set of steady states. Specifically, we consider the local property termed zero sensitivity at a coordinate x_i, which means that the tangent space is contained in a hyperplane of the form x_i = c, and provide a criterion to identify it. We consider the global property termed absolute concentration robustness (ACR), meaning that all steady states are contained in a hyperplane of the form x_i = c. We clarify and formalize the relation between the two approaches. In particular, we show that ACR implies zero sensitivity and identify when the two properties do not agree, via an intermediate property we term local ACR. For families of systems arising from modeling biochemical reaction networks, we obtain the first practical and automated criterion to decide upon (local) ACR.     

A general steady state distribution based stopping criteria for finite length genetic algorithms

We propose two general stopping criteria for finite length, simple genetic algorithms based on steady state distributions, and empirically investigate the impact of mutation rate, string length, crossover rate and population size on their convergence. Our first stopping criterion is based on the second largest eigenvalue of the genetic algorithm transition matrix, and the second stopping criterion is based on minorization conditions.     

Stability of evolutionary algorithms

We prove under mild conditions the convergence of some evolutionary algorithm to the solution of the global optimization problem. In the proof, the Lyapunov function's techniques is applied to some semi-dynamical system generated by a Foias operator on the space of the probability measures defined on the set of admissible solutions.     

Busy period distributions in the steady state single-server queue and their applications

A method of generating probability distributions of the number of customers served in a busy period of a steady state single-server queueing system with univariate and multivariate inputs is described. A few moments in terms of the moments of the input distributions are derived. Some applications of the busy period distributions to such areas as branching processes, traffic flows, first passage problems, ballot theorems and waiting time distributions are briefly mentioned.     

Optimizing steady state Markov chains by state reduction

Many service systems have a parameter which can be changed continuously within a certain range. In queueing, for instance, one may be able to change the service rate by means of faster servers, or the arrival rate through advertising. The question to be addressed is how to choose the value of the parameter in order to maximize rewards. In this paper, service systems are formulated as Markov chains in equilibrium. The optimum is then found by Newton's method. This requires one to determine the first and second derivative of the rewards, and an effective method for doing this is proposed. The method is based on state reduction, which is a technique for finding equilibrium probabilities for finite and even for infinite state Markov chains. The optimization technique is then used to obtain a number of curves involving two simple service systems.     

Autonomous operator management for evolutionary algorithms

The performance of an evolutionary algorithm strongly depends on the design of its operators and on the management of these operators along the search; that is, on the ability of the algorithm to balance exploration and exploitation of the search space. Recent approaches automate the tuning and control of the parameters that govern this balance. We propose a new technique to dynamically control the behavior of operators in an EA and to manage a large set of potential operators. The best operators are rewarded by applying them more often. Tests of this technique on instances of 3-SAT return results that are competitive with an algorithm tailored to the problem.     

Mechanical dislocations and steady state processes

Zusammenfassung Es wird gezeigt, dass in einem elastischen, zylindrischen Körper der stationäre Wärmefluss (oder ein vergleichbarer physikalischer Prozess) eine hinreichendeund notwendige Bedingung dafür ist, dass sich die Spannungen aus einem Hilfsproblem mit fester Temperatur berechnen lassen. Es folgt daraus, dass sich in der Elastizität ebener Probleme nur stationäre Prozesse bei der Anwendung photoelastischer Methoden durch mechanische Dislokationen darstellen lassen.     

Robustness in multi-objective optimization using evolutionary algorithms

This work discusses robustness assessment during multi-objective optimization with a Multi-Objective Evolutionary Algorithm (MOEA) using a combination of two types of robustness measures. Expectation quantifies simultaneously fitness and robustness, while variance assesses the deviation of the original fitness in the neighborhood of the solution. Possible equations for each type are assessed via application to several benchmark problems and the selection of the most adequate is carried out. Diverse combinations of expectation and variance measures are then linked to a specific MOEA proposed by the authors, their selection being done on the basis of the results produced for various multi-objective benchmark problems. Finally, the combination preferred plus the same MOEA are used successfully to obtain the fittest and most robust Pareto optimal frontiers for a few more complex multi-criteria optimization problems.     

On the convergence of multiobjective evolutionary algorithms

We consider the usage of evolutionary algorithms for multiobjective programming (MOP), i.e. for decision problems with alternatives taken from a real-valued vector space and evaluated according to a vector-valued objective function. Selection mechanisms, possibilities of temporary fitness deterioration, and problems of unreachable alternatives for such multiobjective evolutionary algorithms (MOEAs) are studied. Theoretical properties of MOEAs such as stochastic convergence with probability 1 are analyzed.     

Using multi-objective evolutionary algorithms for single-objective optimization

In recent decades, several multi-objective evolutionary algorithms have been successfully applied to a wide variety of multi-objective optimization problems. Along the way, several new concepts, paradigms and methods have emerged. Additionally, some authors have claimed that the application of multi-objective approaches might be useful even in single-objective optimization. Thus, several guidelines for solving single-objective optimization problems using multi-objective methods have been proposed. This paper offers a survey of the main methods that allow the use of multi-objective schemes for single-objective optimization. In addition, several open topics and some possible paths of future work in this area are identified.     

Perturbation of a globally stable steady state

It is shown that within a parameterized family of semi-dynamical systems enjoying a mild uniform dissipative condition, the property that a locally asymptotically stable steady state is globally attracting is an open condition in the parameters.

     

On steady state Euler-Poisson models for semiconductors

This paper is concerned with an analysis of the Euler-Poisson model for unipolar semiconductor devices in the steady state isentropic case. In the two-dimensional case we prove the existence of smooth solutions under a smallness assumption on the prescribed outflow velocity (small boundary current) and, additionally, under a smallness assumption on the gradient of the velocity relaxation time. The latter assumption allows a control of the vorticity of the flow and the former guarantees subsonic flow. The main ingredient of the proof is a regularization of the equation for the vorticity.Also, in the irrotational two- and three-dimensional cases we show that the smallness assumption on the outflow velocity can be replaced by a smallness assumption on the (physical) parameter multiplying the drift-term in the velocity equation. Moreover, we show that solutions of the Euler-Poisson system converge to a solution of the drift-diffusion model as this parameter tends to zero.     

Pareto-optimality of oblique decision trees from evolutionary algorithms

This paper investigates the performance of evolutionary algorithms in the optimization aspects of oblique decision tree construction and describes their performance with respect to classification accuracy, tree size, and Pareto-optimality of their solution sets. The performance of the evolutionary algorithms is analyzed and compared to the performance of exhaustive (traditional) decision tree classifiers on several benchmark datasets. The results show that the classification accuracy and tree sizes generated by the evolutionary algorithms are comparable with the results generated by traditional methods in all the sample datasets and in the large datasets, the multiobjective evolutionary algorithms generate better Pareto-optimal sets than the sets generated by the exhaustive methods. The results also show that a classifier, whether exhaustive or evolutionary, that generates the most accurate trees does not necessarily generate the shortest trees or the best Pareto-optimal sets.     

Multiobjective evolutionary algorithms for complex portfolio optimization problems

This paper investigates the ability of Multiobjective Evolutionary Algorithms (MOEAs), namely the Non-dominated Sorting Genetic Algorithm II (NSGA-II), Pareto Envelope-based Selection Algorithm (PESA) and Strength Pareto Evolutionary Algorithm 2 (SPEA2), for solving complex portfolio optimization problems. The portfolio optimization problem is a typical bi-objective optimization problem with objectives the reward that should be maximized and the risk that should be minimized. While reward is commonly measured by the portfolio’s expected return, various risk measures have been proposed that try to better reflect a portfolio’s riskiness or to simplify the problem to be solved with exact optimization techniques efficiently. However, some risk measures generate additional complexities, since they are non-convex, non-differentiable functions. In addition, constraints imposed by the practitioners introduce further difficulties since they transform the search space into a non-convex region. The results show that MOEAs, in general, are efficient and reliable strategies for this kind of problems, and their performance is independent of the risk function used.     

Convergence to steady states of solutions of semilinear evolutionary integral equations

We study the convergence and decay rate to a steady state of bounded solutions of the nonlinear evolutionary integral equation and we apply our abstract results to the viscoelastic Euler-Bernoulli beam and to Kelvin-Voigt solids.Received: 25 March 2003, Accepted: 5 April 2004, Published online: 16 July 2004This work was partially supported by the DFG project Regularität und Asymptotik für elliptische und parabolische Probleme and by the grants GAR 201/01/D094, MSM 113200007.     

Multiple steady state solutions in a multi-junction structure

Using the conventional drift-diffusion model, multiple steady state solutions are constructed for a PNPN-junction structure using a combination of numerical and asymptotic techniques. We assume constant mobilities and a piecewise constant doping profile.     

A steady state potential flow model for semiconductors

Summary We present a three-dimensional steady state irrotational flow model for semiconductors which is based on the hydrodynamic equations. We prove existence and local uniqueness of smooth solutions under a smallness assumptions on the data. This assumption implies subsonic flow of electrons in the semiconductors device.     

Strong stabilizability and the steady state Riccati equation

We explore strong stabilizability (as opposed to exponential stabilizability) with the aid of the steady state Riccati equation. We show that the latter can have at most one strongly stable solution and obtain some sufficient conditions for existence. We also indicate an application to steady state Kalman filtering where the observation operator is compact so that we may not have exponential stability.Research supported in part under Grant No. 78-3550, AFOSR, USAF, Applied Math Division.