Genetic Algorithms (GA): Core Idea and Steps for Selection, Crossover, and Mutation

A Genetic Algorithm (GA) is an evolutionary computation method that repeatedly evolves a population of candidate solutions over generations until a stopping criterion is met. The GA framework typically includes: initialize a population, evaluate each candidate via a fitness function, select parents, apply crossover and mutation, then form a new generation and repeat. This canonical flow is described in GA overviews and tutorials. 3

Key learning goals in this section:

• Understand how fitness evaluation guides search pressure.
• Outline the GA cycle with selection, crossover, and mutation, using a concrete optimization example. 2
• Recognize practical termination criteria used in GA variants.

Footnotes

1. Genetic Algorithms - GeeksforGeeks - Lists GA steps including population initialization, fitness evaluation, selection, crossover, mutation, and termination criteria. ↩ ↩²

2. Julian Blank — An Introduction to Genetic Algorithms - Describes the GA cycle: evaluate, select parents, crossover, mutation, merge, and survival/termination. ↩ ↩²

3. A Genetic Algorithm Tutorial (JHU PDF) - Tutorial explaining GA components like roulette-style selection, crossover, and mutation mechanics. ↩ ↩²

4. Choosing Mutation and Crossover Ratios for Genetic Algorithms—A Review - Documents typical GA stopping/termination criteria (fixed generations, fitness-level reached, no improvement). ↩

Core components (what each part does)

Fitness function transforms a candidate solution into a numeric score that the GA tries to maximize (or minimize). Tutorials commonly present GA iterations as: initialize population → evaluate fitness → select parents → crossover → mutation → repeat with termination. 2

Selection implements “survival of the fittest” by probabilistically favoring better individuals (fitness-proportional) or by deterministic competition among random subsets (tournament). GA tutorials and references also explicitly list selection as choosing individuals to act as parents for recombination.

Crossover recombines parents to form offspring; simple forms include one-point crossover where a crossover point is chosen and gene segments are swapped.

Mutation applies small random changes (often bit-flips for binary encoding) to introduce diversity and reduce the risk of premature convergence to local optima. 2

Termination may occur after a fixed number of generations, when improvement stalls, or when the population fitness reaches a target level; GA reviews and tutorials document these common criteria.

Footnotes

1. Genetic Algorithms - GeeksforGeeks - Lists GA steps including population initialization, fitness evaluation, selection, crossover, mutation, and termination criteria. ↩ ↩²

2. Julian Blank — An Introduction to Genetic Algorithms - Describes the GA cycle: evaluate, select parents, crossover, mutation, merge, and survival/termination. ↩ ↩²

3. JCBose UES T (GA notes PDF excerpt) - Explains roulette-wheel selection with fitness-based probability mapping. ↩

4. A Genetic Algorithm Tutorial (JHU PDF) - Tutorial explaining GA components like roulette-style selection, crossover, and mutation mechanics. ↩

5. Protorials By Saif — Genetic Algorithms Explained (Representation, Fitness, Parent Selection, Crossover, Mutation) - Demonstrates crossover/mutation and selection concepts in a step-by-step explanation. ↩

6. Choosing Mutation and Crossover Ratios for Genetic Algorithms—A Review - Documents typical GA stopping/termination criteria (fixed generations, fitness-level reached, no improvement). ↩

Example optimization problem: maximize a simple linear function under binary encoding

We’ll solve a small maximization problem using a standard binary-encoded GA.

Objective: maximize

$$f(x)=x_1+2x_2+4x_3$$

where each gene $x_i\in\{0,1\}$. This objective is equivalent to interpreting the chromosome $x_1x_2x_3$ as a 3-bit integer with weights $1,2,4$.

Encoding: chromosome = a length-3 bit string $(x_1,x_2,x_3)$.

Fitness function: since we are maximizing, we can use

$$\text{fitness}(x)=f(x)=x_1+2x_2+4x_3.$$

