Basic Genetic Algorithm
BY
DR. A. AMEER RASHED KHAN, M.SC., M.SC.,(PSYH.) M.PHIL., PHD.,
ASSISTANT PROCESSOR,
FACULTY OF ENGINEERING AND TECHNOLOGY,
SHARDA UNIVERSITY.
Basic Genetic Algorithm
A Genetic Algorithm (GA) is an optimization and search
technique based on principles of natural selection and genetics.
Genetic Algorithms are flexible, biology-inspired techniques for
optimization problems, where solutions evolve over time through
selection, crossover, and mutation.
What is Optimization?
Optimization is the process of finding the best possible solution to
a problem, given a set of constraints or limitations.
It's about making something as efficient, effective, or desirable as
possible.
Basic GA Framework (Steps)
1️⃣Initialization: Generate an initial population of possible solutions (chromosomes) randomly.
2️⃣Evaluation: Calculate the fitness of each individual using a fitness function.
3️⃣Selection: Select individuals for reproduction based on fitness (better solutions have higher
chances).
4️⃣Crossover (Recombination): Combine two parent chromosomes to produce new offspring.
5️⃣Mutation: Randomly alter genes in some offspring to maintain diversity.
6️⃣Replacement: Form a new population with selected offspring (and sometimes a few parents).
7️⃣Termination: Repeat steps 2–6 until a stopping condition is met (e.g., number of generations or
satisfactory fitness value).
Different GA Architectures
Architecture Description Example
Standard GA with fixed population and single
Simple GA Classic optimization problems
objective
Divides population into sub-populations, evolves
Parallel GA Distributed computing
them separately, then merges
Only a few individuals are replaced in each
Steady-State GA Real-time adaptive systems
generation
Micro GA Very small populations with frequent restarts Fast convergence problems
Combines GA with other techniques (e.g., local Complex, multi-modal
Hybrid GA
search, neural networks) optimization
GA Operators
1. Encoding (Representation)
2. Selection
3. Crossover (Recombination)
4. Mutation
1️⃣Encoding (Representation)
Represents possible solutions in a GA.
Common types:
Binary Encoding: Uses strings of 0s and 1s.
Real-Value Encoding: Uses actual numbers.
Permutation Encoding: Useful for ordering problems (like TSP).
2️⃣Selection
Chooses individuals for reproduction based on fitness.
Popular methods:
Roulette Wheel Selection (fitness proportionate)
Tournament Selection (randomly selects best out of a group)
Rank Selection (assigns ranks based on fitness)
Elitism (best individuals are always carried forward)
3️⃣Crossover (Recombination)
Combines genetic material from two parents.
Common techniques:
•Single-Point Crossover
•Two-Point Crossover
•Uniform Crossover
4️⃣Mutation
Randomly alters genes to introduce new traits.
Types:
Bit Flip Mutation (for binary)
Swap Mutation (for permutations)
Gaussian Mutation (for real values)
Summary
GA Component Purpose Example
Encoding Represent solutions Binary, Real, Permutation
Selection Choose parents Roulette, Tournament
Crossover Mix parents' genes Single-Point, Uniform
Mutation Add variation Bit Flip, Swap
Application Find optimal solution Maximize f(x)=x2f(x) = x^2f(x)=x2
