What Is a Genetic Algorithm?

Imagine you have to schedule dozens of courses. Every class needs a room and a time. An instructor cannot teach two classes at once, a room cannot hold two classes at once, and a laboratory course may need special equipment. A human scheduler can solve a small version by hand, but the number of combinations grows quickly. A genetic algorithm offers one way to search through those combinations without examining every possible timetable.

The name comes from an analogy with biological evolution. Possible solutions are represented as individuals in a population. The algorithm evaluates them, favors promising ones, creates variations, and repeats. The analogy is useful, but the program does not literally reproduce nature. A developer chooses the representation, scoring rules, variation operators, and stopping condition.

Start with a representation

Before writing any selection or mutation code, decide what one candidate solution looks like. For a timetable, it might be a list of course assignments, each with a room and time slot. For a delivery route, it might be an ordering of stops. For a small numerical problem, it could simply be a list of numbers. This representation is sometimes called a chromosome, and its individual values are sometimes called genes.

The representation affects everything that follows. If a timetable can accidentally assign a class to a room with too few seats, the program must either prevent that assignment or penalize it during evaluation. A good representation makes valid solutions easier to produce and easier to modify. It also lets you explain exactly what crossover or mutation means for the problem, instead of treating those words as magic steps.

Give each candidate a fitness score

A fitness function measures how well a candidate meets the objective. In our scheduling example, you might assign a large penalty for an instructor conflict or a room conflict, then smaller penalties for inconvenient times or unused capacity. A solution with fewer severe conflicts should rank above one with a cosmetically appealing schedule that is impossible to run.

Separating hard constraints from preferences matters. “An instructor cannot be in two rooms at once” is a hard constraint. “Prefer classes before 4 p.m.” may be a preference. One approach is to reject candidates that break hard constraints; another is to score violations so heavily that they are very unlikely to win. Either way, document the scoring rules. Otherwise, a high fitness number can hide a result that fails the real-world task.

Select, recombine, and mutate

After scoring a population, the algorithm selects candidates to influence the next generation. Better candidates usually get a greater chance, but always choosing only the current best can reduce variety too quickly. Selection methods such as tournaments compare small random groups and choose a winner from each group. The exact method is a design decision, not a universal rule.

Crossover combines information from two parent candidates. If a schedule is represented as course assignments, a simple crossover might take some assignments from one parent and the rest from another. That can create a child with promising pieces from both, but it may also create conflicts, so a repair step or constraint-aware crossover may be necessary. Mutation makes a small random change, such as moving one class to another allowed time. It helps the search keep exploring when many candidates become similar.

Some implementations also preserve one or more of the best candidates unchanged, a practice called elitism. Without it, a good solution can disappear in the next generation. With too much of it, the search may become less diverse. There is no setting that guarantees the best result on every problem.

A small example you can trace

Suppose there are four classes and four time slots. A candidate lists a time slot for each class: [1, 3, 2, 4]. Another candidate is [2, 1, 4, 3]. The fitness function checks whether classes sharing an instructor overlap and whether rooms meet the requirements. Selection chooses two promising candidates. Crossover exchanges part of their assignments, and mutation may move one class to a different slot. The next candidates are evaluated again.

This toy example leaves out rooms and instructors in the representation, but it makes the loop visible. For a real timetable, you would need a richer encoding, constraint checks, and a way to report why one result is better. The goal is typically a good feasible schedule within a reasonable amount of computation, not proof that no better schedule exists.

When is a genetic algorithm useful?

Genetic algorithms are most interesting when a problem has many combinations, you can evaluate a proposed answer, and an exhaustive search would be impractical. Scheduling, parameter tuning, and layout design are possible examples. They are less attractive when a simple deterministic method solves the problem cleanly or when scoring a candidate is so expensive that thousands of evaluations are unrealistic.

Always compare the result with a baseline. A greedy scheduler, a hand-built rule set, or an established optimization method may be faster and easier to explain. Run the search more than once with different random seeds, record the best feasible solution, and inspect its actual constraints. A clever algorithm is useful only if it solves the right problem.

My connection to the subject

In 2003, Manuel Penaloza and I published A Genetic Algorithm Approach for Finding a Good Course Schedule. That project is one reason evolutionary computing has a personal place on this site. You can read the research overview and follow its link to the original paper. This introductory guide explains the general method; the research page covers our particular scheduling problem.

A useful next experiment is to define a tiny scheduling problem with only a few classes, write down every constraint, and compare the algorithm’s output with a timetable you can verify by eye. Once the simple version is correct, add rooms, preferences, and more courses one at a time. That progression teaches more than starting with a large opaque result.

Further reading: Ellingsen and Penaloza, 2003 paper (PDF).