Does mutation always make a solution better?

No. It creates alternatives. Evaluation and the surrounding algorithm determine which alternatives are retained.

Can mutation work without crossover?

Yes. Some evolutionary search methods rely primarily or entirely on mutation-based variation.

Is one-bit mutation the same as independently flipping every bit with a small probability?

No. Exactly-one-bit mutation always changes one position. Independent bit mutation can change zero, one, or several positions.

AI Glossary / Graphs and symbolic AI / Beginner

Mutation

Definition

In evolutionary computation, mutation is an operator that changes a candidate solution to create a variant for evaluation. It introduces variation into the search, commonly through random changes chosen according to a specified rule. The change may improve, worsen, or leave fitness unchanged. This entry uses the evolutionary-algorithm sense, rather than biological mutation or changing a software object's state in general.

What it means

An evolutionary algorithm represents possible solutions as individuals: bit strings, numerical vectors, permutations, trees, or another suitable encoding. Mutation changes an individual within that representation. The resulting candidate is then assessed by the problem's fitness function and handled by the algorithm's selection or replacement rules.
Mutation provides possibilities; it does not know that a change is beneficial merely because the operator produced it. A random proposal can be useful when combined with systematic evaluation. The design question is which kinds of variation allow the algorithm to explore meaningful alternatives without routinely destroying the representation's basic validity.

How it works

Choose an operator suited to the encoding. A bit-string operator can flip selected bits. A numerical operator can perturb selected values. A permutation operator can swap positions while retaining each item exactly once. Tree-based representations require changes that respect their syntax and any type restrictions.
Specify how often the operator is invoked and how much it changes when invoked. These are separate choices. Evaluate the resulting candidate before relying on its fitness, because a previously stored score may no longer apply. Some frameworks modify an individual in place, so cloning and score invalidation are implementation responsibilities rather than automatic consequences of the word mutation.

Three practical examples

A feature-selection experiment can flip bits indicating which input features are included in a candidate model, then reevaluate predictive performance and feature cost.
A scheduling search can swap two jobs in a candidate ordering while checking whether precedence constraints remain satisfied.
A simulation-based design search can perturb numerical settings within an explicitly allowed range and evaluate the resulting behavior.

Think of it this way

Think of revising a draft proposal by changing one or two choices and then reviewing the result. The revision creates an alternative; review determines whether it is useful. The analogy is limited because mutation operators often sample changes randomly, while a human editor may use detailed understanding to choose a specific improvement.

Worked example

Consider an invented six-bit candidate 101100. Its toy fitness is simply the number of ones, so its starting fitness is 3. Use a mutation operator that chooses exactly one of the six positions uniformly and flips that bit.
If position 2 is chosen, counting positions from 1, the bit changes from 0 to 1 and the candidate becomes 111100. Its fitness is 4. If position 3 is chosen instead, the candidate becomes 100100 and its fitness falls to 2. There are three zero positions and three one positions, so the probability of improvement is 3/6 and the probability of deterioration is also 3/6.
The expected fitness after this one mutation is therefore 0.5 × 4 + 0.5 × 2 = 3. Random variation has not improved expected fitness in this particular starting state. If a separate replacement rule keeps the parent whenever the child is worse, the retained candidate instead has expected fitness 0.5 × 4 + 0.5 × 3 = 3.5. This demonstrates the distinct contributions of mutation and replacement, not a general convergence guarantee.

Illustrative case study

In a fictional planning prototype, a team represents delivery stops as a permutation. Its first mutation operator replaces a randomly selected stop with another randomly selected name. This sometimes duplicates a stop and removes another, producing invalid routes before travel cost is even evaluated.
The team changes to a swap-based operator that preserves the set of stops. It then adds checks for constraints that swaps do not automatically preserve, such as a required pickup-before-drop-off relationship. The case illustrates representation-aware variation; it does not imply that one operator solves all routing constraints or guarantees an optimal route.

Common misconceptions and mistakes

Mutation is not the same as crossover. Mutation changes a candidate; crossover combines material from parent candidates according to a recombination rule. Algorithms can use either or both.
Do not assume that invoking mutation must visibly alter the candidate. Some operators make probabilistic per-position choices and may select no positions; replacement-based mutations can also draw an existing value. Likewise, validity preservation is operator-specific. A bit flip preserves a binary encoding but may violate a business constraint represented by those bits. Always distinguish syntactic validity from feasibility for the actual problem.

Business use

Mutation is useful when an organization explores a large design or planning space with a measurable evaluation procedure. Its effectiveness depends on the encoding, evaluation quality, computational budget, and how candidates are selected and retained. More variation is not automatically better: disruptive changes can repeatedly undo useful structure.
For a practical experiment, document the exact operator, invocation probability, internal probabilities, parameter scales, and constraint treatment. Compare repeated runs using consistent evaluation budgets. If fitness is noisy, examine whether apparent improvements persist when reevaluated rather than interpreting every better score as a real improvement.

Check your understanding

For the same exactly-one-bit operator applied to 111100, what is the probability of improvement under the count-ones fitness?

Answer: Two of the six bits are zero, so improvement has probability 2/6 = 1/3. Flipping any of the other four bits decreases fitness by one.

Related terms

Evolutionary algorithms
Genetic algorithms
Fitness function
Mutation rate
Permutations
Selection
Exploration
Evolutionary algorithm
genetic algorithm
crossover
genotype
permutation

Learn next

Study mutation rate next, distinguishing the probability of invoking an operator from the probability of changing each position. Then compare exactly-one-bit mutation with independent bit flips on the six-bit example. List which possible offspring each operator can produce and why their search behavior differs.

Mutation rate

Sources

DEAP official documentation, Evolutionary Tools, mutation operators and in-place behavior: https://deap.readthedocs.io/en/stable/api/tools.html . DEAP Algorithms, variation and evaluation responsibilities: https://deap.readthedocs.io/en/stable/api/algo.html . Relevant documentation was read. The bit-string probabilities and fictional route example are original illustrations, not executed optimization results.

Previous: Mutable Data Types Next: Mutation rate