Eldorado Collection: Design und Management komplexer technischer Prozesse und Systeme mit Methoden der Computational Intelligence
http://hdl.handle.net/2003/256
Design und Management komplexer technischer Prozesse und Systeme mit Methoden der Computational Intelligence2024-03-29T11:57:29ZCapabilities of EMOA to detect and preserve equivalent Pareto subsets
http://hdl.handle.net/2003/26182
Title: Capabilities of EMOA to detect and preserve equivalent Pareto subsets
Authors: Naujoks, Boris; Preuss, Mike; Rudolph, Günter
Abstract: 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.2009-06-02T07:25:55ZFast distance computation between cylinders for the design of mold temperature control systems
http://hdl.handle.net/2003/26166
Title: Fast distance computation between cylinders for the design of mold temperature control systems
Authors: Biermann, Dirk; Joliet, Raffael; Michelitsch, Thomas
Abstract: 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.2008-01-01T00:00:00ZAnalysis of a simple evolutionary algorithm for the multiobjective shortest path problem
http://hdl.handle.net/2003/26165
Title: Analysis of a simple evolutionary algorithm for the multiobjective shortest path problem
Authors: Horoba, Christian
Abstract: 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.2008-12-01T00:00:00ZAdditive approximations of pareto-optimal sets by evolutionary multi-objective algorithms
http://hdl.handle.net/2003/26164
Title: Additive approximations of pareto-optimal sets by evolutionary multi-objective algorithms
Authors: Horoba, Christian; Neumann, Frank
Abstract: 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.2008-12-01T00:00:00ZSPOT Sequential Parameter Optimization Toolbox
http://hdl.handle.net/2003/26163
Title: SPOT Sequential Parameter Optimization Toolbox
Authors: Bartz-Beielstein, Thomas; Lasarczyk, Christian; Preuß, Mike2008-12-01T00:00:00ZIntelligent group movement and selection in realtime strategy games
http://hdl.handle.net/2003/26162
Title: Intelligent group movement and selection in realtime strategy games
Authors: Beume, Nicola; Danielsiek, Holger; Hein, Tobias; Naujoks, Boris; Piatkowski, Nico; Preuss, Mike; Stüer, Raphael; Thom, Andreas; Wessing, Simon
Abstract: 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.2008-12-01T00:00:00ZAnalysis of a memetic algorithm for global optimization in chemical process synthesis
http://hdl.handle.net/2003/26161
Title: Analysis of a memetic algorithm for global optimization in chemical process synthesis
Authors: Engell, Sebastian; Sand, Guido; Urselmann, Maren
Abstract: 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.2008-12-01T00:00:00ZOn the size of weights in randomized search heuristics
http://hdl.handle.net/2003/26160
Title: On the size of weights in randomized search heuristics
Authors: Reichel, Joachim; Skutella, Martin
Abstract: 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.2008-08-01T00:00:00ZPG511 - CI in Games
http://hdl.handle.net/2003/26159
Title: PG511 - CI in Games
Authors: Danielsiek, Holger; Eichhorn, Christian; Hein, Tobias; Kurtić, Edina; Neugebauer, Georg; Piatkowski, Nico; Quadflieg, Jan; Schnelker, Sebastian; Stüer, Raphael; Thom, Andreas; Wessing, Simon2008-08-01T00:00:00ZRuntime analyses for using fairness in evolutionary multi-objective optimization
http://hdl.handle.net/2003/26158
Title: Runtime analyses for using fairness in evolutionary multi-objective optimization
Authors: Friedrich, Tobias; Horoba, Christian; Neumann, Frank
Abstract: 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.2008-07-01T00:00:00ZA mix of Markov-chain and drift analysis
http://hdl.handle.net/2003/26157
Title: A mix of Markov-chain and drift analysis
Authors: Jägersküpper, Jens2008-06-01T00:00:00ZApproximating minimum multicuts by evolutionary multi-objective algorithms
http://hdl.handle.net/2003/26156
Title: Approximating minimum multicuts by evolutionary multi-objective algorithms
Authors: Neumann, Frank; Reichel, Joachim
Abstract: 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.2008-06-01T00:00:00ZBenefits and drawbacks for the use of e-dominance in evolutionary multi-objective optimization
http://hdl.handle.net/2003/26155
Title: Benefits and drawbacks for the use of e-dominance in evolutionary multi-objective optimization
Authors: Horoba, Christian; Neumann, Frank
Abstract: 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.2008-05-01T00:00:00ZSimplified drift analysis for proving lower bounds in evolutionary computation
http://hdl.handle.net/2003/26154
Title: Simplified drift analysis for proving lower bounds in evolutionary computation
Authors: Oliveto, Pietro S.; Witt, Carsten
Abstract: 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.2008-04-01T00:00:00ZA hybrid Markov chain modeling architecture for workload on parallel computers
http://hdl.handle.net/2003/26153
Title: A hybrid Markov chain modeling architecture for workload on parallel computers
Authors: Krampe, Anne; Lepping, Joachim; Sieben, Wiebke
Abstract: 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.2008-04-01T00:00:00ZAn empirical investigation of simplified step-size adapatation in evolution strategies with a view to theory
http://hdl.handle.net/2003/26152
Title: An empirical investigation of simplified step-size adapatation in evolution strategies with a view to theory
Authors: Jägersküpper, Jens; Preuss, Mike
Abstract: 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.2008-04-01T00:00:00ZSelf-stablizing cuts in synchronous networks
http://hdl.handle.net/2003/26151
Title: Self-stablizing cuts in synchronous networks
Authors: Sauerwald, Thomas; Sudholt, Dirk
Abstract: 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.2008-04-01T00:00:00ZRigorous analyses for the combination of ant colony optimization and local search
http://hdl.handle.net/2003/26150
Title: Rigorous analyses for the combination of ant colony optimization and local search
Authors: Neumann, Frank; Sudholt, Dirk; Witt, Carsten
Abstract: 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.2008-03-01T00:00:00ZComputing minimum cuts by randomized search heuristics
http://hdl.handle.net/2003/26149
Title: Computing minimum cuts by randomized search heuristics
Authors: Neumann, Frank; Reichel, Joachim; Skutella, Martin
Abstract: 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.2008-02-01T00:00:00ZRuntime analysis of binary PSO
http://hdl.handle.net/2003/26148
Title: Runtime analysis of binary PSO
Authors: Sudholt, Dirk; Witt, Carsten
Abstract: 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.2008-02-01T00:00:00ZTight bounds for blind search on the integers
http://hdl.handle.net/2003/26147
Title: Tight bounds for blind search on the integers
Authors: Dietzfelbinger, Martin; Rowe, Jonathan E.; Wegener, Ingo; Woelfel, Philipp
Abstract: We analyze a simple random process in which a token is moved in the interval A = [0,n]: Fix a probability distribution µ over [1,n]. Initially, the token is placed in a random position in A. In round t, a random value d is chosen according to µ. If the token is in position a >= d, then it is moved to position a-d. Otherwise it stays put. Let T be the number of rounds until the token reaches position 0. We show tight bounds for the expectation of T for the optimal distribution µ, i.e., we show that min_µ{E_µ(T)} = Theta((log n)^2). For the proof, a novel potential function argument is introduced. The research is motivated by the problem of approximating the minimum of a continuous function over [0,1] with a "blind" optimization strategy.2008-01-01T00:00:00ZCoevolution for classification
http://hdl.handle.net/2003/26146
Title: Coevolution for classification
Authors: Dumitrescu, D.; Preuss, Mike; Stoean, Catalin; Stoean, Ruxandra
Abstract: A data mining field with daily, and sometimes even vital, practical applications, classification has been addressed by many powerful paradigms, among which evolutionary algorithms (EAs) play a successful role. Nevertheless, as evolutionary computation (EC) progresses, there appear new possibilities of developing simpler and yet robust classification techniques. The aim of this paper is hence to put forward a novel evolutionary classification framework which embodies two contradictory prototypes coming from the state-of-the-art field of coevolution and which has proven to be a viable alternative. Coevolution between individuals assumes two opposite interactions: cooperative and competitive. Analogously, coevolution for classification assumes two possible and opposed manners of solving the task. Within both approaches, the solution of a classification problem is regarded as a set of IFTHEN conjunctive rules in first order logic. As a consequence, learning will be driven either by the cooperation between rules towards a complete and accurate rule set or by the competition between rules and training samples in the direction of extensive and hard testing on each side. The paper is organized as follows. The next section introduces a general point of view upon classification. Section three brings an overview on coevolution: The cooperative and competitive archetypes are outlined and explained. Section four describes the proposed manner of approaching classification from the cooperative side, while section five presents the application of the competitive counterpart. Experiments on three data sets, two benchmark and one real-world, are depicted in section six and the paper closes with the concluding remarks.2008-01-01T00:00:00ZMemetic algorithms with variable-depth search to overcome local optima
http://hdl.handle.net/2003/26145
Title: Memetic algorithms with variable-depth search to overcome local optima
Authors: Sudholt, Dirk
Abstract: Variable-depth search (VDS) is well-known as Lin-Kernighan strategy for the TSP and Kernighan-Lin for graph partitioning. The basic idea is to make a sequence of local moves and to freeze all moved combinatorial objects to prevent the search from looping. VDS stops when no further local move is possible and returns a best found solution. We analyze memetic algorithms with VDS for three binary combinatorial problems: Mincut, Knapsack, and Maxsat. More precisely, we focus on simply structured problem instances containing local optima that are very hard to overcome. Many common trajectory-based algorithms fail to find a global optimum: the (1+1) EA, iterated local search, and simulated annealing need exponential time with high probability. However, memetic algorithms using VDS easily manage to find a global optimum in expected polynomial time. These results strengthen the usefulness of memetic algorithms with VDS from a theoretical perspective.2008-01-01T00:00:00ZTheoretical analysis of diversity mechanisms for global exploration
http://hdl.handle.net/2003/26144
Title: Theoretical analysis of diversity mechanisms for global exploration
Authors: Friedrich, Tobias; Oliveto, Pietro S.; Sudholt, Dirk; Witt, Carsten
Abstract: Maintaining diversity is important for the performance of evolutionary algorithms. Diversity mechanisms can enhance global exploration of the search space and enable crossover to find dissimilar individuals for recombination. We focus on the global exploration capabilities of mutation-based algorithms. Using a simple bimodal test function and rigorous runtime analyses, we compare well-known diversity mechanisms like deterministic crowding, fitness sharing, and others with a plain algorithm without diversification. We show that diversification is necessary for global exploration, but not all mechanisms succeed in finding both optima efficiently.2008-01-01T00:00:00ZPG511 - CI in Games
http://hdl.handle.net/2003/26143
Title: PG511 - CI in Games
Authors: Danielsiek, Holger; Eichhorn, Christian; Hein, Tobias; Kurtić, Edina; Neugebauer, Georg; Piatkowski, Nico; Puchowezki,Michael; Quadflieg, Jan; Schnelker, Sebastian; Stüer, Raphael; Thom, Andreas; Wessing, Simon2007-12-01T00:00:00ZOn the complexity of computing the hypervolume indicator
http://hdl.handle.net/2003/26142
Title: On the complexity of computing the hypervolume indicator
Authors: Beume, Nicola; Fonseca, Carlos M.; López-Ibáñez, Manuel; Paquete, Luís; Vahrenhold, Jan
Abstract: The goal of multi-objective optimization is to find a set of best compromise solutions for typically conflicting objectives. Due to the complex nature of most real-life problems, only an approximation to such an optimal set can be obtained within reasonable (computing) time. To compare such approximations, and thereby the performance of multi-objective optimizers providing them, unary quality measures are usually applied. Among these, the hypervolume indicator (or S-metric) is of particular relevance due to its good properties. Moreover, this indicator has been successfully integrated into stochastic optimizers, such as evolutionary algorithms, where it serves as a guidance criterion for searching the parameter space. Recent results show that computing the hypervolume indicator can be seen as solving a specialized version of Klee s Measure Problem. In general, Klee s Measure Problem can be solved in O(n^d/2 log n) for an input instance of size n in d dimensions; as of this writing, it is unknown whether a lower bound higher than Omega(n log n) can be proven. In this article, we derive a lower bound of Omega(n log n) for the complexity of computing the hypervolume indicator in any number of dimensions d > 1 by reducing the problem to the so-called UNIFORMGAP problem. For the three dimensional case, we also present a matching upper bound of O(n log n) that is obtained by extending an algorithm for finding the maxima of a point set.2007-12-01T00:00:00ZDesign and analysis of an asymmetric mutation operator
http://hdl.handle.net/2003/26141
Title: Design and analysis of an asymmetric mutation operator
Authors: Jansen, Thomas; Sudholt, Dirk
Abstract: Evolutionary algorithms are general randomized search heuristics and typically perform an unbiased random search that is guided only by the fitness of the search points encountered. However, in practical applications there is often problem-specific knowledge that suggests some additional bias. The use of appropriately biased variation operators may speed-up the search considerably. Problems defined over bit strings of finite length often have the property that good solutions have only very few 1-bits or very few 0-bits. A specific mutation operator tailored towards such situations is studied under different perspectives and in a rigorous way discussing its assets and drawbacks. This is done by considering illustrative example functions as well as function classes. The main focus is on theoretical run time analysis yielding asymptotic results. These findings are accompanied by the results of empirical investigations that deliver additional insights.2007-11-01T00:00:00ZGeneral lower bounds for randomized direct search with isotropic sampling
http://hdl.handle.net/2003/26140
Title: General lower bounds for randomized direct search with isotropic sampling
Authors: Jägersküpper, Jens
Abstract: The focus is on a certain class of randomized direct-search methods for optimization in (high-dimensional) Euclidean space, namely for minimization of a function f: R^n -> R, where f is given by an oracle, i. e. a black box for f-evaluations. The iterative methods under consideration generate a sequence of candidate solutions, where potential candidate solutions are generated by adding an isotropically distributed vector to the current candidate solution (possibly several times, to then choose one of these samples to become the next in the sequence of candidate solutions). This class of randomized direct-search methods covers in particular several evolutionary algorithms. Lower bounds on the number of samples (i. e. queries to the f-oracle) are proved which are necessary to enable such a method to reduce the approximation error in the search space. The lower bounds to be presented do not only hold in expectation, but they are such that runtimes below these bounds are observed only with an exponentially small probability (in the search space dimension n). To derive such strong bounds, an appealingly simple, but nevertheless powerful method is applied: We think of the guided/directed random search as a selected fragment of a purely/obliviously random search. Interestingly, the lower bounds so obtained turn out to be tight (up to an absolute constant).2007-07-01T00:00:00ZGradient-based/evolutionary relay hybrid for computing Pareto front approximations maximizing the S-metric
http://hdl.handle.net/2003/26139
Title: Gradient-based/evolutionary relay hybrid for computing Pareto front approximations maximizing the S-metric
Authors: Beume, Nicola; Deutz, André; Emmerich, Michael
Abstract: The computation of a good approximation set of the Pareto front of a multiobjective optimization problem can be recasted as the maximization of its S-metric value. A high-precision method for computing approximation sets of a Pareto front with maximal S-Metric is presented in this paper as a high-level relay hybrid of an evolutionary algorithm and a gradient method, both guided by the S-metric. First, an evolutionary multiobjective optimizer moves the initial population close to the Pareto front. The gradient-based method takes this population as its starting point for computing a local maximal approximation set with respect to the S-metric. As opposed to existing work on gradient-based multicriteria optimization in the new gradient approach we compute gradients based on a set of points rather than for single points. We will term this approach indicatorbased gradient method, and exemplify it for the S-metric. We derive expressions for computing the gradient of a set of points with respect to its S-metric based on gradients of the objective functions. To deal with the problem of vanishing gradient components in case of dominated points in an approximation set, a penalty approach is introduced. We present a gradient based method for the aforementioned hybridization scheme and report on first results on artificial test problems.2007-06-01T00:00:00ZOn improving approximate solutions by evolutionary algorithms
http://hdl.handle.net/2003/26138
Title: On improving approximate solutions by evolutionary algorithms
Authors: Friedrich, Tobias; Hebbinghaus, Nils; He, Jun; Neumann, Frank; Witt, Carsten
Abstract: Hybrid methods are very popular for solving problems from combinatorial optimization. In contrast to this the theoretical understanding of the interplay of different optimization methods is rare. The aim of this paper is to make a first step into the rigorous analysis of such combinations for combinatorial optimization problems. The subject of our analyses is the vertex cover problem for which several approximation algorithms have been proposed. We point out specific instances where solutions can (or cannot) be improved by the search process of a simple evolutionary algorithm in expected polynomial time.2007-06-01T00:00:00ZComparing variants of MMAS ACO algorithms on pseudo-boolean functions
http://hdl.handle.net/2003/26137
Title: Comparing variants of MMAS ACO algorithms on pseudo-boolean functions
Authors: Neumann, Frank; Sudholt, Dirk; Witt, Carsten
Abstract: Recently, the first rigorous runtime analyses of ACO algorithms have been presented. These results concentrate on variants of the MAX-MIN ant system by St¨utzle and Hoos and consider their runtime on simple pseudo-Boolean functions such as OneMax and LeadingOnes. Interestingly, it turns out that a variant called 1-ANT is very sensitive to the choice of the evaporation factor while a recent technical report by Gutjahr and Sebastiani suggests partly opposite results for their variant called MMAS. In this paper, we elaborate on the differences between the two ACO algorithms, generalize the techniques by Gutjahr and Sebastiani and show improved results.2007-05-01T00:00:00ZLower bounds for hit-and-run optimization
http://hdl.handle.net/2003/26136
Title: Lower bounds for hit-and-run optimization
Authors: Jägersküpper, Jens2007-04-01T00:00:00ZA framework of quantum-inspired multi-objective evolutionary algorithms and its convergence properties
http://hdl.handle.net/2003/26135
Title: A framework of quantum-inspired multi-objective evolutionary algorithms and its convergence properties
Authors: Li, Zhiyong; Rudolph, Günter
Abstract: In this paper, a general framework of quantum-inspired multiobjective evolutionary algorithms is proposed based on the basic principles of quantum computing and general schemes of multi-objective evolutionary algorithms. One of the sufficient convergence conditions to Pareto optimal set is presented and it is proved under partially order set theory. Moreover, two algorithms are given as examples meeting this convergence condition, in which two improved Q-gates are used. Their convergence properties are discussed. Additionally, one counterexample is also given.2007-04-01T00:00:00ZTime-optimal large view visual servoing with dynamic sets of SIFT
http://hdl.handle.net/2003/26134
Title: Time-optimal large view visual servoing with dynamic sets of SIFT
Authors: Hoffmann, Frank; Kahn, Umar; Krettek, Johannes; Nierobisch, Thomas
Abstract: This paper presents a novel approach to large view visual servoing in the context of object manipulation. In many scenarios the features extracted in the reference pose are only perceivable across a limited region of the work space. The limited visibility of features necessitates the introduction of additional intermediate reference views of the object and requires path planning in view space. In our scheme visual control is based on decoupled moments of SIFT-features, which are generic in the sense that the control operates with a dynamic set of feature correspondences rather than a static set of geometric features. The additional flexibility of dynamic feature sets enables flexible path planning in the image space and online selection of optimal reference views during servoing to the goal view. The time to convergence to the goal view is estimated by a neural network based on the residual feature error and the quality of the SIFT feature distribution. The transition among reference views occurs on the basis of this estimated cost which is evaluated online based on the current set of visible features. The dynamic switching scheme achieves robust and nearly time-optimal convergence of the visual control across the entire task space. The effectiveness and robustness of the scheme is confirmed in an experimental evaluation in a virtual reality simulation and on a real robot arm with a eye-in-hand configuration.2007-02-01T00:00:00ZWeighted moments of SIFT-features for decoupled visual servoing in 6DOF
http://hdl.handle.net/2003/26133
Title: Weighted moments of SIFT-features for decoupled visual servoing in 6DOF
Authors: Hoffmann, Frank; Kahn, Umar; Krettek, Johannes; Nierobisch, Thomas
Abstract: Mobile manipulation in service robotic applications requires the alignment of the end-effector with recognized objects of unknown pose. Image based visual servoing provides a means of model-free manipulation of objects solely relying on 2D image information. This contribution proposes a visual servoing scheme that utilizes the pixel coordinates, scale and orientation of the Scale Invariant Feature Transform (SIFT). The control is based on dynamic weighted moments aggregated from a mutable set of redundant SIFT feature correspondences between the current and the reference view. The key idea of our approach is to weight the point features in a way that eliminates or at least minimizes the undesired couplings to establish a one-to-one correspondence between feature and camera motion. The scheme achieves a complete decoupling in 4DOF, additionally the visual features in 6DOF are largely decoupled except for some minor residual coupling between the horizontal translation and the two rotational degrees of freedom. The decoupling results in a visual control in which the convergence in image and task space along a particular degree of motion is not effected by the remaining feature errors. Several simulations in virtual reality and experiments on a robotic arm equipped with a monocular eye-in-hand camera demonstrate that the approach is robust, efficient and reliable for 4DOF as well as 6DOF positioning.2007-02-01T00:00:00ZEvolutionary algorithms and matroid optimization problems
http://hdl.handle.net/2003/26132
Title: Evolutionary algorithms and matroid optimization problems
Authors: Reichel, Joachim; Skutella, Martin
Abstract: We analyze teh performance fo evolutionary algorithms on various matroid optimization problems that encompass a vast number of efficiently solvable as well as NP-hard combinatorial optimization problems (including many well-known examples such as minimum spanning tree and maximum bipartite matching). We obtain very promising bounds on the expected running time and quality of the computed solution. Our results establish a better theoretical understanding of why randomized search heuristics yield empirically good results for many real-world problems.2007-02-01T00:00:00ZApproximating covering problems by randomized search heuristics using multi-objective models
http://hdl.handle.net/2003/26131
Title: Approximating covering problems by randomized search heuristics using multi-objective models
Authors: Friedrich, Tobias; Hebbinghaus, Nils; He, Jun; Neumann, Frank; Witt, Carsten
Abstract: The main aim of randomized search heuristics is to produce good approximations of optimal solutions within a small amount of time. In contrast to numerous experimental results, there are only a few theoretical results on this subject. We consider the approximation ability of randomized search for the class of covering problems and compare single-objective and multi-objective models for such problems. For the VertexCover problem, we point out situations where the multi-objective model leads to a fast construction of optimal solutions while in the single-objective case even no good approximation can be achieved within expected polynomial time. Examining the more general Set-Cover problem we show that optimal solutions can be approximated within a factor of log n, where n is the problem dimension, using the multi-objective approach while the approximation quality obtainable by the single-objective approach in expected polynomial time may be arbitrarily bad.2007-02-01T00:00:00ZOn the influence of pheromone updates in ACO algorithms
http://hdl.handle.net/2003/26130
Title: On the influence of pheromone updates in ACO algorithms
Authors: Doerr, Benjamin; Neumann, Frank; Sudholt, Dirk; Witt, Carsten
Abstract: The runtime analysis of randomized search heuristics is a growing field where, in the last two decades, many rigorous results have been obtained. These results, however, apply particularly to classical search heuristics such as Evolutionary Algorithms (EAs) and Simulated Annealing. First runtime analyses of modern search heuristics have been conducted only recently w. r. t. a simple Ant Colony Optimization (ACO) algorithm called 1-ANT. In particular, the influence of the evaporation factor in the pheromone update mechanism and the robustness of this parameter w. r. t. the runtime have been determined for the example function OneMax. This paper puts forward the runtime analysis of the 1-ANT on example functions. With respect to EAs, such analyses have been essential to develop methods for the analysis on more complicated problems. The proof techniques required for the 1-ANT, unfortunately, differ significantly from those for EAs, which means that a new reservoir of methods has to be built up. Again, the influence of the evaporation factor is analyzed rigorously, and it is proved that its choice can be very crucial to allow efficient runtimes. Moreover, the analyses provide insight into the working principles of ACO algorithms and, in terms of their robustness, describe essential differences to other randomized search heuristics.2007-01-01T00:00:00ZICSPEA
http://hdl.handle.net/2003/26129
Title: ICSPEA
Authors: Kersting, Petra; Mehnen, Jörn; Rudolph, Günter; Tipura, Igor; Wagner, Tobias
Abstract: The covariance matrix adaptation (CMA) is a concept originally introduced for improving the single-objective evolution strategy (ES). CMA varies the classical ES-mutation operator by utilising a mutation distribution adaptation scheme and an evolution path, which takes the evolutionary history into account. SPEA2 surely belongs to the most popular multi-objective evolutionary algorithms. It uses the strength Pareto concept and a special distribution measure for the evaluation of offspring individuals. An archive collects non-dominated individuals, which are used during selection, making the SPEA2 a typical elitist strategy. The new ICSPEA (Integrated CMA-SPEA) combines the powerful mutation concept of the CMA-ES with the evaluation scheme of the SPEA2. Tests on selected benchmark functions show the promising features of this new multi-objective optimisation algorithm.2007-01-01T00:00:00ZReporting on experiments in evolutionary computation
http://hdl.handle.net/2003/26128
Title: Reporting on experiments in evolutionary computation
Authors: Preuss, Mike2007-01-01T00:00:00ZAnt colony optimization and the minimum spanning tree problem
http://hdl.handle.net/2003/26127
Title: Ant colony optimization and the minimum spanning tree problem
Authors: Neumann, Frank; Witt, Carsten
Abstract: Ant Colony Optimization (ACO) is a kind of randomized search heuristic that has become very popular for solving problems from combinatorial optimization. Solutions for a given problem are constructed by a random walk on a so-called construction graph. This random walk can be influenced by heuristic information about the problem. In contrast to many successful applications, the theoretical foundation of this kind of randomized search heuristic is rather weak. Theoretical investigations with respect to the runtime behavior of ACO algorithms have been started only recently for the optimization of pseudo-boolean functions. We present the first comprehensive rigorous analysis of a simple ACO algorithms for a combinatorial optimization problem. In our investigations we consider the minimum spanning tree problem and examine the effect of two construction graphs with respect to the runtime behavior. The choice of the construction graph in an ACO algorithm seems to be crucial for the success of such an algorithm. First, we take the input graph itself as the construction graph and analyze the use of a construction procedure that is similar to Broder s algorithm [1] for choosing a spanning tree uniformly at random. After that, a more incremental construction procedure is analyzed. It turns out that this procedure is superior to the Broder-based algorithm and produces additionally in a constant number of iterations a minimum spanning tree if the influence of the heuristic information is large enough.2006-11-01T00:00:00ZWhen the plus strategy performs better than the comma strategy - and when not
http://hdl.handle.net/2003/26126
Title: When the plus strategy performs better than the comma strategy - and when not
Authors: Jägersküpper, Jens; Storch, Tobias
Abstract: Occasionally there have been long debates on whether to use elitist selection or not. In the present paper the simple (1,lambd) EA and (1+lambda) EA operating on {0,1}^n are compared by means of a rigorous runtime analysis. It turns out that only values for lambda that are logarithmic in n are interesting. An illustrative function is presented for which newly developed proof methods show that the (1,lambda) EA - where lambda is logarithmic in n - outperforms the (1+lambda) EA for any lambda. For smaller offspring populations the (1,lambda) EA is inefficient on every function with a unique optimum, whereas for larger lambda the two randomized search heuristics behave almost equivalently.2006-11-01T00:00:00ZPareto-, aggregation-, and indicator-based methods in many-objective optimization
http://hdl.handle.net/2003/26125
Title: Pareto-, aggregation-, and indicator-based methods in many-objective optimization
Authors: Beume, Nicola; Naujoks, Boris; Wagner, Tobias
Abstract: Research within the area of Evolutionary Multi-objective Optimization (EMO) focused on two- and three-dimensional objective functions, so far. Most algorithms have been developed for and tested on this limited application area. To broaden the insight in the behavior of EMO algorithms (EMOA) in higher dimensional objective spaces, a comprehensive benchmarking is presented, featuring several state-ofthe-art EMOA, as well as an aggregative approach and a restart strategy on established scalable test problems with three to six objectives. It is demonstrated why the performance of well-established EMOA (NSGAII, SPEA2) rapidly degradates with increasing dimension. Newer EMOA like e-MOEA, MSOPS, IBEA and SMS-EMOA cope very well with highdimensional objective spaces. Their specific advantages and drawbacks are illustrated, thus giving valuable hints for practitioners which EMOA to choose depending on the optimization scenario. Additionally, a new method for the generation of weight vectors usable in aggregation methods is presented.2006-09-01T00:00:00ZFaster S-metric calculation by considering dominated hypervolume as
Klee s measure problem
http://hdl.handle.net/2003/26124
Title: Faster S-metric calculation by considering dominated hypervolume as
Klee s measure problem
Authors: Beume, Nicola; Rudolph, Günter
Abstract: The dominated hypervolume (or S-metric) is a commonly accepted quality measure for comparing approximations of Pareto fronts generated by multi-objective optimizers. Since optimizers exist, namely evolutionary algorithms, that use the S-metric internally several times per iteration, a faster determination of the S-metric value is of essential importance. This paper describes how to consider the S-metric as a special case of a more general geometrical problem called Klee s measure problem (KMP). For KMP, an algorithm exists with run time O(n log n + n^(d/2) log n), for n points of d>= 3 dimensions. This complex algorithmis adapted to the special case of calculating the S-metric. Conceptual simplifications of the implementation are concerned that save on a factor of O(log n) and establish an upper bound of O(n log n + n^(d/2)) for the S-metric calculation, improving the previously known bound of O(n^(d-1)).2006-07-01T00:00:00ZNeyman-Pearson theory of testing and Mayo s extensions applied to evolutionary computing
http://hdl.handle.net/2003/26123
Title: Neyman-Pearson theory of testing and Mayo s extensions applied to evolutionary computing
Authors: Bartz-Beielstein, Thomas
Abstract: Evolutionary computation (EC) is a relatively new discipline in computer science (Eiben & Smith, 2003). It tackles hard real-world optimization problems, e.g., problems from chemical engineering, airfoil optimization, or bioinformatics, where classical methods from mathematical optimization fail. Many theoretical results in this field are too abstract, they do not match with reality. To develop problem specific algorithms, experimentation is necessary. During the first phase of experimental research in EC (before 1980), which can be characterized as -foundation and development,- the comparison of different algorithms was mostly based on mean values - nearly no further statistics have been used. In the second phase, where EC -moved to mainstream- (1980-2000), classical statistical methods were introduced. There is a strong need to compare EC algorithms to mathematical optimization (main stream) methods. Adequate statistical tools for EC are developed in the third phase (since 2000). They should be able to cope with problems like small sample sizes, nonnormal distributions, noisy results, etc. However - even if these tools are under development - they do not bridge the gap between the statistical significance of an experimental result and its scientific meaning. Based on Mayo s learning model (NPT) we will propose some ideas how to bridge this gap (Mayo, 1983, 1996). We will present plots of the observed significance level and discuss the sequential parameter optimization (SPO) approach. SPO is a heuristic, but implementable approach, which provides a framework for a sound statistical methodology in EC (Bartz-Beielstein, 2006).2006-07-01T00:00:00ZOn advantages of scheduling using genetic fuzzy systems
http://hdl.handle.net/2003/26122
Title: On advantages of scheduling using genetic fuzzy systems
Authors: Franke, Carsten; Lepping, Joachim; Schwiegelshohn, Uwe
Abstract: In this paper, we present a methodology for automatically generating online scheduling strategies for a complex scheduling objective with the help of real life workload data. The scheduling problem includes independent parallel jobs and multiple identical machines. The objective is defined by the machine provider and considers different priorities of user groups. In order to allow a wide range of objective functions, we use a rule based scheduling strategy. There, a rule system classifies all possible scheduling states and assigns an appropriate scheduling strategy based on the actual state. The rule bases are developed with the help of a Genetic Fuzzy System that uses workload data obtained from real system installations. We evaluate our new scheduling strategies again on real workload data in comparison to a probability based scheduling strategy and the EASY standard scheduling algorithm. To this end, we select an exemplary objective function that prioritizes some user groups over others.2006-06-01T00:00:00ZA library of multiobjective functions with corresponding graphs
http://hdl.handle.net/2003/26121
Title: A library of multiobjective functions with corresponding graphs
Authors: Mehnen, Jörn2006-06-01T00:00:00ZEvolutionary support vector machines and their application for classification
http://hdl.handle.net/2003/26120
Title: Evolutionary support vector machines and their application for classification
Authors: Dumitrescu, D.; Preuss, Mike; Stoean, Catalin; Stoean, Ruxandra
Abstract: We propose a novel learning technique for classification as result of the hybridization between support vector machines and evolutionary algorithms. Evolutionary support vector machines consider the classification task as in support vector machines but use evolutionary algorithms to solve the optimization problem of determining the decision function. They can acquire the coefficients of the separating hyperplane, which is often not possible within classical techniques. More important, ESVMs obtain the coefficients directly from the evolutionary algorithm and can refer them at any point during a run. The concept is furthermore extended to handle large amounts of data, a problem frequently occurring e.g. in spam mail detection, one of our test cases. Evolutionary support vector machines are validated on this and three other real-world classification tasks; obtained results show the promise of this new technique.2006-06-01T00:00:00ZFinding large cliques in sparse semi-random graphs by simple randomized search heuristics
http://hdl.handle.net/2003/26119
Title: Finding large cliques in sparse semi-random graphs by simple randomized search heuristics
Authors: Storch, Tobias
Abstract: Surprisingly, general heuristics often solve hard combinatorial problems quite sufficiently, although they do not outperform specialized algorithms. Here, the behavior of simple randomized optimizers on the maximum clique problem is investigated. We focus on semi-random models for sparse graphs, in which an adversary is even allowed to insert a limited number of edges and not only to remove them. In the course of these investigations also the approximation behavior on general graphs and the optimization behavior on sparse graphs and further semi-random graph models are considered. With regard to the optimizers particular interest is given to the influences of the population size and the search operator.2006-06-01T00:00:00ZWhy comma selection can help with the escape from local optima
http://hdl.handle.net/2003/26118
Title: Why comma selection can help with the escape from local optima
Authors: Jägersküpper, Jens; Storch, Tobias
Abstract: We investigate (1,lambda) ESs using isotropic mutations for optimization in R^n by means of a theoretical runtime analysis. In particular, a constant offspring-population size lambda will be of interest. We start off by considering an adaptation-less (1,2) ES minimizing a linear function. Subsequently, a piecewise linear function with a jump/cliff is considered, where a (1+lambda) ES gets trapped, i. e., (at least) an exponential (in n) number of steps are necessary to escape the local-optimum region. The (1,2) ES, however, manages to overcome the cliff in an almost unnoticeable number of steps. Finally, we outline (because of the page limit) how the reasoning and the calculations can be extended to the scenario where a (1,lambda) ES using Gaussian mutations minimizes Cliff, a bimodal, spherically symmetric function already considered in the literature, which is merely Sphere with a jump in the function value at a certain distance from the minimum. For lambda a constant large enough, the (1,lambda) ES manages to conquer the global-optimum region { in contrast to (1+lambda) ESs which get trapped.2006-06-01T00:00:00ZControlled model assisted evolution strategy with adaptive preselection
http://hdl.handle.net/2003/26117
Title: Controlled model assisted evolution strategy with adaptive preselection
Authors: Hoffmann, Frank; Hölemann, Sebastian
Abstract: The utility of evolutionary algorithms for direct optimization of real processes or complex simulations is often limited by the large number of required fitness evaluations. Model assisted evolutionary algorithms economize on actual fitness evaluations by partially selecting individuals on the basis of a computationally less complex fitness model. We propose a novel model management scheme to regulate the number of preselected individuals to achieve optimal evolutionary progress with a minimal number of fitness evaluations. The number of preselected individuals is adapted to the model quality expressed by its ability to correctly predict the best individuals. The method achieves a substantial reduction of fitness evaluations on a set of benchmarks not only in comparison to a standard evolution strategy but also with respect to other model assisted optimization schemes.2006-06-01T00:00:00ZLocal search in memetic algorithms
http://hdl.handle.net/2003/26116
Title: Local search in memetic algorithms
Authors: Sudholt, Dirk
Abstract: Memetic algorithms are popular randomized search heuristics combining evolutionary algorithms and local search. Their efficiency has been demonstrated in countless applications covering a wide area of practical problems. However, theory of memetic algorithms is still in its infancy and there is a strong need for a rigorous theoretical foundation to better understand these heuristics. Here, we attack one of the fundamental issues in the design of memetic algorithms from a theoretical perspective, namely the choice of the frequency with which local search is applied. Since no guidelines are known for the choice of this parameter, we care about its impact on memetic algorithm performance. We present worst-case problems where the choice of the local search frequency has an enormous impact on the performance of a simple memetic algorithm. A rigorous theoretical analysis shows that on these problems, with overwhelming probability, even a small factor of 2 decides about polynomial versus exponential optimization times.2006-06-01T00:00:00ZVisual servoing with moments of SIFT features
http://hdl.handle.net/2003/26115
Title: Visual servoing with moments of SIFT features
Authors: Hoffmann, Frank; Nierobisch, Thomas; Rudolph, Günter; Seyffarth, Thorsten
Abstract: Robotic manipulation of daily-life objects is an essential requirement in service robotic applications. In that context image based visual servoing is a means to position the end-effector in order to manipulate objects of unknown pose. This contribution proposes a 6 DOF visual servoing scheme that relies on the pixel coordinates, scale and orientation of SIFT features. The control is based on geometric moments computed over an alterable set of redundant SIFT feature correspondences between the current and the reference view. The method is generic as it does not depend on a geometric object model but automatically extracts SIFT features from images of the object. The foundation of visual servoing on generic SIFT features renders the method robust with respect to loss of redundant features caused by occlusion or changes in view point.The moment based representation establishes an approximate one-to-one relationship between visual features and degrees of motion. This property is exploited in the design of a decoupled controller that demonstrates superior performance in terms of convergence and robustness compared with an inverse image Jacobian controller. Several experiments with a robotic arm equipped with a monocular eye-in-hand camera demonstrate that the approach is efficient and reliable.2006-05-01T00:00:00ZTakeover time in parallel populations with migration
http://hdl.handle.net/2003/26114
Title: Takeover time in parallel populations with migration
Authors: Rudolph, Günter
Abstract: The term takeover time regarding selection methods used in evolutionary algorithms denotes the (expected) number of iterations of the selection method until the entire population consists of copies of the best individual, provided that the initial population consists of a single copy of the best individual whereas the remaining individuals are worse. Here, this notion is extended to parallel subpopulations that exchange individuals according to some migration paths modelled by a directed graph. We develop upper bounds for migrations path along uni- and bidirectial rings as well as arbitrary connected graphs where each vertex is reachable from every other vertex.2006-05-01T00:00:00ZPareto set and EMOA behavior for simple multimodal multiobjective functions
http://hdl.handle.net/2003/26113
Title: Pareto set and EMOA behavior for simple multimodal multiobjective functions
Authors: Naujoks, Boris; Preuss, Mike; Rudolph, Günter
Abstract: Recent research on evolutionary multiobjective optimization has mainly focused on Pareto-fronts. However, we state that proper behavior of the utilized algorithms in decision/search space is necessary for obtaining good results if multimodal objective functions are concerned. Therefore, it makes sense to observe the development of Pareto-sets as well. We do so on a simple, configurable problem, and detect interesting interactions between induced changes to the Pareto-set and the ability of three optimization algorithms to keep track of Pareto-fronts.2006-05-01T00:00:00ZEvolutionary Optimization of Dynamic Multiobjective Functions
http://hdl.handle.net/2003/26112
Title: Evolutionary Optimization of Dynamic Multiobjective Functions
Authors: Mehnen, Jörn; Rudolph, Günter; Wagner, Tobias
Abstract: Many real-world problems show both multiobjective as well as dynamic characteristics. In order to use multiobjective evolutionary optimization algorithms (MOEA) efficiently, a systematic analysis of the behavior of these algorithms in dynamic environments is necessary. Dynamic fitness functions can be classified into problems with moving Pareto fronts and Pareto sets having varying speed, shape, and structure. The influence of the dimensions of the objective and decision space is considered. The analysis will focus on standard benchmark functions and newly designed test functions. Convergence and solution distribution features of modern MOEA, namely NSGA-II, SPEA 2 and MSOPS using different variation operators (SBX and Differential Evolution), will be characterized using Pareto front metrics. A new path integral metric is introduced. Especially the ability of the algorithms to use historically evolved population properties will be discussed.2006-05-01T00:00:00Zhow randomized search heuristics find maximum cliques in planar graphs
http://hdl.handle.net/2003/26111
Title: how randomized search heuristics find maximum cliques in planar graphs
Authors: Storch, Tobias
Abstract: Surprisingly, general search heuristics often solve combinatorial problems quite sufficiently, although they do not outperform specialized algorithms. Here, the behavior of simple randomized optimizers on the maximum clique problem on planar graphs is investigated rigorously. The focus is on the worst-, average-, and semi-average-case behaviors. In semi-random planar graph models an adversary is allowed to modify moderately a random planar graph, where a graph is chosen uniformly at random among all planar graphs. With regard to the heuristics particular interest is given to the influences of the following four popular strategies to overcome local optima: local- vs. global-search, single- vs. multi-start, small vs. large population, and elitism vs. non-elitism selection. Finally, the black-box complexities of the planar graph models are analyzed.2006-03-01T00:00:00ZOn the effect of populations in evolutionary multi-objective optimization
http://hdl.handle.net/2003/24343
Title: On the effect of populations in evolutionary multi-objective optimization
Authors: Giel, Oliver; Lehre, Per Kristian
Abstract: Multi-objective evolutionary algorithms (MOEAs) have become increasingly popular as multi-objective problem solving techniques.
Most studies of MOEAs are empirical. Only recently, a few theoretical
results have appeared. It is acknowledged that more theoretical research
is needed. An important open problem is to understand the role of populations in MOEAs. We present a simple bi-objective problem which emphasizes when populations are needed. Rigorous runtime analysis point
out an exponential runtime gap between a population-based algorithm
(SEMO) and several single individual-based algorithms on this problem.
This means that among the algorithms considered, only the populationbased MOEA is successful and all other algorithms fail.2007-06-04T16:20:03ZOn the analysis of the (1+1) memetic algorithm
http://hdl.handle.net/2003/24342
Title: On the analysis of the (1+1) memetic algorithm
Authors: Sudholt, Dirk
Abstract: Memetic algorithms are evolutionary algorithms incorporating local search to increase exploitation. This hybridization has been fruitful
in countless applications. However, theory on memetic algorithms is
still in its infancy.
Here, we introduce a simple memetic algorithm, the (1+1) Memetic
Algorithm ((1+1) MA), working with a population size of 1 and no
crossover. We compare it with the well-known (1+1) EA and randomized local search and show that these three algorithms can outperform
each other drastically.
On problems like, e. g., long path problems it is essential to limit
the duration of local search. We investigate the (1+1) MA with a fixed
maximal local search duration and define a class of fitness functions
where a small variation of the local search duration has a large impact
on the performance of the (1+1) MA.
All results are proved rigorously without assumptions.2007-06-04T16:11:37ZQuadratische Optimierung unter Nebenbedingungen und Anwendungen in der Kraftwerksführung
http://hdl.handle.net/2003/22133
Title: Quadratische Optimierung unter Nebenbedingungen und Anwendungen in der Kraftwerksführung
Authors: Hansen, W.; Kiendl, H.2006-01-23T13:33:21ZSimulated Annealing Beats Metropolis in Combinatorial Optimization
http://hdl.handle.net/2003/22129
Title: Simulated Annealing Beats Metropolis in Combinatorial Optimization
Authors: Wegener, Ingo2006-01-19T15:33:23ZConstraint Programming versus Logik
http://hdl.handle.net/2003/22128
Title: Constraint Programming versus Logik
Authors: Köpcke, Hanna; Schröder, Andreas2006-01-19T15:33:10ZA Predator-Prey Approach for Pareto-Optimization
http://hdl.handle.net/2003/22127
Title: A Predator-Prey Approach for Pareto-Optimization
Authors: Mehnen, Jörn; Michelitsch, Thomas; Schmitt, Karlheinz2006-01-19T15:32:51ZKEA - a software package for development, analysis and application of multiple objective evolutionary algorithms
http://hdl.handle.net/2003/22126
Title: KEA - a software package for development, analysis and application of multiple objective evolutionary algorithms
Authors: Bartz-Beielstein, Thomas; Mehnen, J.; Naujoks, B.; Schmitt, K.; Zibold, D.2006-01-19T15:32:38ZRuntime Analysis of the (1+1) ES Minimizing Simple Quadratic Forms Using the 1/5-Rule
http://hdl.handle.net/2003/22125
Title: Runtime Analysis of the (1+1) ES Minimizing Simple Quadratic Forms Using the 1/5-Rule
Authors: Jägersküpper, Jens2006-01-19T15:32:20ZUsing Gene Duplication and Gene Deletion in Evolution Strategies
http://hdl.handle.net/2003/22124
Title: Using Gene Duplication and Gene Deletion in Evolution Strategies
Authors: Schmitt, Karlheinz2006-01-19T15:32:06ZMultikriterielle evolutionäre Aufstellungsoptimierung von Chemie-Anlagen unter Beachtung gewichteter Designregeln
http://hdl.handle.net/2003/22123
Title: Multikriterielle evolutionäre Aufstellungsoptimierung von Chemie-Anlagen unter Beachtung gewichteter Designregeln
Authors: Geisbe, Thorsten; Mierswa, Ingo2006-01-19T15:31:50ZpMOHypEA: Parallel Evolutionary Multiobjective Optimization using Hypergraphs
http://hdl.handle.net/2003/22122
Title: pMOHypEA: Parallel Evolutionary Multiobjective Optimization using Hypergraphs
Authors: Kohlen, Torsten; Mehnen, Jörn; Michelitsch, Thomas; Schmitt, Karlheinz2006-01-19T15:31:34ZScheduling Algorithm Development based on Complex Owner Defined Objectives
http://hdl.handle.net/2003/22121
Title: Scheduling Algorithm Development based on Complex Owner Defined Objectives
Authors: Beume, Nicola; Emmerich, Michael; Ernemann, Carsten; Schönemann, Lutz; Schwiegelshohn, Uwe2006-01-19T15:31:22ZUser Group-based Workload Analysis and Modelling
http://hdl.handle.net/2003/22120
Title: User Group-based Workload Analysis and Modelling
Authors: Ernemann, Carsten; Song, Baiyi; Yahyapour, Ramin2006-01-19T15:31:09ZMinimum Spanning Trees Made Easier Via Multi-Objective Optimization
http://hdl.handle.net/2003/22119
Title: Minimum Spanning Trees Made Easier Via Multi-Objective Optimization
Authors: Neumann, Frank; Wegener, Ingo2006-01-19T15:30:54ZOn the Impact of Objective Function Transformations on Evolutionary and Black-Box Algorithms
http://hdl.handle.net/2003/22118
Title: On the Impact of Objective Function Transformations on Evolutionary and Black-Box Algorithms
Authors: Storch, Tobias2006-01-19T15:30:39ZEfficient Case Based Feature Construction for Heterogeneous Learning Tasks
http://hdl.handle.net/2003/22117
Title: Efficient Case Based Feature Construction for Heterogeneous Learning Tasks
Authors: Mierswa, Ingo; Wurst, Michael2006-01-19T15:30:23ZDesign and Analysis of an Asymmetric Mutation Operator
http://hdl.handle.net/2003/22116
Title: Design and Analysis of an Asymmetric Mutation Operator
Authors: Jansen, Thomas; Sudholt, Dirk2006-01-19T15:30:08ZCrossover is Provably Essential for the Ising Model on Trees
http://hdl.handle.net/2003/22115
Title: Crossover is Provably Essential for the Ising Model on Trees
Authors: Sudholt, Dirk2006-01-19T15:29:55ZRuntime Analysis of a (μ +1) ES for the Sphere Function
http://hdl.handle.net/2003/22114
Title: Runtime Analysis of a (μ +1) ES for the Sphere Function
Authors: Jägersküpper, Jens; Witt, Carsten2006-01-19T15:29:40ZOn the Complexity of Overcoming Gaps When Using Elitist Selection and Isotropic Mutations
http://hdl.handle.net/2003/22113
Title: On the Complexity of Overcoming Gaps When Using Elitist Selection and Isotropic Mutations
Authors: Jägersküpper, Jens2006-01-19T15:29:23ZAnalysis of a simple (1+1) ES for the Class of Positive Definite Quadratic Forms with Bounded Condition Number
http://hdl.handle.net/2003/22112
Title: Analysis of a simple (1+1) ES for the Class of Positive Definite Quadratic Forms with Bounded Condition Number
Authors: Jägersküpper, Jens2006-01-19T15:29:01ZRuntime Analysis of a Simple Ant Colony Optimization Algorithm
http://hdl.handle.net/2003/22111
Title: Runtime Analysis of a Simple Ant Colony Optimization Algorithm
Authors: Neumann, Frank; Witt, Carsten2006-01-19T15:07:01ZOn the Choice of Offspring Population Size in Evolutionary Algorithms
http://hdl.handle.net/2003/5481
Title: On the Choice of Offspring Population Size in Evolutionary Algorithms
Authors: De Jong, Kenneth A.; Jansen, Thomas; Wegener, Ingo2004-10-21T00:00:00ZBridging the Gap Between Theory and Practice
http://hdl.handle.net/2003/5480
Title: Bridging the Gap Between Theory and Practice
Authors: Jansen, Thomas; Wiegand, R. Paul2004-10-21T00:00:00ZMerkmalsbasiertes Lernen von Platzierungsregeln im Rahmen der Aufstellungsplanung von Chemieanlagen
http://hdl.handle.net/2003/5479
Title: Merkmalsbasiertes Lernen von Platzierungsregeln im Rahmen der Aufstellungsplanung von Chemieanlagen
Authors: Hicking, Bernd; Ritthoff, Oliver2004-10-21T00:00:00ZSearching Randomly for Maximum Matchings
http://hdl.handle.net/2003/5478
Title: Searching Randomly for Maximum Matchings
Authors: Giel, Oliver; Wegener, Ingo2004-10-21T00:00:00ZOn the Analysis of Dynamic Restart Strategies for Evolutinary Algotithms
http://hdl.handle.net/2003/5477
Title: On the Analysis of Dynamic Restart Strategies for Evolutinary Algotithms
Authors: Jansen, Thomas2004-10-21T00:00:00ZThe Ising Model: Simple Evolutionary Algorithms as Adaptation Schemes
http://hdl.handle.net/2003/5476
Title: The Ising Model: Simple Evolutionary Algorithms as Adaptation Schemes
Authors: Briest, Patrick; Brockhoff, Dimo; Degener, Bastian; Englert, Matthias; Gunia, Christian; Heering, Oliver; Jansen, Thomas; Leifhelm, Michael; Plociennik, Kai; Röglin, Heiko; Schweer, Andrea; Sudholt, Dirk; Tannenbaum, Stefan; Wegener, Ingo2004-10-21T00:00:00ZExperimental Supplements to the Theoretical Analysis of EAs on Problems from Combinatiorial Optimization
http://hdl.handle.net/2003/5475
Title: Experimental Supplements to the Theoretical Analysis of EAs on Problems from Combinatiorial Optimization
Authors: Briest, Patrick; Brockhoff, Dimo; Degener, Bastian; Englert, Matthias; Gunia, Christian; Heering, Oliver; Jansen, Thomas; Leifhelm, Michael; Plociennik, Kai; Röglin, Heiko; Schweer, Andrea; Sudholt, Dirk; Tannenbaum, Stefan; Wegener, Ingo2004-10-21T00:00:00ZWorst-Case and Averange-Case Approximations by Simple Randomized Search Heuristics
http://hdl.handle.net/2003/5474
Title: Worst-Case and Averange-Case Approximations by Simple Randomized Search Heuristics
Authors: Witt, Carsten2004-10-21T00:00:00ZPredicting the Solution Quality in Noisy Optimization
http://hdl.handle.net/2003/5473
Title: Predicting the Solution Quality in Noisy Optimization
Authors: Beyer, Hans-Georg; Meyer-Nieberg, Silja2004-10-21T00:00:00ZValidation and optimization of an elevator simulation model with modern search heuristics
http://hdl.handle.net/2003/5472
Title: Validation and optimization of an elevator simulation model with modern search heuristics
Authors: Bartz-Beielstein, Thomas; Markon, Sandor; Preuss, Mike2004-07-13T00:00:00ZOptimization and information processing
http://hdl.handle.net/2003/5471
Title: Optimization and information processing
Authors: Wiesmann, Dirk2004-07-13T00:00:00ZA partial order approach to noisy fitness functions
http://hdl.handle.net/2003/5470
Title: A partial order approach to noisy fitness functions
Authors: Rudolph, Günter2004-07-13T00:00:00ZDesigning particle swarm optimization with regression trees
http://hdl.handle.net/2003/5469
Title: Designing particle swarm optimization with regression trees
Authors: Bartz-Beielstein, Thomas; Parsopoulos, K. E.; Vegt, M. de; Vrahatis, M. N.2004-07-13T00:00:00ZTuning search algorithms for real-world applications
http://hdl.handle.net/2003/5468
Title: Tuning search algorithms for real-world applications
Authors: Bartz-Beielstein, Thomas; Markon, Sandor2004-07-13T00:00:00ZMulti-layered neural network based on multi-valued neurons (MLMVN) and a backpropagation learning algorithm
http://hdl.handle.net/2003/5467
Title: Multi-layered neural network based on multi-valued neurons (MLMVN) and a backpropagation learning algorithm
Authors: Aizenberg, Igor; Moraga, Claudio2004-07-13T00:00:00ZAn analysis of the (u+1) EA on pseudo-boolean functions
http://hdl.handle.net/2003/5466
Title: An analysis of the (u+1) EA on pseudo-boolean functions
Authors: Witt, Carsten2004-07-13T00:00:00ZOn the design and analysis of evolutionary algorithms
http://hdl.handle.net/2003/5465
Title: On the design and analysis of evolutionary algorithms
Authors: Wegener, Ingo2004-05-24T00:00:00ZEfficient design of a complete rule search in sparsely populated search spaces
http://hdl.handle.net/2003/5464
Title: Efficient design of a complete rule search in sparsely populated search spaces
Authors: Krause, Peter; Krone, Angelika; Slawinski, Timo2004-05-24T00:00:00ZA distance measure for the mutation of fuzzy rules
http://hdl.handle.net/2003/5463
Title: A distance measure for the mutation of fuzzy rules
Authors: Krone, Angelika; Slawinski, Timo2004-05-24T00:00:00ZParallel evolutionary algorithms for optimizing data based generated fuzzy systems
http://hdl.handle.net/2003/5462
Title: Parallel evolutionary algorithms for optimizing data based generated fuzzy systems
Authors: Krause, Peter; Slawinski, T.; Wiesmann, D.2004-05-24T00:00:00ZFuzzy interpretation of music
http://hdl.handle.net/2003/5461
Title: Fuzzy interpretation of music
Authors: Kiendl, Harro; Kiseliova, Tatiana; Rambinintsoa, Yves2004-05-24T00:00:00Z