Notes on Binary Coded Genetic Algorithm (BGA) Module

Introduction

• Module 2 focuses on Binary Coded Genetic Algorithm (BGA).
• This session covers the introduction, an example, operators, and processes involved in BGA.

Recap of Module 1

• Started with optimization and search definitions.
• Discussed applications of evolutionary computation techniques.
• Addressed properties of complex optimization problems.
• Covered mathematical formulations: objective function, constraints, variable bounds, and types.
• Identified sensitive decision variables for objective functions and constraints.
• Discussed equality and inequality constraints.
• Noted duality principle for maximization and minimization.
• Reviewed numerical optimization techniques and limitations of conventional methods.
• Introduced evolutionary computation principles: genetics, natural evolution, survival of the fittest.
• Explained the generalized framework for EC techniques, along with advantages and limitations.
• Discussed behavior on one-dimensional landscapes and the no free lunch theorem.

Overview of BGA Process

• Step 1: Solution Representation
  • Solutions represented using binary strings.
• Step 2: Input Parameters
  • Setting parameters for running BGA.
• Step 3: Initial Population
  • Creating the parent population.
• Step 4: Evaluation
  • Evaluating the population for fitness.
• Step 5: Selection
  • Using survival of the fittest; creating a mating pool (M_t).
• Step 6: Variation
  • Performing crossover and mutation to generate new solutions.
• Step 7: Population Evaluation
  • Evaluating new solutions generated from crossover/mutation.
• Step 8: Survival
  • Selecting solutions for the next generation from parent and offspring populations.
• Step 9: Generation Counter
  • Incrementing the generation counter.
• Step 10: Termination Condition
  • Deciding based on maximum generations.

Solution Representation

• Decision variables represented using Boolean (0, 1).
  • Examples: Transportation problem, unit commitment problem in electrical engineering.
• Can also represent real, discrete, and integer variables.

Example: Real Variable Representation

• Example of a real variable, x_i, with a string length of 5.
• Maximum value of binary string: 31 (all bits = 1).
• Minimum value of binary string: 0 (all bits = 0).
• Scaling function used for binary to real conversion.
• Example calculation leads to a real number derived from the binary string.

Precision and Scaling

• Precision calculated from the scaling function.
• Discussed how increasing precision requires longer binary strings.
• Observations on search space discreteness and its implications.

Example Case Study: Rosenbrock Function

• Objective: Minimize Rosenbrock function with specific variable bounds.
• Process of initial population generation explained.
• The encoding of solutions and evaluation of fitness values covered.

Selection Operator

• Selection process aims to identify and preserve good solutions.
• Binary Tournament Selection
  • Randomly selects pairs of solutions to identify winners based on fitness.
• Observations: Best solutions get more copies; worst solutions get none.

Crossover and Mutation

• Crossover Operator
  • Combines parent solutions to create offspring, exploring new search spaces.
• Mutation Operator
  • Perturbs solution to maintain diversity and avoid local optima.
• Described stochastic nature of both operators and their effects on fitness values.

Survival Stage

• Combines parent and offspring populations, selecting the best for the next generation.
• Mu plus Lambda Strategy
  • An elitist approach preserving good solutions.

Conclusion

• Recap of BGA process through the generalized framework.
• Illustrated steps through hand calculations and graphical representation of population evolution towards optimization.
• Emphasized the importance of crossover and mutation in generating diverse populations.

Thank You

• End of session.