Nicollet.Net

Annealing is a process to harden metals: by repeatedly heating and freezing metal, atoms within the metallic structure are dislodged and then moved back into place, which moves those atoms that were not part of a regular structure to more correct positions, resulting in a stronger metal piece.

The underlying process is that of energy reduction: an atom in a non-regular position within a crystalline lattice has a high potential energy, but is kept into place because it has reached a local energy minimum (so moving away requires more energy than it has). By imcreasing the available energy, the atom is allowed to move out of the local minimum, and so it ends up in a location with lower energy (with a reasonable probability, though this is by no means certain). By applying this process a high enough number of times, the global minimum can be reached.

Simulated Annealing

In computer science, that process can be applied to minimization techniques: instead of exploring the problem space completely, annealing is simulating by moving around randomly in that space. In order to move towards minima, every move which increases the value can be canceled with a certain probability that increases as time passes.

For example:

let annealing steps energy initial =
  let rec aux n best best_energy current =
    if n = 0 then best else
      let current = random_move current in
      let new_energy = energy current in
      if new_energy < best_energy then
        aux (n-1) current new_energy current
      else if Random.int steps < n then
        aux (n-1) best best_energy best
      else
        aux (n-1) best best_energy current
  in aux steps initial (energy initial) initial

This is by no means the only possible approach: other variations can involve checking whether the move is upwards since the last position (instead of the best position so far) or using a different probability approach for preventing up-moves.

Genetic Computing

A common problem found in simulated annealing and genetic algorithms is the implementation of solutions as programs: since these approaches require the ability to randomly mutate a solution, and a program is usually a fickle and weak construct that can easily die if one of its parts is forcibly removed, representing programs as randomly altered entities is difficult.

One possible solution is to consider stack based-languages: these languages have very light syntax requirements and can be represented mostly as a sequence of words. Besides, the only way for a program in these languages to die is to underflow the stack (which can be easily solved by stating that reading from an empty stack yields a reasonable value, such as zero or one. My concept was to use a language which reads a single integer variable ‘x’ and manipulates a stack ‘s’, and outputs a stack of numbers. These numbers are then multiplied together to yield the final result. The available instructions are:

let operations =
  [|
    "nop", (fun (s,_) -> s);
    "pop", (fun (s,_) -> !s) ;
    "dup", (fun (s,_) -> t s :: s);
    "div", (fun (s,_) -> (t s /. t !s) :: !!s);
    "two", (fun (s,_) -> 2. :: s);
    "mul", (fun (s,_) -> (t s *. t !s) :: !!s);
    "add", (fun (s,_) -> (t s +. t !s) :: !!s);
    "cos", (fun (s,_) -> cos (t s) :: !s);
    "sin", (fun (s,_) -> sin (t s) :: !s);
    "sub", (fun (s,_) -> (t s -. t !s) :: !!s);
    "min", (fun (s,_) -> min (t s) (t !s) :: !!s);
    "max", (fun (s,_) -> max (t s) (t !s) :: !!s);
    "avg", (fun (s,_) -> ((t s +. t !s) *. 0.5) :: !!s);
    "var", (fun (s,x) -> x :: s);
    "bra", (fun (s,_) -> (if t s > 0. then t !s else t !!s) :: !!!s);
    "zer", (fun (s,_) -> 0. :: s);
    "one", (fun (s,_) -> 1. :: s);
    "neg", (fun (s,_) -> -1. :: s);
    "opp", (fun (s,_) -> -. (t s) :: !s);
    "dp2", (fun (s,_) -> t s :: t s :: s);
  |]

I have altered the meaining of ‘!’ to represent the tail of the list (or, if the list is empty, the empty list), and defined ‘t’ as the top of the list (or 0. if the list is empty).

The evaluation algorithm is extremely straightforward:

let run p x =
  List.fold_left ( *. ) 1.
    (Array.fold_left (fun s (_,o) -> o (s,x)) [] p)

I then apply simulated annealing to such programs (using a program size of 10 instructions) for 10000 iterations. The energy function is simply the error between the value computed by the program and the expected value. For instance, with the function ‘fun x -> x’, simulated annealing gives me the program:

cos dup pop nop bra cos dp2 nop var nop

Which can be rewritten as:

let t = cos (if 0 > (cos 0) then 0 else 0) in t *. t *. t *. x

This is a fairly convoluted way of saying “x”. Another example, with the function ‘fun x -> x +. x *. x’:

max bra one dup nop max add var add var

The infix form here would be:

((if max 0 0 > 0 then 0 else 0) + (max 1 1) + x) * x

Which is just ‘(1+x)*x’.