# Simulated annealing

I’m currently studying a whole bunch of *nature inspired algorithms*, or in other words optimisation methods inspired by natural phenomena.

The simulated annealing (SA) algorithm is an optimisation method that is able to also solve complex optimisation problems. The strength of SA is its ability to overcome the ‘neighbourhood limit’ that restricts simple optimisation algorithms.

A classical example of the applicability of SA, also emphasised in the original article Optimization by Simulated Annealing (Kirkpatrick et al. 1983), is its ability to solve the traveling salesman problem (a well known NP problem where we want to optimise a travel person’s path, so (s)he travels the least amount of miles).

## Optimisation algorithms in general

In large terms, most optimisation algorithms will generate a random solution and explore the nearby area of solutions to see if it yields better solutions than the current one. For simple algorithms, if a neighbouring solution is better than the current one, the algorithm will settle on this instead. If not, the algorithm has probably found the best solution.

The ‘size of the neighbourhood’ therefore becomes the limit of efficiency, and this can be problematic for some functions. Say, we want to find the global maximum of the following graph, and that we initiate our simple algorithm at the star. We will find better solutions towards Top 5, until we reach this solution and (wrongly) conclude that there are no better solutions in the neighbourhood.

## The nature of simulated annealing

SA is based on an analogy with the annealing of metals. Strong metals are created by the heating and step-wise cooling of the material. In the beginning, when the material is completely melted, there is no order or structure in the atoms. As they flow about, the material changes state (configuration of atoms) constantly. During each cooling step, the material is given some time to allow it to relax and slowly harden into a stable structure. If you cool it too fast, some areas will settle in random non-ordered structures from the melting phase, and you will end up with a weaker metal.

Extending this process to the problem of function optimisation has shown surprising potential, and the analogy is so rich that the extension with thermodynamic analogies guides and explains optimisation approaches surprisingly well.

## The big picture

Let’s bring this analogy back down to Earth for a moment; we will jump anywhere in the domain of whatever function we are trying to optimise and slowly narrow in on the optimum using various criteria to ensure this. A gross simplification of the annealing schedule is illustrated below, but it captures the essence of SA. Already in the first jump (the blue one), we cross two minima we wouldn’t have crossed using a simple algorithm. This is what helps the algorithm to determine decent approximations to complex optimisation problems.

## Pseudocode steps

Let’s continue to work with a simplification of the algorithm, and gradually add more to it. The essential steps of the algorithm is to:

- Identify an objective and cost function
- Initiate a random solution and calculate its cost
- Generate a random neighbouring solution and calculate its cost too
- Accept the new solution with some probability
- Let the solution settle

*Identify an objective and cost function*

This is entirely up to you – your objective function is whatever function you want to optimise, and the cost function is whatever ‘price’ this solution represents. Notice that you have to calculate the cost of every proposed solution, so keep it as simple as possible in order to keep your algorithm efficient. It could simply be the function value (the y-value to the proposed x-value) or the number of miles traveled by the traveling sales person, and sometimes it has to be more complex. It entirely depends on your optimisation problem.

*Initiate a random solution and calculate its cost*

You don’t have to guess anything near the optimal solution, just use a random generator to initiate the algorithm and calculate its cost.

*Generate a random neighbouring solution and calculate its cost too*

To generate a ‘random neighbouring’ solution, all you have to do is switch two random elements of your current solution. The main requirement is that the two elements are randomly chosen. Then, calculate its cost too.

*Accept the new solution with some probability*

Random movement in optimisation yields surprising benefits – that’s why we generate random neighbourhood solutions. But sometimes, we need to cross through a ‘bad’ neighbourhood to get closer to the best solution – especially if we’re far away from it to begin with. With this in mind, we need to define an acceptance probability that will always move towards better solutions, but will also sometimes go towards worse solutions. To help keep the cost function simple, we need to exaggerate the difference between slightly better solutions (very close neighbours have almost the same cost), so we want to use the exponential difference of the costs:

\( P_{acc} = \exp {\text{cost}_{\text{proposed}} – \text{cost}_{\text{current}} } \)

