Genatic Algorithms

Genatic
Algorit
hm
Supervised By
Dr. Mahmoud
Abdelal
Eng. Waleed
Shaban
Eng. Mahmoud
Yasser
Table of Content
What are Genatic
1 Introduction 2
Algorithms
Basic Structure
Basics
3
Terminology
4 of Genetic
Algorithm
5 Knapsack Problem 6 Code
1
Introductio
n
Genetic Algorithm
• Genetic Algorithm (GA) is a search-based
optimization technique based on the principles
of Genetics and Natural Selection. It is
frequently used to find optimal or near-optimal
solutions to difficult problems which otherwise
would take a lifetime to solve.
Genetic Algorithm
https://www.youtube.com/watch?v=7VM9YxmUL
uo
Introduction to
Optimization
• Optimization is the process of making
something better.
2
What are Genetic
Algorithms?
• Nature has always been a great source of
inspiration to all mankind. Genetic Algorithms
(GAS) are search based algorithms based on the
concepts of natural selection and genetics.
• GAS are a subset of a much larger branch of

computation known as Evolutionary Computation.
3
Basic Terminology
• Population: is a subset of all the possible
(encoded) solutions to the given problem.
• Chromosome: is one such solution to the given
problem.
• Gene: is one element position of a chromosome.
• Allele: is the Value a gene takes for a particular
chromosome.
Example
• Genotype: is the population in the
computation space in which the solutions are
represented in a way which can be easily
understood and manipulated using a
computing system.
• Phenotype: is the population in the actual

real world solution space in which solutions are
represented in a way they are represented in
real world situations.
phenotype and genotype spaces are the same.
However,
in most of the cases, the phenotype and
genotype spaces
are different.
Decoding is a process of transforming a
solution from the genotype to the phenotype
space.
Encoding is a process of transforming from the
phenotype
to genotype space.
Decoding should be fast as it is carried out

repeatedly in a GA during the fitness value
• Fitness Function: simply defined is a
function which takes the solution as input and
produces the suitability of the solution as the
output.
In some cases, the fitness function and the
objective
function may be the same, while in others
it might be
different based on the problem.
• Genetic Operators: These alter the genetic

composition of the offspring.
These include crossover, mutation,
selection, etc.
4
Basic Structure of
Genetic Algorithm
Genotype Representation
• Binary Representation
• Real Valued Representation
• Integer Representation
• Population is a subset of solutions in the
current generation
• Set of chromosomes
• Population Initialization
1. Random Initialization
2. Heuristic Initialization
Fitness Function
• Takes a candidate solution to the problem as
input and produces as output
• The objective is to either maximize or minimize

the given objective function
Parent Selection
• Fitness Proportionate Selection
Roulette Wheel Selection
Parent Selection
• Tournament Selection
Survivor Selection
• Age Based Selection
Survivor Selection
• Fitness Based Selection
Crossover
• one parent is selected and one or more off-
springs are produced using the genetic material
of the parents
• One Point Crossover

Crossover
• Multi Point Crossover
• Uniform Crossover
Mutation
• used to maintain and introduce diversity in the
genetic population
• Mutation Operators:
• Bit Flip Mutation
• Swap Mutation
Mutation
• Scramble Mutation
• Inversion Mutation
Termination Condition
• When there has been no improvement in the
population for X iterations.
• When we reach an absolute number of

generations.
• When the objective function value has reached

a certain pre-defined value
5
Knapsack
Problem
• The knapsack problem or rucksack problem
is a problem in combinatorial optimization:
Given a set of items, each with a weight and a
value, determine the number of each item to include
in a collection so that the total weight is less than or
equal to a given limit and the total value is as large
as possible.
It derives its name from the problem faced by
someone who is constrained by a fixed-size
knapsack and must fill it with the most valuable
items.
Item Number
Chromosome
Profit Values
Weight Values
Knapsack capacity = 15
Total associated profit = 18
Last item not picked as it exceeds knapsack capacity
6
Code

Genatic Algorithms

Uploaded by

Copyright:

Available Formats

Genatic Algorithms

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Genatic Algorithms

Uploaded by

Copyright:

Available Formats

Genatic

• GAS are a subset of a much larger branch of

• Phenotype: is the population in the actual

Decoding should be fast as it is carried out

• Genetic Operators: These alter the genetic

• Real Valued Representation

• The objective is to either maximize or minimize

• One Point Crossover

• When we reach an absolute number of

• When the objective function value has reached

You might also like