AI::SimulatedAnnealing – optimize a list of numbers according to a specified cost function.
use AI::SimulatedAnnealing;
$optimized_list = anneal($number_specs, $cost_function, $cycles_per_temperature);
This module provides a single public function, anneal(), that optimizes a list of
numbers according to a specified cost function.
Each number to be optimized has a lower bound, an upper bound, and a
precision, where the precision is an integer in the range 0–4
that specifies the number of decimal places to which all instances of
the number will be rounded. The upper bound must be greater than the
lower bound but not greater than 10 to the power of
(4 - p), where p is the precision.
The lower bound must be not less than -1 times the result
of taking 10 to the power of (4 - p).
A bound that has a higher degree of precision than that specified for the number to which the bound applies is rounded inward (that is, downward for an upper bound and upward for a lower bound) to the nearest instance of the specified precision.
The attributes of a number (bounds and precision) are encapsulated
within a number specification, which is a reference to a hash
containing "LowerBound",
"UpperBound", and
"Precision" fields.
The anneal() function takes a
reference to an array of number specifications, a cost function, and a
positive integer specifying the number of randomization cycles per
temperature to perform. The anneal() function returns a
reference to an array having the same length as the array of number
specifications. The returned list represents the optimal list of
numbers matching the specified attributes, where "optimal"
means producing the lowest cost.
The cost function must take a reference to an array of numbers that match the number specifications. The function must return a single number representing a cost to be minimized.
In order to work efficiently with the varying precisions, the
anneal() function converts each bound to an integer by
multiplying it by 10 to the power of the precision; then the function
performs the temperature reductions and randomization cycles (which
include tests performed via calls to the cost function) on integers in
the resulting ranges. When passing an integer to the cost function or
when storing the integer in a collection of numbers to be returned by
the function, anneal() first converts the integer back to
the appropriate decimal number by dividing the integer by 10 to the
power of the precision.
The initial temperature is the size of the largest range after the
bounds have been converted to integers. During each temperature
reduction, the anneal() function multiplies the
temperature by 0.95 and then rounds the result down to the nearest
integer (if the result isn't already an integer). When the
temperature reaches zero, annealing is immediately terminated.
Note: Annealing can sometimes
complete before the temperature reaches zero if, after a particular
temperature reduction, a brute-force optimization approach (that is,
testing every possible combination of numbers within the subranges
determined by the new temperature) would produce a number of tests
that is less than or equal to the specified cycles per temperature.
In that case, the anneal() function performs the
brute-force optimization to complete the annealing process.
After a temperature reduction, the anneal() function
determines each new subrange such that the current optimal integer
from the total range is as close as possible to the center of the new
subrange. When there is a tie between two possible positions for the
subrange within the total range, a "coin flip" decides.
This module requires Perl 5, version 5.10.1 or later.
The anneal() function takes a reference to an array
of number specifications (which are references to hashes
containing "LowerBound",
"UpperBound", and
"Precision" fields), a code reference
pointing to a cost function (which takes a list of numbers
matching the specifications and returns a number representing a
cost to be minimized), and a positive integer specifying the
number of randomization cycles to perform at each temperature.
The function returns a reference to an array containing the optimized list of numbers.
Benjamin Fitch, <blernflerkl@yahoo.com>
Copyright 2010 by Benjamin Fitch.
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.