view release on metacpan or  search on metacpan

lib/AI/SimulatedAnnealing.pm  view on Meta::CPAN

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 to 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.

=head1 PREREQUISITES

This module requires Perl 5, version 5.10.1 or later.

=head1 METHODS

=over

=item anneal($number_specs, $cost_function, $cycles_per_temperature);

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.

=back

=head1 AUTHOR

Benjamin Fitch, <blernflerkl@yahoo.com>

=head1 COPYRIGHT AND LICENSE

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.

=cut