YouTube: https://youtube.com/watch?v=I_0GBWCKft8
Previous: Why Do Neutrinos Have Mass? A Small Question with Huge Consequences
Next: How Long Does SARS-CoV-2 Last on Surfaces? What We Know

Categories

Statistics

View count:9,192
Likes:1,135
Dislikes:18
Comments:97
Duration:06:47
Uploaded:2020-06-11
Last sync:2020-06-11 22:00
Have a problem with many competing variables? Why not solve it with a computer algorithm based on cooling metal?

Hosted by: Hank Green

SciShow has a spinoff podcast! It's called SciShow Tangents. Check it out at http://www.scishowtangents.org
----------
Support SciShow by becoming a patron on Patreon: https://www.patreon.com/scishow
----------
Huge thanks go to the following Patreon supporters for helping us keep SciShow free for everyone forever:

Kevin Bealer, Jacob, Katie Marie Magnone, D.A. Noe, Charles Southerland, Eric Jensen, Christopher R Boucher, Alex Hackman, Matt Curls, Adam Brainard, Jeffrey McKishen, Scott Satovsky Jr, James Knight, Sam Buck, Chris Peters, Kevin Carpentier, Patrick D. Ashmore, Piya Shedden, Sam Lutfi, Charles George, Christoph Schwanke, Greg
----------
Looking for SciShow elsewhere on the internet?
Facebook: http://www.facebook.com/scishow
Twitter: http://www.twitter.com/scishow
Tumblr: http://scishow.tumblr.com
Instagram: http://instagram.com/thescishow
----------
Sources:
https://www.mit.edu/~dimitrib/Constrained-Opt.pdf
https://science.sciencemag.org/content/220/4598/671/tab-pdf
https://www.sciencedirect.com/topics/materials-science/annealing
https://www.sciencedirect.com/topics/materials-science/simulated-annealing
https://www.sciencedirect.com/science/article/pii/B9780444595195500058
https://www.sciencedirect.com/science/article/pii/S0969699716301168
http://www.cs.qub.ac.uk/itc2007/examtrack/report/Exam_Track_TechReportv4.0.pdf
https://ieeexplore.ieee.org/abstract/document/931933
http://www.numerical.rl.ac.uk/people/nimg/course/lectures/paper/paper.pdf
https://ieeexplore.ieee.org/abstract/document/1388541
https://www.annualreviews.org/doi/pdf/10.1146/annurev.pc.42.100191.001213
https://www.sciencedirect.com/book/9780124167438/nature-inspired-optimization-algorithms

Image Sources:
https://www.istockphoto.com/photo/liquid-molten-steel-industry-gm492798423-40641662
https://commons.wikimedia.org/wiki/File:Microstructure_of_rolled_and_annealed_brass;_magnification_400X.jpg
https://commons.wikimedia.org/wiki/File:Closest_packing_ABAC.png
https://www.istockphoto.com/vector/levels-of-protein-structure-from-amino-acids-to-complex-of-protein-molecule-gm1156462691-315184201
https://www.istockphoto.com/photo/empty-airplane-cabin-interior-gm1209626570-350095109
https://www.istockphoto.com/vector/world-map-and-global-airline-vector-gm1143071560-306841888
https://www.istockphoto.com/photo/master-goldsmith-working-with-silver-annealing-the-metal-to-make-gm512983716-87399907
https://commons.wikimedia.org/wiki/File:Travelling_salesman_problem_solved_with_simulated_annealing.gif
https://www.istockphoto.com/vector/factory-industry-manufactory-power-electricity-buildings-flat-icons-set-isolated-gm1160427625-317639897
https://www.istockphoto.com/vector/usa-territories-map-gm1152337586-312592656
https://www.istockphoto.com/photo/african-doctor-working-with-samples-gm1220382399-357326136
https://www.istockphoto.com/photo/steel-foundry-gm1162353342-318795425
https://www.istockphoto.com/photo/male-hands-typing-text-or-programming-code-on-laptop-gm1165260383-320565976
https://www.istockphoto.com/photo/black-metal-texture-background-design-gm1162391481-318823625
https://www.istockphoto.com/photo/rocker-gm1135152394-301885667
https://www.istockphoto.com/photo/group-of-business-people-in-office-cafeteria-gm1125784792-296100697
https://www.istockphoto.com/photo/cardboard-boxes-on-conveyor-roller-in-distribution-warehouse-delivery-and-packaging-gm1046521978-279993938
[ ♪INTRO ].

Say you're starting a business to make and sell…I don't know, cardboard boxes. You have some big decisions to make—like, where should you put your factories, and your warehouses, and your distribution centers?

