Genetic Algorithms & Evolutionary Computation: Operators, Fitness, and Applications

Core Concepts: How Genetic Algorithms Work

1. Biological Inspiration

Genetic algorithms (GAs) are population-based metaheuristic optimization algorithms inspired by Darwin’s theory of evolution. They mimic natural selection to iteratively improve a candidate solution to an optimization problem.

2. Key Definitions

• Population: A set of candidate solutions (e.g., 100 possible routes for a delivery truck).
• Chromosome: A single candidate solution (e.g., one route encoded as a sequence of genes).
• Gene: A parameter of the solution (e.g., a city ID in the route).
• Fitness Function: Evaluates how "good" a solution is (e.g., total distance traveled).
• Generations: Iterations where the population evolves toward better solutions.

How Genetic Algorithms Solve Problems

Step-by-Step Process

1. Initialization: Randomly generate an initial population of solutions.
2. Evaluation: Compute the fitness of each solution using the fitness function.
3. Selection: Choose parents for reproduction based on fitness (e.g., tournament selection).
4. Crossover (Recombination): Combine parents to produce offspring (e.g., single-point crossover).
5. Mutation: Introduce random changes to maintain diversity (e.g., flip a bit in a binary chromosome).
6. Termination: Stop when a satisfactory solution is found or a maximum generation is reached.

Operators in Genetic Algorithms

1. Selection Operators

Selects parents for reproduction based on fitness. Common methods:

• Roulette Wheel Selection: Probability proportional to fitness.
• Tournament Selection: Randomly pick k individuals; the best one wins.
• Rank-Based Selection: Assign ranks instead of raw fitness scores.

Example: Suppose we optimize a function $f(x)=x^2$ for $x\in [0,10]$.

• Population: [3, 7, 2, 9]
• Fitness: [9, 49, 4, 81] (higher is better)
• Roulette Wheel Probabilities: [9/142, 49/142, 4/142, 81/142]

2. Crossover Operators

Combines two parent chromosomes to produce offspring. Common types:

• Single-Point Crossover: Split at a random point and swap tails.
• Two-Point Crossover: Split at two points and swap the middle segment.
• Uniform Crossover: Each gene has a 50% chance of coming from either parent.

Example (Single-Point Crossover):

• Parent 1: [1, 0, 1, 1, 0]
• Parent 2: [0, 1, 0, 1, 1]
• Crossover Point: 2
• Offspring 1: [1, 0, 0, 1, 1]
• Offspring 2: [0, 1, 1, 1, 0]

3. Mutation Operators

Introduces random changes to maintain genetic diversity. Common types:

• Bit Flip Mutation: Flip a bit in a binary chromosome (e.g., 1 → 0).
• Gaussian Mutation: Add small random noise to a real-valued gene.
• Swap Mutation: Swap two genes in a sequence.

Example (Bit Flip Mutation):

• Chromosome: [1, 0, 1, 1, 0]
• Mutation Point: 3 (flip the 3rd bit)
• Mutated Chromosome: [1, 0, 0, 1, 0]

Fitness Functions and Problem Encoding

1. Encoding Schemes

• Binary Encoding: Represent solutions as binary strings (e.g., [1, 0, 1]).
• Real-Valued Encoding: Use floating-point numbers (e.g., [3.2, 5.7]).
• Permutation Encoding: Represent sequences (e.g., [2, 5, 1] for a route).

Example (Binary Encoding for Knapsack Problem):

• Items: [ (w=2, v=3), (w=3, v=4), (w=1, v=2) ]
• Chromosome: [1, 0, 1] (take item 1 and 3, skip item 2)
• Fitness: Total value without exceeding weight limit.

2. Fitness Function Design

The fitness function must:

1. Reflect the problem’s objective (maximize/minimize).
2. Handle constraints (e.g., knapsack weight limit).
3. Be differentiable if using gradient-based methods (though GAs don’t require this).

Example (Traveling Salesman Problem - TSP):

• Fitness: $\text{Fitness}=\frac{1}{\text{Total Distance}}$
• Goal: Maximize fitness (minimize distance).

Advantages and Disadvantages of GAs

Real-World Applications

1. Optimization Problems

• eSewa (Nepal): GAs optimize delivery routes for couriers to minimize fuel costs and time.
• Daraz (Logistics): Uses GAs to schedule warehouse pick-and-pack operations efficiently.
• NTC (Nepal Telecom): Optimizes network traffic routing to reduce latency.

2. Machine Learning and Neural Networks

• Hyperparameter Tuning: GAs optimize neural network architectures (e.g., number of layers, neurons).
• Feature Selection: Selects the best subset of features for a dataset (e.g., in medical diagnosis).

3. Game AI and Strategy

• Pathao (Ride-Hailing): Uses GAs to dynamically adjust surge pricing during peak hours.
• NEPSE (Stock Market): Predicts stock trends by evolving trading strategies.

Worked Example: Optimizing a Delivery Route for Pathao

• Problem: Find the shortest route for a driver serving 4 locations: A → B → C → D → A.
• Encoding: Permutation of [A, B, C, D] (e.g., [B, A, D, C]).
• Fitness: Inverse of total distance.
• GA Steps:
  1. Initialize population: [A,B,C,D], [B,A,D,C], [C,D,A,B], [D,C,B,A].
  2. Evaluate fitness (shorter distance = higher fitness).
  3. Select parents (e.g., [B,A,D,C] and [C,D,A,B]).
  4. Crossover: Swap middle two genes → [B,C,A,D].
  5. Mutate: Swap A and D → [B,C,D,A].
  6. Repeat until convergence (e.g., [A,B,C,D] is found).

Comparison with Other Search Techniques

Exam Tip

1. Understand the Process: Always show the initialization → selection → crossover → mutation → termination steps in your answer.
2. Fitness Function: Clearly define how you compute fitness (e.g., "maximize profit" or "minimize distance").
3. Encoding: Specify whether you’re using binary, real-valued, or permutation encoding.
4. Parameters: Mention key GA parameters (population size, mutation rate, crossover type) in your explanation.
5. Real-World Tie-In: Relate problems to eSewa routes, Daraz logistics, or NTC network optimization for full marks.
6. Pseudocode: If asked to "discuss how GA works," provide a high-level pseudocode like this:

   def genetic_algorithm(population, fitness_fn, max_generations):
       while not termination_condition(population, max_generations):
           evaluate_fitness(population, fitness_fn)
           new_population = select(population)
           new_population = crossover(new_population)
           new_population = mutate(new_population)
           population = new_population
       return best_solution(population)
   

Visual: Game Tree for GA Exploration

graph TD
    A["Generation 0"] --> B["[A,B,C,D]"]
    A --> C["[B,A,D,C]"]
    A --> D["[C,D,A,B]"]
    A --> E["[D,C,B,A]"]
    B --> F["Fitness: 1/20"]
    C --> G["Fitness: 1/15"] --> H["Selected for Crossover"]
    D --> I["Fitness: 1/18"]
    E --> J["Fitness: 1/22"]
    H --> K["Crossover with [C,D,A,B]"]
    K --> L["Offspring: [B,C,A,D]"]
    L --> M["Mutation: Swap A,D → [B,C,D,A]"]
    M --> N["Generation 1"]
    N --> O["[B,C,D,A] (Best So Far)"]