This was a TGIF talk, the blurb of which read:
Engineers use computer algorithms to solve a vast array of difficult problems, from route finding to code breaking to car design to generating jokes. The ways in which computers optimise under uncertainty has interesting implications for how we form our own beliefs.
Join Herman for a layman’s tour of engineering optimisation, travelling salesmen, evolutionary algorithms, e-tolling, baking bread, and believing in God.
Find the shortest distance between these points. You may start anywhere, but you have to finish where you started.
How did you decide upon your best route? Could you describe it in a step-by-step way (an algorithm) so that a computer or another person would be able to solve similar problem in the exact same way you would solve that problem? Most people can’t describe what steps they followed or which criteria they used. Even worse: no two people I have shown this to have given me the same answer. And no-one has given the best answer. Everyone’s answers have been sub-optimal. Humans aren’t very good at this, and the engineers I asked fared worse than the artists. (If you want to explore this further, look at the Excel spreadsheet I set up to solve the problem here).
This is the travelling salesman problem (TSP), a classic problem in industrial engineering because of its wide variety of applications and the fact that “brute-force” full enumeration (where a computer calculates every possible route and chooses the best one) isn’t practical on most of these problems. If we had a computer that would be able to calculate a “route” or combination every millisecond, the time taken to do full enumeration would look like this:
No. of towns Computation time
10 1 hour
11 11 hours
12 5.5 days
14 2.76 years
21 1.62 billion years
22 35.64 billion years
Would the answer be to increase computing power? For every town you add (between 20 and 30), you have to increase computing power roughly 20 times; a great computational leap for negligible practical advantage. This also shows that knowing exactly what the absolute best combination is (because you’ve tried all the other ones), is unrealistic. We have to settle for answers that are good enough – that are probably quite close to the best, but we’ll never really know. What we need is not more computing power, but better algorithms. I “solved” this problem in a couple of seconds using a heuristic. But more about that later.
Let us make it more interesting. Up to now, the “best” route implied the shortest distance (which assumed distance and time were interchangeable). But what if your objective was to minimise? If some of the obvious routes are tolled, the “best” answer may be to use alternative routes. By changing your objective (mathematically it would be an objective function), you have shifted the goal posts, and the “best” or optimal solution would look different.
Now suppose that there are also road closures. This may or may not force you onto the tolled roads again, but at any rate, you are now constrained, and these constraints also affect your solution.
We thus have a number of factors that affect our optimal solution: The data at our disposal (travelling times), our objective function (what it is we want / evaluation criteria), and our constraints (where we can’t or won’t go).
Heuristics: a picture
What we do when we can’t know the best answer by full enumeration, i.e. when we aren’t omniscient, but we have to act? What rules do we follow in order to get to fairly decent answers? These rules, or ways in which we (or computers) decide, are called heuristics.
I used an Evolutionary Algorithm (also called a Genetic Algorithm, or GA) built into MS Excel to solve the problem above. Of course, I don’t know whether it is the best answer (global optimum), but no-one has been able to beat it.
The GA is quite interesting. You start with a random population of genes. Each gene would be a solution to the problem, e.g., 1-2-3-4-5-6-7-8-9-10 or 2-4-6-8-10-1-3-5-7-9. You then mate them with each other, and they produce offspring. You might take the first half of the one parent’s gene, and the second half of the other parent’s gene. The computer then checks these offspring against the objective function (evaluates fitness), keeps the good/fit ones, throws away the bad/unfit ones. Survival of the fittest.
Every now and then random migrants are introduced to maintain genetic diversity, and mutations are also introduced by altering a gene, e.g. swopping the last two numbers in the gene. This can be quite important. In certain problems I am working on professionally, the solution space can be compared to a very mountainous area (more on that later). ‘Hick towns’ develop very quickly, and if I don’t introduce a large proportion of migrants, the genetic diversity plummets, and the algorithm converges on “sub-optimal” solutions. However, if you tune it well, the GA converges to very good solutions within relatively few generations (or iterations). It is relatively insensitive to the initial population, and is good at solving problems other algorithms struggle with.
Is this an engineering stamp of approval on natural, undirected biological evolution? Absolutely not. There are some significant mathematical problems with trying to do this, which I wrote about here. But it is interesting to note that most of these algorithms (particle swarm optimisation, simulated annealing) used to solve TSP’s and other problems are derived from nature. The ones devised solely by humans aren’t great.
Another picture
Genes are one way of looking at solutions to optimisation problems. But engineers also refer to the set of possible solutions as the solution space. This is easy to visualise for problems with only two variables. Let’s assume that when baking the perfect bread, the amount of salt and the amount of yeast are the two factors which you are controlling. No salt is bad, and so is no yeast. But the salt inhibits the yeast, so that they interact with each other to produce the taste you want.
The solution space can therefore be visualised as a 3D space: x, or latitude being the amount of salt, and y, or longitude being the amount of yeast. The lay of the land, or topography, will be taste. There will be some peak, or some mountain range, where we have good combinations of salt and yeast. There will also be some valleys or plains where the combination produces very salty, flat bread, for example.
Our objective is to find the highest peak on the map. The problem is that we don’t have the map, and we can’t see. We are like a man who parachutes in at night or in the mist, and must set about finding the highest peak. How should we do it? Should we just walk uphill? That might take us to the top of the local hill (local optimum), but it might turn out to be a minor hill. We should therefore tolerate walking downhill sometimes, in order to find the highest peak somewhere else.
Remember also that when our objective changed from time to money, our optimal solution also changed. So our objective determines where the highest peak is, and how high it is. The objective function determines the topography. The constraints would determine the borders of our solution space – with certain constraints we may have a very small solution space, and with others we may have a very large solution space.
Heuristics and being human
How does this apply to how we make decisions? We don’t think in terms of objective functions, solution spaces and topography. And humans aren’t computers that use genetic algorithms and the like.
Although I wouldn’t want to model a human as a machine, we still use heuristics whether we like it or not. Recognising this fact and identifying some of these heuristics won Daniel Kahnemann a Nobel Prize.
However, it is still a model. As per Deming, all models are wrong, some models are useful.
That is to say, models don’t give you a complete picture, and are severely limited. We need to recognise limitations and abide by them. I’ll also be using the model as a metaphor, and thereby more limitations are introduced. But the limitations are also distillations: by clearing away the clutter and complexity, we are able to simplify reality and focus on important features.
I’d like to apply this to the big question facing every person: choosing a worldview. The metaphor of heuristics and solution spaces offer some insights into how to approach this question:
- There are good and bad heuristics, or ways of choosing. This is probably politically incorrect, but not all ways of choosing are equally good. When you need to place the new couch in the living room, some people may look at it for a minute and find the best spot. Others may walk around it for a year before realising that there is a better way. And as with beliefs about couches, so with beliefs about God. What needs to happen for you to let go of a cherished belief? How quickly do you select another one? What do you do in between? These answers are determined by your heuristics.
- Just because you can’t see the best answer clearly, doesn’t mean that it doesn’t exist. Reality is, in this sense, still objective even if our perspectives aren’t. This is not relativism, but finite-ism.
- Let’s say that the different peaks are different worldviews, and the higher the peak, the better the worldview explains reality. How do we choose? Do we only walk uphill for fear of “compromising” and satisfy ourselves with a local maximum? That’s fundamentalism. Do we walk around the valleys, but never commit to a peak because “there are many hills?” that’s lazy agnosticism.
- The metaphor also allows us to be compassionate toward those who have a different worldview to ours. The view from their hill is probably quite good. When you ask them to come over to your side, you are asking them to walk downhill – to start somewhere where they don’t have the kind of answers they had before, and to un-understand certain fundamental things. It’s brave to let go of your answers and start again at a place of ignorance, where they view isn’t that good, even if you’ve seen the postcards of the top. It requires a good heuristic – one which tolerates temporary ignorance, but is honest enough to follow leads through to their necessary conclusions.
- What are we prepared to let go of? I have non-negiotiables – places I won’t go – constraints on what I accept as solutions – the borders of my solution space. Most people do. What are your non-negotiables? Where are your Here Be Dragons signs? How did you decide upon them? Are they worth it? It’s a bit like owning a car: it is difficult for me to get by without one. And yet it is the most dangerous piece of equipment I’ll ever operate, probably. Since I’m stuck with using a car (as with non-negotiables), the question becomes, how do I manage it responsibly?
- Up to now, explanatory power has been the objective. But I’m aware that this is my intellectual bias. This may not be everyone’s highest priority. Perhaps some people value compassion or inner peace more than I do, and would seek after a worldview that provides this for them. The implication is that their objective function is different to mine. What looks like a peak in my brand of intellectualised Christianity, may be a minor hill to them.
- Have you tried to explain to someone how to get somewhere over a telephone when they are using a different map to you? There’s a lot of confusion and irritation on both sides before you see the problem, that is, before you are quiet long enough to hear the other person describe where they are and how they see the world laid out. Again you understand by not seeing, by closing your map. Because of other peoples’ hierarchy of values, their ideal worldview looks different to your ideal worldview. Trying to bring them over to where you are is not what they need. As a Christian I do believe that Jesus is the consummation of all virtue. So he should be the highest point on all maps (or the big multidimensional map describing all virtue). But most Christians probably don’t believe it, and can’t explain it anyway.
- The hierarchy of values is an idea you find in Plato as well as in Paul. Paul calls it “inordinate desires” – desires that are not bad in themselves, but become so when they are placed in the wrong order. What does your hierarchy look like? For Jesus, love for God and love for others were number one and two. He said that if you had those two in place, the rest would follow naturally. What does your hierarchy of values look like? Is it time to reshuffle?
Herman blogs at standard-deviations.com
Recent Comments