Variation Operators for Binary Genetic Algorithms

Variation operators generate new candidate solutions. Their role is to balance new competing objectives: exploration (discover new regions of the search space) and exploitation (refine and recombine good solutions).

Crossover

Crossover aims to recombine information from multiple parents. This exploits existing building blocks, enabling structured exploration.

For example, we can combine genetic material from two parents:

$$\text{Offspring}=\text{Recombination}({\text{parent}}_1,{\text{parent}}_2)$$

The intuition is that good solutions often share useful building blocks. These blocks correspond to partial patterns in the genotype. Recombining blocks may yield to better solutions.

A simple intuition if we consider something like this:

$${\text{parent}}_1=11010100,{\text{parent}}_2=00110111$$

These two share a $101$ block. Crossover would aim to preserve this shared structure while exploring new combinations.

Crossover probability

We can choose to not crossover some parent pairs and instead simply pass them onto the next generation. Crossover probability $p_c$ is applied independently to each parent pair.

For every parent pair chosen for reproduction:

• Draw a random number $u\sim \mathcal{U}(0,1)$
• If $u\le p_c$: apply crossover
• If $u>p_c$: copy parents unchanged

Crossover Methods

• One-Point Crossover
• N-Point Crossover
• Uniform Crossover

Mutation

Mutation introduces random variation, maintaining diversity. This allows escape from local optima.

Mutation probability

Like crossover probability, for each gene in each offspring:

• Draw a random number $u\sim \mathcal{U}(0,1)$
• If $u\le p_m$: mutate the gene
• If $u>p_m$: leave the gene unchanged

Typically, $p_m\approx \frac{1}{L}$, where $L$ is the chromosome length. Thus, on average, one bit mutates per chromosome, preserving most structure.

If $p_m$ is too low, diversity collapses, and population stagnates. This may cause premature convergence to local optima.

If $p_m$ is too high, the genetic algorithm drifts toward random search. Building blocks are destroyed, such that selection cannot accumulate strucutre.

Bit-Flip Mutation

With a binary representation, we can simply do bit flips for mutation: