319 - What is Simulated Annealing Optimization​?

Summary

In 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

00:00

😀 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.

05:00

🔍 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.

10:01

📊 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.

Keywords

💡Simulated Annealing

Simulated annealing is a metaheuristic optimization algorithm inspired by the process of annealing in metallurgy, where the temperature of a material is slowly cooled to reach an optimal structure. In this context, the algorithm starts at a high 'temperature' and iteratively cools down, exploring various solutions to find an optimal or near-optimal result. The video focuses on how this technique is applied to optimization problems, comparing solutions at each iteration and adjusting based on a cooling schedule.

💡Cooling Schedule

The cooling schedule in simulated annealing determines how quickly the temperature decreases over time. A slower cooling schedule allows more exploration of the solution space, while a faster schedule speeds up the process but might lead to suboptimal solutions. In the video, different cooling rates (e.g., 0.95, which means a 5% decrease per iteration) are experimented with to demonstrate their impact on finding an optimal solution.

💡Objective Function

The objective function is the function that needs to be optimized, whether by minimizing or maximizing its value. In the video, a mathematical function involving parameters like x, y, and z is used as the objective function, and the goal is to find the parameter values that yield the best solution (e.g., 4, 5, and -6). The function serves as the core problem that the simulated annealing algorithm attempts to solve.

💡Temperature

In simulated annealing, temperature is a metaphor for the control parameter that decreases over time. The algorithm starts with a high temperature, allowing it to explore more random solutions, including worse ones, and gradually lowers the temperature to narrow down to a more precise solution. The temperature is reduced according to a cooling schedule, and at lower temperatures, the algorithm becomes less likely to accept worse solutions.

💡Solution Space

The solution space refers to the range of possible solutions that the algorithm explores to find an optimal answer. In the video, the bounds for x, y, and z parameters (e.g., 0 to 10 for x, -10 to 0 for z) define the limits of the search. Visualizations, such as contour plots and 3D graphs, are used to depict the solution space and how the algorithm navigates through it to find the optimal solution.

💡Probability

Probability plays a key role in determining whether or not to accept a solution, especially when it is worse than the current one. At higher temperatures, the probability of accepting a worse solution is higher, which allows the algorithm to explore different areas of the solution space. The video explains that this randomness is gradually reduced as the temperature lowers, making the algorithm more selective as it approaches an optimal solution.

💡Delta (Δ)

Delta represents the change in the value of the objective function between iterations. It is used to compare the new solution with the current solution. If Delta is less than zero (i.e., the new solution is better), it is accepted outright. Otherwise, it is accepted with a certain probability based on the temperature. The concept of Delta is crucial in understanding how simulated annealing balances exploration and exploitation.

💡Local Minima

A local minimum is a solution that is better than neighboring solutions but may not be the best possible (global) solution. Simulated annealing helps overcome the problem of getting stuck in local minima by allowing worse solutions to be accepted at higher temperatures. The video emphasizes that this helps the algorithm explore more broadly before narrowing in on a final solution as the temperature decreases.

💡Perturbation

Perturbation refers to the small changes made to the current solution to generate new solutions. In each iteration of simulated annealing, the algorithm perturbs the parameters (e.g., x, y, z) to explore new possibilities in the solution space. The video discusses how these perturbations are evaluated to decide whether to accept the new solution based on the objective function and temperature.

💡Metaheuristic Algorithms

Metaheuristic algorithms are optimization techniques that provide near-optimal solutions for complex problems by exploring a large search space. Simulated annealing is one such algorithm. The video mentions that other metaheuristic algorithms, such as particle swarm optimization, will be discussed in future videos. Metaheuristics are widely used in situations where finding an exact solution is computationally impractical.

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