29 August 2017 in IEEE Transactions on Evolutionary Computation
Population diversity is essential for avoiding premature convergence in Genetic Algorithms and for the effective use of crossover. Yet the dynamics of how diversity emerges in populations are not well understood. We use rigorous run time analysis to gain insight into population dynamics and Genetic Algorithm performance for the (μ+1) Genetic Algorithm and the Jump test function. We show that the interplay of crossover followed by mutation may serve as a catalyst leading to a sudden burst of diversity. This leads to significant improvements of the expected optimisation time compared to mutation-only algorithms like the (1+1) Evolutionary Algorithm. Moreover, increasing the mutation rate by an arbitrarily small constant factor can facilitate the generation of diversity, leading to even larger speedups. Experiments were conducted to complement our theoretical findings and further highlight the benefits of crossover on the function class.
1 December 2015 in Evolutionary Computation
Many combinatorial optimization problems have underlying goal functions that are submodular. The classical goal is to find a good solution for a given submodular function f under a given set of constraints. In this paper, we investigate the runtime of a simple single objective evolutionary algorithm called ([ ]) EA and a multiobjective evolutionary algorithm called GSEMO until they have obtained a good approximation for submodular functions. For the case of monotone submodular functions and uniform cardinality constraints, we show that the GSEMO achieves a [ ]-approximation in expected polynomial time. For the case of monotone functions where the constraints are given by the intersection of [ ] matroids, we show that the ([ ]) EA achieves a ([ ])-approximation in expected polynomial time for any constant [ ]. Turning to nonmonotone symmetric submodular functions with [ ] matroid intersection constraints, we show that the GSEMO achieves a [ ]-approximation in expected time [ ].
1 February 2013 in Artificial Intelligence
16 February 2021 in Natural Computing
1 June 2016 in Evolutionary Computation
Recently, ant colony optimization (ACO) algorithms have proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses have focused on combinatorial problems such as path finding. We rigorously analyze an ACO algorithm optimizing linear pseudo-Boolean functions under additive posterior noise. We study noise distributions whose tails decay exponentially fast, including the classical case of additive Gaussian noise. Without noise, the classical [ ] EA outperforms any ACO algorithm, with smaller [ ] being better; however, in the case of large noise, the [ ] EA fails, even for high values of [ ] (which are known to help against small noise). In this article, we show that ACO is able to deal with arbitrarily large noise in a graceful manner; that is, as long as the evaporation factor [ ] is small enough, dependent on the variance [ ] of the noise and the dimension n of the search space, optimization will be successful. We also briefly consider the case of prior noise and prove that ACO can also efficiently optimize linear functions under this noise model.
1 October 2015 in Journal of Theoretical Biology
The theory of population genetics and evolutionary computation have been evolving separately for nearly 30 years. Many results have been independently obtained in both fields and many others are unique to its respective field. We aim to bridge this gap by developing a unifying framework for evolutionary processes that allows both evolutionary algorithms and population genetics models to be cast in the same formal framework. The framework we present here decomposes the evolutionary process into its several components in order to facilitate the identification of similarities between different models. In particular, we propose a classification of evolutionary operators based on the defining properties of the different components. We cast several commonly used operators from both fields into this common framework. Using this, we map different evolutionary and genetic algorithms to different evolutionary regimes and identify candidates with the most potential for the translation of results between the fields. This provides a unified description of evolutionary processes and represents a stepping stone towards new tools and results to both fields.