RTFC

Simulated Annealing - When brute-force takes too long

5 posts in this topic




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


Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______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

 

Share this post


Link to post
Share on other sites

#4 ·  Posted (edited)

@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
1 person likes this

Share this post


Link to post
Share on other sites

#5 ·  Posted (edited)

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

Share this post


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

  • Similar Content

    • scintilla4evr
      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!
    • Wicked_Caty
      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
    • MattX
      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
    • stormbreaker
      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..
    • PhoenixXL
      By PhoenixXL
      I use Fractions Always In My Script
      But I never Found a UDF for That
      I made a UDF for Using
      So here I want to Share it
      I Named it MathsEx UDF but I Guess Fraction UDF would be Better

      It Requires Three Funtions Of Array.au3

      Currently Supported Functions

      ; #INDEX# ======================================================================================================================= ; Title .........: MathsEx ; AutoIt Version : 3.2.10++ ; Language ......: English ; Description ...: Functions for Carrying Out More Advanced Mathematical Calculations. ; Author(s) .....: Phoenix XL ; Included.......: Three Functions of Array.au3 i.e. _ArraySort and _ArrayReverse and __ArrayQuickSort1D Requires Array.au3 ; =============================================================================================================================== ; 0xDead=57005...............I just Like The Number :) ; #CURRENT# ===================================================================================================================== ; _Find_GCF ; _Find_LCM ; _Subtract_Fraction ; _Add_Fraction ; _Multiply_Fraction ; _Divide_Fraction ; _Reciprocal ; _Compare_Fraction ; _Quotient ; _Simplify ; _IntegerisNegative ; _IntegerisPositive ; _Get_Denominator ; _Get_Numerator ; _To_Fraction ; _To_Mixed_Fraction ; _Is_Fraction_Improper ; _Is_Fraction_Proper ; _Is_Fraction ; =============================================================================================================================== ; #INTERNAL_USE_ONLY# =========================================================================================================== ; _CheckArray ; _Greatest_Common_Factor ; _Operate_Fraction ; _Set_Sequence ; ===============================================================================================================================
      I havent Included Any Examples Yet
      The Documentation is Enough and Is Very Easy To Implement the Funtions
      Though If any Bug or Problem With The UDF Please Share It

      The UDF is Attached in the Post
      V1.1 = Fixed A Bug

      Regards
      Phoenix XL
      MathsEx V1.1.au3