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
Initial Problem & Guess Generation:
Generate a set of potential solutions.
Evaluation:
Solutions are assessed based on performance.
Recombination:
Successful solutions interact to produce new solutions.
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
Learning Problem: Defines the problem to be solved.
Fitness Function: Evaluates how well solutions perform (denoted as f(x)).
Initial Pool of Solutions: e.g., programs that can play chess.
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.