Skip to content
Tutorials Center
My learning

Topics

Lesson 1 of 36 ยท Getting Started

What Are Genetic Algorithms?

Learn what a genetic algorithm is, why evolution makes a good search method, and when to use one, with runnable Python that compares random search to evolution.

Some problems are easy to check and hard to solve. Given a delivery route, you can add up its length in a second. Finding the shortest route through 60 cities is another matter, because the number of possible routes is larger than the number of atoms you could count in a lifetime. You cannot try them all, and there is no formula that jumps straight to the answer.

A genetic algorithm (GA) attacks this kind of problem by borrowing a strategy that has worked for billions of years: evolution. Keep a population of candidate solutions, let the better ones "reproduce" by mixing their parts, add small random changes, and repeat. Over many generations the population drifts towards good solutions, even though no single step is clever. This course teaches you how, step by step, with Python code that runs in your browser.

The core idea

A genetic algorithm is a search and optimization method. You give it two things:

  1. A way to describe a candidate solution as data (for example, a list of 40 bits, or a list of cities in visiting order).
  2. A fitness function: a function that takes a candidate and returns a number saying how good it is.

The algorithm does the rest. It never needs to know why a solution is good, only how good it is. That makes GAs useful when the problem has no tidy mathematical structure: no derivative to follow, no clever decomposition, just a score.

The loop looks like this:

flowchart LR
    A["Create a random<br/>population"] --> B["Measure the fitness<br/>of every individual"]
    B --> C["Select the<br/>better parents"]
    C --> D["Crossover: mix<br/>parent genes"]
    D --> E["Mutation: small<br/>random changes"]
    E --> F["New generation<br/>replaces the old"]
    F --> B

One generation of a genetic algorithm. The loop stops when the solution is good enough or a budget runs out.

Each part of that loop has a chapter of its own in this course. For now, notice how little is required: random numbers, a score, and repetition.

Why the search space is the problem

The set of all candidate solutions is the search space. Its size explains why brute force fails. A solution made of n binary choices has 2^n possibilities, and the number of orderings of n cities is n! (n factorial). Both explode quickly.

Python How fast search spaces explode

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Forty bits already means over a trillion strings, and 30 cities need more years than the age of the universe. A GA does not look at every candidate. It samples a few hundred or thousand and uses their scores to decide where to look next.

Random search versus evolution

To see why "keep the good parts and vary them" beats guessing, compare two methods on a toy problem called OneMax: a bit string is as fit as it has 1s, and the best string is all 1s. Random search generates fresh random strings and remembers the best. A tiny evolutionary search keeps a current solution, flips each bit with small probability, and keeps the child if it is at least as good.

Python Random guessing versus mutate-and-keep

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both methods get exactly 3,000 fitness evaluations. Random search tops out in the low 40s because the chance of drawing a nearly perfect string by luck is tiny. The evolutionary version reaches 60 because every improvement is remembered and built on. That memory is the whole trick. A full GA adds a population and crossover on top, which you will build in your first genetic algorithm.

What genetic algorithms are good at

GAs shine when:

  • The search space is huge and has no obvious structure.
  • The fitness can be computed by a simulation or a black box, so you have no gradient.
  • You want a good solution, not a mathematically proven best one.
  • The problem mixes discrete and continuous choices, or has odd constraints.

Typical uses include scheduling, routing, layout design, feature selection for machine learning, tuning parameters of a simulation, evolving neural network structures, and designing antennas or circuits.

What they are not good at

Be honest about the limits:

  • Smooth problems with derivatives. If you can differentiate your function, gradient descent usually wins by a wide margin.
  • Problems with exact algorithms. Shortest path in a graph, sorting, linear programming: use the classic algorithm. See the DSA tutorial for those.
  • Expensive fitness. A GA may need tens of thousands of evaluations. If each one takes an hour, you need surrogates or a different method.
  • Guarantees. A GA returns the best it found. It cannot promise that nothing better exists.

GAs are heuristics: practical rules that find good answers without proof. Treat the result as "very good, found cheaply", and run it several times with different random seeds before trusting it.

A map of this course

Four steps to a GA

Represent Encode a solution as genes
Score Write a fitness function
Select Pick the fitter parents
Vary Crossover and mutation

Repeat until the answer is good enough.

1 / 2

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a fitness function do in a genetic algorithm?

    The fitness function scores each candidate. Everything else in the GA (selection, crossover, mutation) works from those scores.
  2. 2. Why can brute force not solve a 30-city routing problem?

    30 cities have 30! orderings, far too many to enumerate. A GA samples a small part of the space guided by fitness.
  3. 3. In the lesson's experiment, why did mutate-and-keep beat random search with the same budget?

    Both used 3,000 evaluations. Mutate-and-keep keeps each improvement and varies it, while random search throws every guess away.
  4. 4. Which problem is the poorest match for a genetic algorithm?

    A smooth differentiable function is solved faster and more reliably by gradient-based or classic numerical methods.

Summary

  • A genetic algorithm evolves a population of candidate solutions using only a fitness score.
  • The loop is: score, select, crossover, mutate, replace, repeat.
  • Search spaces grow exponentially (2^n) or factorially (n!), so brute force is hopeless.
  • Remembering and varying good solutions beats random guessing at equal cost.
  • GAs are heuristics: great for black-box, discrete or messy problems, not for smooth ones with derivatives.

Next: Evolutionary Computation and Its Vocabulary