Definition
A delivery rider has ten parcels to drop across the city. There are more than three million possible orders to visit them in. Which one is fastest?
Optimisation means finding the best possible solution to a problem from all the possible ones, according to a clear goal and within limits. The goal might be the shortest time, the lowest cost or the fewest mistakes; the limits, called constraints, are rules the solution must obey.
In simple words
Packing a school bag is optimisation. You want everything you need for the day (the goal), the bag can only hold so much and must not be too heavy (the constraints), so you choose the best combination of books, tiffin and water bottle.
Why it matters
Optimisation is everywhere: routes, timetables, factory schedules, electricity grids and train networks. It is also how AI learns: training a model means searching for the settings that make the fewest mistakes.
Key terms
- Optimisation
- Finding the best solution according to a goal and within limits.
- Objective
- What you are trying to make as small or as large as possible, such as travel time or profit.
- Constraint
- A rule the solution must obey, such as a budget or a deadline.
- Trade-off
- Giving up some of one thing to get more of another, such as speed for cost.
- Greedy approach
- Taking the best-looking choice at each step, which is fast but not always best overall.
- Good-enough solution
- A solution that is close to the best and can be found quickly, when the perfect one would take too long.
Explained in detail
Goal, constraints and options
Every optimisation problem has three parts. The options are all the possible solutions: every order the rider could visit the parcels in. The objective is the measure of how good an option is: total travel time. The constraints are the rules: a parcel promised by 11 a.m. must arrive before then, and the bike has room for only six parcels at once. The best solution is the option that scores best on the objective while obeying every constraint.
Why trying everything does not work
With 3 parcels there are only 6 possible orders, easy to check by hand. With 10 there are over 3.6 million. With 20 there are more than two billion billion, and even the fastest computer could not check them all in a lifetime. This explosion is why clever methods are needed. Some cut out options that clearly cannot be best; others build a good solution step by step; others start with any solution and keep making small improvements.
The greedy approach
A simple method is to always go to the nearest parcel next. This greedy approach is fast and usually gives a reasonable route, but not always the best one: going to the nearest place first can leave you with a long trip back at the end. Greedy methods are useful when a good-enough answer is needed quickly, such as for a delivery app planning thousands of routes every minute.
Trade-offs
| Situation | What you gain | What you give up |
|---|---|---|
| Taking the toll highway | Time | Money |
| Buying in bulk | Lower price per item | Storage space and cash now |
| A bigger AI model | Accuracy | Speed, cost and energy |
| A stricter spam filter | Less spam | More real emails wrongly blocked |
Optimisation inside AI
Training a machine learning model is an optimisation problem. The options are all the possible settings of the model; the objective is to make as few mistakes as possible on the training examples. The usual method is like walking down a hill in thick fog: you cannot see the bottom, but you can feel which way slopes downward under your feet, take a small step that way, and repeat. Step by step, the mistakes get smaller. This method is called gradient descent, and you will learn more about it in later levels.
How it works
- State the objective: what should be as small or as large as possible?
- List the constraints the solution must obey.
- List or describe the possible options.
- If there are few, compare them all; if many, use a method such as greedy or step-by-step improvement.
- Check the trade-offs and whether a good-enough answer will do.
Try it yourself
Greedy is not always best
Ravi delivers three parcels, starting and ending at the shop. Places are on one straight road: A is 1 km left, B is 2 km right, C is 6 km right.
Pack the best picnic basket
Your basket holds 5 kg. Each item has a weight and a fun score.
- Items: water 2 kg (score 9), sandwiches 1 kg (8), cricket set 3 kg (10), fruit 1 kg (6), board game 2 kg (5).
- Find a combination that stays within 5 kg.
- Add up its fun score.
- Try at least three combinations and keep the best.
Think about it
- What was the objective, and what was the constraint?
- Did choosing the highest-score item first always give the best basket?
Common mistakes
- Not stating the goal clearly before searching for the best answer.
- Ignoring constraints, so the "best" answer is impossible.
- Assuming the first or greedy answer must be the best.
Check yourself
Summary
- Optimisation finds the best option for a goal within constraints.
- When options explode, use smart methods and accept good-enough answers.
- AI training is optimisation: step by step towards fewer mistakes.
Finished reading?
Sources: Elements of AI (University of Helsinki) · CS Unplugged