1.3 History of evolutionary computation

Evolutionary computation, inspired by biological evolution, emerged in the mid-20th century to solve complex optimization problems. It combines natural selection, genetic inheritance, and adaptation principles, bridging biology, computer science, and artificial intelligence.

The field's history spans early biological inspirations, cybernetics, and AI research. Foundational algorithms like genetic algorithms, evolution strategies, and evolutionary programming were developed independently in the 1960s and 1970s, shaping modern evolutionary computation approaches.

Origins of evolutionary computation

• Evolutionary computation draws inspiration from biological evolution to solve complex optimization problems
• Combines principles of natural selection, genetic inheritance, and adaptation to create powerful algorithms
• Emerged as a field in the mid-20th century, bridging biology, computer science, and artificial intelligence

Early biological inspirations

Top images from around the web for Early biological inspirations

• 

  Patterns of Inheritance | Anatomy and Physiology II View original

  Is this image relevant?

• 

  Darwin and The Theory of Evolution ‹ OpenCurriculum View original

  Is this image relevant?

• 

  Patterns of Inheritance | Anatomy and Physiology II View original

  Is this image relevant?

• 

  Darwin and The Theory of Evolution ‹ OpenCurriculum View original

  Is this image relevant?

1 of 2

Top images from around the web for Early biological inspirations

• 

  Patterns of Inheritance | Anatomy and Physiology II View original

  Is this image relevant?

• 

  Darwin and The Theory of Evolution ‹ OpenCurriculum View original

  Is this image relevant?

• 

  Patterns of Inheritance | Anatomy and Physiology II View original

  Is this image relevant?

• 

  Darwin and The Theory of Evolution ‹ OpenCurriculum View original

  Is this image relevant?

1 of 2

• Darwin's theory of natural selection provided the foundational concept for evolutionary algorithms
• Mendel's laws of inheritance influenced the representation of genetic information in computational models
• Population genetics research by Fisher, Haldane, and Wright contributed to understanding evolutionary dynamics
• Sewall Wright's concept of fitness landscapes inspired the visualization of solution spaces in optimization problems

Cybernetics and artificial intelligence

• Norbert Wiener's work on cybernetics introduced feedback loops and self-regulating systems
• Alan Turing's proposal of "learning machines" in 1950 sparked interest in machine intelligence
• Early AI research in the 1950s and 1960s explored problem-solving techniques inspired by human cognition
• Marvin Minsky and John McCarthy's work on symbolic AI influenced early approaches to evolutionary computation

Foundational evolutionary algorithms

• Evolutionary algorithms form the core of evolutionary computation, simulating natural evolution processes
• These algorithms operate on populations of candidate solutions, iteratively improving them over generations
• Three main branches of evolutionary algorithms emerged independently in the 1960s and 1970s

Genetic algorithms

• Developed by John Holland at the University of Michigan in the 1960s
• Use binary string representations of solutions (chromosomes)
• Employ genetic operators
  • Crossover combines genetic material from parent solutions
  • Mutation introduces random changes to maintain diversity
• Selection mechanisms favor fitter individuals for reproduction
• Applications include optimization, machine learning, and adaptive systems

Evolution strategies

• Originated from the work of Ingo Rechenberg and Hans-Paul Schwefel in Germany
• Focus on real-valued parameter optimization problems
• Use self-adaptation of strategy parameters (mutation step sizes)
• Employ (μ, λ) or (μ + λ) selection schemes
  • μ parents produce λ offspring
  • Selection occurs among offspring only (comma strategy) or among parents and offspring (plus strategy)
• Well-suited for continuous optimization and engineering design problems

Evolutionary programming

• Developed by Lawrence Fogel in the United States in the 1960s
• Originally designed for evolving finite state machines for prediction tasks
• Emphasizes behavioral changes rather than genetic recombination
• Uses mutation as the primary variation operator
• Selection is typically based on a tournament scheme
• Applied to various domains including machine learning and time series prediction

