Module 16 · Lesson 16.2
Deterministic and stochastic methods
Downhill methods, methods that sometimes go uphill, and why the second kind exists at all.
Why this matters
The two families look like a choice between rigour and guesswork. They are not. They are a choice about what you assume: a downhill method assumes the local slope is a reliable guide to where the answer is, and a stochastic method assumes it is not.
On a smooth landscape the first assumption is true and the downhill method wins comfortably. On a rugged one it is false, and the same method walks confidently into the wrong basin and reports success.
By the end of this lesson you should be able to
- Describe gradient descent and say precisely what it cannot do
- Explain the acceptance test in simulated annealing
- Describe a genetic algorithm's population, selection and diversity
- Compare methods on an equal evaluation budget
Deterministic methods
Same inputs, same answer, every time. Fast, reliable, and reproducible — which matters more in engineering than it does in most fields, because a design has to be defensible two years later.
Calculus. Where you can write the objective as a differentiable function, differentiate and set the derivative to zero. Exact, and available for almost nothing real, because real objectives involve catalogues, constraints and analyses rather than formulas.
Gradient descent. Estimate the local slope, step downhill, repeat, shrinking the step when you overshoot. It converges quickly and precisely, and it has one property that decides everything:
A gradient method cannot leave the basin it started in, and nothing in its output tells you there was another one.
Ordered enumeration. The method engineers use without naming it: sort the catalogue by weight, work up the list, take the first section that passes. It is a gradient method on a discrete variable and it is exactly right for a determinate member.
Stochastic methods
Simulated annealing. Propose a nearby design. If it is better, accept it. If it is worse, accept it anyway with probability exp(−Δ/T), where T is a temperature that falls as the search proceeds.
That single line is the whole method. Early on, T is high, most uphill moves are accepted and the search wanders freely. Late on, T is low, uphill moves are refused and the search settles. Exploration first, exploitation afterwards, controlled by one number.
Genetic algorithms. Keep a population rather than a point. Score them, select the better ones preferentially, combine pairs to make new candidates, mutate a few at random, repeat. Diversity in the population is what lets it hold two basins at once, and losing diversity early is exactly how it converges prematurely.
Particle swarm. Every candidate remembers its own best position and the group's, and is pulled towards both. Cheap and effective, and prone to collapsing onto the first good answer anyone finds.
Exploration and exploitation
Every method balances two things that compete:
- Exploration — looking somewhere new, which may waste the evaluation.
- Exploitation — refining what you have, which may polish a second-rate answer.
Too much exploration and the search never converges. Too much exploitation and it converges on the wrong thing. Annealing's temperature, a genetic algorithm's mutation rate and a swarm's inertia are all the same knob wearing different names.
Comparing fairly
A method that finds a better answer with ten times the evaluations has not beaten one that did not.
The comparison must be on an equal budget, and the evaluation is the unit of cost — because in structural optimisation one evaluation is one analysis, and the analysis dominates everything else by orders of magnitude. Algorithm cleverness is free; evaluations are not.
Worked example
The same method on two landscapes
Given
- Two two-variable landscapes: one smooth with a single basin, one rugged with several
- Gradient descent started from the same point (1, 5) on both
- The rugged landscape's global optimum is 1.150, located by a dense sweep
Find
What gradient descent finds on each, and what that establishes
Predict first
A gradient-based optimisation of a steel frame is run three times from three different starting designs and returns three different answers. What does that tell you?
Practice
A simulated annealing step proposes a design 0.5 units worse than the current one, at a temperature of 2. What is the probability it is accepted? Use exp(−Δ/T) and give the probability to three decimal places.
Practice
A genetic algorithm runs 30 individuals for 40 generations, evaluating every new individual once plus the initial population. Roughly how many objective evaluations is that?
Check yourself
A gradient method finds the same answer every time it is run. Is that an advantage?
Summary
- A gradient method assumes the local slope is a guide to the answer; a stochastic one assumes it is not
- Annealing's acceptance test is one line and it is the whole method
- A genetic algorithm's diversity is what lets it hold two basins at once
- Exploration and exploitation compete, and every method's control knob is the same knob
- Compare on evaluations, because in structural optimisation one evaluation is one analysis
This is educational material. It uses simplified examples to teach principles, and must not be relied on for real design or safety-critical decisions. Module overview and checkpoint