GA hyperparameters (for the worked step):

• Population size $N=4$
• Crossover probability $p_c=0.7$
• Mutation probability $p_m=0.1$ per gene
• Selection: fitness-proportional (roulette-wheel) in this worked example (tutorials describe roulette-style fitness-biased selection).

Footnotes

1. JCBose UES T (GA notes PDF excerpt) - Explains roulette-wheel selection with fitness-based probability mapping. ↩

Worked iteration (from generation $t$ to generation $t+1$)

1) Initialize population and evaluate fitness

Let the initial population be:

Fitness sum:

$$S=0+2+5+7=14.$$

So roulette-wheel selection probabilities are:

• $P(A)=0/14=0$
• $P(B)=2/14$
• $P(C)=5/14$
• $P(D)=7/14$

(Conceptually consistent with roulette-wheel selection that maps fitness to selection probability.)

2) Selection (choose parents)

Suppose the GA selects two parents (for producing two offspring) using roulette-wheel outcomes. Assume:

• Parent 1 = D (111)
• Parent 2 = C (101)

This selection is fitness-biased: higher-fitness individuals have higher chance to be chosen.

3) Crossover (make offspring)

Use one-point crossover. Pick a crossover point between gene positions. For 3 genes, suppose we choose the point after the first gene.

Parents:

• D: 1 | 11 (111)
• C: 1 | 01 (101)

After one-point crossover at the shown cut:

• Offspring O1: take left from D and right from C → 1 01 = 101
• Offspring O2: take left from C and right from D → 1 11 = 111

Apply crossover only if a random draw is below $p_c=0.7$; in this example we assume crossover occurred (common GA step description). 3

4) Mutation (randomly flip bits)

Mutation introduces random diversity. For $p_m=0.1$ per gene, suppose mutation flips:

• In O1 (101): flip the last bit with the given event → 100
• In O2 (111): no mutation occurs → 111

Now recompute offspring fitness:

• fitness(100) = 4
• fitness(111) = 7

5) Form next generation

If we use a generational GA for simplicity, the next population becomes (in some order):

• 101 → mutated to 100 (fitness 4)
• 111 → (fitness 7)
• plus other offspring created from additional parent pairings (to fill $N=4$)

After each generation, the GA checks termination criteria (max generations, stagnation, or reaching a fitness level).

Footnotes

1. JCBose UES T (GA notes PDF excerpt) - Explains roulette-wheel selection with fitness-based probability mapping. ↩ ↩²

2. Julian Blank — An Introduction to Genetic Algorithms - Describes the GA cycle: evaluate, select parents, crossover, mutation, merge, and survival/termination. ↩

3. A Genetic Algorithm Tutorial (JHU PDF) - Tutorial explaining GA components like roulette-style selection, crossover, and mutation mechanics. ↩

4. Protorials By Saif — Genetic Algorithms Explained (Representation, Fitness, Parent Selection, Crossover, Mutation) - Demonstrates crossover/mutation and selection concepts in a step-by-step explanation. ↩

5. Choosing Mutation and Crossover Ratios for Genetic Algorithms—A Review - Documents typical GA stopping/termination criteria (fixed generations, fitness-level reached, no improvement). ↩

Minimal pseudo-logic of the GA loop (ties to the steps)

A canonical GA iteration can be summarized as:

$$\text{repeat: evaluate fitness} \rightarrow \text{select parents} \rightarrow \text{crossover} \rightarrow \text{mutate} \rightarrow \text{update population}$$

and stop on a termination criterion such as max generations or fitness stagnation. 2

Footnotes

1. Julian Blank — An Introduction to Genetic Algorithms - Describes the GA cycle: evaluate, select parents, crossover, mutation, merge, and survival/termination. ↩

2. Choosing Mutation and Crossover Ratios for Genetic Algorithms—A Review - Documents typical GA stopping/termination criteria (fixed generations, fitness-level reached, no improvement). ↩