Sonderforschungsbereich (SFB) 531

Permanent URI for this collection

http://hdl.handle.net/2003/256

The field of Computational Intelligence (CI) covers all sorts of techniques for subsymbolic (numerical) knowledge processing, such as the well known Fuzzy Logic (FL), Neural Networks (NN), and Evolutionary Algorithms (EA) as well as other approaches with lesser dissemination. Although CI techniques are widely in use, there still exists a large gap between theory and application. To close this gap the Collaborative Research Center (SFB) 531 has been founded at the University of Dortmund in 1997 as an interdisciplinary research institute. It is financially supported by the Deutsche Forschungsgemeinschaft (DFG). The scientific goals of the SFB are the investigation and improvement of the foundations, applications, as well as combinations of CI methods.

Browse

Now showing 1 - 20 of 249

Capabilities of EMOA to detect and preserve equivalent Pareto subsets
(2009-06-02T07:25:55Z) Naujoks, Boris; Preuss, Mike; Rudolph, Günter
Recent works in evolutionary multiobjective optimization suggest to shift the focus from solely evaluating optimization success in the objective space to also taking the decision space into account. They indicate that this may be a) necessary to express the users requirements of obtaining distinct solutions (distinct Pareto set parts or subsets) of similar quality (comparable locations on the Pareto front) in real-world applications, and b) a demanding task for the currently most commonly used algorithms.We investigate if standard EMOA are able to detect and preserve equivalent Pareto subsets and develop an own special purpose EMOA that meets these requirements reliably.
Fast distance computation between cylinders for the design of mold temperature control systems
(2008) Biermann, Dirk; Joliet, Raffael; Michelitsch, Thomas
Optimization algorithms for the design of mold temperature control systems based on deep-hole bores have to assure that the minimal distances between the bores meet given safety margins. If the bores are geometrically modeled as cylinders, this leads to the necessity of determining the minimal Euclidean distances between cylinders and testing them against the corresponding margins. In this paper a very fast and reliable algorithm for the distance computation between cylinders is introduced, which has been developed due to the run-time requirements of the problem at hand.
Analysis of a simple evolutionary algorithm for the multiobjective shortest path problem
(2008-12) Horoba, Christian
We present a natural fitness function f for the multiobjective shortest path problem, which is a fundamental multiobjective combinatorial optimization problem known to be NP-hard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomial-time randomized approximation scheme (FPRAS) for the problem under consideration, which exemplifies how EAs are able to find good approximate solutions for hard problems.
Additive approximations of pareto-optimal sets by evolutionary multi-objective algorithms
(2008-12) Horoba, Christian; Neumann, Frank
Often the Pareto front of a multi-objective optimization problem grows exponentially with the problem size. In this case, it is not possible to compute the whole Pareto front efficiently and one is interested in good approximations. We consider how evolutionary algorithms can achieve such approximations by using different diversity mechanisms. We discuss some well-known approaches such as the density estimator and the e-dominance approach and point out how and when such mechanisms provably help to obtain good additive approximations of the Pareto-optimal set.
SPOT Sequential Parameter Optimization Toolbox
(2008-12) Bartz-Beielstein, Thomas; Lasarczyk, Christian; Preuß, Mike
Intelligent group movement and selection in realtime strategy games
(2008-12) Beume, Nicola; Danielsiek, Holger; Hein, Tobias; Naujoks, Boris; Piatkowski, Nico; Preuss, Mike; Stüer, Raphael; Thom, Andreas; Wessing, Simon
Movement of groups in realtime strategy games is often a nuisance: Units travel and battle separately, resulting in huge losses and the AI looking dumb. This applies to computer as well as human commanded factions. We suggest to tackle that by using flocking improved by influence-map based pathfinding which leads to a much more natural and intelligent looking behavior. A similar problem occurs if the computer AI has to select groups to combat a specific target: Assignment of units to groups, especially for multiple enemy groups, is often suboptimal when units have very different attack skills. This can be cured by using offline prepared self-organizing feature maps that use all available information for looking up good matches. We demonstrate that these two approaches work well separately, but also that they go together very naturally, thereby leading to an improved and - via parametrization - very flexible group behavior. Opponent AI may be strenghtened that way as well as player-supportive AI. A thorough experimental analysis supports our claims.
Analysis of a memetic algorithm for global optimization in chemical process synthesis
(2008-12) Engell, Sebastian; Sand, Guido; Urselmann, Maren
Engineering optimization often deals with very large search spaces which are highly constrained by nonlinear equations that couple the continuous variables. In this contribution the development of a memetic algorithm (MA) for global optimization in the solution of a problem in the chemical process engineering domain is described. The combination of an evolutionary strategy and a local solver based on the general reduced gradient method enables the exploitation of a significant reduction in the search space and of the ability of local mathematical programming solvers to efficiently handle large continuous problems containing equality constraints. The global performance of the MA is improved by the exclusion of regions that are defined by approximations of the basins of attraction of the local optima. The MA is compared to the combination of a scatter search based multi-start heuristic using OQNLP and the local solver CONOPT.
On the size of weights in randomized search heuristics
(2008-08) Reichel, Joachim; Skutella, Martin
Runtime analyses of randomized search heuristics for combinatorial optimization problems often depend on the size of the largest weight. We consider replacing the given set of weights with smaller weights such that the behavior of the randomized search heuristic does not change. Upper bounds on the size of the new, equivalent weights allow us to obtain upper bounds on the expected runtime of such randomized search heuristics independent of the size of the actual weights. Furthermore we give lower bounds on the largest weights for worst-case instances. Finally we present some experimental results, including examples for worst-case instances.
PG511 - CI in Games
(2008-08) Danielsiek, Holger; Eichhorn, Christian; Hein, Tobias; Kurtić, Edina; Neugebauer, Georg; Piatkowski, Nico; Quadflieg, Jan; Schnelker, Sebastian; Stüer, Raphael; Thom, Andreas; Wessing, Simon
Runtime analyses for using fairness in evolutionary multi-objective optimization
(2008-07) Friedrich, Tobias; Horoba, Christian; Neumann, Frank
It is widely assumed that evolutionary algorithms for multi-objective optimization problems should use certain mechanisms to achieve a good spread over the Pareto front. In this paper, we examine such mechanisms from a theoretical point of view and analyze simple algorithms incorporating the concept of fairness introduced in [Laumanns, Thiele, Zitzler, IEEE TEC 2004]. This mechanism tries to balance the number of off-spring of all individuals in the current population. We rigorously analyze the runtime behavior of different fairness mechanisms and present showcase examples to point out situations, where the right mechanism can speed up the optimization process significantly. We also indicate drawbacks for the use of fairness by presenting instances, where the optimization process is slowed down drastically.
A mix of Markov-chain and drift analysis
(2008-06) Jägersküpper, Jens
Approximating minimum multicuts by evolutionary multi-objective algorithms
(2008-06) Neumann, Frank; Reichel, Joachim
It has been shown that simple evolutionary algorithms are able to solve the minimum cut problem in expected polynomial time when using a multi-objective model of the problem. In this paper, we generalize these ideas to the NP-hard minimum multicut problem. Given a set of k terminal pairs, we prove that evolutionary algorithms in combination with a multi-objective model of the problem are able to obtain a k-approximation for this problem in expected polynomial time.
Benefits and drawbacks for the use of e-dominance in evolutionary multi-objective optimization
(2008-05) Horoba, Christian; Neumann, Frank
Using diversity mechanisms in evolutionary algorithms for multi-objective optimization problems is considered as an important issue for the design of successful algorithms. This is in particular the case for problems where the number of non-dominated feasible objective vectors is exponential with respect to the problem size. In this case the goal is to compute a good approximation of the Pareto front. We investigate how this goal can be achieved by using the diversity mechanism of e-dominance and point out where this concept is provably helpful to obtain a good approximation of an exponentially large Pareto front in expected polynomial time. Afterwards, we consider the drawbacks of this approach and point out situations where the use of e-dominance slows down the optimization process significantly.
Simplified drift analysis for proving lower bounds in evolutionary computation
(2008-04) Oliveto, Pietro S.; Witt, Carsten
Drift analysis is a powerful tool used to bound the optimization time of evolutionary algorithms (EAs). Various previous works apply a drift theorem going back to Hajek in order to show exponential lower bounds on read and to apply since it requires two bounds on the moment-generating (exponential) function of the drift. A recent work identifies a specialization of this drift theorem that is much easier to apply. Nevertheless, it is not as simple and not as general as possible. The present paper picks up Hajek s line of thought to prove a drift theorem that is very easy to use in evolutionary computation. Only two conditions have to be verified, one of which holds for virtually all EAs with standard mutation. The other condition is a bound on what is really relevant, the drift. Applications show how previous analyses involving the complicated theorem can be redone in a much simpler and clearer way. Therefore, the simplified theorem is also a didactical contribution to the runtime analysis of EAs.
A hybrid Markov chain modeling architecture for workload on parallel computers
(2008-04) Krampe, Anne; Lepping, Joachim; Sieben, Wiebke
This paper proposes a comprehensive modeling architecture for workloads on parallel computers using Markov chains in combination with state dependent empirical distribution functions. This hybrid approach is based on the requirements of scheduling algorithms: the model considers the four essential job attributes submission time, number of required processors, estimated processing time, and actual processing time. To assess the goodness-of-fit of a workload model the similarity of sequences of real jobs and jobs generated from the model needs to be captured. We propose to reduce the complexity of this task and to evaluate the model by comparing the results of a widely-used scheduling algorithm instead. This approach is demonstrated with commonly used scheduling objectives like the Average Weighted Response Time and total Utilization. We compare their outcomes on the simulated workload traces from our model with those of an original workload trace from a real Massively Parallel Processing system installation. To verify this new evaluation technique, standard criteria for assessing the goodness-of-fit for workload models are additionally applied.
An empirical investigation of simplified step-size adapatation in evolution strategies with a view to theory
(2008-04) Jägersküpper, Jens; Preuss, Mike
Randomized direct-search methods for the optimization of a function f: R^n -> R given by a black box for f-evaluations are investigated. We consider the cumulative step-size adaptation (CSA) for the variance of multivariate zero-mean normal distributions. Those are commonly used to sample new candidate solutions within metaheuristics, in particular within the CMA Evolution Strategy (CMA-ES), a state-of-the-art direct-search method. Though the CMA-ES is very successful in practical optimization, its theoretical foundations are very limited because of the complex stochastic process it induces. To forward the theory on this successful method, we propose two simplifications of the CSA used within CMA-ES for step-size control. We show by experimental and statistical evaluation that they perform sufficiently similarly to the original CSA (in the considered scenario), so that a further theoretical analysis is in fact reasonable. Furthermore, we outline in detail a probabilistic/theoretical runtime analysis for one of the two CSA-derivatives.
Self-stablizing cuts in synchronous networks
(2008-04) Sauerwald, Thomas; Sudholt, Dirk
Consider a synchronized distributed system where each node can only observe the state of its neighbors. Such a system is called self-stabilizing if it reaches a stable global state in a finite number of rounds. Allowing two different states for each node induces a cut in the network graph. In each round, every node decides whether it is (locally) satisfied with the current cut. Afterwards all unsatisfied nodes change sides independently with a fixed probability p. Using different notions of satisfaction enables the computation of maximal and minimal cuts, respectively. We analyze the expected time until such cuts are reached on several graph classes and consider the impact of the parameter p and the initial cut.
Rigorous analyses for the combination of ant colony optimization and local search
(2008-03) Neumann, Frank; Sudholt, Dirk; Witt, Carsten
Ant colony optimization (ACO) is a metaheuristic that produces good results for a wide range of combinatorial optimization problems. Often such successful applications use a combination of ACO and local search procedures that improve the solutions constructed by the ants. In this paper, we study this combination from a theoretical point of view and point out situations where introducing local search into an ACO algorithm enhances the optimization process significantly. On the other hand, we illustrate the drawback that such a combination might have by showing that this may prevent an ACO algorithm from obtaining optimal solutions.
Computing minimum cuts by randomized search heuristics
(2008-02) Neumann, Frank; Reichel, Joachim; Skutella, Martin
We study the minimum s-t-cut problem in graphs with costs on the edges in the context of evolutionary algorithms. Minimum cut problems belong to the class of basic network optimization problems that occur as crucial subproblems in many real-world optimization problems and have a variety of applications in several different areas. We prove that there exist instances of the minimum s-t-cut problem that cannot be solved by standard single-objective evolutionary algorithms in reasonable time. On the other hand, we develop a bicriteria approach based on the famous MaxFlow-MinCut Theorem that enables evolutionary algorithms to find an optimum solution in expected polynomial time.
Runtime analysis of binary PSO
(2008-02) Sudholt, Dirk; Witt, Carsten
We investigate the runtime of the Binary Particle Swarm Optimization (PSO) algorithm introduced by Kennedy and Eberhart (1997). The Binary PSO maintains a global best solution and a swarm of particles. Each particle consists of a current position, an own best position and a velocity vector used in a probabilistic process to update the particle s position. We present lower bounds for a broad class of implementations with swarms of polynomial size. To prove upper bounds, we transfer a fitness-level argument well-established for evolutionary algorithms (EAs) to PSO. This method is then applied to estimate the expected runtime on the class of unimodal functions. A simple variant of the Binary PSO is considered in more detail. The 1-PSO only maintains one particle, hence own best and global best solutions coincide. Despite its simplicity, the 1-PSO is surprisingly efficient. A detailed analysis for the function OneMax shows that the 1-PSO is competitive to EAs.

Browse

Recent Submissions