Key figures and contributions

• Pioneering researchers laid the groundwork for evolutionary computation
• Their work established distinct approaches that continue to influence the field today
• Contributions span theoretical foundations, algorithm design, and practical applications

John Holland's genetic algorithms

• Introduced the concept of adaptive systems based on genetic principles in the 1960s
• Developed the first formal framework for genetic algorithms in his 1975 book "Adaptation in Natural and Artificial Systems"
• Proposed the schema theorem to explain the power of genetic algorithms
• Introduced the building block hypothesis, suggesting that complex solutions are built from simpler, high-fitness components
• Influenced the development of classifier systems and other machine learning techniques

Rechenberg and Schwefel's evolution strategies

• Ingo Rechenberg initiated work on evolution strategies at the Technical University of Berlin in the 1960s
• Hans-Paul Schwefel joined the research and contributed to the development of multi-membered evolution strategies
• Introduced the concept of self-adaptation of strategy parameters
• Developed the (1+1)-ES and later the more general (μ+λ)-ES and (μ,λ)-ES algorithms
• Applied evolution strategies to complex engineering optimization problems (aerodynamics)

Fogel's evolutionary programming

• Lawrence Fogel introduced evolutionary programming in the 1960s
• Focused on evolving artificial intelligence through simulated evolution
• Developed methods for evolving finite state machines to predict symbol sequences
• Emphasized the importance of maintaining behavioral diversity in evolving populations
• His son, David Fogel, continued to advance evolutionary programming in the 1980s and 1990s

Milestones in evolutionary computation

• The field of evolutionary computation has seen significant growth and formalization since its inception
• Key events have helped establish it as a recognized discipline within computer science and artificial intelligence
• Milestones reflect the increasing academic and industrial interest in evolutionary algorithms

First international conferences

• 1985 First International Conference on Genetic Algorithms (ICGA) held in Pittsburgh, USA
• 1990 Parallel Problem Solving from Nature (PPSN) conference series began in Dortmund, Germany
• 1992 First IEEE Conference on Evolutionary Computation held in Orlando, USA
• These conferences provided platforms for researchers to share ideas and advancements in the field
• Helped establish evolutionary computation as a distinct research area within computer science

Establishment of academic journals

• 1993 Launch of "Evolutionary Computation" journal by MIT Press
• 1995 "IEEE Transactions on Evolutionary Computation" began publication
• 2001 "Genetic Programming and Evolvable Machines" journal established
• These peer-reviewed publications provided venues for in-depth research articles
• Contributed to the academic credibility and dissemination of evolutionary computation research

Formation of professional societies

• 1991 Establishment of the Genetic Programming Special Interest Group (SIGEVO) within ACM
• 1994 Foundation of the Evolutionary Programming Society
• 2005 Creation of ACM SIGEVO (Special Interest Group on Genetic and Evolutionary Computation)
• These societies promote research, organize conferences, and foster collaboration in the field
• Help standardize terminology and methodologies in evolutionary computation

Applications and impact

• Evolutionary computation techniques have found widespread use across various domains
• The field has significantly influenced both academic research and industrial applications
• Continuous advancements expand the range of problems that can be addressed using evolutionary approaches

Early industrial applications

• Optimization of gas pipeline systems using genetic algorithms in the 1980s
• Scheduling problems in manufacturing and logistics (job shop scheduling)
• Aircraft wing design optimization using evolution strategies
• Antenna design for NASA space missions (evolved antenna designs)
• These applications demonstrated the practical value of evolutionary algorithms in solving real-world problems

Influence on artificial intelligence

• Evolutionary computation provided new approaches to machine learning and optimization
• Genetic programming enabled automatic generation of computer programs
• Neuroevolution techniques for evolving artificial neural networks
• Evolutionary algorithms used in reinforcement learning for policy optimization
• Contributed to the development of hybrid AI systems combining evolutionary and traditional AI techniques

