simulation::annealing(3tcl)

📦
version 2.0 · 2 versions
, in debian trixie, ubuntu questing, ubuntu resolute, ubuntu stonking

✨ simulation::annealing ✨

okay bestie, gather round, because today we're talking about simulated annealing — it's a Tcl package from the Tcl Simulation Tools crew, version 0.3, and it's literally the chillest way to hunt down a global optimum 🧊🔥

💖 NAME 💖

simulation::annealing — Simulated annealing. that's it, that's the name, and yes it's exactly as iconic as it sounds 💅

🎀 SYNOPSIS 🎀

package require Tcl ?8.5 9?

package require simulation::annealing 0.3

::simulation::annealing::getOption keyword

::simulation::annealing::hasOption keyword

::simulation::annealing::setOption keyword value

::simulation::annealing::findMinimum args

::simulation::annealing::findCombinatorialMinimum args

🦋 DESCRIPTION 🦋

so. simulated annealing is a technique for estimating the global optimum of a function, and it's described in some detail over on the Wiki at http://wiki.tcl.tk/.... (iykyk). the whole idea is genuinely simple, no cap:

  • you randomly select points inside a given search space
  • for each point you evaluate the function you're optimising, then you either keep the point with the lowest (or highest) function value, or — and this is the spicy part — sometimes you accept a point that has a less optimal value. the chance of accepting one of those non-optimal points gets smaller and smaller over time 📉
  • because you're willing to accept less optimal points, the method doesn't necessarily get stuck in a local optimum, and theoretically it can find the global optimum inside the search space 👑

the whole thing resembles the cooling of material, which is literally why it's called annealing. the vibe check passed, the name stayed.

the package simulation::annealing hands you the findMinimum command, like this:

puts [::simulation::annealing::findMinimum  -trials 300  -parameters {x -5.0 5.0 y -5.0 5.0}  -function {$x*$x+$y*$y+sin(10.0*$x)+4.0*cos(20.0*$y)}]

and that prints the estimated minimum value of the function f(x,y) = x**2+y**2+sin(10*x)+4*cos(20*y), plus the values of x and y where that minimum was attained:

result -4.9112922923 x -0.181647676593 y 0.155743646974

ate. 🍓

💅 PROCEDURES 💅

the package defines these auxiliary procedures, bestie:

  • ::simulation::annealing::getOption keyword — get the value of an option given as part of the findMinimum command.
    • string keyword — the given keyword (without the leading minus)
  • ::simulation::annealing::hasOption keyword — returns 1 if the option is available, 0 if not.
    • string keyword — the given keyword (again, without the leading minus)
  • ::simulation::annealing::setOption keyword value — set the value of the given option.
    • string keyword — the given keyword (yes, without the leading minus)
    • string value — the (new) value for the option

the main character procedures are findMinimum and findCombinatorialMinimum:

  • ::simulation::annealing::findMinimum args — find the minimum of a function using simulated annealing. the function and the method's parameters come in via a list of keyword-value pairs.
    • int n — list of keyword-value pairs, all of which are available during execution through the getOption command
  • ::simulation::annealing::findCombinatorialMinimum args — find the minimum of a function of discrete variables using simulated annealing. the function and the method's parameters come in via a list of keyword-value pairs.
    • int n — list of keyword-value pairs, all of which are available during execution through the getOption command

🌈 the options findMinimum predefines

  • -parameters list — triples defining parameters and ranges
  • -function expr — expression defining the function
  • -code body — body of code to define the function. this one takes precedence over -function, and the code should set the variable "result"
  • -init code — code to be run at start up
  • -final code — code to be run at the end
  • -trials n — number of trials before reducing the temperature
  • -reduce factor — reduce the temperature by this factor (between 0 and 1)
  • -initial-temp t — initial temperature
  • -scale s — scale of the function (order of magnitude of the values)
  • -estimate-scale y/n — estimate the scale (only if -scale is not present)
  • -verbose y/n — print detailed information on progress to the report file (1) or not (0)
  • -reportfile file — opened file to print to (defaults to stdout)

any other options can be used via the getOption procedure in the body. 💫

🌸 the options findCombinatorialMinimum predefines

  • -number-params n — number of binary parameters (the solution space consists of lists of 1s and 0s). this is a required option, no skipping it
  • -initial-values — list of 1s and 0s constituting the start of the search

the other predefined options are identical to those of findMinimum. ✨

🔥 TIPS 🔥

the findMinimum procedure works by constructing a temporary procedure that does the actual work. it loops until the point representing the estimated optimum does not change anymore within the given number of trials. as the temperature gets lower and lower, the chance of accepting a point with a higher value becomes lower too, so in practice the procedure will terminate. periodt. 💀

you can optimise over a non-rectangular region, but some care must be taken:

  • if the point is outside the region of interest, you can specify a very high value
  • but this does mean that the automatic determination of a scale factor is out of the question — those high function values that force the point inside the region would distort the estimation

here's an example of finding an optimum inside a circle:

puts [::simulation::annealing::findMinimum  -trials 3000  -reduce 0.98  -parameters {x -5.0 5.0 y -5.0 5.0}  -code {
        if { hypot($x-5.0,$y-5.0) < 4.0 } {
            set result [expr {$x*$x+$y*$y+sin(10.0*$x)+4.0*cos(20.0*$y)}]
        } else {
            set result 1.0e100
        }
    }]

the method is theoretically capable of determining the global optimum, but often you need to use a large number of trials and a slow reduction of temperature to get reliable and repeatable estimates. ngl, patience is the vibe here 🧘

you can use the -final option to use a deterministic optimization method, once you're sure you're near the required optimum. 👑

the findCombinatorialMinimum procedure is suited for situations where the parameters have the values 0 or 1 (and there can be many of them). here's an example:

  • we have a function that attains an absolute minimum if the first ten numbers are 1 and the rest is 0:
proc cost {params} {
    set cost 0
    foreach p [lrange $params 0 9] {
        if { $p == 0 } {
            incr cost
        }
    }
    foreach p [lrange $params 10 end] {
        if { $p == 1 } {
            incr cost
        }
    }
    return $cost
}
  • we want to find the solution that gives this minimum for various lengths of the solution vector params:
foreach n {100 1000 10000} {
    break
    puts "Problem size: $n"
    puts [::simulation::annealing::findCombinatorialMinimum  -trials 300  -verbose 0  -number-params $n  -code {set result [cost $params]}]
}
  • as the vector grows, the computation time increases, but the procedure will stop if some kind of equilibrium is reached. to achieve a useful solution you may want to try different values of the trials parameter, for instance. also make sure that the function to be minimized depends on all or most parameters — see the source code for a counter example and run that. 🫶

⭐ KEYWORDS ⭐

math, optimization, simulated annealing

👑 CATEGORY 👑

Mathematics

Copyright (c) 2008 Arjen Markus <arjenmarkus@users.sourceforge.net>

and that's the whole page, bestie!! this was tcllib 0.3, simulation::annealing(3tcl), brought to you with love, lowkey a little chaos, and a whole lot of cooling schedules. go find your global optimum, you absolute icon 🎀✨🦋

📦 where this page comes from