Writing Neighbour Functions

Neighbor functions

A core part of simulated annealing is effective neighbor selection. The neighbor is the next arbitrary modification to apply to the data to advance the search. In a graph trying to find the shortest path between all nodes, it might be easiest to pick paths to swap. In a tree, it might be to remove or add a node. In a pathfinding exercise, it may be to add one or five steps.

To submit our own neighbor function, we must use the ?USERNF(Generator, Next) macro. The generator value is the same generator pattern we’d usually give to ?FORALL_TARGETED. The next argument is where we pass in the function used to create the next value. The overall patterns look like this:

prop_example() ->
     ?FORALL_TARGETED(Var, ?USERNF(list(integer()), next_list()),
         some_check(Var).

next_list() ->
     fun(PreviousValue, {Depth, CurrentTemperature}) ->
          ?LET(Val, some_generator(), 
               modify(Val, PreviousValue))
     end.

The tricky stuff is all within the next_list() function. This is a function with no arguments that must return an anonymous function. That anonymous function itself takes two arguments. The previously generated term ((PreviousValue)) that we’re searching on and the temperature parameters. Depth is a positive integer representing how deep the generator is nested, and CurrentTemperature is any number, representing the current temperature.

Let’s try it with our tree property. It has been defined in the code below between line 5 and line 12.

The macro specifies the neighbor function, and the neighbor function takes the previous tree and just inserts one additional element in it. At runtime, PropEr will first call the generator (tree()) to get the initial piece of data, to later pass it on to next_tree()’s inner function. The next_tree function is defined between line 14 and line 17.

That could be enough on its own. Note that the number inserted in the tree is first scaled according to the temperature. The temperature is usually a floating-point value from 0.0 to 1.0, so it’s used as a multiplicative percentage (T*100). The final result is re-transformed into an integer with trunc and then inserted.