As described in the beginning, the analogy is centred around the cooling schedule of a system which allows it to slowly settle into an optimal solution, so we introduce a temperature parameter, \(T\). Usually, we start the temperature at 1 and slowly decrease it using an \(\alpha\)-value typically between 0.8 and 0.99. The temperature is therefore dependent on the number of iterations you have gone through, and we want it to affect how much we will accept random movements away from the current optimal solution. After N iterations, we’d prefer the algorithm to confidently settle on a solution and not accidentally end up at an entirely random solution. We therefore include it in the acceptance probability (this also has strong connection with the actual thermodynamic formulation):

\( P_{acc} = \exp {\frac{\text{cost}_{\text{proposed}} – \text{cost}_{\text{current}}}{T} } \)

Using random uniform numbers between 0 and 1, we will accept a proposed solution as our next move if the acceptance probability is larger than the random number. After N iterations, it will thus be highly unlikely to move towards worse solutions, and all we’d have to do to see that we hit a rare coincidence would be to run the algorithm a few times.

*Letting the optimal solution settle in each step*

For each iteration, that is for each value of T, we should run the algorithm (with this T-value), somewhere between 100-1000 times. This is analogous to the step-wise cooling scheme of actual annealing where the material gets time to settle. Remember, as the temperature decreases, so does the probability of random movement, but we still need to explore the possible configurations at that temperature before continuing, otherwise we might end up in a random place and suddenly just get stuck because the temperature decreases too fast. With gradual exploration at each temperature step, we’re less likely to end up at the wrong optimal solution.

## Pseudo code

To really pull SA down to Earth, take a look at the following (incomplete) script. It is only meant to highlight the characteristics of the algorithm. I plan on describing my implementation of SA in a graph partitioning example, if I get the time. If I do, I’ll make sure to include a link for it in this post.

from random import random as r def annealing_schedule(some_solution): current_optimal_solution = some_solution cost_old = cost(current_optimal_solution) T = 1 T_min = 0.000001 alpha = 0.99 while T > T_min: i = 1 while i <= 500: proposed_solution = neighbour(current_solution) cost_proposed = cost(proposed_solution) P_acc = acceptance_probability(cost_proposed, cost_old, T) if P_acc > r(): current_optimal_solution = proposed_solution cost_old = cost_proposed i += 1 T *= alpha return current_optimal_solution

## Final remarks

There are many variations of simulated annealing, but this article stays true to the core principles without drawing too much on the original articles which I found difficult to follow and translate into generalisable programming. Simulated annealing essentially is kind of a mix of a hill climbing method and an extended Metropolis algorithm. It gradually chooses the better solutions, but jumps randomly in the neighbourhood and will sometimes choose poorer solutions similar to the Metropolis algorithm.

##### Inspiration for this post

- This post was strongly inspired by Katrina Ellison Geltman’s post (and her sources), where I personally found that it was missing some helpful parts – you can read her post here.
- http://mathworld.wolfram.com/SimulatedAnnealing.html
- http://www.cs.cmu.edu/afs/cs.cmu.edu/project/learn-43/lib/photoz/.g/web/glossary/anneal.html
- https://stackoverflow.com/questions/5413115/understanding-simulated-annealing-conceptually
- The original 1983 article by Kirkman et al.

## 58 Comments

## Tracy

Thanks for the excellent guide

## ปั๊มไลค์

Like!! I blog frequently and I really thank you for your content. The article has truly peaked my interest.

## ทิชชู่เปียกแอลกอฮอล์

I really like and appreciate your blog post.

## cialis online

The main component of The Levitra Tablet is vardenafil, another phosphodiesterase inhibitor.I’m in zakopana for 10 days.After ingesting Viagra 50 in the body, it produces the following action.Avoid getting up too fast from a sitting or lying position, or you may feel dizzy.This supplement may be of most benefit to CYP2D6 poor metabolizers.

## cbd oil

I needed to draft you one little bit of observation so as to say thanks once again for your lovely opinions you’ve documented in this article. It is quite remarkably generous of people like you to deliver openly exactly what a number of us could possibly have marketed as an e book to end up making some cash for themselves, most importantly given that you could possibly have done it in the event you wanted. Those tactics in addition worked to become great way to realize that someone else have the same keenness similar to my very own to realize significantly more with reference to this problem. I know there are some more pleasurable situations up front for people who scan through your website.

