genetic_algorithms - 4

Genetic Algorithms & Evolutionary Computation

Introduction

• Presenter: Dr. Matthia Sabatelli

• Date: September 30th, 2024

• Agenda:

  • Motivation & General Principles

  • Genetic Algorithms

  • Genetic Programming

  • Practical Applications

Motivation & General Principles

History of Genetic Algorithms

• 1960s: Development began by John Holland, considered the father of Algorithmic Evolution.

• 1980s: Successful applications emerged.

• 1990s: Evolution led to Genetic Programming.

• Current Status: GAs are less popular despite their capability to solve specific classes of problems.

Key Characteristics of Genetic Algorithms

• Learning Mechanism: Simulates evolution and falls under search techniques.

• Search Type: Categorized as Global Search Heuristics that explore solution spaces through mutation and recombination rather than a systematic search.

Process of Genetic Algorithms

1. Initial Problem & Guess Generation:

   • Generate a set of potential solutions.

2. Evaluation:

   • Solutions are assessed based on performance.

3. Recombination:

   • Successful solutions interact to produce new solutions.

4. Iteration:

   • Process repeats until a satisfactory solution is found or a stopping criterion is met.

Reasons for Popularity in the 80s and 90s

• Evolution's efficiency in nature applied to AI.

• Ability to search through complex hypothesis spaces.

• Easy parallelization, leveraging powerful hardware.

Genetic Algorithms

Core Components

1. Learning Problem: Defines the problem to be solved.

2. Fitness Function: Evaluates how well solutions perform (denoted as f(x)).

3. Initial Pool of Solutions: e.g., programs that can play chess.

4. Evolution Strategy: Method for modifying solutions based on evaluation outcomes.

Practical Example: The MAXONE Problem

• Objective: Maximize the number of ones in a binary string (e.g., from 1011010110 to 1111111111).

• Initial Generation G1:

  • Randomly generated solutions, e.g., {0101100001, 1100010001, 1111110000, 1010101111, 0000000010}.

• Evaluation:

  • Count ones in each string to score solutions (e.g., 3 ones for 0010100001).

• Selection of Fittest: Retain only the best solutions for the next generation.

• Creation of New Solutions:

  • Perform mating/crossover between fittest participants to create new candidates.

Genetic Operators

Crossover

• Definition: Produces new offspring from parent solutions by sharing bits.

• Types:

  • Single-Point Crossover: Exchange portions of two parent strings.

  • Two-Point Crossover: More complex mating strategy involving two positions for crossover.

• Outcome: Generates children that inherit characteristics from both parents, enhancing diversity and potential solution quality.

Mutation

• Definition: Introduces random alterations to a solution to maintain genetic diversity within a population.

• Importance: Prevents premature convergence to local optima.

Genetic Programming

• Definition: An extension of Genetic Algorithms where individuals are computer programs, not just binary strings.

• Representation: Programs are represented as trees where functions are nodes and arguments are child nodes.

  • e.g., Expression: sin(x) + px^2 + y represented as a functional program tree.

• Genetic Operators: Utilizes the same genetic operators but applies to program structures, making evaluation computationally intensive. e.g. crossover and mutation the most common ones

Practical Applications

• Applications of Genetic Algorithms and Programming span various domains due to their adaptability to complex optimization problems.

Pros & Cons of Genetic Algorithms

Advantages

• Easy to understand and implement.

• Suitable for multi-objective optimization.

• Capable of distributed learning across tasks.

Limitations

• No guaranteed convergence to the global optimum.

• Evaluation function can be computationally expensive.

• Requires careful tuning of multiple implementation parameters.

• Need for effective termination criteria.

Conclusion

• The study of Genetic Algorithms and their applications continues to evolve, with ongoing research into their efficiency and effectiveness in solving complex problems.