Simulated Annealing
Summary
TLDRThis video explores the limitations of hill climbing in optimization and introduces simulated annealing as a solution. The speaker explains how hill climbing struggles with local maxima and how simulated annealing overcomes this by sometimes allowing worse moves, mimicking the metallurgic process of heating and cooling metals. By controlling the randomness of these decisions, simulated annealing helps find better solutions over time, eventually narrowing down to the optimal one. The video delves into the math behind this method and demonstrates how it works with temperature decline and probability.
Takeaways
- 🤔 Hill climbing struggles with local maxima, where it won't accept worse moves, potentially trapping it.
- 🎲 Introducing controlled randomness allows for sometimes making worse moves to escape local maxima.
- 🌱 Metaheuristics are inspired by natural processes and provide solutions beyond simple optimization algorithms.
- 🔥 Simulated annealing is inspired by metallurgical processes, where heated metal gradually cools to a stable structure.
- 🌡️ Simulated annealing involves accepting worse moves more frequently when the system (or temperature) is volatile or 'hot.'
- 🔄 The algorithm computes the energy change (Delta E) to determine whether to accept a move based on its impact.
- 📉 As temperature decreases, the probability of accepting worse moves decreases, guiding the system to a stable, optimized solution.
- 🔢 The probability of accepting worse moves is based on an exponential function: e^(Delta E / temperature).
- 🎯 The goal is to sometimes accept worse solutions early on to avoid getting stuck, gradually stabilizing at better solutions.
- 📊 Simulated annealing is useful for escaping local maxima to potentially find a global maximum in optimization problems.
Q & A
What is the main limitation of hill climbing as described in the video?
-The main limitation of hill climbing is that it can get stuck at a local maxima and won't consider moves that reduce the objective function, even if those moves could eventually lead to a better overall solution.
What is the solution proposed to overcome the limitation of hill climbing?
-The proposed solution is to introduce randomness, allowing for the possibility of taking steps that reduce the objective function temporarily, which can help escape local maxima and potentially reach a better global solution.
What is simulated annealing, and how is it related to metallurgy?
-Simulated annealing is an optimization technique inspired by the process of cooling metal in metallurgy. As the temperature of the metal decreases, the movement of molecules slows down and they settle into a more stable, crystalline structure. Similarly, simulated annealing allows for exploration (random moves) at high temperatures, and as the temperature decreases, the algorithm becomes more selective about improving moves.
How does simulated annealing handle 'bad moves' in optimization?
-Simulated annealing allows for 'bad moves' (those that decrease the objective function) with a probability based on the difference in energy (Delta E) and the current temperature. At high temperatures, the probability of accepting a bad move is higher, but as the temperature decreases, this probability becomes smaller.
What is the role of temperature in simulated annealing?
-Temperature controls the likelihood of accepting worse solutions. At higher temperatures, the algorithm is more likely to accept worse solutions to explore more of the solution space. As the temperature decreases, the algorithm becomes more conservative and favors only improving moves.
How is the probability of accepting a worse move calculated in simulated annealing?
-The probability is calculated using the formula e^(Delta E / T), where Delta E is the change in energy (objective function value) and T is the current temperature. If Delta E is negative (indicating a worse move), the probability decreases as T decreases.
What happens to the probability of accepting a worse move as temperature decreases?
-As temperature decreases, the probability of accepting a worse move also decreases. Eventually, when the temperature is very low, the probability becomes so small that the algorithm mostly rejects bad moves.
How is randomness introduced in the simulated annealing algorithm?
-Randomness is introduced by selecting a random candidate move from the possible options at each step. This allows the algorithm to explore the solution space without always following the best or worst move.
What happens if the Delta E (energy difference) is positive in simulated annealing?
-If Delta E is positive (indicating an improvement in the objective function), the move is always accepted, as it represents a step toward a better solution.
How does simulated annealing help in finding the global maxima?
-Simulated annealing helps in finding the global maxima by allowing occasional moves to worse solutions, which helps escape local maxima. As the temperature decreases, the algorithm focuses on refining the solution to find a global or better local maxima.
Outlines
🧠 Introduction to Limitations of Hill Climbing and Random Control
The video begins by discussing a limitation of hill climbing optimization, specifically the problem of getting stuck in a local maximum. The concept of sometimes accepting moves that seem worse in the short term is introduced as a solution. This leads to the idea of meta-heuristics, a broader approach inspired by nature, which allows for controlled randomness. One such meta-heuristic, simulated annealing, is introduced as a technique that mimics the process of cooling in metallurgy to find better solutions in optimization problems.
📉 Delta E and Energy-Based Moves
This paragraph dives into the concept of calculating the change in energy (Delta E) when transitioning between states in simulated annealing. A positive Delta E represents a favorable move, while a negative Delta E may still be accepted in the early, volatile stages of optimization. The probability of accepting unfavorable moves is proportional to the energy difference and the current temperature of the system, allowing for exploration beyond local maxima.
🎲 Random Move Selection and Optimization
The process of randomly selecting potential moves in simulated annealing is explained here. Rather than always choosing the best or worst option, the algorithm picks a random candidate and evaluates its fitness. If the move improves the state, it is accepted. If not, the algorithm may still accept it depending on the calculated probability, which helps escape local maxima.
🔢 Probabilities and Temperature Decline in Simulated Annealing
This section explores how probabilities of accepting worse moves decrease as the temperature declines in simulated annealing. It shows how the probability of taking a suboptimal step starts high when the system is volatile (with high temperature) and gradually decreases as the temperature cools down. A Python code example demonstrates this decline in probability and how it affects decision-making in the optimization process.
Mindmap
Keywords
💡Hill Climbing
💡Local Maxima
💡Simulated Annealing
💡Metaheuristics
💡Biologically Inspired AI
💡Objective Function
💡Temperature
💡Energy Difference (Delta E)
💡Crystallization
💡Temperature Decline Schedule
Highlights
The limitation of hill climbing algorithms is they can get stuck in local maxima, where no potential moves improve the solution.
To resolve the local maxima issue, the introduction of randomness allows occasional moves to worse solutions, potentially leading to better maxima.
Meta-heuristics are strategies inspired by natural processes that provide alternative optimization methods.
Simulated annealing is introduced as a biologically inspired AI technique based on metallurgic processes.
In simulated annealing, molecules in hot metal move rapidly, similar to how solutions in optimization problems explore the search space when volatility is high.
As temperature decreases in simulated annealing, the exploration reduces, allowing solutions to settle into more stable states.
The optimization process in simulated annealing mimics crystallization, where molecules settle into a more fixed position as temperature cools.
Energy difference (Delta E) is a key factor in deciding whether a move is accepted in simulated annealing, even if it leads to a worse solution.
The probability of accepting a worse move is determined by the formula e^(Delta E / Temperature), meaning the worse the move and lower the temperature, the less likely it is to be accepted.
The algorithm starts with a high temperature, which allows for more exploration, and gradually decreases it over time.
Simulated annealing can help avoid local maxima by allowing occasional downward steps, potentially leading to a better overall solution.
The temperature decline schedule can vary, and different strategies can be applied to manage how quickly the temperature drops.
The probability of accepting worse moves decreases as the temperature decreases, and at very low temperatures, only better moves are accepted.
Simulated annealing uses random selection of moves from possible configurations rather than always picking the best option.
The randomness and controlled temperature decline in simulated annealing help explore different solution spaces, potentially leading to the global maxima.
Transcripts
so in our last video we were talking
about one of the sort of limitations of
uh just working off of hill climbing
that issue was specifically if I was at
sort of a local Maxima uh I would never
go to any potential move that was worse
for me and so that's actually where we
introduced that idea of maybe we want to
attempt to control
random and what I mean by that is again
if we see that we have a better move if
we're trying to maximize and we see
something that makes our value go up we
obviously take that step
but again to sort of resolve this issue
of no possible moves what we could do is
we could utilize sometimes going down
because sometimes going down right may
lead us to some bottom but that may lead
us to some new better uh Maxima that
we've not yet discovered and it so sort
of you know again goes the opposite way
so when we're trying to minimize yes we
want to always go down but sometimes we
want to go up and that actually
introduces us to what we call Meta
heuristics or
you often all see the term
biologically
inspired
AI
and the entire idea here is looking at
something that we see out there in the
world as sort of a natural occurrence
and saying hey
that might work
and So Meta heuristics big fancy five
dollar word it's just sort of this
umbrella term to really kind of talk
about all those things that we see out
in nature and for at least this first
video what I'm going to focus in on it
is this idea of simulated annealing now
we'll come and we'll explore some of
these later on but again what we're just
sort of doing is saying oh well maybe
there are other heuristics that we could
work off of so the best way to think
about again that idea of simulated
annealing that is another big fancy five
dollar word where does it come from well
specifically what we do is we think
about it like it's metallurgic
again if we're thinking about this we're
we're a blacksmith we're in a forge you
know we're heating up and banging the
swords and what's happening as that
whole process is going on if I were to
draw sort of the edge of uh our blade
for a moment
right is all of the molecules and atoms
that are going on as the blade is being
heating up
they're moving very radically very fast
and so what's technically sort of going
on there is this idea that you know we
may be seeing some bad positions in
those molecules but that's not just the
only thing that happens when we start to
work off of you know
smithing what we do is then we take that
we port
that's the best bucket you'll see
into a bucket of water what happens when
we do that is that really hot metal gets
quenched into that water and all of
those molecules are going to
slow
down
and what happens sort of in that process
is we can think about it as very similar
to sort of a crystallization process
because the molecules have sort of moved
all over the place and they crystallize
because the temperature's gotten so low
they're locked into place and that's
actually going to allow us sort of to
carry that thought with our optimization
problem we can think about sort of this
idea of sometimes going down when we had
that's not how you start a v
you can think about when we sometimes go
down is because of just a very high
temperature high volatility we're
letting the molecules do their dance but
then as temperature starts to decline we
stop doing this sometimes and only work
off of that good times
so we allow those worst solutions to
happen but we don't always do them so
how do we start to kind of take a look
at this well we're going to start to
look at that objective function one more
time we still work off of the idea of
sort of that F but now we're going to
call it energy
big old fit that's not big old fancy e
and so what we're looking at when we
start to compare our state our state
with a next possible state is that we're
looking at this idea of the Delta e or
change
in e
as you can sort of see here what we can
do with that is just a very simple
subtraction so taking whatever that next
was going to be or what that next is
going to be minus what we currently are
and if that is a larger than zero number
that's a good move that that distance is
a positive move in the right direction
and so from our perspective that's where
we look at that always
go up
again probability of going up is one
meaning yes we do it but more
specifically again we're trying to look
at when
we're dealing with that sometimes going
down and that's when we get a move that
is not so good we take our next and then
we subtract our current position and we
still get a Delta e but what if that
Delta e is negative
well in that case again if we're
thinking about it that's not a good step
forward not a good step forward but we
still want to accept it because we're
working off of that idea that right now
we're in a highly volatile situation and
the step is okay how we do that is we
determine
the probability through e raised to the
power of Delta energy over what our
current temperature is at this given
time step
a lot of words a lot of stuff going on
there right and so the big idea here is
again what's happening is that uh this
suddenly becomes proportional to the
energy difference so as this
energy difference occurs
if it's a large distance oh it's not a
good move and it's a really really bad
move but if it's a super small you know
difference that's not so bad and then
secondly we've got the idea of t t he is
working by going down right I want my T
my T started at say for example 100 I
want to gradually reach maybe one or
zero well you can't divide by zero so
gradually go down to one and when that's
occurring this number
is going to get much lower and we'll see
sort of an example of that in just a bit
but just to kind of help calm your minds
a little bit all we need to do is if
we're trying to minimize instead is all
we have to do is flip which one is
subtracted first or from the other one
so to take a look at this there's a very
simple pseudo code going on here the
first part is again if we're thinking
about sort of my prior video what we're
doing is not a search tree right we're
not doing this we're going through a
loop well how often does that Loop run
technically it can run an infinite
number of times again
could just keep on running and you know
hopefully we eventually reach some point
where we can stop it but again it can
just run forever
then specifically we look at that idea
of T and T declining as lowercase T in
this case goes down or in our case you
know it's going from one to a million
whatever whatever we're looking at is
specifically we could design out our
temperature decline schedule
well what that means is again maybe we
start with a very high temp
but as you notice it's a very very quick
drop off
before leveling out and so T doesn't
change
doesn't
change there that's a way we can write
that
that works that's one approach that we
could do here's another approach that we
could do the point being is what we're
looking to do is just establish T is
some value because again
looking at that algorithm we have
are our difference proportional to T so
we wanted to gradually start to go down
then what we're looking at is
specifically you know oh well if T hits
zero we could consider that good enough
and you know we're done or you could
strip this out entirely and just not
ever have this
be a part of the algorithm again you
just constantly are moving through your
search
slowly declining T however you want
maybe you wanted to go down by a
percentage instead of a hard you know by
one number
either way works but specifically what
we're looking at is when we had some
configuration right we're going to look
at all of the possible steps that that
configuration could do so c 1 a c 1 b c
1 c c 1 D these are all just possible
steps that we could work off of and
specific to simulated annealing in that
idea of
controlling
random
I just pick one I just doesn't matter
I'm not looking for the best I'm not
looking for the worst I'm just going to
pick one of them I'm going to say for
this case you know oh this time around I
pick c1b that's it then what I do is I
say well what is the Delta this is
technically the Delta e of that
candidate so that would be the c1b
minus
C1 whatever the evaluation the F score
the fitness measure of C1 was check the
difference once again if it's greater
than zero again if we're trying to
maximize
immediately go to it we're done awesome
right
we're good but more specifically when
we're dealing with when it's not not
a good
move
we want to sometimes do it we need to
sometimes do it again to potentially
break out of local maximums and to do
that again what we're looking at is this
idea
of some proportional distance again we
want this to happen because again this
is going to allow us to calculate that
out we figure out what that probability
is let's arbitrarily say that our P
currently equals you know 65.
right so there's a 65 chance we take
that value because what that does is
then if I show it again P being 65 I'm
going to generate some random number
some random number between 0 and 1.
because all right well if that number is
less than 65 so let's say I generated a
0.25 well happen that happens to be a
true statement that is less than 65
therefore we can say okay well that is
you going into that new move that works
same kind of thing going on if it
doesn't if it's uh 75
oh this is not a true statement
we don't make the step this time so
again let's sort of play this out see
what happens here
so again we're working off of our simple
example I've generated a fitness score
of 106. I have all my potential
candidates again red switching with
orange red switching with green red
switching with blue red switching with
purple again just working off of those
to make it easier for me
but my point being is okay I can make
one swap
which one do I pick
I pick one at random I pick arbitrarily
one at random because again we're making
the assessment of whether or not we do
this again with sort of our our next
approach
if we're dealing with something that is
better again let's say arbitrarily we
want to maximize our value and we
randomly picked uh you know this third
option
well again that's a better move so yes
we obviously take that move but then you
notice I have three other possibilities
I have sort of a worse move here a worse
move here and a worse move here if I
picked any one of those again we have to
say I might take that route and to do
that again what we're looking at is this
idea let's say if we picked this one
well the Delta e for this is again 93
minus 106
which turns into a negative 13. negative
13 means it's a bad move it's less than
zero
so we have to make a few more steps
so again if we're looking at that
pseudocode we generate out what is the
probability that we go to that move and
it's e to the negative 13 negative 13
over t
okay
what's T to kind of take this into
perspective here's just me you know
cheating with a little python so let's
arbitrarily say that t is 100 right and
we're gonna just make it go down by one
every single time so 4 I in range uh T
to 1 with a step of negative one right
that in mind again what I'm trying to do
is calculate out the probability so the
prob is going to equal math dot e you
can see I I sort of cheated here and I
already had that imported in math.e
raised to the power of negative 13 over
t
or sorry it would be I in this case
and so again that's going to be
1998 97 96 Etc up to 1. and so I'm going
to just print that out so here's that I
here's the value and then what is the
probability at that particular
temperature level we take this we run it
and what you can see here specifically
is again when T is 100 right
we have an 87 chance of making that step
87.8 chance and then as T goes down
87.7
87.6 87.5 if I start to jump down to
let's say 65 right that probability is
now 87 or
81.9 if I keep jumping down to say 35
probability of making this step or
selecting this 93 would be a 68.9 or you
know 69 uh as we get down to a 10 you
know where temperature is super low at
this point our probability is starting
to hit
0.273 right we're starting to get lower
and lower until as we reach ultimately
to those zero values the probability
becomes so low that we don't do it
so again what this allows us to do is we
make these types of selections because
the hope is that after we made this hop
there
May
be a chance
at
something
better
than
106. and again that's the sole purpose
because we're maybe getting out of that
that that that little local Maxima that
we're dealing with we may be able to
move towards a better local Maxima or
the the mythical Global Maxima that may
be impossible for us to otherwise find
out
and that simulated annealing in a
nutshell
تصفح المزيد من مقاطع الفيديو ذات الصلة
The simulated annealing algorithm explained with an analogy to a toy
319 - What is Simulated Annealing Optimization?
TA_5026201012
Hill Climbing Search Solved Example using Local and Global Heuristic Function by Dr. Mahesh Huddar
Hill Climbing Algorithm in Artificial Intelligence with Real Life Examples| Heuristic Search
Beam Search Algorithm in Artificial Intelligence | All Imp Points | Heuristic Search Techniques
5.0 / 5 (0 votes)