## Main.SimulatedAnnealing History

Hide minor edits - Show changes to output

Changed lines 23-31 from:

* [[https://docs.google.com/document/d/1pYurFx302tFh3J-i3O0yR7nFauVqiUPUu5eLJLHIKtc/edit?usp=sharing|MATLAB Collaborative Source Code]]

* [[https://docs.google.com/document/d/1oSdU7tETNkgXqpyEzuwNGPj6UkoeJWa51Sz1sSXs0pk/edit?usp=sharing|Python Collaborative Source Code]]

----

You can also download these files to retrieve the latest versions of the example simulated annealing files in MATLAB and Python

to:

You can download anneal.m and anneal.py files to retrieve example simulated annealing files in MATLAB and Python, respectively.

Deleted lines 26-27:

Please leave comments below if you would like to suggest improvements to the current code.

Changed line 7 from:

Simulated annealing copies a phenomenon in nature--the annealing of solids--to optimize a complex system. Annealing refers to heating a solid and then cooling it slowly~~ so that thermal equilibrium is maintained~~. Atoms then assume a nearly globally minimum energy state. In 1953 Metropolis created an algorithm to simulate the annealing process. The algorithm simulates a small random displacement of an atom that results in a change in energy. If the change in energy is negative, the energy state of the new configuration is lower and the new configuration is accepted. If the change in energy is positive, the new configuration has a higher energy state; however, it may still be accepted according to the Boltzmann probability factor:

to:

Simulated annealing copies a phenomenon in nature--the annealing of solids--to optimize a complex system. Annealing refers to heating a solid and then cooling it slowly. Atoms then assume a nearly globally minimum energy state. In 1953 Metropolis created an algorithm to simulate the annealing process. The algorithm simulates a small random displacement of an atom that results in a change in energy. If the change in energy is negative, the energy state of the new configuration is lower and the new configuration is accepted. If the change in energy is positive, the new configuration has a higher energy state; however, it may still be accepted according to the Boltzmann probability factor:

Changed line 7 from:

Simulated annealing copies a phenomenon in nature--the annealing of solids--to optimize a complex system. Annealing refers to heating a solid~~ to a liquid state~~ and then cooling it slowly so that thermal equilibrium is maintained. Atoms then assume a nearly globally minimum energy state. In 1953 Metropolis created an algorithm to simulate the annealing process. The algorithm simulates a small random displacement of an atom that results in a change in energy. If the change in energy is negative, the energy state of the new configuration is lower and the new configuration is accepted. If the change in energy is positive, the new configuration has a higher energy state; however, it may still be accepted according to the Boltzmann probability factor:

to:

Simulated annealing copies a phenomenon in nature--the annealing of solids--to optimize a complex system. Annealing refers to heating a solid and then cooling it slowly so that thermal equilibrium is maintained. Atoms then assume a nearly globally minimum energy state. In 1953 Metropolis created an algorithm to simulate the annealing process. The algorithm simulates a small random displacement of an atom that results in a change in energy. If the change in energy is negative, the energy state of the new configuration is lower and the new configuration is accepted. If the change in energy is positive, the new configuration has a higher energy state; however, it may still be accepted according to the Boltzmann probability factor:

Added lines 36-39:

Attach:sim_annealing_contour.png

Attach:sim_annealing_iterations.png

Changed lines 21-22 from:

Click the link below to use a Google Docs word processor to interactively and collaboratively develop the MATLAB or Python source code.

to:

Click the link below to use a Google Docs word processor to interactively and collaboratively develop the MATLAB or Python source code. These documents will only be unlocked for editing during class interactive sessions but they can be viewed at any time.

Deleted line 24:

Changed line 23 from:

* [[https://docs.google.com/document/d/~~1oSdU7tETNkgXqpyEzuwNGPj6UkoeJWa51Sz1sSXs0pk~~/edit?usp=sharing|MATLAB Collaborative Source Code]]

to:

* [[https://docs.google.com/document/d/1pYurFx302tFh3J-i3O0yR7nFauVqiUPUu5eLJLHIKtc/edit?usp=sharing|MATLAB Collaborative Source Code]]

Changed line 32 from:

[[Attach:simulated_annealing.zip|simulated_annealing.png]]

to:

[[Attach:simulated_annealing.zip|Attach:simulated_annealing.png]]

Added lines 1-53:

(:title Simulated Annealing Tutorial:)

(:keywords simulated annealing, Python, MATLAB:)

(:description Tutorial on simulated annealing in optimization applications.:)

!!!! Simulated Annealing

Simulated annealing copies a phenomenon in nature--the annealing of solids--to optimize a complex system. Annealing refers to heating a solid to a liquid state and then cooling it slowly so that thermal equilibrium is maintained. Atoms then assume a nearly globally minimum energy state. In 1953 Metropolis created an algorithm to simulate the annealing process. The algorithm simulates a small random displacement of an atom that results in a change in energy. If the change in energy is negative, the energy state of the new configuration is lower and the new configuration is accepted. If the change in energy is positive, the new configuration has a higher energy state; however, it may still be accepted according to the Boltzmann probability factor:

Attach:sim_annealing_boltzmann.png

where is the Boltzmann constant and T is the current temperature. By examining this equation we should note two things: the probability is proportional to temperature--as the solid cools, the probability gets smaller; and inversely proportional to --as the change in energy is larger the probability of accepting the change gets smaller.

When applied to engineering design, an analogy is made between energy and the objective function. The design is started at a high “temperature”, where it has a high objective (we assume we are minimizing). Random perturbations are then made to the design. If the objective is lower, the new design is made the current design; if it is higher, it may still be accepted according the probability given by the Boltzmann factor. The Boltzmann probability is compared to a random number drawn from a uniform distribution between 0 and 1; if the random number is smaller than the Boltzmann probability, the configuration is accepted. This allows the algorithm to escape local minima.

As the temperature is gradually lowered, the probability that a worse design is accepted becomes smaller. Typically at high temperatures the gross structure of the design emerges which is then refined at lower temperatures.

Although it can be used for continuous problems, simulated annealing is especially effective when applied to combinatorial or discrete problems. Although the algorithm is not guaranteed to find the best optimum, it will often find near optimum designs with many fewer design evaluations than other algorithms. (It can still be computationally expensive, however.) It is also an easy algorithm to implement.

----

Click the link below to use a Google Docs word processor to interactively and collaboratively develop the MATLAB or Python source code.

* [[https://docs.google.com/document/d/1oSdU7tETNkgXqpyEzuwNGPj6UkoeJWa51Sz1sSXs0pk/edit?usp=sharing|MATLAB Collaborative Source Code]]

* [[https://docs.google.com/document/d/1oSdU7tETNkgXqpyEzuwNGPj6UkoeJWa51Sz1sSXs0pk/edit?usp=sharing|Python Collaborative Source Code]]

----

You can also download these files to retrieve the latest versions of the example simulated annealing files in MATLAB and Python.

[[Attach:simulated_annealing.zip|Download Simulated Annealing Example Files]]

[[Attach:simulated_annealing.zip|simulated_annealing.png]]

Please leave comments below if you would like to suggest improvements to the current code.

----

(:html:)

<div id="disqus_thread"></div>

<script type="text/javascript">

/* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */

var disqus_shortname = 'apmonitor'; // required: replace example with your forum shortname

/* * * DON'T EDIT BELOW THIS LINE * * */

(function() {

var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;

dsq.src = 'http://' + disqus_shortname + '.disqus.com/embed.js';

(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);

})();

</script>

<noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>

<a href="http://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>

(:htmlend:)

(:keywords simulated annealing, Python, MATLAB:)

(:description Tutorial on simulated annealing in optimization applications.:)

!!!! Simulated Annealing

Simulated annealing copies a phenomenon in nature--the annealing of solids--to optimize a complex system. Annealing refers to heating a solid to a liquid state and then cooling it slowly so that thermal equilibrium is maintained. Atoms then assume a nearly globally minimum energy state. In 1953 Metropolis created an algorithm to simulate the annealing process. The algorithm simulates a small random displacement of an atom that results in a change in energy. If the change in energy is negative, the energy state of the new configuration is lower and the new configuration is accepted. If the change in energy is positive, the new configuration has a higher energy state; however, it may still be accepted according to the Boltzmann probability factor:

Attach:sim_annealing_boltzmann.png

where is the Boltzmann constant and T is the current temperature. By examining this equation we should note two things: the probability is proportional to temperature--as the solid cools, the probability gets smaller; and inversely proportional to --as the change in energy is larger the probability of accepting the change gets smaller.

When applied to engineering design, an analogy is made between energy and the objective function. The design is started at a high “temperature”, where it has a high objective (we assume we are minimizing). Random perturbations are then made to the design. If the objective is lower, the new design is made the current design; if it is higher, it may still be accepted according the probability given by the Boltzmann factor. The Boltzmann probability is compared to a random number drawn from a uniform distribution between 0 and 1; if the random number is smaller than the Boltzmann probability, the configuration is accepted. This allows the algorithm to escape local minima.

As the temperature is gradually lowered, the probability that a worse design is accepted becomes smaller. Typically at high temperatures the gross structure of the design emerges which is then refined at lower temperatures.

Although it can be used for continuous problems, simulated annealing is especially effective when applied to combinatorial or discrete problems. Although the algorithm is not guaranteed to find the best optimum, it will often find near optimum designs with many fewer design evaluations than other algorithms. (It can still be computationally expensive, however.) It is also an easy algorithm to implement.

----

Click the link below to use a Google Docs word processor to interactively and collaboratively develop the MATLAB or Python source code.

* [[https://docs.google.com/document/d/1oSdU7tETNkgXqpyEzuwNGPj6UkoeJWa51Sz1sSXs0pk/edit?usp=sharing|MATLAB Collaborative Source Code]]

* [[https://docs.google.com/document/d/1oSdU7tETNkgXqpyEzuwNGPj6UkoeJWa51Sz1sSXs0pk/edit?usp=sharing|Python Collaborative Source Code]]

----

You can also download these files to retrieve the latest versions of the example simulated annealing files in MATLAB and Python.

[[Attach:simulated_annealing.zip|Download Simulated Annealing Example Files]]

[[Attach:simulated_annealing.zip|simulated_annealing.png]]

Please leave comments below if you would like to suggest improvements to the current code.

----

(:html:)

<div id="disqus_thread"></div>

<script type="text/javascript">

/* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */

var disqus_shortname = 'apmonitor'; // required: replace example with your forum shortname

/* * * DON'T EDIT BELOW THIS LINE * * */

(function() {

var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;

dsq.src = 'http://' + disqus_shortname + '.disqus.com/embed.js';

(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);

})();

</script>

<noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>

<a href="http://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>

(:htmlend:)