Course Work,  Guides,  Programming,  Python

Simulated annealing

March 6, 2018 /

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:

  1. Identify an objective and cost function
  2. Initiate a random solution and calculate its cost
  3. Generate a random neighbouring solution and calculate its cost too
  4. 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

You May Also Like

Statistics on wine tasting reviews

February 21, 2018

Genetic algorithms

April 19, 2020

Heavy sand

February 19, 2018

58 Comments

  • cialis online

    December 23, 2020 at 14:23 Reply

    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

    January 7, 2021 at 01:35 Reply

    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

    January 8, 2021 at 03:15 Reply

    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.

  • balenciaga

    January 18, 2021 at 19:01 Reply

    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

    January 18, 2021 at 19:01 Reply

    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

    January 21, 2021 at 21:28 Reply

    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

    January 21, 2021 at 21:29 Reply

    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

    January 21, 2021 at 21:29 Reply

    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

    January 25, 2021 at 03:46 Reply

    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

    January 25, 2021 at 03:47 Reply

    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

    January 31, 2021 at 16:46 Reply

    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

    January 31, 2021 at 16:47 Reply

    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

    January 31, 2021 at 16:47 Reply

    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.

  • free movies

    February 1, 2021 at 22:03 Reply

    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

  • dizi

    February 8, 2021 at 14:39 Reply

    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

    February 9, 2021 at 11:16 Reply

    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

  • tinyurl.com

    February 12, 2021 at 02:30 Reply

    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/

    February 21, 2021 at 19:19 Reply

    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

    February 22, 2021 at 05:01 Reply

    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 sleep

    February 22, 2021 at 08:50 Reply

    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 gummies

    February 22, 2021 at 11:18 Reply

    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 for anxiety

    February 22, 2021 at 17:35 Reply

    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

    February 22, 2021 at 19:11 Reply

    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!

  • wso shell

    February 27, 2021 at 22:41 Reply

    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!

  • instagram takipci almak

    February 28, 2021 at 00:05 Reply

    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

  • nova88

    March 1, 2021 at 07:40 Reply

    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

    March 1, 2021 at 12:52 Reply

    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!

Leave a Reply

Your email address will not be published. Required fields are marked *