1,407 research outputs found
Bioinspired computation in combinatorial optimization : algorithms and their computational complexity
No full textFrank Neumann and Carsten Witthttp://nla.gov.au/anbd.bib-an4690199
Runtime analysis of a simple Ant Colony Optimization algorithm
No full textAnt Colony Optimization (ACO) has become quite popular in recent years. In contrast to many successful applications, the theoretical foundation of this randomized search heuristic is rather weak. Building up such a theory is demanded to understand how these heuristics work as well as to come up with better algorithms for certain problems. Up to now, only convergence results have been achieved showing that optimal solutions can be obtained in a finite amount of time. We present the first runtime analysis of a simple ACO algorithm that transfers many rigorous results with respect to the runtime of a simple evolutionary algorithm to our algorithm. In addition, we examine the choice of the evaporation factor, which is a crucial parameter in such an algorithm, in greater detail and analyze its effect with respect to the runtime.
Carsten Holtmann and Dirk Neumann Market and Firm – Two Sides of a Coin 1
No full textElectronic markets are not just evolving they are designed. As such providing electronic trading venues is an entrepreneurial activity. The institutional approach followed here introduces a market operator as an economic player. As the entrepreneur charges fees for his service of operating an electronic market, the transaction cost savings incurred by information technology are essentially fully shifted to the market participants. As such the momentum predicted by the Electronic Market Hypothesis is limited in practice. The paper addresses this gap by deriving a conceptual framework, which reconciles the classical view on electronic markets with the entrepreneurial view.
Correction to: When terminology hinders research: the colloquialisms of transitions of control in automated driving (Cognition, Technology & Work, (2022), 10.1007/s10111-022-00705-3)
No full textIn the original article, author affiliation published with error. The correct affiliations are: Davide Maggi—Institute for Transport Studies, Leeds, UK. Richard Romano—Institute for Transport Studies, Leeds, UK. Oliver Carsten—Institute for Transport Studies, Leeds, UK. Joost C. F. De Winter—Faculty of Mechanical, Maritime and Materials Engineering, Delft University of Technology, Delft, The Netherlands. The original article has been corrected.Human-Robot Interactio
Theoretical properties of two ACO approaches for the traveling salesman problem
No full textAnt colony optimization (ACO) has been widely used for different combinatorial optimization problems. In this paper, we investigate ACO algorithms with respect to their runtime behavior for the travelling salesperson (TSP) problem. We present a new construction graph and show that it has a stronger local property than the given input graph which is often used for constructing solutions. Later on, we investigate ACO algorithms for both construction graphs on random instances and show that they achieve a good approximation in expected polynomial time.Timo Kötzing, Frank Neumann, Heiko Röglin and Carsten Wit
3-Objective Pareto Optimization for Problems with Chance Constraints
No full textEvolutionary multi-objective algorithms have successfully been used in the context of Pareto optimization where a given constraint is relaxed into an additional objective. In this paper, we explore the use of 3-objective formulations for problems with chance constraints. Our formulation trades off the expected cost and variance of the stochastic component as well as the given deterministic constraint. We point out benefits that this 3-objective formulation has compared to a bi-objective one recently investigated for chance constraints with Normally distributed stochastic components. Our analysis shows that the 3-objective formulation allows to compute all required trade-offs using 1-bit flips only, when dealing with a deterministic cardinality constraint. Furthermore, we carry out experimental investigations for the chance constrained dominating set problem and show the benefit for this classical NP-hard problem.Frank Neumann, Carsten Wit
Runtime analysis of a simple ant colony optimization algorithm
No full textAnt Colony Optimization (ACO) has become quite popular in recent years. In contrast to many successful applications, the theoretical foundation of this randomized search heuristic is rather weak. Building up such a theory is demanded to understand how these heuristics work as well as to come up with better algorithms for certain problems. Up to now, only convergence results have been achieved showing that optimal solutions can be obtained in finite time. We present the first runtime analysis of an ACO algorithm, which transfers many rigorous results with respect to the runtime of a simple evolutionary algorithm to our algorithm. Moreover, we examine the choice of the evaporation factor, a crucial parameter in ACO algorithms, in detail. By deriving new lower bounds on the tails of sums of independent Poisson trials, we determine the effect of the evaporation factor almost completely and prove a phase transition from exponential to polynomial runtime.Frank Neumann and Carsten Wit
Computational complexity of ant colony optimization and its hybridization with local search
No full textThe computational complexity of ant colony optimization (ACO) is a new and rapidly growing research area. The finite-time dynamics of ACO algorithms is assessed with mathematical rigor using bounds on the (expected) time until an ACO algorithm finds a global optimum. We review previous results in this area and introduce the reader into common analysis methods. These techniques are then applied to obtain bounds for different ACO algorithms on classes of pseudo-Boolean problems. The resulting runtime bounds are further used to clarify important design issues from a theoretical perspective. We deal with the question whether the current best-so-far solution should be replaced by new solutions with the same quality. Afterwards, we discuss the hybridization of ACO with local search and present examples where introducing local search leads to a tremendous speed-up and to a dramatic loss in performance, respectively.Frank Neumann, Dirk Sudholt, and Carsten Wit
Analysis of different MMAS ACO algorithms on unimodal functions and plateaus
No full textRecently, the first rigorous runtime analyses of ACO algorithms appeared, covering variants of the MAX - MIN ant system and their runtime on pseudo-Boolean functions. Interestingly, a variant called 1-ANT is very sensitive to the evaporation factor while Gutjahr and Sebastiani proved partly opposite results for their variant MMASbs. These algorithms differ in their pheromone update mechanisms and, moreover, 1-ANT accepts equally fit solutions in contrast to MMASbs. By analyzing variants of MMASbs, we prove that the different behavior of 1-ANT and MMASbs results from the different pheromone update mechanisms. Building upon results by Gutjahr and Sebastiani, we extend their analyses of MMASbs to the class of unimodal functions and show improved results for test functions using new and specialized techniques; in particular, we present new lower bounds. Finally, we compare MMASbs with a variant that also accepts equally fit solutions as this enables the exploration of plateaus. For well-known plateau functions we prove that this drastically reduces the optimization time. Our findings are complemented by experiments that support our asymptotic analyses and yield additional insights. © The Author(s) 2008.Frank Neumann, Dirk Sudholt, Carsten Wit
- …
