Archive | October 2013

Finding a Better Truss

This was an experiment in using simulated annealing to improve the load bearing capacity of a truss.

Essentially, SA is a technique used to find the “best” state of a given system. It stems from the metallurgical technique of heating and cooling a metal to reduce the Gibbs energy and relieve internal stresses. In general terms we begin with a problem which has a certain energy landscape, and use SA to find either the highest or lowest point on the landscape. The animation below (Wikipedia) is probably the simplest explanation:

Simulated Annealing

In Layman’s Terms

If you start at a point on the landscape, say somewhere in the leftmost valley above, you can easily find a “better” spot by just walking up the hill. But eventually you’ll get to the top and be unable to move any higher, even though you can clearly see that gigantic mountain in the middle. To get there, you have to go back down! But at least you can see the mountain peak so you know you’re not in the best spot, because the best spot is over there. What if you were blind, and all you had was an altimeter to tell you how high you were? You wouldn’t be able to see the mountain, so from your perspective you would have already found the best spot. SA is just what you need to find the actual best spot.

Our blind mountain climber with an altimeter – let’s call him Dave – is a smart guy. He knows that if his altimeter shows a certain value, and whenever he moves it shows a lower value, he’s at a high point: a local maximum. But he wants to find the single highest point: the global maximum. Dave knows that he will sometimes have to move down before he can start moving back up, and that when he does he may end up in a better position.

At dawn, when he first sets out, he doesn’t mind going back down the gradient to try finding a better spot. There’s a pretty low chance that he’d be able to find the highest point so early in the morning and he accepts that, contentedly moving back downhill before going higher. But as the day wears on, Dave gets a bit tired of the whole business. He’s passed a few peaks in the last few hours but none was as high as the one he passed around noon, and he’s wondering if maybe that midday mountain was the highest. So he becomes less happy about moving downhill and gradually starts just moving uphill. When night comes, he has found a good peak, but it’s not quite as high as the earlier one. He doesn’t much care about darkness, but he’s tired of searching, so he goes straight back to the highest point and makes camp, satisfied that this is most likely the best spot in the area.

In General

The general SA algorithm is analogous to Dave’s adventure. To apply SA to optimising an arbitrary system requires only two parts: a way to define the “energy” of the system’s state at any given time, and a temperature. We begin with a certain state s and a temperature T, and let’s say we’re looking for the state with minimum energy. We find a point (in configuration space) near s, called s'. The two states have energies e and e' respectively. If e' < e then s' is a better configuration than s, so we move to the new state and repeat from there. But if e' > e then we’d be moving in the wrong direction! This is where the temperature comes in: as the temperature of the simulation cools, the likelihood of moving to a “worse” state decreases. This is just like Dave getting tired through the day. So we define a function P(e,e',T) which compares the two energies, taking into account the temperature, and gives the probability of moving to the worse point. As the simulation evolves, the temperature cools, and the probability of choosing a worse configuration decreases.

The probability function P(e,e',T) can really be anything, as long as:

  • If e' < e (or > for a maximisation problem) then P = 1
  • If e' > e then P decreases as e'-e increases: there’s a lower chance of going up a steep gradient
  • P decreases as T decreases

In Particular

By keeping the truss’ member “network” (i.e. which members connect to which) constant, the state of the truss can be represented by the lengths of it’s members. The truss is represented by the (x,y) coordinates of it’s joints, so the list of joint positions acts as a proxy for the list of member lengths. Neighbouring states can then be found by moving a joint by a small amount; in this implementation I move a single joint by a random small amount each iteration. This way, the neighbouring states whose energies we compare differ only in the position of one joint.

The “energy” of a given truss is whatever we’re trying to optimise, which makes the maximum safe load a good metric. Another metric could be (maximum load)/(mass of truss) to give an efficiency score of sorts, but I haven’t explored this yet.

For the probability function I’ve found good results with P(e,e',T) = exp \left( -10 \cdot \frac{\Delta E}{T} \right). I’ve been running all these simulations on a five year old netbook, so there may be other functions which give better results but this one finds a good result in reasonable time (

For the temperature cycle, I’m repeatedly heating and cooling the simulation until sufficient time has passed since the last “best” state was found. The length of the cooling period is denoted by k_{max} – the maximum number of iterations k before reheating. The temperature function T(k,k_{max}) = \frac{2}{1+exp\left(15\cdot\frac{k}{k_{max}}\right)} has given decent results. It follows the lower half of a sigmoid curve, decreasing quickly from one and asymptotically approaching zero.

To limit the time taken, after 400 consecutive failed attempts at improving the truss, the simulation resets to the best solution so far. After 5 consecutive resets (2000 failed attempts in a row) the SA is finished. These numbers are arbitrary and as they’re quite small, generally won’t find the single optimum solution. But for a ten minute processing time, I find it sufficient.

As a side note, this program is an extension of the previous truss analysis script. In that script the truss was represented by a set of global tables, which was fine for that application but as SA requires comparing multiple trusses this wasn’t a great structure. So here the trusses are instances of a Truss class, which contains the necessary tables and methods for calculating the maximum load, etc. I’m more familiar with C++ classes so learning the python way was interesting!

And finally, here is another example of the program’s output:

8.0

The project is available on GitHub.