319 - What is Simulated Annealing Optimization?
Summary
TLDRIn this video, the speaker delves into simulated annealing optimization, explaining its fundamentals by drawing parallels to the metallurgical process of annealing. The algorithm lowers temperature iteratively, accepting better solutions and sometimes worse ones to avoid local minima. By doing so, it explores solution spaces effectively. The speaker also walks through Python code snippets, detailing how to set cooling rates, initial and final temperatures, and bounds for the algorithm. The video concludes with a demonstration of a 3D optimization example, setting the stage for further exploration of simulated annealing in practical scenarios.
Takeaways
- 😀 The video is part of a series covering meta-heuristic algorithms, specifically focusing on simulated annealing and particle swarm optimization.
- 🤖 Simulated annealing is inspired by the metallurgical process of annealing, where temperature is slowly reduced to achieve an optimal structure.
- 🔥 The algorithm iteratively decreases the temperature and compares current solutions to previous ones, accepting worse solutions at higher temperatures to avoid local minima.
- 📉 At high temperatures, the algorithm is more likely to accept suboptimal solutions, which helps explore the search space more effectively.
- 🌡️ The cooling schedule determines how fast the temperature decreases over each iteration, and the typical approach is to use a fixed cooling rate.
- 💻 The algorithm is explained through Python code, demonstrating how it starts with an initial solution, iterates through solutions, and accepts or rejects them based on probability.
- 🔧 The example given uses a simple objective function, with specific bounds set for the search space, and uses standard Python libraries like NumPy and Matplotlib for visualization.
- 🎲 The algorithm uses random values and probabilities to explore different solutions, with a key focus on finding a balance between exploration and exploitation.
- 📊 Visualization of the solution space helps demonstrate how the algorithm searches for the optimal solution, navigating through a contour or 3D plot.
- 📈 The video concludes with an example of visualizing a more complex optimization problem, setting the stage for more practical applications in the next tutorial.
Q & A
What is the main topic of the video?
-The main topic of the video is simulated annealing optimization, which is a metaheuristic algorithm inspired by the metallurgical process of annealing.
What is the goal of the simulated annealing algorithm?
-The goal of the simulated annealing algorithm is to find the optimal solution to a given problem by iteratively adjusting a temperature parameter that guides the search process.
How does the simulated annealing algorithm work?
-The algorithm works by starting at a high temperature and iteratively decreasing it. At each step, it generates a new solution and decides whether to accept it based on whether it's better than the current solution and the current temperature.
What is the significance of starting at a high temperature in simulated annealing?
-Starting at a high temperature allows the algorithm to accept worse solutions, which helps it escape local minima and explore the solution space more effectively.
How does the cooling schedule affect the simulated annealing process?
-The cooling schedule determines how quickly the temperature decreases. A slower cooling schedule allows for more iterations and can lead to better solutions, but it also increases the computation time.
What is the role of the probability function in accepting new solutions?
-The probability function determines the likelihood of accepting a new solution that is worse than the current one. It is higher at higher temperatures, allowing more exploration of the solution space.
What does the algorithm do if the new solution is better than the current one?
-If the new solution is better (i.e., has a lower objective function value), it is accepted as the current solution.
How is the initial solution for the algorithm determined?
-The initial solution is randomly chosen within the defined search space at the start of the algorithm.
What is the purpose of defining bounds in the simulated annealing algorithm?
-Defining bounds helps limit the search space to where the solution is most likely to be found, making the search more efficient.
How does the algorithm ensure it finds the global minimum or maximum?
-The algorithm does not guarantee finding the global minimum or maximum but increases the likelihood by accepting worse solutions at higher temperatures and gradually decreasing the temperature to focus on better solutions.
What is the difference between simulated annealing and other optimization algorithms?
-Simulated annealing differs from other optimization algorithms by using a temperature parameter to control the acceptance of worse solutions, allowing it to escape local minima and explore the solution space more thoroughly.
Outlines
😀 Introduction to Simulated Annealing Optimization
The speaker introduces the video by recapping the previous discussion on meta-heuristic algorithms and promising to cover simulated annealing (SA) and particle swarm optimization (PSO). This video focuses on SA, an optimization technique inspired by the metallurgical process of annealing, where temperature decreases gradually to reach an optimal structure. SA similarly cools down iteratively to explore potential solutions, comparing them to previous iterations to assess improvements. The speaker hints at the importance of temperature adjustments, discussing how higher temperatures allow the acceptance of worse solutions to avoid getting stuck in local minima.
🔍 Overview of the Simulated Annealing Process
This section delves deeper into the SA process, explaining how it works by starting with an initial solution and iteratively generating new ones. If the new solution is better, it's accepted; if worse, it's accepted with a certain probability, especially at high temperatures. The idea is to explore a wider solution space and avoid local optima by accepting worse solutions during the early stages. The cooling schedule dictates how fast the temperature decreases over iterations. A balance between exploration (high temperatures) and exploitation (low temperatures) is emphasized.
📊 Setting Up the Simulated Annealing Algorithm
Here, the speaker transitions into setting up the algorithm using Python code. They define an objective function and set bounds for the search space. Initial and final temperatures, as well as the cooling rate, are established. The speaker describes the goal as finding the optimal solution within these bounds, working through iterations to achieve that. They also explain how visualizing the solution space via contour plots aids in understanding the optimization process, though this part of the visualization is optional for the audience.
🖥️ Coding the Simulated Annealing Algorithm
The speaker outlines the implementation of the SA algorithm in Python, step by step. The function takes parameters like the objective function, bounds, initial and final temperatures, and the cooling rate. The process involves initializing random parameters and iterating while the temperature is higher than the final set point. The speaker explains how solutions are updated, the delta is calculated, and how probabilities influence whether to accept worse solutions. The cooling rate controls how quickly temperature decreases, and multiple cooling rates are tested to see how they affect optimization performance.
📈 Visualizing the Optimization Process
In this final section, the speaker introduces a more complex objective function and uses 3D plotting to visualize the optimization process. The goal is to start at a random point in the solution space and iteratively navigate toward the peak. The speaker demonstrates how the SA algorithm finds the peak in the 3D plot and emphasizes that the method used for visualization can help in understanding how SA performs in real-world scenarios. The speaker ends by teasing a future video focused on a steel optimization example and the use of pre-existing libraries for optimization tasks.
Mindmap
Keywords
💡Simulated Annealing
💡Cooling Schedule
💡Objective Function
💡Temperature
💡Solution Space
💡Probability
💡Delta (Δ)
💡Local Minima
💡Perturbation
💡Metaheuristic Algorithms
Highlights
Introduction to simulated annealing optimization and comparison with particle swarm optimization.
Simulated annealing is inspired by the metallurgical process of annealing, where temperature is slowly decreased to achieve an optimal grain structure.
The key principle is decreasing temperature slowly to optimize the solution and avoid being stuck in local minima.
At high temperatures, the algorithm may accept worse solutions to explore other areas of the solution space.
As the temperature lowers, the algorithm becomes more selective, accepting fewer solutions that are worse than the previous iteration.
The cooling schedule controls how fast the temperature decreases, with a typical constant cooling rate used in practice.
A probability-based approach is used to accept or reject solutions at each iteration, allowing the algorithm to explore diverse possibilities.
Key parameters in simulated annealing include the initial temperature, final temperature, and the cooling rate.
Demonstration of how the algorithm works through a Python code example, with a visual representation of the search space.
In the Python example, an objective function is defined, and the search space is visualized using a contour plot.
The algorithm randomly starts with a solution and iteratively perturbs the parameters to find better solutions.
The code showcases how different cooling rates affect the optimization process, with results printed for cooling rates ranging from 0.2 to 0.9.
At a higher cooling rate of 0.9, the solution is close to the true minimum of the objective function.
Another example is presented using a more complex 3D objective function, with the goal of finding the peak in the solution space.
Conclusion of the video with a teaser for the next video, which will focus on applying simulated annealing to real-world problems.
Transcripts
hi everyone welcome back I hope you
watched the last video where I quickly
provided an overview of meta heuristic
algorithms and I promise to talk to you
about simulated annealing optimization
and particle swarm optimization so here
we go in this video I'm going to talk
about simulated annealing the goal is
for us to understand exactly what it is
by looking at uh you know a little bit
of code and uh and in the next videos or
in the upcoming videos I'll talk about
particles form optimization in a very
similar way now if you would like to be
informed about the upcoming ones as soon
as it gets released you know what to do
hit the Subscribe button and of course
while you're there find the thanks
button if you're feeling extra generous
okay let's jump in here again I provided
a brief overview of simulated annealing
optimization in the last video but let's
understand this at a little bit more
depth in this one now it's again it's uh
it's inspired by the metallurgical
process of annealing where the
temperature is slowly cooled so you get
the optimal grain structure for the
material but in this case for
optimization algorithm there is nothing
like Metallurgy grain structure so
forget all of that it's basically comes
down to one fact you're decreasing the
temperature slowly
to get the desired result what happens
when you're doing that and that's let's
understand that and how does it work it
works by iteratively adjusting the
temperature obviously not adjusting
actually decreasing the temperature uh
in an iterative way and looking at your
final solution and comparing it with the
solution from previous iteration and
saying is this better or worse now again
I'll explain that in a minute if you
haven't watched the last video I mean
this is basically the same slide from
the last video but I promise to give
more context and at high temperatures
you start at a high temperature you go
to low temperature okay that's what
annealing is and at high temperature the
algorithm accepts solutions that are
worse
than the previous iteration because
maybe you're stuck at a local Minima or
maybe what where you are is not the
right solution
okay so the right solution may be
somewhere else so you need to explore
that and that's exactly why you change
this temperature and at high
temperatures you accept there's a good
chance that you're accepting the
solution at low temperatures there's a
good chance you are not accepting this
weird solutions that are out of the
scope and the cooling schedule of course
determines how fast you are actually
changing this over every iteration now
let's go to the next slide and just look
at a couple of aspects here which is it
starts with an initial solution like I
mentioned and iteratively generates a
new solution now if this is not better
it's accepted now again I'm repeating
myself I hear that so let's go and look
at exactly what happens yeah so if the
Delta is less than zero Delta is again
the change from last time to this time
it's less than zero means I have a
better solution this time
or greater than zero depending on
whether you're finding Maxima or Minima
either way if the change is uh within
what you wanted to accept then accept
the new solution else
you accept it with certain probability
then you calculate that okay what is the
probability at high temperature the
probability is high
there's a negative sign right there at
high temperature there is a higher
probability and then you generate a
random number and say okay is that less
than this probability if so accept the
new solution if not X rejects the new
solution meaning you are rejecting the
good solution and sticking with the bad
solution so you can explore this space
better
okay I hope things make sense once we go
into the code but I'll show you uh
Snippets of code before jumping into the
uh into actual or Google collab notebook
now cooling schedule as I mentioned
determines how quickly the temperature
actually decreases
of course everyone wants to have like
infinitely slow cooling temperatures but
that means you have a lot more
iterations to go through
and usually you the common convention is
set a constant cooling rate and then
just go through it I say usually but you
can be a bit more tricky you can say hey
when the temperature is large I just
want like uh you know smaller steps or
larger steps but as temperature gets
lower and lower I want the cooling to be
slower for example yeah you can schedule
it but typically people leave it at a
fixed fraction uh just like the one I
show you on the screen some Alpha some
value multiplied by the temperature is
what you're taking as the next one and
Alpha can be 0.95 for example which
means you're cooling the temperature by
five percent
each iteration okay now let's understand
the algorithm by looking at the python
code here there is an objective function
where we Define some function the goal
is to find the Minima
or the solution basically right for this
one
and in this case the answer is 4 5 and
minus 6 as you know
and you define a search space you say
okay my bounce again this is a lot we
will look at this in a minute but you
basically say the bounce is uh okay my
solution is between 0 to 10 x 0 to 10
why and minus 10 to 0 Z right so those
are the bounds and you need to Define
that otherwise if your solution is here
no point in searching somewhere else you
have to search where the solution is
most probably lying and you also provide
initial and final temperature so you
start at certain temperature and you
cool it uh I don't know five percent
every time yeah uh
and uh yeah so here is something that we
will be generating in this uh in this
tutorial which is you we have a solution
space and trying to find the Maxima in
this example so you start somewhere you
work your way you work your way not the
right solution not the right solution
not the right solution and so on and you
finally find the peak in this case yeah
so we'll visually do this in this uh in
in just by jumping into the code right
now so let's go ahead and do that
and I am going to give you this this
this uh notebook linked to this so don't
bother writing down anything and I have
all the text here in case you want to go
back and read it at your own pace okay
so understanding the algorithm via
python code I explained a lot of this
stuff but a couple of things I want to
show you the initial T final we talked
about it cooling rate I'm gonna set it
to 0.95 which means it's going to change
by five percent
every iteration and the bounds we are
going to set between 0 to 10 for the
first two values and minus 10 to 0 for
the third parameter because that's where
the solution lies okay
okay I think that's enough background
let's go ahead and run this all I'm
using is standard libraries there is no
tricky libraries here numpy random math
and matplotlib for plotting and I'm
defining my objective function as this
x minus 4 squared so you know the
solution is going to be 4 5 and minus 6.
okay now let's define the range because
our solution lies between -10 oh in this
case I'm instead of defining 0 to 10 for
all of these I'm actually defining minus
10 to 10. which is okay we know that our
solution lies between this a bit larger
search space but still I'm confident
we'll find this in a fraction of a
second so minus 10 to 10 minus 10 to 10
minus 10 to 10 for x y z and I'm going
to create a mesh right there from and my
objective function
and filling that objective function
right there and creating a contour plot
so basically this this part is just so
we can visualize how the objective
function looks like and this is a
contour plot so I expect a 2d Contour
plot let's see that's what I'm yeah
that's not a 3D plot
okay there we go and again all of this
is optional I'm just doing this because
I just want to show you how the solution
space looks like and initially I I said
these are my bounds these are not the
bounds this is just my X range y range
and Z range for the plotting itself so
you can ignore this part completely if
you don't want to visualize this but I
just want to show you how the solution
space looks like yeah so the goal for
our optimization algorithm is to
navigate through this and find the right
solution which is around 5 and 6 and in
Z it's going to be around -6 right so
that's the solution so how do we do that
so let's define our simulated annealing
functions and then go ahead and run
these functions so I again showed this
as part of our presentation the
parameters that go in are the objective
function that we are trying to you know
use as a fitness function here bounce
the limits the initial temperature final
temperature and the cooling that's it
it's very straightforward actually and
uh you're looking at how many parameters
uh based on the bounce right I mean if
my bounds have uh multiple parameters
like three parameters then I have three
that's the number of parameters what are
the current parameters just go ahead and
start somewhere you have to start
somewhere so I'm gonna randomly start
somewhere within this space and the
current solution is you take those
parameters and plug them into objective
function then you get a solution
right and that is your current solution
and then you have your current
temperature
and while the current temperature is
higher than the final temperature go
ahead and do the following
perturbed parameters or the new
parameters
are updated parameters are the ones
right there and the updated solution is
where you plug in the updated parameters
into the objective function so you get
updated solution now now you take the
supply difference between the updated
solution and the previous solution or
the current solution the existing
solution and that is your Delta and in
this case I'm accepting I'm trying to
find the peak so if the Delta is less
than zero go ahead and accept it which
means current parameters equals to the
the updated one or the new one current
solution is the new one if not go ahead
and calculate the probability based on
the current temperature
and if that probability is greater or if
a random number is less than that
probability then go ahead and accept the
solution right there uh current
parameters is the perturbed parameters
and current solution is the Prototype
solution right there okay and uh go
ahead and I mean basically this part
again I hope this is the meat of it yeah
which means instead of rejecting the
solution we are accepting a solution
that's worse with a certain probability
that's exactly what we are doing right
there okay and then we are just changing
the temperature that's it and this part
is basically plotting the cooling rates
so let me go ahead and
run that and now let's go ahead and run
this so our bounds are minus 10 to 10.
for all of these well I guess I ended up
using minus 10 to 10 as bounds for all
and the initial temperature 100 final
temperature is 0.1 and change it at five
percent and cooling rates are there and
plot the cooling rates right here so
let's go ahead and so it took that many
result for cooling rate 0.2 for cooling
rate 0.5 instead of doing one cooling
rate by the way I should explain this
instead of doing one cooling rate of 0.2
remember we set the cooling rate
constant uh so instead of that I
actually experimented with a few
different cooling rates like
0.2.5.6.8 and 0.9 and I'm printing all
the values down here
so the result at cooling rate 0.2 is 6.5
minus 0.6 that's not a good result
in fact if you look at a high uh
equivalent rate of 0.9 the solution is 3
7 and minus 5. so what is the actual
solution
4 5 and minus 6. so this is almost minus
six this is 7 this is 2.8 which is like
3 let's say this is uh it should be four
so maybe we should just do more
iterations or more you know smaller I
mean eventually you can see that how the
solution is actually showing up right
there for this cooling rate it's
actually doing a much better much better
job
okay so with that information let's go
ahead and actually understand the
visualizing the optimization process
again I did kind of something similar
but I kind of got a bit more complex
objective function
the one that you saw in the image before
so let's go ahead and run that Define
the objective function and now let's go
ahead and plot it yeah this is a 3D plot
not a controller plot so let's go ahead
and see so this is the new objective
function instead of just a
a simple one that I showed you earlier
so the goal is to start somewhere but
then find the peak right here okay so
for that we have a simulated any link
right there I called it 3d nothing
everything is exactly identical I don't
have like much of a difference between
previous one and here so you can see
it's very similar code right here and
I'm defining my bounce and cooling rate
of 0.95 let's set it to 0.95 which means
we are changing the rate at five percent
and there you go that's the plot and
this time it actually started when I did
the first simulation you saw on my
Opening screen that it started over
there and it worked its way to the top
now it started over here and slowly it
found its way to the top right there so
uh I think again these are abstract
examples in the next video let's go
ahead and use the steel optimization
example and then try to understand how
we can put the simulated annealing to
use and should we actually code all of
this or is this is there a standard
library that we can import and do these
type of examples we'll see go ahead and
watch our next tutorial until then keep
learning see you next time
5.0 / 5 (0 votes)