## purchase finasteride

I am only writing to make you understand what a superb experience our princess undergone viewing your webblog. She picked up such a lot of things, with the inclusion of what it is like to possess an ideal teaching spirit to make the mediocre ones without difficulty master specified tricky topics. You undoubtedly surpassed readers’ expected results. Thanks for rendering those useful, trustworthy, revealing as well as unique tips on your topic to Sandra.

## superbeets review

Saved as a favorite, I love your site!|

## balenciaga

I precisely had to thank you very much again. I’m not certain the things that I could possibly have tried in the absence of the actual pointers provided by you regarding such a field. It has been an absolute frightening crisis in my opinion, however , witnessing a new professional manner you processed that made me to leap with fulfillment. I will be happy for the information and thus expect you comprehend what a powerful job you happen to be getting into instructing others all through your webpage. Most probably you’ve never met any of us.

## supreme clothing

I actually wanted to write down a brief note in order to say thanks to you for these precious items you are giving on this site. My extensive internet search has at the end been honored with beneficial content to talk about with my companions. I would point out that many of us visitors are undeniably fortunate to be in a decent site with so many perfect individuals with very helpful plans. I feel really fortunate to have discovered your entire webpages and look forward to tons of more fun times reading here. Thanks once more for a lot of things.

## lebron shoes

My spouse and i ended up being very lucky that Michael could deal with his basic research using the ideas he grabbed when using the web site. It is now and again perplexing to just be releasing strategies which often a number of people might have been making money from. And now we take into account we’ve got you to give thanks to because of that. These explanations you have made, the simple site menu, the friendships your site assist to instill – it is mostly terrific, and it’s really letting our son and us imagine that the concept is thrilling, and that’s exceptionally vital. Thank you for the whole thing!

## off white x jordan 1

I actually wanted to type a quick comment in order to say thanks to you for some of the nice tips and tricks you are showing on this website. My prolonged internet search has now been recognized with reasonable suggestions to exchange with my classmates and friends. I would express that most of us website visitors are very lucky to live in a very good network with so many wonderful professionals with useful secrets. I feel really lucky to have encountered the webpage and look forward to some more brilliant times reading here. Thanks a lot once more for everything.

## yeezy boost 350

I wish to point out my gratitude for your kind-heartedness giving support to men who require help with in this content. Your very own commitment to getting the message all-around came to be exceedingly advantageous and has specifically permitted somebody much like me to get to their goals. Your helpful suggestions entails a great deal a person like me and extremely more to my peers. Regards; from each one of us.

## kyrie 6 shoes

My wife and i have been absolutely fulfilled when Ervin could deal with his investigation through the ideas he had from your site. It is now and again perplexing just to choose to be handing out hints that many others might have been selling. And we also fully understand we have the website owner to appreciate for that. Those illustrations you have made, the straightforward web site menu, the friendships your site help to promote – it’s all terrific, and it’s facilitating our son in addition to our family do think the situation is cool, which is really serious. Thank you for everything!

## pandora

I precisely desired to say thanks yet again. I do not know the things I would’ve worked on without the entire tips and hints discussed by you relating to my concern. It was actually an absolute alarming crisis for me, but considering a new well-written technique you processed the issue made me to weep over gladness. I am just thankful for the support and as well , believe you are aware of an amazing job you are getting into teaching people today through the use of your web blog. More than likely you have never met any of us.

## kobe shoes

I really wanted to type a brief note to thank you for all of the amazing techniques you are giving out on this website. My extended internet search has at the end of the day been honored with pleasant content to go over with my contacts. I would point out that most of us website visitors are unequivocally fortunate to dwell in a great network with many awesome people with interesting guidelines. I feel very much blessed to have used the web page and look forward to so many more entertaining moments reading here. Thank you once more for all the details.

## stone island

I as well as my pals came looking at the good key points located on your site and then the sudden got a terrible suspicion I had not expressed respect to the web site owner for those tips. The boys had been certainly stimulated to read all of them and now have certainly been tapping into them. Thanks for being well helpful and also for going for this sort of remarkable areas most people are really desperate to know about. Our honest apologies for not expressing gratitude to you sooner.

