Contributed Session Fri.2.MA 144

Friday, 13:15 - 14:45 h, Room: MA 144

Cluster 22: Stochastic optimization [...]

Stochastic algorithms


Chair: Nikolaus Hansen



Friday, 13:15 - 13:40 h, Room: MA 144, Talk 1

Song Luo
A nonadaptive probabilistic group testing algorithm for detecting consecutive positives of linear DNA library

Coauthors: Maiko Shigeno, Mingchao Zhang


Identifying and isolating clones containing a particular segment of a specific DNA sequence of interest play important roles in molecular biology. Group testing is one of useful techniques to reduce the number of nonadaptive tests and screening necessary for determining which clones contain the segment. A testing algorithm is proposed for a case where clones are placed in a linear order corresponding to their appearance in the linear DNA and where the DNA
library is constructed by consecutive clones. The proposed algorithm, which is based on a computationally feasible stochastic model of consecutive positive clones, efficiently identifies the consecutive positives of a linear DNA library.



Friday, 13:45 - 14:10 h, Room: MA 144, Talk 2

Nikolaus Hansen
Information-geometric optimization

Coauthors: Anne Auger, Yann Ollivier


Given an arbitrary search space with an arbitrary objective function and a parametrized family of probability distributions on this search space, we derive in a generic way a stochastic search method. The derivation is based on invariance principles, keeping the number of arbitrary decisions to a minimum. If the parametrization of the probability distribution is a smooth manifold, we derive a canonical ODE and the related IGO flow that conducts a natural gradient ascent on the manifold. The ascent is based on a time-dependent transformation of the original objective function. Via discretization, a corresponding search algorithm can be derived. Depending on the given family of probability distributions, several well-known algorithms are recovered.



Friday, 14:15 - 14:40 h, Room: MA 144, Talk 3

Madeleine Theile
How crossover helps in pseudo-boolean optimization

Coauthors: Timo K├Âtzing, Dirk Sudholt


Understanding the impact of crossover on performance is a
major problem in the theory of genetic algorithms (GAs).
In this talk I present new insights on working principles of crossover by analyzing the performance of crossover-based GAs on the simple functions OneMax and Jump.
First, the potential speedup by crossover is assessed when combined with a fitness-invariant bit shuffling operator that
simulates a lineage of independent evolution on a function
of unitation. Theoretical and empirical results show drastic
speedups for both functions.
Second, a simple GA without shuffling is considered and the interplay of mutation and crossover on Jump is investigated. If the crossover probability is small, subsequent mutations create sufficient diversity, even for very small populations. Contrarily, with high crossover probabilities crossover tends to lose diversity more quickly than mutation can create it. This has a drastic impact on the performance on Jump. The theoretical findings are complemented by Monte Carlo simulations on the population diversity.


  There are three major facts that should be watched out for in all payday loans in the United States. Cialis Professional online is capableto release you reliably from the erection problems, its improved formula gives the new properties to the drug.