Tutorial: Genetic Algorithms

Introduction to Genetic Algorithms

A Genetic Algorithm (GA) is an optimization technique inspired by the principles of natural selection and biological evolution.

Genetic algorithms are useful for finding good solutions to complex optimization problems where traditional mathematical techniques may be difficult to apply.

The basic idea is:

Generate a population of possible solutions → evaluate their quality → select better solutions → create new solutions through crossover and mutation → repeat until a satisfactory solution is found.

Genetic algorithms are commonly used in:

Optimization
Scheduling
Feature selection
Machine learning
Engineering design
Route optimization
Resource allocation
Function optimization

1. Basic Terminology

A genetic algorithm uses terminology inspired by biological evolution.

Population

A population is a collection of candidate solutions.

If there are $N$ candidate solutions, the population can be represented as:

P = \{C_1, C_2, \ldots, C_N\}

where each $C_i$ represents one chromosome.

Chromosome

A chromosome represents a complete candidate solution to the problem.

For a binary genetic algorithm, a chromosome may be:

C = 101101

For example:

C_1 = 101101, \qquad C_2 = 011010

Each chromosome represents a possible solution.

Gene

A gene is an individual element of a chromosome.

For:

C = 101101

the individual genes are:

1,\ 0,\ 1,\ 1,\ 0,\ 1

Thus, a chromosome consists of multiple genes.

Allele

An allele represents the possible value of a gene.

For a binary genetic algorithm, the possible alleles are:

\{0, 1\}

For example, $C = 101101$ contains genes whose alleles are either $0$ or $1$ .

2. Population Initialization

The first step in a genetic algorithm is to generate an initial population.

For example, suppose the chromosome length is $6$ and the population size is $4$ :

P = \{101101,\ 011010,\ 110011,\ 001110\}

The initial population can be generated randomly.
The algorithm then evaluates every chromosome using a fitness function.

3. Fitness Function

The fitness function determines how good a candidate solution is.

It maps a chromosome to a numerical fitness value:

F(C) \rightarrow \mathbb{R}

where:

$C$ = chromosome
$F(C)$ = fitness value

For a maximization problem, a larger fitness value generally represents a better solution.

Example:

Chromosome	Fitness
$101101$	$5$
$011010$	$3$
$110011$	$4$

The chromosome $101101$ has the highest fitness:

F(101101) = 5

and is therefore a strong candidate for selection.

4. Selection

Selection chooses chromosomes from the current population to become parents for reproduction.

The basic principle is:

Better chromosomes should have a higher probability of being selected.

One common method is fitness-proportional selection (also known as roulette-wheel selection).

The probability of selecting chromosome $i$ is:

P_i = \dfrac{F_i}{\displaystyle\sum_{j=1}^{N} F_j}

where:

$P_i$ = probability of selecting chromosome $i$
$F_i$ = fitness of chromosome $i$

5. Selection Example

Suppose four chromosomes have fitness values:

F_1 = 5,\quad F_2 = 3,\quad F_3 = 4,\quad F_4 = 3

The total fitness is:

F_{\text{total}} = 5 + 3 + 4 + 3 = 15

Selection probabilities:

\begin{align*} P_1 &= \dfrac{5}{15} \approx 0.333 \\ P_2 &= \dfrac{3}{15} = 0.200 \\ P_3 &= \dfrac{4}{15} \approx 0.267 \\ P_4 &= \dfrac{3}{15} = 0.200 \end{align*}

Chromosome	Fitness	Selection Probability
$C_1$	$5$	$0.333$
$C_2$

The chromosome with the highest fitness has the highest selection probability.

6. Other Selection Methods

Several selection strategies can be used in genetic algorithms.

Roulette-Wheel Selection

Selection probability is proportional to fitness:

P_i = \dfrac{F_i}{\sum_j F_j}

Tournament Selection

A small group of chromosomes is randomly selected, and the best chromosome from that group becomes a parent.

Rank Selection

Chromosomes are ranked according to fitness, and selection probabilities depend on their ranks rather than their raw fitness values.

7. Crossover

Crossover combines genetic information from two parent chromosomes to produce new offspring.

The two selected chromosomes are called parents.
The resulting chromosomes are called children or offspring.

Example:

text
1Parent 1: 101|101
2Parent 2: 011|010

If the crossover point is after the third gene:

text
1Child 1: 101|010
2Child 2: 011|101

Therefore:

101101 + 011010 \;\xrightarrow{\text{crossover}}\; 101010,\ 011101

Crossover allows useful characteristics from different parents to be combined.

8. Single-Point Crossover

In single-point crossover, one crossover point is selected.

Suppose:

P_1 = 110|101, \qquad P_2 = 001|110

After crossover:

C_1 = 110|110, \qquad C_2 = 001|101

The general representation is:

