Ch 4 - Improve Simulated Annealing diagram

[redblobgames]

@Rishav159 writes:

Simulated Annealing is a hard concept to explain in just a single diagram. We realized this while working on it. There are several parameters that determine a good simulated annealing and it might require something more than just a "Hill representation of state space diagram". I am out of ideas on this one for now. You are welcomed to come up with new ways to demonstrate this algorithm :)

[nervgh]

When I have looked first time at the visualization of algorithm of Simulated Annealing it was not clear for me. I had expected decreasing the temperature step by step and completion of working of the algorithm. Then I opened the Wikipedia and found out that it has visualization which fits my expectations.

I guess we may visualize this concept like wikipedia does it:

In particular that assumes:

1. We should visualize the search process as the process which has the beginning and the end
2. Each search process should show changing the temperature from MAX to MIN
3. And maybe the slider should control the speed of the animation

I need your opinions about my proposal @redblobgames , @Rishav159

:smiley_cat:

[Rishav159]

@nervgh Hello, Thanks for your interest in this diagram. I did come across this particular gif in wikipedia while working on the project and in-fact my initial implementation was also the same. But we dropped that idea and decided that the user should control the temperature for the following reasons:

1. Visualizations work much better if they are interactive. An animation may help showcase a difficult concept (which simulated annealing is), but only through interaction can the user gain more insights. For instance, in this case, one of the important concept is that during high temperatures, the agent chooses bad states much more frequently than during low temperatures. If a user fixes the temperature at a particular value, he/she can observe the states the agent chooses.
2. The wikipedia example is almost too perfect :). When I actually implemented this, very rarely did the algorithm converge towards the maxima that smoothly.

I know that the current implementation is not very clear and needs several improvements, I can't really see why simply automatically decreasing temperatures as a process will fix it.

What are your thoughts about this ?

[nervgh]

@Rishav159 thanks for your work :v: Many of your visualization are really helpful for me.

Decreasing the temperature is not main idea that I was attempting to point on. It is just the trick that would help us to explain the process of optimization.

My vision is:

• let us say, f(x) -- Simulated Annealing and x -- temperature, then
• there is the range of f(x) that is bounded with x

and we are discussing about how to visualize this bound *

In the current implementation (problems) 1) the reader cannot observe all bounded area 2) and he/she cannot see how the algorithm works from the beginning to the end, step-by-step

(possible solutions) 1) We may highlight all bounded area for the specific temperature. For example, for the temperature 35° I would see one highlighted area on the diagram, for 15° I would see another (more small) highlighted region on the diagram. When I see this area I know the potential behavior (steps) of the algorithm. 2) About the visualization of all process of optimization algorithm. In my opinion it should be something like the visualization of the Hill Climbing Search. Where I see how it starts, how it works (step-by-step) and how it ends. And decreasing the temperature might help us with that. What about the slider (interaction)? Well, maybe, it should control the progress (0%...100%) of optimization algorithm.

* That is the main concept of the algorithm (in my opinion): when the temperature goes down we decrease the radius of the search cone

[Rishav159]

let us say, f(x) -- Simulated Annealing and x -- temperature, then there is the range of f(x) that is bounded with x

I am not sure how f(x) is bounded with x. Almost all states are possible for every temperature. Its just that the probability of bad states being selected at lower temperatures is very low.

In the current implementation (problems)

the reader cannot observe all bounded area and he/she cannot see how the algorithm works from the beginning to the end, step-by-step

I agree with this.

We may highlight all bounded area for the specific temperature. For example, for the temperature 35° I would see one highlighted area on the diagram, for 15° I would see another (more small) highlighted region on the diagram. When I see this area I know the potential behavior (steps) of the algorithm.

For a particular temperature, there are several states that the algorithm could be in. What differs with temperature is not the states but the probability of selecting a state. This gives me an idea though. Maybe we can use a color code to show the probability of choosing a state for a particular temperature. For example, blue means high probability and red means low probability. Initially when the temperature is high, several states are deep blue with some states with small heuristic value light blue. As the temperature decreses, the small states becomes less and less probable to be selected and hence becomes orangish and then red. This could help visualize how probabilities of states being selected depend on the temperature.

What are your thoughts on this ? @redblobgames @nervgh

[nervgh]

@Rishav159 yes, i was talking about something very similar. I have done a couple of sketches based on Wikipedia's picture to clarify my vision. I was changing the background and temperature only (without moving of current state, red line):

Sketch 1

frame 0 frame 1 frame 2 frame 3 frame 4

Sketch 2

frame 0 frame 1 frame 2 frame 3 frame 4 frame 5

[redblobgames]

Would it be useful to plot the probability of choosing a state, as a function of temperature? Then as the temperature changes you'd see that probability distribution change. (This might be a separate diagram to introduce the concept before the diagram that shows the algorithm running)

[ghost]

I think a combination of the two ideas would be ideal. If we can give every state a color based on a it's probability, I think it would be a lot easier to understand.

However, I think the best solution would be to provide an alternate implementation before the current one, where the only actions that can be taken are left and right moves. This will cause the agent to move back-and-forth very quickly, and would not be much better at solving the problem than hill-climbing. However it would allow us to easily display how heat relates to the probability of taking bad actions. More heat->more random. The leap from understanding this diagram to the current one will be small.