OPERATIONAL DECISION MAKING SYSTEMS
Workgroup ISCE/BI Jean-Charles HUET Jean-charles.huet@efrei.fr
What is simulated annealing?
• It’s an algorithm for finding a good solution to an optimization problem
2
What’s an optimization problem?
• It’s the problem of finding the best solution from all feasible solutions. (Wikipedia)
3
Canonical Example: Traveling Salesman
4
Canonical Example: Traveling Salesman
• The salesman needs to minimize the number of miles he travels. An itinerary is better if it is shorter.
• There are many feasible itineraries to choose from. We are looking for the best one.
Simulated annealing solves this type of problem. https://www.youtube.com/watch?v=0rPZSyTgo-w&t=281s
5
Why ‘annealing’?
• Simulated annealing is inspired by a metalworking process called annealing.
• It uses the equation that describes changes in a metal’s embodied energy during the annealing process.
6
HOW DOES IT WORK?
7
The Process
• Generate a random solution! • Assess its cost!
• Find a neighboring solution! • Assess its cost!
Move ! Maybe move
Why??
8
… To escape local maxima
9
… To escape local maxima
10
… To escape local maxima
11
… To escape local maxima
12
… To escape local maxima
13
• The probability of accepting a worse solution depends on:
> How much worse it is
> Which iteration you’re on
14
• The probability of accepting a worse solution depends on:
> How much worse it is > Which iteration you’re on
15
• The probability of accepting a worse solution depends on:
> How much worse it is
> Which iteration you’re on
(later iteration = less likely)
16
• Big jumps to worse states happen early.
• After many iterations, the algorithm hones in on a local
optimum.
• So a good-enough solution is usually found.
17
• The algorithm’s parameters must be tuned correctly, which requires some guesswork.
• But overall, simulated annealing is generally considered a good choice for solving optimization problems.
18
The basic algorithm
19
Let’s break it down
1. First, generate a random solution
You can do this however you want. The main point is that it’s random – it doesn’t need to be your best guess at the optimal solution.
20
Let’s break it down
2. Calculate its cost using some cost function you’ve defined
This, too, is entirely up to you. Depending on your problem, it might be as simple as counting the total number of miles the traveling salesman’s traveled. Or it might be an incredibly complex melding of multiple factors. Calculating the cost of each solution is often the most expensive part of the algorithm, so it pays to keep it simple.
21
Let’s break it down
3. Generate a random neighboring solution
“Neighboring” means there’s only one thing that differs between the old solution and the new solution. Effectively, you switch two elements of your solution and re-calculate the cost. The main requirement is that it be done randomly.
22
Let’s break it down
4. Calculate the new solution’s cost
Use the same cost function as above. You can see why it needs to perform well – it gets called with each iteration of the algorithm.
23
Let’s break it down
5. Compare then
• If cnew < cold: move to the new solution
If the new solution has a smaller cost than the old solution, the new one is better. This makes the algorithm happy - it's getting closer to an optimum. It will "move" to that new solution, saving it as the base for its next iteration.
24
Let's break it down
5. Compare then
• If cnew > cold: maybe move to the new solution
This is where things get interesting. Most of the time, the algorithm will eschew moving to a worse solution. If it did that all of the time, though, it would get caught at local maxima. To avoid that problem, it sometimes elects to keep the worse solution. To decide, the algorithm calculates something called the ‘acceptance probability’ and then compares it to a random number.
25
The acceptance probability function
26
Need more details?
• http://katrinaeg.com/simulated-annealing.html
• Let’s apply SA to optimize the tools position in the loader of a numerical control machine!
27
Set of data
1 line. Number of tools
2 line. Number of places
3 line. Number of operations
4 line. Unit of time
5 line to … tool use with machining duration
28