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) ; DOI: 10.1016/j.physa.2011.04.027

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, B. and Hoffmann, K. H. and Nulton, J. and Tsirlin, A. and Salamon, P.
European Journal of Physics 32(3): 827--843 (2011) ; ISSN 0143-0807, DOI: 10.1088/0143-0807/32/3/018

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.

Computational manufacturing of optical interference coatings: method, simulation results, and comparison with experiment
Friedrich, K. and Wilbrandt, S. and Stenzel, O. and Kaiser, N. and Hoffmann, K. H.
Applied Optics 49(16): 3150--3162 (2010)

Virtual depostion runs have been performed to estimate the procuction yield of selected oxide optical interference coatings when plasma ion-assisted deposition with an advanced plasma source is applied. Therby, depostion of each layer can be terminated either by broadband optical monitoring or quertz crystal monitoring. Numerous deposition runs of single-layer coatings have been performed to investigate the reproducibility of coating properties and to quantifydeposition errors for the simulation. Variations of the following parameters are considered in the simulation: refractive index, extinction coefficient, and film thickness. The refractive index and the extinction coefficient are simulated in terms of the oscillator model. The parameters are varied using an apodized normal distribution with known mean value and standard strategy. Several depositon runs of the selected oxide interference coatings have been performed to verify the simulation results by experimental data.

Funktionsorientierte Toleranzanalyse in der Motorenentwicklung
Schwalbe, Karsten
Bachelorarbeit an der TU Chemnitz, 2009

Threshold-selecting strategy for best possible ground state detection with genetic algorithms
Lässig, J and Hoffmann, K. H.
Physical Review E 79: 046702-1--046702-8 (2009) ; DOI: 10.1103/PhysRevE.79.046702

$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. and Hoffmann, K. H.
Research and Development in Intelligent Systems XXVI : 263--276 , 2009 ; ISBN: 978-1-84882-982-4 (print) , 978-1-84882-983-1 (online), DOI: 10.1007/978-1-84882-983-1_19

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, K. H. and Salamon, P.
Applied Mathematics Letters 22: 1471--1475 (2009) ; ISSN: 0893-9659, DOI: 10.1016/j.aml.2009.03.016

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.

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: 212002 (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.