Source author record

Pietro S. Oliveto

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Neural and Evolutionary Computing Computational Complexity Populations and Evolution

Catalog footprint

Research overview

2works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Escaping Local Optima using Crossover with Emergent or Reinforced Diversity

Population diversity is essential for avoiding premature convergence in Genetic Algorithms (GAs) and for the effective use of crossover. Yet the dynamics of how diversity emerges in populations are not well understood. We use rigorous runtime analysis to gain insight into population dynamics and GA performance for the ( $μ$ +1) GA and the $\text{Jump}_k$ test function. We show that the interplay of crossover and mutation may serve as a catalyst leading to a sudden burst of diversity. This leads to improvements of the expected optimisation time of order $Ω(n/\log n)$ compared to mutation-only algorithms like (1+1) EA. Moreover, increasing the mutation rate by an arbitrarily small constant factor can facilitate the generation of diversity, leading to speedups of order $Ω(n)$ . We also compare seven commonly used diversity mechanisms and evaluate their impact on runtime bounds for the ( $μ$ +1) GA. All previous results in this context only hold for unrealistically low crossover probability $p_c=O(k/n)$ , while we give analyses for the setting of constant $p_c < 1$ in all but one case. For the typical case of constant $k > 2$ and constant $p_c$ , we can compare the resulting expected runtimes for different diversity mechanisms assuming an optimal choice of $μ$ : $O(n^{k-1})$ for duplicate elimination/minim., $O(n^2\log n)$ for maximising the convex hull, $O(n\log n)$ for deterministic crowding (assuming $p_c = k/n$ ), $O(n\log n)$ for maximising Hamming distance, $O(n\log n)$ for fitness sharing, $O(n\log n)$ for single-receiver island model. This proves a sizeable advantage of all variants of the ( $μ$ +1) GA compared to (1+1) EA, which requires time $Θ(n^k)$ . Experiments complement our theoretical findings and further highlight the benefits of crossover and diversity on $\text{Jump}_k$ .

preprint2012arXiv

Erratum: Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation

This erratum points out an error in the simplified drift theorem (SDT) [Algorithmica 59(3), 369-386, 2011]. It is also shown that a minor modification of one of its conditions is sufficient to establish a valid result. In many respects, the new theorem is more general than before. We no longer assume a Markov process nor a finite search space. Furthermore, the proof of the theorem is more compact than the previous ones. Finally, previous applications of the SDT are revisited. It turns out that all of these either meet the modified condition directly or by means of few additional arguments.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.