Selection, Crossover and Mutation: How a Genetic Algorithm Searches

A genetic algorithm is easy to summarize: score a population, select parents, combine their information, make small changes, and repeat. The interesting work begins when you ask what those steps mean for a particular problem. A delivery route, a course timetable, and a set of numerical parameters cannot necessarily use the same representation or the same crossover operation.

This guide follows the main operations using a small example, then connects them to constrained problems such as scheduling. It builds on the introduction to genetic algorithms. The goal is to understand the design decisions well enough to explain why your program produces one candidate rather than another.

Fitness defines what success means

Consider a candidate represented by eight bits: 10110100. For a deliberately simple exercise, the objective is to maximize the number of ones. Its fitness is four. The string 11100110 scores five. This makes scoring transparent, although a direct solution is obvious: eight ones. That is why this is an educational example rather than a problem that needs a genetic algorithm.

A real fitness function must reflect the actual task. In course scheduling, a timetable with a room conflict cannot be considered good merely because its classes finish early. You can keep feasibility separate from preference scores, compare candidates in a defined order, or impose suitable penalties. Whichever approach you choose, make the rules visible. A fitness number is a summary of your criteria; it is not independent proof of quality.

Selection chooses who contributes

Selection influences which candidates become parents. One straightforward method is tournament selection: sample a small group from the population, compare their scores, and choose the best candidate in that group. Repeat the process to select another parent. A candidate with a modest score may still become a parent if the other sampled candidates are worse.

The size of the tournament changes the pressure toward better scores. Larger tournaments tend to favor stronger candidates more heavily, but can also make the population resemble its current best members sooner. Small tournaments preserve more variety but may make progress slower. These are tendencies to measure on your problem, not settings that guarantee a better result. Keep a simple baseline and compare repeat runs.

Other selection methods use probabilities derived from fitness or from rank. If your fitness values are negative or contain large penalties, a naive probability formula can be misleading. Ranking candidates or using a tournament can avoid some of those scaling problems. Selection also does not necessarily mean deleting every weaker candidate immediately; reproduction and replacement can be separate choices.

Crossover combines information

For our eight-bit example, suppose the parents are 11110000 and 00001111. A one-point crossover after the fourth bit produces 11111111 and 00000000. One child is excellent and the other is poor. This illustrates both the opportunity and the uncertainty: combining parents can bring useful pieces together, but it does not promise improvement for every child.

Parent A: 1111 | 0000
Parent B: 0000 | 1111
Child A:  1111 | 1111
Child B:  0000 | 0000

That operation is valid because every eight-bit string is allowed in this exercise. It would be unsafe to copy the same method directly to a route represented as an ordering of unique stops. Combining two slices might repeat one stop and omit another. A timetable can similarly acquire room or instructor conflicts. Choose operators that preserve important constraints, or provide a repair procedure and evaluate its effects.

Mutation introduces a small change

In the bit example, mutation can flip a zero to a one or a one to a zero. In a route, it might swap two stops. In a timetable, it might move one class to another allowed room and time. The useful definition of “small” depends on the representation. One changed value could be a minor adjustment in one problem and invalidate several assignments in another.

Be precise about the mutation rate. A probability applied to every gene is different from a probability applied once to an entire candidate. With an eight-bit candidate and a per-bit probability of one eighth, the expected number of flipped bits is one, but a particular candidate can experience zero, one, or several flips. Saying “one mutation per child” describes a different procedure.

Replacement and elitism complete the generation

Once new candidates have been generated, the algorithm needs a rule for forming the next population. It can replace the old population, compare parents and children, or preserve a limited set of good candidates while filling the other positions with new ones. Keeping an unchanged copy of a best candidate is commonly called elitism. In a deterministic evaluation, that can protect the best score found so far from accidental loss.

Too many preserved copies can reduce variety. More generally, keep track of duplicate candidates, feasible solutions, and improvement over time rather than looking only at the single best score. If evaluating the same candidate involves noise or simulation, a preserved candidate’s recorded score may also need rechecking. The replacement rule should match how reliable your evaluation is.

A practical way to tune the search

Start with a small problem you can verify manually. Confirm that selection prefers better candidates under your scoring convention, crossover produces a valid representation, and mutation changes only what you intend. Then record results from several random seeds using the same evaluation budget. Change one setting at a time so you can tell which change matters.

Look for a good feasible result within your time budget, and compare it with a simpler method. If the algorithm exploits a loophole in the score, fix the objective before increasing the population size. My 2003 course-scheduling research gives this topic a practical context, but the operators in this article are illustrative and are not a reconstruction of that implementation.

Further reading: John H. Holland, Genetic Algorithms (PDF).