Genetic Algorithms (GA) are a type of search algorithm used
for problem-solving, based on the principles of Natural Selection and Genetics.
They are widely used to solve complex Optimization problems.
In simple terms, it involves a computer simulating an
"evolutionary" process to find the best solution to a problem.
Basic Steps and Concepts
- Initialization:
A basic "population" consisting of several solution candidates
is created randomly. Each solution is called a "chromosome."
- Fitness
Evaluation: A "Fitness Function" is used to determine
how well each chromosome (solution) fits the problem. Those with the
highest fitness scores are the best solutions.
- Selection:
Chromosomes with high fitness scores (the best solutions) are selected for
the next generation. Just like in nature, the solutions that "survive
better" are chosen.
- Crossover
(Recombination): Two selected chromosomes (parents) are combined to
create a new "child" (solution candidate). This mixes the traits
of the parents.
- Mutation:
A random part (gene segment) of the new chromosome is slightly altered.
This helps in exploring "new" solutions and prevents the
algorithm from getting stuck in a single solution.
- New
Generation: A new population is formed from the new chromosomes
created through crossover and mutation.
This process is repeated until the best solution (the
chromosome with the highest fitness) is found.
Example Applications
- Engineering
Design Optimization
- Timetabling
- Complex
search problems like the Travelling Salesman Problem.
How a Simple Genetic Algorithm Works: An Example
The Problem:
Find the value of xbetween 0 and 31 that gives the
Maximum Value using the function f(x) = x^2.
1. Encoding (The Chromosome)
Our solutions are numbers from 0 to 31.
The number 31 can be represented in Binary (5 bits).
The chromosome (solution candidate) is a string of 5 bits.
Example: x = 13 is represented in binary as 01101.
2. Initial Population
Let's create an initial population of 4 chromosomes
randomly:
|
Chromosome (Binary) |
Decimal Value (x) |
Fitness f(x)=x2 |
|
10100 |
20 |
400 |
|
01111 |
15 |
225 |
|
11000 |
24 |
576 |
|
00010 |
2 |
4 |
Current best solution: x = 24 (f(x) = 576).
3. Selection
Chromosomes with the highest fitness values are selected as
parents.
We select 11000 (24) and 10100 (20).
4. Crossover
Mixing the genes of the selected parents:
- Parent
1: 10100
- Parent
2: 11000
Let's choose a random Crossover Point, for example,
after the third bit:
- Split
Parts: 101 | 00 and 110 | 00
We get two new children:
- Child
A: First part of Parent 1 + Second part of Parent 2 = 10100
- Child
B: First part of Parent 2 + Second part of Parent 1 = 11000
5. Mutation
Flipping a randomly selected bit (e.g., 0 to 1 or 1 to
0):
- Child
A (10100): Change the last bit to 10101
- Child
B (11000): Change the fourth bit to 11010
New Generation results:
- Child
A: 10101 (x=21) to f(x)=441
- Child
B: 11010 (x=26) to f(x)=676
6. Replacement and Iteration
Now, these two new children replace the low-fitness
chromosomes in the original population.
Our new best solution is x = 26 (f(x) = 676). This is
better than the original best value of 576!
#GeneticAlgorithms #ArtificialIntelligence #DataScience #Optimization #EvolutionaryComputing #Programming #CodingTutorial #TechBlog
0 Comments