Jove
Visualize
Contact Us

Related Experiment Videos

Toward a theory of evolutionary computation.

Eugene Eberbach1

  • 1Computer and Information Science Department, University of Massachusetts, North Dartmouth, MA 02747-2300, USA. eeberbach@umassd.edu

Bio Systems
|August 17, 2005
PubMed
Summary

We introduce the Evolutionary Turing Machine, a novel model enhancing evolutionary computation theory. This model offers a more complete framework for evolutionary search, proving it more expressive than traditional Turing Machines.

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

Cooperative combinatorial optimization: evolutionary computation case study.

Bio Systemsยท2007
See all related articles
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

Area of Science:

  • Theoretical Computer Science
  • Evolutionary Computation
  • Computational Complexity

Background:

  • Conventional Turing Machines and Markov chains offer limited models for evolutionary computation.
  • Existing models struggle with the intractability and optimality of evolutionary search.
  • The need for a more robust theoretical framework for evolutionary computation is evident.

Purpose of the Study:

  • To introduce a formal model, the Evolutionary Turing Machine (ETM), as an extension of the Turing Machine.
  • To define and investigate convergence properties within the ETM framework.
  • To explore the expressiveness and problem-solving capabilities of evolutionary computation.

Main Methods:

  • Formal modeling using the Evolutionary Turing Machine.
  • Analysis of convergence and convergence rates.
  • Investigation of conditions for evolutionary search completeness and optimality.
  • Introduction of 'total optimality' for multiobjective optimization in ETMs.

Main Results:

  • ETMs provide a more complete model for evolutionary computing than conventional Turing Machines.
  • Sufficient conditions for evolutionary search completeness and optimality are identified.
  • The concept of total optimality is introduced for simultaneous optimization of solution quality and search costs.
  • Evolutionary computation is shown to be more expressive than Turing Machines.
  • ETMs can non-algorithmically solve the Universal Turing Machine's halting problem.

Conclusions:

  • The Evolutionary Turing Machine offers a superior theoretical foundation for evolutionary computation.
  • Evolutionary computation exhibits greater expressiveness than traditional Turing Machines.
  • The problem of finding the 'best' evolutionary algorithm is undecidable, but can be asymptotically approximated.

Related Experiment Videos