Interdisciplinary research areas

• Bioinformatics and computational biology (protein folding, gene expression analysis)
• Evolutionary robotics for designing robot morphologies and control systems
• Evolutionary art and music generation
• Financial modeling and trading strategy optimization
• Evolutionary approaches in chemistry for molecular design and drug discovery
• These applications showcase the versatility of evolutionary computation across diverse fields

Theoretical developments

• Theoretical advancements have provided insights into the behavior and performance of evolutionary algorithms
• These developments help explain why evolutionary algorithms work and guide their design and application
• Theoretical results have both supported and challenged commonly held beliefs about evolutionary computation

Schema theorem

• Proposed by John Holland in 1975 as a theoretical foundation for genetic algorithms
• Describes how beneficial gene combinations (schemata) are propagated through generations
• States that short, low-order, above-average schemata receive exponentially increasing trials in subsequent generations
• Formula: $E[m(H,t+1)] \geq m(H,t) \frac{f(H)}{f_{avg}} [1 - p_c \frac{\delta(H)}{l-1} - o(H)p_m]$
• Criticized for its limitations in explaining the full dynamics of genetic algorithms
• Sparked further research into the theoretical underpinnings of evolutionary algorithms

No free lunch theorem

• Introduced by David Wolpert and William Macready in 1997
• States that no single optimization algorithm outperforms all others across all possible problems
• Formally expressed as $\sum_f P(d_{y,m}|f,m,a_1) = \sum_f P(d_{y,m}|f,m,a_2)$
• Implications
  • No universal "best" evolutionary algorithm exists
  • Algorithm performance depends on problem characteristics
  • Importance of tailoring algorithms to specific problem domains
• Encouraged research into problem-specific algorithm design and hyper-heuristics

Convergence analysis

• Studies the conditions under which evolutionary algorithms converge to optimal solutions
• Markov chain models used to analyze the long-term behavior of evolutionary processes
• Takeover time analysis examines how quickly the best solution spreads through a population
• Runtime analysis provides bounds on the expected time to find optimal solutions
• Key results
  • Elitist algorithms converge to global optima given sufficient time
  • Mutation-only algorithms can solve any problem with non-zero probability
  • Crossover can significantly speed up optimization for certain problem classes
• Informs algorithm design choices and parameter settings for improved performance

Evolutionary computation paradigms

• Various evolutionary computation paradigms have emerged beyond the foundational algorithms
• Each paradigm addresses specific types of problems or introduces novel evolutionary mechanisms
• These approaches expand the applicability of evolutionary computation to diverse problem domains

Genetic programming

• Introduced by John Koza in the early 1990s
• Evolves computer programs represented as tree structures
• Uses genetic operators adapted for tree manipulation
  • Subtree crossover exchanges branches between parent trees
  • Mutation can modify nodes or introduce new subtrees
• Applications include
  • Automatic program synthesis
  • Symbolic regression for discovering mathematical expressions
  • Circuit design and optimization
• Challenges include bloat (uncontrolled growth of program size) and maintaining program validity

Differential evolution

• Developed by Storn and Price in 1995
• Designed for continuous parameter optimization problems
• Uses vector differences for creating new candidate solutions
• Algorithm steps
  1. Initialize population of candidate solutions
  2. For each vector, create a mutant vector using vector differences
  3. Perform crossover between the original and mutant vector
  4. Select the better of the trial vector and original vector
• Advantages include simplicity, effectiveness, and few control parameters
• Successfully applied to various engineering and scientific optimization problems

Particle swarm optimization

• Introduced by Kennedy and Eberhart in 1995
• Inspired by social behavior of bird flocking or fish schooling
• Particles move through the search space guided by their own best known position and the swarm's best known position
• Update equations for particle velocity and position
  • $v_i(t+1) = w v_i(t) + c_1 r_1 (p_i - x_i(t)) + c_2 r_2 (g - x_i(t))$
  • $x_i(t+1) = x_i(t) + v_i(t+1)$
