Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Runtime analysis of the (mu+1) EA on simple Pseudo-Boolean functions.

Carsten Witt1

  • 1FB Informatik, LS 2, Universität Dortmund, 44221 Dortmund, Germany. carsten.witt@cs.uni-dortmund.de

Evolutionary Computation
|March 16, 2006
PubMed
Summary

This study rigorously analyzes the (mu+1) Evolutionary Algorithm (EA) on pseudo-Boolean functions. Results show the (mu+1) EA is often less efficient than the (1+1) EA, but can be faster with increased population size on complex problems.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Fast Pareto Optimization Using Sliding Window Selection for Problems with Determinstic and Stochastic Constraints.

Evolutionary computation·2025
Same author

Runtime Analysis of Single- and Multiobjective Evolutionary Algorithms for Chance-Constrained Optimization Problems with Normally Distributed Random Variables.

Evolutionary computation·2024
Same author

Stagnation Detection with Randomized Local Search.

Evolutionary computation·2022
Same author

A Runtime Analysis of Parallel Evolutionary Algorithms in Dynamic Optimization.

Algorithmica·2020
Same author

The Impact of a Sparse Migration Topology on the Runtime of Island Models in Dynamic Optimization.

Algorithmica·2019
Same author

Approximating covering problems by randomized search heuristics using multi-objective models.

Evolutionary computation·2010

Area of Science:

  • Computer Science
  • Artificial Intelligence
  • Optimization

Background:

  • Evolutionary Algorithms (EAs) are widely used for discrete optimization.
  • Theoretical analysis of population-based EAs, like the (mu+1) EA, is underdeveloped.
  • Understanding EA performance on pseudo-Boolean functions is crucial for algorithm design.

Purpose of the Study:

  • To provide a rigorous theoretical analysis of the (mu+1) EA on pseudo-Boolean functions.
  • To derive bounds for expected runtime and success probability.
  • To introduce a novel proof technique applicable to population-based EAs.

Main Methods:

  • Analysis of the (mu+1) EA on three established benchmark functions.
  • Derivation of theoretical bounds on runtime and success probability.

Related Experiment Videos

  • Investigation of the stochastic process of individual "family trees" to bound their depth.

    • Main Results:

    • For two benchmark functions, tight upper and lower bounds on expected runtime were established.
    • The (mu+1) EA demonstrated no efficiency gain over the (1+1) EA on the tested functions.
    • Lower bounds on runtime increase with population size (mu), but a small increase in mu can drastically reduce runtime on complex functions.

    Conclusions:

    • The (mu+1) EA's performance is comparable to or worse than the (1+1) EA on simpler functions.
    • A new proof technique effectively bounds the runtime of the (mu+1) EA.
    • The developed technique offers a generalizable approach for analyzing other population-based EAs.