This might not sound like a mind-bending problem, but it can be ridiculously complex. You clearly want to be close to your customers and to your suppliers to keep shipping and transportation costs down. But you also have to account for those suppliers' prices; the demand for each type of box; how much material each box uses; setup and maintenance costs; production capacity; the costs of power, and rent, and real estate; and, if you're a good citizen, the environmental impact of every choice.

It's a /lot/ to keep track of! This type of situation is called a constrained optimization problem: You're looking for the best balance of competing factors—/while/ making sure your solution is actually possible. Constrained optimization doesn't exactly get much press, like you probably had never heard of it before, but it's the hidden architecture beneath practically every human endeavor you can think of, from cardboard manufacturing to the power grid, airline routing, and even molecular biology.

And one of the most popular ways to solve problems like these takes inspiration from an unusual source: the way metals cool. Now, when I say “business decisions,” metallurgy probably isn't the first thing that comes to your mind. And it also wasn't, like, computer scientists' first thought.

They initially designed lots of efficient algorithms to find the absolute best solutions to constrained optimization problems. But those methods work best when the problem has a nice, friendly mathematical form— like when the algorithm just has to find the mathematical equivalent of like the highest spot on a hill. When the problem involves lots of variables related in more complicated ways, even a computer would take ages to find the best solution!

So eventually, researchers looked for inspiration in nature, which is great at finding solutions that might not be perfectly optimal, but come pretty close. For example, in 1983, three IBM researchers drew an analogy between optimization and, of all things, cooling metal. See, when a metal is heated and then slowly cooled, its atoms tend to settle into the arrangement with the lowest possible energy.

In other words, the arrangement of the atoms gets naturally optimized. That's convenient in metalworking, because if you want to work some metal into a certain shape, it's easiest if the atoms are all neatly arranged in a crystal structure. But normally, there are defects, like atoms out of place and fault lines between different sections of the crystal.

So metalworkers use a technique called annealing: They heat up the metal really hot, then slowly cool it down. When the metal is hot, its atoms move around randomly. But as they cool, their movements become less random: With less energy, they become less likely to jump from low-energy positions into high-energy ones.

So they naturally settle into the lowest-energy configuration, which is a defect-free crystal. Because the atoms cool so slowly, they have the opportunity to find low-energy positions before they get frozen in place. For the IBM researchers, this natural process wasn't just a neat fact about metalworking.

It was also inspiration for an optimization algorithm—in other words, a procedure computers could follow to solve complicated optimization problems. They called it simulated annealing —and the idea was to imitate the natural process. Just like physical annealing goes through different arrangements of atoms, the algorithm goes through different solutions to a constrained optimization problem.

This might not sound like an obvious comparison, but here's how it works:. In the example of the cardboard business, you'd start by generating some random choices of products, facilities, and locations. Then you'd keep making random changes.

Initially, you allow even some changes that make the profit margin or environmental impact /worse/—like moving a warehouse far from its nearest factory. That's because at this point, allowing detrimental changes is like letting the atom bounce into a position that temporarily puts the metal structure into a higher-energy state. Ultimately, that high-energy state might turn out to be a step on the way to the lowest energy one.

It's kind of like giving something a good shake to get it out of a rut. Similarly, when the algorithm suggests a /bad/ solution, that can eventually lead to an even /better/ option than it would have found otherwise. Over time, though, the algorithm becomes less and less willing to accept changes that don't improve the result—just like, as the metal cools, it keeps getting harder for atoms to bounce into higher-energy states.

Eventually, you converge on something very close to the best possible set of products, facilities, and locations. Simulated annealing is extremely popular. It's been used in over a /million/ research papers and real-world projects—and not just for cardboard boxes.

Say you work for an airline, planning flight routes. Deciding where to fly and which planes should fly each route is tricky—because you want to optimize profit per passenger and minimize wasted fuel. Meanwhile, you're constrained by things like travel time and each aircraft's capacity.

How do you balance all those factors? How do you make decisions in that wild world? Maybe simulated annealing!

Or maybe you're a molecular biologist trying to work out the structure of a protein—say, a protein that some deadly virus uses to replicate. You want your structure to match your experimental data as closely as possible, but it's constrained by the fact that the structure has to be physically possible. Again, you could try simulated annealing!

This method has also been used to schedule university exams, to decide when and where to build power generators, to help robots find the best route from point a to point b, and on and on. And it's just one of dozens of popular optimization algorithms—each of which works for a different class of problems. So really, we've just scratched the surface of how constrained optimization powers modern society—and one of the best methods comes from studying nature itself!

Thanks for watching this episode of SciShow! And a special thank you to this month's President of Space, Matthew Brant, who is one of the amazing supporters making it possible for us to keep doing episodes like this. To find out more about how you can support what we do, check out patreon.com/SciShow. [ ♪OUTRO ].