• Effective for continuous optimization problems
• Variants include binary PSO and multi-objective PSO
• Applications in neural network training, power systems, and robotics

Integration with other techniques

• Evolutionary computation has been combined with various other computational and optimization techniques
• These integrations aim to leverage the strengths of different approaches and overcome individual limitations
• Hybrid methods often outperform pure evolutionary algorithms on specific problem classes

Hybrid algorithms

• Memetic algorithms combine evolutionary search with local search techniques
  • Incorporate problem-specific knowledge through local improvement operators
  • Balance global exploration and local exploitation
• Evolutionary algorithms with machine learning
  • Using neural networks to approximate fitness functions
  • Evolving neural network architectures and weights
• Integration with exact methods (matheuristics)
  • Combining evolutionary search with mathematical programming techniques
  • Using evolutionary algorithms to guide branch-and-bound or cutting plane methods
• These hybrids often achieve better performance than standalone methods on complex optimization problems

Multi-objective optimization

• Addresses problems with multiple, often conflicting objectives
• Pareto-based approaches seek to find a set of non-dominated solutions (Pareto front)
• Key algorithms
  • NSGA-II (Non-dominated Sorting Genetic Algorithm II)
  • SPEA2 (Strength Pareto Evolutionary Algorithm 2)
  • MOEA/D (Multi-objective Evolutionary Algorithm based on Decomposition)
• Performance metrics include hypervolume, inverted generational distance, and spread
• Applications in engineering design, portfolio optimization, and environmental management
• Challenges include maintaining diversity along the Pareto front and scaling to many objectives

Parallel evolutionary algorithms

• Exploit parallel computing architectures to improve performance and scalability
• Models of parallelization
  • Master-slave model for parallel fitness evaluation
  • Island model with multiple subpopulations and migration
  • Cellular model with local interactions between individuals
• Advantages
  • Reduced computation time for expensive fitness evaluations
  • Improved exploration through population diversity
  • Ability to tackle larger problem instances
• Implementations on multi-core CPUs, GPUs, and distributed computing environments
• Considerations include load balancing, communication overhead, and synchronization issues

Modern trends and future directions

• Evolutionary computation continues to evolve, adapting to new challenges and technologies
• Recent trends focus on scalability, integration with other AI techniques, and novel application domains
• Future directions aim to address limitations and expand the reach of evolutionary approaches

Big data and evolutionary computation

• Scaling evolutionary algorithms to handle large-scale optimization problems
• Techniques for reducing computational complexity and memory requirements
• Distributed and cloud-based implementations of evolutionary algorithms
• Evolutionary feature selection and dimensionality reduction for big data analytics
• Challenges include maintaining population diversity and effective selection in high-dimensional spaces
• Applications in data mining, pattern recognition, and large-scale model training

Evolutionary computation in machine learning

• Neuroevolution for designing and training deep neural networks
• Evolutionary reinforcement learning combining policy evolution with value-based methods
• Automated machine learning (AutoML) using evolutionary algorithms for hyperparameter optimization
• Evolving ensemble methods and decision trees for improved predictive modeling
• Integration with deep learning
  • Evolving neural architecture search
  • Using evolutionary algorithms for adversarial example generation and robustness testing
• These approaches aim to improve the performance and adaptability of machine learning systems

Emerging application domains

• Quantum computing optimization using evolutionary algorithms
• Evolutionary approaches in synthetic biology and genetic circuit design
• Climate modeling and optimization of climate change mitigation strategies
• Personalized medicine and drug discovery using evolutionary computation
• Autonomous systems and swarm robotics
• Cybersecurity applications (evolving intrusion detection systems, adaptive firewalls)
• These domains present new challenges and opportunities for evolutionary computation research
• Require adaptation of existing algorithms and development of novel evolutionary approaches