Study in Chemnitz. To know what is good.






  • Anmelden

Optimization

Stochastic optimization procedures try to provide solutions to optimization problems which have many local minima in their objective function. For these optimization problems the usual steepest descent algorithms fail as they get easily caught in local minima. For such problems stochastic optimization procedures and especially simulated annealing have been used with growing success -- not to determine the global minimum but to provide "good" solutions with values of the objective which are not too "far" apart from the desired global minimum. Simulated annealing is based on the idea of a controlled thermal relaxation dynamic in the state of the system, where the objective function to be minimized is the energy. Not surprisingly, it turns out that the concept of an energy landscape is particularly helpful in describing the thermal relaxation dynamics which leads to a solution of the underlying optimization problem. We investigate the controlled optimization dynamics on energy landscapes using tools from mathematics and from theoretical physics. Typical methods employed are the theory of Markov processes as well as simulation techniques.

Recent Publications

Accuracy of coarse grained Markovian dynamics
Hoffmann, Karl Heinz and Salamon, Peter
Physica A: Statistical Mechanics and its Applications 390: 3086--3094 (2011)

Markov chain models on a mesoscopic level are a widely used description for complex systems. They are based on the assumption that certain sets of microstates can be coarse grained as their internal dynamics is faster than the time scales considered in the modeling. Here we analyze quantitatively the errors made by using lumping techniques and present the first rigorous proof for bounds on such errors. Our bounds express the deviations from a full microscopic description for all subsequent time steps in terms of the deviations in the first time step.

Competitive trapping in complex state spaces
Fischer, Andreas and Hoffmann, Karl Heinz and Schön, J. Christian
Journal of Physics A: Mathematical and General 44(7): 1--15 (2011) ; doi:10.1088/1751-8113/44/7/075101

In complex state space dynamics at finite time scales, the trapping in certain regions of state space is of great importance, e.g. in the field of protein folding or in the application of stochastic global optimization algorithms. Here, we analyze the influence of the density of states on the features of the trapping process. In particular, we compare the trapping power of a valley with a power-law density of states to one with an exponentially growing density of states. The outcome of this competition crucially depends on the annealing speed and shows that the clear difference between these two paradigmatic densities of states observed at very slow (near-equilibrium) annealing is lost for fast non-equilibrium processes, and that the outcome of the relaxation can strongly depend on the time scale of the process and subtle features of the density of states.

Optimal control of the parametric oscillator
Andresen, Bjarne and Hoffmann, Karl Heinz and Nulton, James and Tsirlin, Anatoly and Salamon, Peter
European Journal of Physics 32(3): 827--843 (2011) ; ISSN 0143-0807

We present a solution to the minimum time control problem for a classical harmonic oscillator to reach a target energy $E_{ ext{T}}$ from a given initial state $(q_ ext{i}, p_ ext{i})$ by controlling its frequency $omega, omega_{ ext{min}} leq omega leq omega_{ ext{max}}$. A brief synopsis of optimal control theory is included and the solution for the harmonic oscillator problem is used to illustrate the theory.

Threshold-selecting strategy for best possible ground state detection with genetic algorithms
Lässig, Jörg and Hoffmann, Karl Heinz
Physical Review E 79(4): 046702-1--8 (2009)

$mathit{Genetic}$ $mathit{algorithms}$ are a standard heuristic to find states of low energy in complex state spaces as given by physical systems such as spin flasses but also in combinatorial optimization. The paper considers the problem of selecting individuals in the current population in Genetic Algorithms for crossover. Many schemes have been considered in literature as possible crossover selection strategies. We show for a large class of quality measures that the best possible probability distribution for selecting individuals in each generation of the algorithm execution is a rectangular distribution over the individuals sorted by their energy values. This means uniform probabilities have to be assigned to a group of the individuals with lowest energy in the population. The considered strategy is dubbed $mathit{threshold}$ $mathit{selection}$. The proof applies basic arguments of Markov chains and linear optimization and makes only a few assumptions on the underlying principles and hence applies to a large class of algorithms.

On the Structure of a Best Possible Crossover Selection Strategy in Genetic Algorithms
Lässig, Jörg and Hoffmann, Karl Heinz
Research and Development in Intelligent Systems XXVI : 263--276 , 2009 ; ISBN: 978-1-84882-982-4 (print) , 978-1-84882-983-1 (online)