## lebron shoes

I truly wanted to write down a remark to be able to express gratitude to you for those pleasant advice you are placing on this website. My particularly long internet search has finally been paid with professional facts and strategies to exchange with my colleagues. I ‘d mention that many of us website visitors are extremely endowed to live in a superb community with many marvellous professionals with very beneficial tactics. I feel rather blessed to have used your entire web page and look forward to plenty of more excellent minutes reading here. Thanks a lot once more for a lot of things.

## cheap flights

Your way of explaining everything in this paragraph

is in fact good, all can easily understand it, Thanks

a lot.

## watch free

I used to be able to find good info from your content. Felita Jarad Wehner

## cheap flights

Hello everybody, here every one is sharing

these familiarity, so it’s pleasant to read this web site, and I used to go to see this website

everyday.

## free movies

I was wondering if you ever considered changing the layout of your website? Its very well written; I love what youve got to say. But maybe you could a little more in the way of content so people could connect with it better. Youve got an awful lot of text for only having 1 or 2 images. Maybe you could space it out better? Cinda Nels Kolnos

## diziler

Wauw! Wat een mooi land zeg! En wat een interessante feiten. Tabitha Edouard Erlandson

## watch online

Dead pent articles , appreciate it for information . Beatrix Pietro Kriste

## canli tv

Pretty! This has been a really wonderful article. Thank you for supplying this information. Greer Thom Galina

## access

Thank you, Josiah. That helps us to pray for you and your family. Lorilyn Cleavland Sheffield

## cheap flights

Howdy! I’m at work browsing your blog from

my new iphone! Just wanted to say I love reading through your blog and look

forward to all your posts! Carry on the superb work!

## dizi

Once I originally commented I clicked the -Notify me when new feedback are added- checkbox and now each time a remark is added I get 4 emails with the same comment. Is there any means you can take away me from that service? Thanks! Emylee Base Lidda

## dizi

Hello There. I found your blog the usage of msn. That is an extremely well written article. Ebonee Sawyer Welles

## dizi

you are in reality a excellent webmaster. The site loading pace is incredible. It seems that you are doing any unique trick. Moreover, The contents are masterwork. you have performed a fantastic process in this subject! Nanete Pavel Kiel

## dizi

It is a very good useful article I like to read such articles Cammi Emmerich Ailin

## fringe

Is it those girls yang kai met inside the emperor garden?? Jessalyn Jarred Torbert

## tinyurl.com

Hello, Neat post. There is a problem with your website in web explorer, may test this?

IE nonetheless is the marketplace chief and a huge portion of people will pass over your

great writing because of this problem.

## https://www.facebook.com/pages/category/Health---Wellness-Website/Vital-flow-reviews-102135748499657/

This video is presenting does vital flow work but also try to cover the following subject:https://www.facebook.com/pages/category/Health—Wellness-Website/Vital-flow-reviews-102135748499657/

-vital flow for prostate

-vitalflow prostate really works

-vitalflow prostate support reviews

One thing I noticed when I was researching info on does vital

flow work was the absence of appropriate details.

Does vital flow work nevertheless is an subject that I know

something about. This video therefore should be relevant and

of interest to you.

~~~~~~~~~~~~~~~~~~~~~

Follow our video clips about does vital flow work as well

as other comparable topics on

Hmm it appears like your website ate my first comment

(it was extremely long) so I guess I’ll just sum it

up what I submitted and say, I’m thoroughly enjoying your blog.

I too am an aspiring blog blogger but I’m still new to everything.

Do you have any recommendations for novice blog writers? I’d definitely

appreciate it.

## buy CBD oil

Hi everyone, it’s my first pay a quick visit at this site, and piece of writing is in fact fruitful in support of me, keep

up posting these types of articles or reviews.

## CBD oil for dogs

In fact no matter if someone doesn’t be aware of

after that its up to other people that they will help, so

here it takes place.

my web site :: CBD oil for dogs

## CBD for sale

Hi, yeah this paragraph is really fastidious and I have learned

lot of things from it about blogging. thanks.

## best CBD for dogs

Hello to all, how is all, I think every one is getting more from

