Jump to content

Simulated Annealing - When brute-force takes too long


RTFC
 Share

Recommended Posts

  • Moderators

RTFC,

Wow, I expected something complex but this is going to take a fair while to understand. I am now reading this to try and get some idea of what is going on in there.

M23

Public_Domain.png.2d871819fcb9957cf44f4514551a2935.png Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind

Open spoiler to see my UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Link to comment
Share on other sites

@JohnOne: Yeah, best not play too much with it, or you might go blind.;)

@M23: It really works mostly like I describe in the analogy. Rolling the dice = _AskOracle(), using an exponential distribution. We always accept a lower cost, but if it's higher, then we only accept the jump if we sample below our annealing temperature (well technically, cost scaled by temperature), and the temperature itself is gradually lowered. And the name annealing is apt, as the metal is cooled slowly to give the atoms the opportunity to settle into the crystal lattice.

Edited by RTFC
Link to comment
Share on other sites

  • 1 month later...

Added a 3rd example in the first post, a Sudoku Generator & Solver.

Paraphrasing the script remarks section:

This example illustrates how some types of problem can cause Simulated Annealing to get stuck in a local optimum other than the global one. To get around this, we can apply a thorough reshuffle of all non-fixed parameters, and try again. The harder the problem is, the larger the average number of required reshuffles to find the full solution (see listed examples in script).

Sudoku puzzles with very few given clues (or none) are easy to solve, because many paths exist that lead to full solutions (non-unique for number of clues < 17). Sudoku's with many clues are also easy to solve, because there are only relatively few paths left, many of which yield the full solution.

Sudoku's with (or close to) the minimum number of clues that identify a unique solution are the hardest, because many paths do exist, but most lead to a sub-optimal, incomplete solution.:think: The location of the clues also becomes increasingly important the closer we get to this minimum. Reshuffling allows us to explore this landscape from different starting points.

The new example script (#3) displays a temporary result (with timing) each time it gets stuck; when the true solution is found, it plays a sound before exiting. Note that this may take a long time.:yawn:

NB This is obviously not the fastest way to solve a Sudoku; the point of this example is to show that SimAnn can (eventually) find it, without knowing how to solve it, just by getting feedback on its current attempts, and despite the solution space itself being rather large. Furthermore, this example does not imply that all intractable problems can be solved by repeated reshuffle + retry. For example, it would be useless to attempt to quickly generate bitcoins this way.

 

EDIT: after fixing a bug in updating $totalcost, it turns out sudoku isn't a particularly good example of simulated annealing after all (it just takes too long). Until I find a better way to implement it in this context I've removed this example.

Edited by RTFC
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...