Scribd
Upload
8 views8 pages

Understanding Genetic Algorithms Basics

Uploaded by

cherishma.puli1939
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
8 views8 pages

Understanding Genetic Algorithms Basics

Uploaded by

cherishma.puli1939
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Unit 4: Genetic Algorithms (Part 2)

Genetic Algorithms

A Genetic Algorithm (GA) is a population-based evolutionary optimization technique


inspired by the process of natural selection and genetics, used to find optimal or near-optimal
solutions to complex problems.

Biological Motivation

GA is based on Darwin’s principle of “Survival of the Fittest”, where:

 Individuals compete for survival


 Fitter individuals reproduce
 Genetic material is passed to next generation

Why Genetic Algorithms?

Traditional optimization techniques:

 Depend on gradient information


 Often get trapped in local optima
 Fail for non-linear and discontinuous problems

GA overcomes these by:

 Performing global search


 Using probabilistic rules
 Exploring multiple solutions simultaneously

Key Characteristics

 Population-based search
 Stochastic operators
 Fitness-driven evolution
 No domain-specific knowledge required
2. Components of Genetic Algorithm

A Genetic Algorithm consists of the following major components:

Chromosome Representation

 Encodes a solution
 Types:
o Binary encoding
o Real-valued encoding
o Permutation encoding
o Tree encoding

2. Population

 Set of chromosomes
 Population diversity is crucial
 Larger population improves exploration

3. Fitness Function

 Measures quality of solution


 Guides selection
 Problem-dependent

4. Selection Mechanism

 Selects individuals for reproduction


 Fitter individuals get higher chance

Examples:

 Roulette Wheel Selection


 Tournament Selection
 Rank Selection

5. Genetic Operators

 Crossover
 Mutation
6. Control Parameters

 Population size
 Crossover probability
 Mutation probability
 Number of generations

3. GA Cycle of Reproduction

The GA cycle of reproduction describes the iterative process through which a population
evolves across generations.

Steps in GA Cycle

1. Initialization

 Random generation of population

2. Fitness Evaluation

 Evaluate fitness of each chromosome

3. Selection

 Select parents based on fitness

4. Crossover

 Exchange genetic material

5. Mutation

 Introduce random changes

6. Replacement

 Create new generation

7. Termination
 Stop when condition is met

Key Features

 Iterative improvement
 Fitness-based survival
 Balance between exploration and exploitation

4. Crossover Operator

Crossover is a genetic operator that combines genetic material from two parent
chromosomes to produce new offspring.

Purpose

 Exploit good solutions


 Combine useful traits
 Speed up convergence

Types of Crossover

1. Single-Point Crossover

 One crossover point


 Exchange tail segments

2. Two-Point Crossover

 Two crossover points


 Swap middle segment

3. Uniform Crossover

 Random gene exchange using a mask

Crossover Probability

 Usually between 0.6 and 0.9


Advantages

 Preserves building blocks


 Encourages diversity

Limitations

 May disrupt good solutions


 Risk of premature convergence

5. Mutation Operator

Mutation is a genetic operator that randomly alters one or more genes in a chromosome.

Purpose

 Maintain population diversity


 Prevent premature convergence
 Explore new areas of search space

Types of Mutation

 Bit-flip mutation
 Swap mutation
 Gaussian mutation

Mutation Probability

 Very small (0.001 – 0.01)

Role in Evolution

 Acts as innovation source


 Helps escape local optima

Advantages

 Introduces new genetic material


 Maintains diversity
Disadvantages

 Too much mutation destroys good solutions

6. Genetic Programming (15 Marks)

. Genetic Programming (GP) is an evolutionary technique that evolves computer


programs instead of fixed-length chromosomes

Representation

 Tree-structured programs
 Internal nodes → functions
 Leaf nodes → terminals

GP Operators

Subtree crossover
Subtree mutation

Fitness Evaluation

 Program performance on problem

Applications

 Symbolic regression
 Automatic code generation
 Controller design

GA vs GP

Aspect GA GP
Representation String Tree
Output Parameters Programs

7. Models of Evolution and Learning (15 Marks)


1. Darwinian Model

 No inheritance of learned traits


 Evolution only through selection

2. Lamarckian Model

 Acquired traits are inherited


 Learning directly affects evolution

3. Baldwin Effect

 Learning improves fitness


 Traits not inherited
 Indirect evolutionary benefit

Relevance to ML

 Hybrid GA + local search


 Improved convergence

8. Applications of Genetic Algorithms

Optimization Problems

 Traveling Salesman Problem


 Scheduling
 Resource allocation

Machine Learning

 Feature selection
 Rule discovery
 Neural network training

Engineering

 Control systems
 Circuit design
 Robotics

Other Domains

 Bioinformatics
 Finance
 Game playing
Advantages in Applications

 Handles large search spaces


 Works with noisy data
 Flexible and robust

You might also like