this web site, and your views are pleasant for new visitors.

Also visit my website … best CBD for dogs

## cbd oil for sleep

I do consider all the concepts you’ve introduced for

your post. They are really convincing and can certainly work.

Still, the posts are very brief for starters. Could you please lengthen them a little from

subsequent time? Thank you for the post.

my blog post … cbd oil for sleep

## cbd for dogs with anxiety

Wow, superb blog layout! How long have you been blogging for?

you made blogging look easy. The overall look of your site is

wonderful, as well as the content!

## cbd gummies

Amazing blog! Is your theme custom made or did you download it from somewhere?

A design like yours with a few simple adjustements would really make my blog jump out.

Please let me know where you got your theme. With thanks

## cbd gummies

It’s very effortless to find out any matter on net as compared to books, as I

found this post at this web site.

## CBD gummies for anxiety

Whats up very nice website!! Man .. Excellent .. Amazing ..

I’ll bookmark your web site and take the feeds also?

I am happy to search out a lot of helpful info here in the publish, we need work out extra strategies in this regard, thanks for sharing.

. . . . .

## cbd gummies for sleep and anxiety

Greetings, I think your blog might be having browser compatibility problems.

Whenever I look at your site in Safari, it looks fine however, when opening in Internet Explorer, it has

some overlapping issues. I merely wanted to give you a quick

heads up! Other than that, fantastic website!

## best cbd oil for dogs

Your style is so unique compared to other people I have

read stuff from. I appreciate you for posting when you’ve got the opportunity, Guess

I’ll just book mark this page.

## best cbd gummies

I love what you guys are usually up too. This type of clever work

and reporting! Keep up the very good works guys I’ve you guys to my personal blogroll.

## lekekremim.com

https://www.lekekremim.com/ türkiyenin en iyi sitelerinden biri olan cilt aydınlatıcı şampuan leke kremi gibi bir çok ürünü barından ve tek marka üzerinden alışveriş seçeneği

sunan lekekremim.com u ziyaret etmenizi tavsiye ediyoruz

## https://www.havadis07.com

Awesome post.

## https://www.antalya-bocek-ilaclama.net/

Its like you read my mind! You seem to know a lot about this, like you wrote the book in it

or something. I think that you could do with a few pics to drive the message home

a little bit, but instead of that, this is great blog. An excellent read.

I will certainly be back.

## Instagram takipçi satın alma

Hey just wanted to give you a quick heads up and let you know a

few of the images aren’t loading correctly. I’m not sure why but I

think its a linking issue. I’ve tried it in two different web browsers and both

show the same outcome.

## takipci satin al

Wonderful, what a blog it is! This weblog provides useful data to us, keep

it up.

## wso shell

Thanks for the marvelous posting! I seriously enjoyed reading

it, you could be a great author.I will ensure that I bookmark your blog and may come back from

now on. I want to encourage one to continue your great

job, have a nice evening!

## takip2018.com

You should be a part of a contest for one of the highest quality websites on the net.

I am going to recommend this web site!

## instagram takipci almak

Hello just wanted to give you a quick heads up. The text in your post seem to be running off the

screen in Ie. I’m not sure if this is a format issue or something to do with

browser compatibility but I figured I’d post to let you know.

The style and design look great though! Hope

you get the issue solved soon. Kudos

## leke kremi satin al

I take pleasure in, cause I discovered just what I

was taking a look for. You have ended my 4 day lengthy hunt!

God Bless you man. Have a great day. Bye

## Instagram Takipçisi Nedir Nasıl Alınır

I am regular reader, how are you everybody? This piece of writing posted at this web page is in fact fastidious.

## instgaram takipci satin alma

My brother recommended I might like this blog. He was entirely right.

This post truly made my day. You can not imagine just

how much time I had spent for this info! Thanks!

## nova88

Hello! I just want to give you a big thumbs up for the great info you have right here on this post.

I will be returning to your blog for more soon.

## Sadrazam logsuz shell

You’re so cool! I do not think I have read

something like that before. So great to discover

another person with some original thoughts on this issue.

Seriously.. thank you for starting this up. This web site is

one thing that’s needed on the web, someone with a little originality!