Two Kinds of Problems
Most of the problems we have studied so far in this course have correct answers. A binary number either converts correctly to decimal or it does not. A SQL query either returns the right rows or it does not. A decision tree either classifies an input correctly or it does not. These are problems with a definite goal state — a specific configuration that counts as success.
But a large and important class of real-world problems does not work this way. Instead of asking "what is the correct answer?" they ask "what is the best answer we can find?" These are called optimization problems, and they are everywhere.
- What is the best schedule for a school that minimizes room conflicts, respects teacher preferences, and keeps class sizes balanced?
- What is the best route for a delivery truck that visits twenty stops in the least total distance?
- What is the best configuration of a neural network's parameters that minimizes prediction error on a dataset?
- What is the best treatment protocol for a patient given their specific combination of symptoms, history, and test results?
None of these has a single "correct" answer in the way a binary conversion does. They have a quality measure — a way to score any candidate solution — and the goal is to find a solution that scores as high as possible. In optimization, this quality measure is called a fitness function (or sometimes an objective function or cost function). The fitness function is what tells you whether one solution is better than another.
Why You Cannot Just Check Everything
The natural approach to finding the best solution is to check all of them. Evaluate every possible schedule, every possible route, every possible parameter combination, and pick the one with the highest fitness. This is exhaustive search, and it works perfectly for small problems.
The problem is scale. Optimization problems typically have solution spaces that grow explosively with the size of the problem. Consider scheduling just five classes into five periods: there are 120 possible orderings. Manageable. Ten classes into ten periods: over 3.6 million orderings. Harder. Twenty classes into twenty periods: over 2.4 quintillion orderings. Even a computer that could evaluate a billion orderings per second would take nearly 80 years to finish. And real school scheduling problems involve hundreds of classes, teachers, rooms, and constraints.
This explosion — the combinatorial explosion we first encountered in Topic 6b — makes exhaustive search impossible for almost every interesting optimization problem. The space of possible solutions is simply too large to search completely in any practical amount of time.
The goal of optimization is not to find the best solution. It is to find a good enough solution, quickly enough to be useful. That shift in ambition is not a defeat — it is how almost all real-world optimization works.
The Fitness Landscape
To visualize the challenge of optimization, it helps to think of the fitness landscape. Imagine spreading out every possible solution to a problem across a flat surface — every point on the surface represents one candidate solution. Now imagine the height of the surface at each point represents the fitness of that solution: better solutions are higher, worse solutions are lower. The result is a landscape of hills and valleys.
The optimization problem is, literally, finding the highest point on this landscape. If the landscape were simple — one smooth hill rising to a single peak — the problem would be easy. Climb in the direction that goes up, and you will reach the peak.
But real optimization landscapes are rarely simple. They typically look more like a mountain range with many peaks of different heights, connected by valleys and ridges. The highest peak — the global optimum, the very best solution — might be far from where you start, separated from you by valleys you would have to descend to cross.
Two neighboring solutions on the landscape are ones that differ by a small, well-defined change. For a scheduling problem, two neighboring solutions might differ by a single swapped class. For a route problem, two neighbors might differ by a single swapped stop. The neighborhood relationship defines how the landscape is structured — which solutions are "next to" which others.
A simplified fitness landscape. The global optimum is the highest peak. Local optima are smaller peaks. A plateau is a flat region where all neighbors score the same.
Two Strategies for Searching the Landscape
Given a fitness landscape too large to explore completely, how does an AI agent find a good solution? The two techniques in this topic represent two very different strategies:
Hill climbing takes the simple, intuitive approach: start somewhere, look at neighboring solutions, move to the best one, repeat. It is fast and easy to implement, but it has a critical weakness: it can get trapped on a local optimum — a peak that is the best solution in the immediate neighborhood, but not the best solution overall.
Genetic algorithms take inspiration from biological evolution: maintain a diverse population of candidate solutions, select the fittest to "reproduce," combine their features to create new solutions, and introduce occasional random mutations. This approach is slower and more complex, but it explores the landscape much more broadly and is far better at escaping local optima.
Reading 2 covers hill climbing in depth, with a concrete classroom scheduling example. Reading 3 covers genetic algorithms and connects both techniques to the reinforcement learning framework from Topic 6c.