\begin{align*} P_1 &= A|B \\ P_2 &= C|D \end{align*}

After crossover:

\begin{align*} C_1 &= A|D \\ C_2 &= C|B \end{align*}

9. Two-Point Crossover

In two-point crossover, two crossover points are selected.

Example:

text
1Parent 1: 10|110|01
2Parent 2: 01|001|11

The middle segments are exchanged:

text
1Child 1: 10|001|01
2Child 2: 01|110|11

Two-point crossover can combine a larger internal section of two parent chromosomes.

10. Crossover Probability

Crossover is usually controlled by a crossover probability:

P_c \quad \text{where} \quad 0 \leq P_c \leq 1

For example:

P_c = 0.8

means that approximately $80\%$ of selected parent pairs are expected to undergo crossover.

A random number can be generated to determine whether crossover occurs.

11. Mutation

Mutation randomly changes one or more genes in a chromosome.

Mutation helps maintain genetic diversity and prevents the population from becoming too similar.

Example:

text
1Before: 101101
2After:  101001

The fifth gene has changed:

1 \rightarrow 0

Therefore, mutation produces a new chromosome.

12. Mutation Probability

Mutation is controlled by a mutation probability:

P_m \quad \text{where} \quad 0 \leq P_m \leq 1

Usually, mutation probability is relatively small.

For example:

P_m = 0.01

means that each gene has approximately a $1\%$ probability of mutation.

For a binary gene, mutation can be represented as:

0 \rightarrow 1 \quad \text{or} \quad 1 \rightarrow 0

13. Mutation Example

Suppose:

C = 101101

If the fifth gene mutates:

C' = 101001

The change is:

101101 \rightarrow 101001

Only one gene has changed. Mutation introduces new genetic information into the population.

14. Elitism

Elitism is a strategy in which one or more of the best chromosomes are directly copied to the next generation.

Suppose the best chromosome is:

C_{\text{best}} = 101101

Instead of risking its loss during crossover or mutation, it can be copied directly into the next population.

The principle is:

\text{Best individuals} \rightarrow \text{Next generation}

Elitism helps preserve high-quality solutions.

15. Genetic Algorithm Flow

The basic genetic algorithm follows these steps:

text
1Initialize Population
2        ↓
3Calculate Fitness
4        ↓
5Select Parents
6        ↓
7Crossover
8        ↓
9Mutation
10        ↓
11Evaluate New Population
12        ↓
13Apply Elitism
14        ↓
15Termination Check
16        ↓
17   No ───────→ Repeat
18        ↓ Yes
19      Best Solution

Mathematically, the evolutionary process can be summarized as:

P_t \rightarrow \text{Selection} \rightarrow \text{Crossover} \rightarrow \text{Mutation} \rightarrow P_{t+1}

where:

$P_t$ = current population
$P_{t+1}$ = next population

16. Termination Condition

A genetic algorithm needs a condition to determine when it should stop.

Common termination conditions include:

Maximum Number of Generations

Stop when:

t \geq T_{\max}

where $T_{\max}$ is the maximum number of generations.

Target Fitness

Stop when:

F(C_{\text{best}}) \geq F_{\text{target}}

Convergence

Stop when the population has stopped improving significantly:

\left| F_{\text{best}}^{(t)} - F_{\text{best}}^{(t-k)} \right| < \epsilon

where $\epsilon$ is a small threshold.

17. Complete Genetic Algorithm

Step 1: Initialize
Generate an initial population:

P_0 = \{C_1, C_2, \ldots, C_N\}

Step 2: Evaluate
Calculate fitness for every chromosome:

F(C_i)

Step 3: Select
Select parents based on their fitness. For fitness-proportional selection:

P_i = \dfrac{F(C_i)}{\displaystyle\sum_{j=1}^{N} F(C_j)}

Step 4: Crossover
Combine selected parents:

(P_1, P_2) \rightarrow (C_1, C_2)

Step 5: Mutation
Randomly modify genes:

C \rightarrow C'

Step 6: Create New Population
Form $P_{t+1}$ from the new offspring.

Step 7: Check Termination
If the termination condition is satisfied → Stop
Otherwise:

t \leftarrow t + 1

and repeat the process.

18. Example of a Complete Generation

Consider the following initial population:

Chromosome	Fitness
$101101$	$5$
$011010$	$3$
$110011$	$4$

Total fitness:

5 + 3 + 4 + 3 = 15

Selection probabilities:

P_1 = \dfrac{5}{15},\quad P_2 = \dfrac{3}{15},\quad P_3 = \dfrac{4}{15},\quad P_4 = \dfrac{3}{15}

Suppose the selected parents are:

text
1Parent 1: 101|101
2Parent 2: 110|011

After single-point crossover:

text
1Child 1: 101|011
2Child 2: 110|101

Suppose mutation changes one gene in Child 1:

text
1Before: 101011
2After:  100011

The new offspring are then evaluated using the fitness function. This process forms the next generation.

19. Genetic Algorithm for Optimization

Suppose we want to maximize a function $f(x)$ .

The genetic algorithm attempts to find:

x^* = \arg\max_x f(x)

where $x^*$ is the best solution found.

If the problem is a minimization problem:

x^* = \arg\min_x f(x)

The fitness function may be directly related to the objective function for maximization problems.
For minimization problems, the objective may need to be transformed into a fitness value.

20. Binary Encoding

In a binary genetic algorithm, solutions can be represented using binary chromosomes.

For example:

C = 10110110

If the chromosome contains $8$ genes, its length is $L = 8$ .

Each gene can have one of two values:

g_i \in \{0, 1\}

Therefore, the chromosome can be represented as:

C = (g_1, g_2, \ldots, g_L) \quad \text{where} \quad g_i \in \{0, 1\}

21. Real-Valued Encoding

Genetic algorithms do not have to use binary chromosomes.

A chromosome can also contain real-valued genes:

C = (2.5,\ 4.7,\ 1.2,\ 8.9)

This representation is useful for continuous optimization problems.

For example, if $x \in [0, 10]$ , a chromosome could directly represent:

x = 7.35

without converting it into a binary string.

22. Advantages of Genetic Algorithms

They can search large solution spaces.
They do not necessarily require derivatives.
They can handle complex objective functions.
They can escape some local optima through population-based search.
They can work with discrete and continuous variables.
They are flexible and applicable to many optimization problems.

23. Limitations of Genetic Algorithms

They can require many fitness evaluations.
Results may vary between runs because of randomness.
Choosing parameters can be difficult.
They do not always guarantee the global optimum.
Poor parameter choices can cause premature convergence.
They can be computationally expensive for large problems.

24. Genetic Algorithms vs Traditional Optimization

Feature	Genetic Algorithm	Traditional Optimization
Search strategy	Population-based	Often single-solution based
Derivatives	Usually not required	Often required
Randomness	Yes	Often less
Complex search spaces	Suitable	Depends on method
Local optima	Can sometimes escape	May get trapped
Global optimum	Not guaranteed	Not always guaranteed

25. Soft Computing: Neural Networks vs Fuzzy Logic vs GA

Soft computing includes several computational techniques that can deal with complex, uncertain, or difficult problems.

Technique	Main Purpose	Inspiration
Neural Networks	Learning	Biological brain
Fuzzy Logic	Reasoning	Human reasoning
Genetic Algorithms	Optimization	Natural evolution

Neural Networks

Neural networks learn patterns from data. Their basic computational structure can be represented as:

x \rightarrow Wx + b \rightarrow f(z) \rightarrow y

They are commonly used for classification, regression, computer vision, natural language processing, and pattern recognition.

Fuzzy Logic

Fuzzy logic represents degrees of truth or membership:

\mu_A(x) \in [0, 1]

It is useful for reasoning with imprecise concepts such as Hot, Cold, Fast, Slow, High, Low.

Genetic Algorithms

Genetic algorithms search for good solutions using evolutionary operations:

\text{Selection} \rightarrow \text{Crossover} \rightarrow \text{Mutation}

They are mainly used for optimization.

26. Important Genetic Algorithm Formulas

Population

P = \{C_1, C_2, \ldots, C_N\}

Fitness

F(C_i)

Fitness-Proportional Selection

P_i = \dfrac{F_i}{\displaystyle\sum_{j=1}^{N} F_j}

Crossover Probability

0 \leq P_c \leq 1

Mutation Probability

0 \leq P_m \leq 1

Maximization

x^* = \arg\max_x f(x)

Minimization

x^* = \arg\min_x f(x)

Binary Gene

g_i \in \{0, 1\}

27. Summary

A Genetic Algorithm is an optimization technique inspired by biological evolution.

The major components are:

\text{Population} \rightarrow \text{Chromosomes} \rightarrow \text{Genes} \rightarrow \text{Fitness}

The main evolutionary operations are:

\text{Selection} \rightarrow \text{Crossover} \rightarrow \text{Mutation}

The overall process is:

\text{Initialize} \rightarrow \text{Evaluate} \rightarrow \text{Select} \rightarrow \text{Crossover} \rightarrow \text{Mutate} \rightarrow \text{Replace} \rightarrow \text{Terminate or Repeat}

The most important selection formula is:

P_i = \dfrac{F_i}{\displaystyle\sum_{j=1}^{N} F_j}

The key idea behind a genetic algorithm is simple:

Keep better solutions, combine useful information, introduce small random changes, and repeat the process to search for better solutions.

Genetic algorithms are therefore particularly useful when the search space is large, complex, non-linear, or difficult to optimize using conventional mathematical methods.