Jump to content

Simulated Annealing - When brute-force takes too long


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 post
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 post
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 post
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
  • Recently Browsing   0 members

    No registered users viewing this page.

  • Similar Content

    • By poddex
      Hello everyone.
      I always try to work with old Windows 10 versions as much as possible because I know mane compatibility issues with Windows 10 upgrading. 
      But I couldn't do anything else (I got drivers problem), and nothing couldn't help me besides upgrading, so I upgraded from 1807 to 1903.
      And...get another problem 😃
      I use AutoitX library in external project like this.
      ObjectAutoIt=New COMObject("AutoItX3.Control");
      ObjectAutoIt.AutoItSetOption("WinTextMatchMode",2);
              While ObjectAutoit.WinExists("",WindowHeader) Cycle 
                  ObjectAutoIt.WinClose("",WindowHeader);
              EndCycle;
      After upgrade I get that this line code 
      While ObjectAutoit.WinExists("",WindowHeader)
      become extremely low - ~ 20 seconds even if 10 windows open. But before upgrade it takes 0.5 s for a max.
      And every time that this code line passes through  - it takes ~20s, (20.115, for example), not less, not more. Something pauses it to work.
      How can I diagnose, what is that?
      I tried reinstall whole AutoIt, but no results.
      Thanks to all.
    • By scintilla4evr
      An advanced mathematics UDF written in AutoIt.
      Features:
      Extending the default mathematical library with functions like Sec, ACsc... Advanced mathematical functions like Riemann's zeta, etc. Differentiating functions Calculating the probability of an event Working with natural numbers (GCD, LCM, primes, ...) Number sequences Working with points in 2D-space Finding paths in a graph And more!
    • By Wicked_Caty
      I've written a short program that calculates all values of a mathematical function in a user-defined interval. The data is written to an user-defined file during that process. Unfortunately, there is no file. I don't have a clue what's wrong with my program, and I've been trying to solve that for nearly 2 hours now. Obviously without success.
      The calculation is done properly (added a ConsoleWrite() to check that), so it must be the FileWrite() that doesn't work.
      Thanks for the help!
      Values.au3
    • By MattX
      Can someone please let me know if I have this is correct - I've sort of tested it and it seems to work but I need a second opinion.
      I'm hoping someone will agree that it will only call the RUN line if the size is over 20 gig ?


      $mail_que = FileGetSize('C:\Program Files\Microsoft\Exchange Server\TransportRoles\data\Queue\mail.que') $mail_que = $mail_que / 1024 If $mail_que > 20000000 Then Run('c:\matt\mail_que_email_alert.exe', 'c:\matt') EndIf Exit
    • By stormbreaker
      Hello everyone!! While solving some maths problems I thought of something and came up with this so-called 'tricky' game. Read instructions and Enjoy playing!!!


      #include <ButtonConstants.au3> #include <GUIConstantsEx.au3> #include <StaticConstants.au3> #include <WindowsConstants.au3>$Form1 = GUICreate("MKISH's Magic Window", 564, 668, 393, 83) GuiSetBkColor(0xffffff) Global $Button[104] Global Const $ANS = Chr(Random(1,100,1)) $Label3 = GUICtrlCreateLabel(" 1-20 21-40 41-60 61-80 81-100", 24, 16, 515, 25) GUICtrlSetFont(-1, 11, 800, 0, "Comic Sans MS") $Button[1] = GUICtrlCreateButton("", 24, 48, 51, 49, $WS_GROUP) $Button[2] = GUICtrlCreateButton("", 74, 48, 51, 49, $WS_GROUP) $Button[3] = GUICtrlCreateButton("", 24, 96, 51, 49, $WS_GROUP) $Button[4] = GUICtrlCreateButton("", 74, 96, 51, 49, $WS_GROUP) $Button[5] = GUICtrlCreateButton("", 24, 144, 51, 49, $WS_GROUP) $Button[6] = GUICtrlCreateButton("", 74, 144, 51, 49, $WS_GROUP) $Button[7] = GUICtrlCreateButton("", 24, 192, 51, 49, $WS_GROUP) $Button[8] = GUICtrlCreateButton("", 74, 192, 51, 49, $WS_GROUP) $Button[9] = GUICtrlCreateButton("", 24, 240, 51, 49, $WS_GROUP) $Button[10] = GUICtrlCreateButton("", 74, 240, 51, 49, $WS_GROUP) $Button[11] = GUICtrlCreateButton("", 24, 288, 51, 49, $WS_GROUP) $Button[12] = GUICtrlCreateButton("", 74, 288, 51, 49, $WS_GROUP) $Button[13] = GUICtrlCreateButton("", 24, 336, 51, 49, $WS_GROUP) $Button[14] = GUICtrlCreateButton("", 74, 336, 51, 49, $WS_GROUP) $Button[15] = GUICtrlCreateButton("", 24, 384, 51, 49, $WS_GROUP) $Button[16] = GUICtrlCreateButton("", 74, 384, 51, 49, $WS_GROUP) $Button[17] = GUICtrlCreateButton("", 24, 432, 51, 49, $WS_GROUP) $Button[18] = GUICtrlCreateButton("", 74, 432, 51, 49, $WS_GROUP) $Button[19] = GUICtrlCreateButton("", 24, 480, 51, 49, $WS_GROUP) $Button[20] = GUICtrlCreateButton("", 74, 480, 51, 49, $WS_GROUP) $Button[21] = GUICtrlCreateButton("", 128, 48, 51, 49, $WS_GROUP) $Button[22] = GUICtrlCreateButton("", 178, 48, 51, 49, $WS_GROUP) $Button[23] = GUICtrlCreateButton("", 128, 96, 51, 49, $WS_GROUP) $Button[24] = GUICtrlCreateButton("", 178, 96, 51, 49, $WS_GROUP) $Button[25] = GUICtrlCreateButton("", 128, 144, 51, 49, $WS_GROUP) $Button[26] = GUICtrlCreateButton("", 178, 144, 51, 49, $WS_GROUP) $Button[27] = GUICtrlCreateButton("", 128, 192, 51, 49, $WS_GROUP) $Button[28] = GUICtrlCreateButton("", 178, 192, 51, 49, $WS_GROUP) $Button[29] = GUICtrlCreateButton("", 128, 240, 51, 49, $WS_GROUP) $Button[30] = GUICtrlCreateButton("", 178, 240, 51, 49, $WS_GROUP) $Button[31] = GUICtrlCreateButton("", 128, 288, 51, 49, $WS_GROUP) $Button[32] = GUICtrlCreateButton("", 178, 288, 51, 49, $WS_GROUP) $Button[33] = GUICtrlCreateButton("", 128, 336, 51, 49, $WS_GROUP) $Button[34] = GUICtrlCreateButton("", 178, 336, 51, 49, $WS_GROUP) $Button[35] = GUICtrlCreateButton("", 128, 384, 51, 49, $WS_GROUP) $Button[36] = GUICtrlCreateButton("", 178, 384, 51, 49, $WS_GROUP) $Button[37] = GUICtrlCreateButton("", 128, 432, 51, 49, $WS_GROUP) $Button[38] = GUICtrlCreateButton("", 178, 432, 51, 49, $WS_GROUP) $Button[39] = GUICtrlCreateButton("", 128, 480, 51, 49, $WS_GROUP) $Button[40] = GUICtrlCreateButton("", 178, 480, 51, 49, $WS_GROUP) $Button[41] = GUICtrlCreateButton("", 232, 48, 51, 49, $WS_GROUP) $Button[42] = GUICtrlCreateButton("", 282, 48, 51, 49, $WS_GROUP) $Button[43] = GUICtrlCreateButton("", 232, 96, 51, 49, $WS_GROUP) $Button[44] = GUICtrlCreateButton("", 282, 96, 51, 49, $WS_GROUP) $Button[45] = GUICtrlCreateButton("", 232, 144, 51, 49, $WS_GROUP) $Button[46] = GUICtrlCreateButton("", 282, 144, 51, 49, $WS_GROUP) $Button[47] = GUICtrlCreateButton("", 232, 192, 51, 49, $WS_GROUP) $Button[48] = GUICtrlCreateButton("", 282, 192, 51, 49, $WS_GROUP) $Button[49] = GUICtrlCreateButton("", 232, 240, 51, 49, $WS_GROUP) $Button[50] = GUICtrlCreateButton("", 282, 240, 51, 49, $WS_GROUP) $Button[51] = GUICtrlCreateButton("", 232, 288, 51, 49, $WS_GROUP) $Button[52] = GUICtrlCreateButton("", 282, 288, 51, 49, $WS_GROUP) $Button[53] = GUICtrlCreateButton("", 232, 336, 51, 49, $WS_GROUP) $Button[54] = GUICtrlCreateButton("", 282, 336, 51, 49, $WS_GROUP) $Button[55] = GUICtrlCreateButton("", 232, 384, 51, 49, $WS_GROUP) $Button[56] = GUICtrlCreateButton("", 282, 384, 51, 49, $WS_GROUP) $Button[57] = GUICtrlCreateButton("", 232, 432, 51, 49, $WS_GROUP) $Button[58] = GUICtrlCreateButton("", 282, 432, 51, 49, $WS_GROUP) $Button[59] = GUICtrlCreateButton("", 232, 480, 51, 49, $WS_GROUP) $Button[60] = GUICtrlCreateButton("", 282, 480, 51, 49, $WS_GROUP) $Button[61] = GUICtrlCreateButton("", 336, 48, 51, 49, $WS_GROUP) $Button[62] = GUICtrlCreateButton("", 386, 48, 51, 49, $WS_GROUP) $Button[63] = GUICtrlCreateButton("", 336, 96, 51, 49, $WS_GROUP) $Button[64] = GUICtrlCreateButton("", 386, 96, 51, 49, $WS_GROUP) $Button[65] = GUICtrlCreateButton("", 336, 144, 51, 49, $WS_GROUP) $Button[66] = GUICtrlCreateButton("", 386, 144, 51, 49, $WS_GROUP) $Button[67] = GUICtrlCreateButton("", 336, 192, 51, 49, $WS_GROUP) $Button[68] = GUICtrlCreateButton("", 386, 192, 51, 49, $WS_GROUP) $Button[69] = GUICtrlCreateButton("", 336, 240, 51, 49, $WS_GROUP) $Button[70] = GUICtrlCreateButton("", 386, 240, 51, 49, $WS_GROUP) $Button[71] = GUICtrlCreateButton("", 336, 288, 51, 49, $WS_GROUP) $Button[72] = GUICtrlCreateButton("", 386, 288, 51, 49, $WS_GROUP) $Button[73] = GUICtrlCreateButton("", 336, 336, 51, 49, $WS_GROUP) $Button[74] = GUICtrlCreateButton("", 386, 336, 51, 49, $WS_GROUP) $Button[75] = GUICtrlCreateButton("", 336, 384, 51, 49, $WS_GROUP) $Button[76] = GUICtrlCreateButton("", 386, 384, 51, 49, $WS_GROUP) $Button[77] = GUICtrlCreateButton("", 336, 432, 51, 49, $WS_GROUP) $Button[78] = GUICtrlCreateButton("", 386, 432, 51, 49, $WS_GROUP) $Button[79] = GUICtrlCreateButton("", 336, 480, 51, 49, $WS_GROUP) $Button[80] = GUICtrlCreateButton("", 386, 480, 51, 49, $WS_GROUP) $Button[81] = GUICtrlCreateButton("", 440, 48, 51, 49, $WS_GROUP) $Button[82] = GUICtrlCreateButton("", 490, 48, 51, 49, $WS_GROUP) $Button[83] = GUICtrlCreateButton("", 440, 96, 51, 49, $WS_GROUP) $Button[84] = GUICtrlCreateButton("", 490, 96, 51, 49, $WS_GROUP) $Button[85] = GUICtrlCreateButton("", 440, 144, 51, 49, $WS_GROUP) $Button[86] = GUICtrlCreateButton("", 490, 144, 51, 49, $WS_GROUP) $Button[87] = GUICtrlCreateButton("", 440, 192, 51, 49, $WS_GROUP) $Button[88] = GUICtrlCreateButton("", 490, 192, 51, 49, $WS_GROUP) $Button[89] = GUICtrlCreateButton("", 440, 240, 51, 49, $WS_GROUP) $Button[90] = GUICtrlCreateButton("", 490, 240, 51, 49, $WS_GROUP) $Button[91] = GUICtrlCreateButton("", 440, 288, 51, 49, $WS_GROUP) $Button[92] = GUICtrlCreateButton("", 490, 288, 51, 49, $WS_GROUP) $Button[93] = GUICtrlCreateButton("", 440, 336, 51, 49, $WS_GROUP) $Button[94] = GUICtrlCreateButton("", 490, 336, 51, 49, $WS_GROUP) $Button[95] = GUICtrlCreateButton("", 440, 384, 51, 49, $WS_GROUP) $Button[96] = GUICtrlCreateButton("", 490, 384, 51, 49, $WS_GROUP) $Button[97] = GUICtrlCreateButton("", 440, 432, 51, 49, $WS_GROUP) $Button[98] = GUICtrlCreateButton("", 490, 432, 51, 49, $WS_GROUP) $Button[99] = GUICtrlCreateButton("", 440, 480, 51, 49, $WS_GROUP) $Button[100] = GUICtrlCreateButton("", 490, 480, 51, 49, $WS_GROUP) $Button[101] = GUICtrlCreateButton("I am Done !!", 80, 576, 123, 57, $WS_GROUP) $Button[102] = GUICtrlCreateButton("Instructions", 208, 576, 123, 57, $WS_GROUP) $Button[103] = GUICtrlCreateButton("Go Home!!", 336, 576, 123, 57, $WS_GROUP) For $i = 1 to 100 GUICtrlSetFont($Button[$i], 16, 400, 4, "Wingdings") GuiCtrlSetData($Button[$i], Chr(Random(101, $i+150, 1))) GUICtrlSetTip($Button[$i], "" & $i) Next For $i = 0 to 100 step 9 GuiCtrlSetData($Button[$i], $ANS) Next $Label1 = GUICtrlCreateLabel("", 8, 544, 548, 4, $SS_SUNKEN) GUISetState(@SW_SHOW) While 1 $nMsg = GUIGetMsg() Switch $nMsg Case $GUI_EVENT_CLOSE, $Button[103] Exit Case $Button[101] GuiSetstate(@SW_DISABLE, $Form1) $Form2 = GUICreate("Answer", 316, 184, -1, -1, BitOR($WS_SYSMENU,$WS_POPUP,$WS_POPUPWINDOW,$WS_BORDER,$WS_CLIPSIBLINGS)) GuiSetBkColor(0xffffff) $GroupBox1 = GUICtrlCreateGroup("", 8, 1, 297, 129) $Labelx1 = GUICtrlCreateLabel("The symbol is:", 80, 24, 153, 34) GUICtrlSetFont(-1, 16, 800, 0, "Comic Sans MS") $Labelx22 = GUICtrlCreateLabel("", 96, 90, 139, 30) GUICtrlSetFont(-1, 18, 800, 0, "Wingdings") GuiCtrlSetData(-1, $ANS) GUICtrlCreateGroup("", -99, -99, 1, 1) GUISetState(@SW_SHOW) Case $Button[102] msgbox(64, "Instructions", "> Think of a number b/w 10 and 100" & @crlf & "> Subtract from it the sum of its digits" & @crlf & "> Look for the symbol corresponding to answer on the list" & @CRLF & "> Click 'I am Done !!' button and Bingo", Default, $Form1) EndSwitch WEnd
      muttley Easy, isn't it?

      EDIT: Now looks fine..
×
×
  • Create New...