The paper considers the problem of selecting individuals in the current population in genetic algorithms for crossover to find a solution with high fitnee for a given optimization problem. Many different schemes have been described in the literature as possible strategies for this task but so far comparisons have been predominantly empirical. It is shown that if one wishes to maximize any linear function of the final state probabilities, e.g. the fitness of the best individual in the final population of the algorithm, then a best probability distribution for selecting an individual in each generation is a rectangular distribution over the individuals sorted in descending sequence by their fitness values. This means uniform probabilities have to be assigned to a group of the best individuals of the population but probabilities equal to zero to individuals from the current population can be chosen independently for each iteration and each individual. This result is then generalized also to typical practically applied performance measures, such as maximizing the expected fitness value of the best individual seen in any generation.

Bounding the lumping error in Markov chain dynamics
Hoffmann, Karl Heinz and Salamon, Peter
Applied Mathematics Letters 22: 1471--1475 (2009)

Forming lumped states in a Markov chain is a very useful device leading to a coarser level of description. The Markov chain on these lumped states is often taken as an approximation for the time evolution of the unlumped chain. In the present work we derive a bound on the error in this approximation.

Threshold Selecting: Best Possible Probability Distribution for Crossover Selection in Genetic Algorithms
Lässig, J örg} and Hoffmann, Karl Heinz and Enachescu, Mihaela
Genetic and Evolutionary Computation Conference , 2008 ; ISBN: 978-1-60558-131-6

The paper considers the problem of selecting individuals in the current population in genetic algorithms for crossover to find a solution of high fitness of a given combinatorial optimization problem. Many different schemes have been considered in literature as possible crossover selection strategies, such as windowing, exponential reduction, linear transformation or normalization and binary tournament selection. It is shown that if one wishes to maximize any linear function of the final state probabilities, e.g. the fitness of the best individual of the final population of the algorithm, then the best probability distribution for selecting individuals in each generation is a rectangular distribution over the individuals sorted by their fitness values. This means uniform probabilities have to be assigned to a group of the best individuals of the population but probabilities equal to zero to individuals with fitness ranks higher than a fixed cutoff, which is equal to a certain rank in the sorted fitness vector. The considered strategy is called threshold selecting. The proof applies basic arguments of Markov chains and linear optimization and requires only a few assumptions on the underlying principles and hence applies to a large class of genetic algorithms.

Numerical methods for density of states calculations
Haber, R.
Master Thesis, Chemnitz University of Technology, 2008

The parQ method, up to now only capable of calculating the density of states in the canonical ensemble, is extended to the grand canonical ensemble and compared to the Wang-Landau algorithm, a local-update flat-histogram method. Both algorithms have been implemented so that the performance and the respective benefits with increasing simulation time can be determined and compared.

An interlacing theorem for reversible Markov chains
Grone, R. and Hoffmann, K. H. and Salamon, P.
Journal of Physics A: Mathematical and General 41: 1--7 (2008) ; ISSN: 1751-8113

Reversible Markov chains are an indispensable tool in the modeling of a vast class of physical, chemical, biological and statistical problems. Examples include the master equation descriptions of relaxing physical systems, stochastic optimization algorithms such as simulated annealing, chemical dynamics of protein folding and Markov chain Monte Carlo statistical estimation. Very often the large size of the state spaces requires the coarse graining or lumping of microstates into fewer mesoscopic states, and a question of utmost importance for the validity of the physical model is how the eigenvalues of the corresponding stochastic matrix change under this operation. In this paper we prove an interlacing theorem which gives explicit bounds on the eigenvalues of the lumped stochastic matrix.

The Investigation of The parQ-Method for Continuous Systems
Schulz, R.
Master Thesis, 2007

To analyze the thermodynamical quantities of canonical systems the parQ-method has been introduced [1]. After testing this method for spin glasses [1, 2], this paper verifies that the parQ-method is also applicable to obtain the density of states of continuous systems, for example fluids, with the periodic boundary condition. Specifically, the energy transitions of a random walk through state space are observed. Therefore, the necessary methods and system configurations are introduced and examined. Furthermore, several potential error sources are investigated. The resulting data is compared to [3] where the density of states of a Lennard-Jones fluid is computed using the Wang-Landau scheme [4].