WK4_5: Genetic Algorithms

• Artificial Intelligence Programming
• Higher Education (degree)

Welcome to Week 4 & 5

Genetic Algorithms 

Module Lecturer: Dr Raghav Kovvuri

Email: [e-mail]

Evolutionary Computation?

What is Evolutionary Computation?

• Inspired by biological evolution and natural selection

Key principles:

1. Population of potential solutions
2. Selection based on fitness
3. Reproduction with variation (crossover and mutation)

• Iterative process: solutions improve over generations
• Applicable to complex optimization and search problems

Evolutionary Algorithms

                      Types of Evolutionary Algorithms?

1) Genetic Algorithms (GA):

• Work with fixed-length strings (often binary)
• Used for optimization problems

2) Genetic Programming (GP):

• Evolves computer programs (often tree structures)
• Used for automatic programming and symbolic regression

3) Evolution Strategies (ES):

• Focuses on real-valued parameters
• Self-adapting mutation rates

4) Evolutionary Programming (EP):

• Originally developed for evolving finite state machines
• Now similar to ES but with fixed mutation rates

Genetic Algorithms

• Definition:  Search heuristic mimicking    natural evolution
• Purpose: Optimize solutions to complex problems

Key components:

1. Chromosomes: Encode potential solutions
2. Fitness function: Evaluates solution quality
3. Genetic operators: Create new solutions

Process: Initialize population → Evaluate fitness → Select parents → Apply genetic operators → Repeat

Chromosome Representation

1) Binary strings: [1,0,1,1,0]

• Used for boolean or discrete problems
• Example: Knapsack problem

2) Real numbers: [3.14, 2.71, 1.41]

• Used for continuous optimization
• Example: Function optimization

3) Permutations: [3,1,4,2,5]

• Used for ordering problems
• Example: Traveling Salesman Problem

Fitness Function

Purpose: Quantifies the quality of a solution

Characteristics:

• Problem-specific
• Guides the evolution process

Examples:

• Maximizing: f(x) = x^2 + 5x (for function optimization)
• Minimizing: f(route) = total distance (for TSP)
• Multi-objective: Balance multiple criteria

Genetic Operators

1) Selection:

• Roulette wheel: Probability proportional to fitness
• Tournament: Select best from random subgroup

2) Crossover:

• Single-point: Exchange segments after a random point
• Two-point: Exchange segment between two random points
• Uniform: Randomly exchange individual bits

3) Mutation:

• Bit-flip: Invert bits with low probability
• Gaussian: Add random value from normal distribution

Implementing a Simple GA

[Code as  provided in Canvas]_SimpleGA.py

Key steps in the algorithm:

Step 1: Initialize random population

Step 2: Evaluate fitness of each individual

Step 3: Select parents based on fitness

Step 4: Create offspring through crossover

Step 5: Apply mutation to maintain diversity

Step 6: Replace old population with new generation

• Repeat steps 2-6 for specified number of generations

• Modify the TARGET_SOLUTION and observe how it affects the algorithm's performance.
• Adjust the POPULATION_SIZE and discuss its impact on convergence speed and solution quality.
• Change the crossover and mutation probabilities in the crossover method and analyze the effects.

Which of the following best describes the inspiration for Genetic Algorithms?

1. Mathematical logic
2. Biological evolution and natural selection
3. Computer hardware architecture
4. Classical physics

Genetic Algorithms are particularly well-suited for:

1. Simple, linear problems with clear solutions
2. Complex, multi-dimensional problems with large search spaces
3. Problems requiring exact, deterministic solutions
4. Problems with a small, well-defined set of possible solutions

Which of the following is NOT a typical genetic operator used in Genetic Algorithms?

1. Selection
2. Crossover
3. Mutation
4. Compilation

The concept of 'population' in Genetic Algorithms refers to:

1. The total number of iterations the algorithm performs
2. A set of potential solutions to the problem
3. The final output of the algorithm
4. The set of constraints in the problem definition

In the context of Genetic Algorithms, 'fitness' refers to:

1. How well a potential solution solves the problem
2. Biological evolution and natural selection
3. The speed at which the algorithm converges
4. The complexity of the problem being solved

Topics for Self-Learning

Canvas Discussion Task: Choose one topic, research it, and share a brief summary and its potential applications.

  

1. Why use Genetic Algorithm over a Gradient-based Algorithm?
2. Are Genetic Algorithms falling behind other AI techniques?
3. Did LLMs use Genetic Algorithms?
4. Advantages and Limitation of Genetic Algorithm.
5. Real-world case studies of Genetic Algorithms.

        Each topic extends the basic concepts covered in class and offers opportunities for              deeper exploration and application.

Genetic Programming Basics

Goal: Automatically create computer programs

Representation: Usually tree structures

• Internal nodes: Functions (e.g., +, -, *, /)
• Leaf nodes: Terminals (variables or constants)

Key difference from GA: Variable-length solutions

Applications: Symbolic regression, automatic programming

GP Components

Crossover:

• Select crossover points in two parent trees
• Swap subtrees at these points
• Creates two new offspring

Mutation:

• Randomly select a node in the tree
• Replace subtree at that node with a new random subtree

Challenges: Maintaining tree validity and managing tree growth

Simple GP Implementation

[Code as provided in Canvas]_ GPImplemenation.py

Key aspects:

• Tree representation using nodes
• Recursive tree generation and evaluation
• Separation of functions and terminals

• GPNode: Represents the structure of the tree.
• generate_tree: Shows how random trees are created.
• evaluate_tree: Demonstrates how expressions are evaluated.
• visualize_tree: Helps students understand the tree structure visually.
• tree_to_expression: Converts the tree to a readable mathematical expression.

GA vs GP

1) Genetic Algorithms:

• Fixed-length solutions
• Often used for parameter optimization
• Simpler to implement and analyze

2) Genetic Programming:

• Variable-length solutions (programs)
• Can discover novel program structures
• More complex, but potentially more powerful

         Choice depends on problem nature and desired output

Real-world Applications

Genetic Algorithms:

• Design optimization (engineering, architecture)
• Financial modeling and portfolio optimization
• Machine learning feature selection
• Scheduling and resource allocation

Genetic Programming:

• Symbolic regression for data analysis
• Evolving game strategies
• Circuit design and optimization
• Automated bug fixing in software

Conclusion

Evolutionary computation: Powerful approach for complex problems

GA and GP: Complementary techniques with broad applications

Key takeaways:

• Population-based search
• Fitness-driven evolution
• Balance between exploration and exploitation

Future directions: Hybridization with other AI techniques, tackling real-world complexity