AI-SimulatedAnnealing

 view release on metacpan or  search on metacpan

Changes  view on Meta::CPAN

1
2
3
4
5
6
7
8
9
10
11
 
Revision history for the AI-SimulatedAnnealing distribution:
 
    Version    Date          Description
    -------    ----          -----------
 
    1.01       2010-10-06    Initial upload
 
    1.02       2010-10-09    In t/annealing_tests.t, added a missing
                             "exit" call that will never get used but
                             looked incorrect when it was missing :-)

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

60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
  specifications. The returned list represents the optimal list of
  numbers matching the specified attributes, where "optimal"
  means producing the lowest cost.</p>
<p>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.</p>
<p>In order to work efficiently with the varying precisions, the
  <code>anneal()</code> 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, <code>anneal()</code> first converts the integer back to
  the appropriate decimal number by dividing the integer by 10 to the
  power of the precision.</p>
<p>The initial temperature is the size of the largest range after the
  bounds have been converted to integers. During each temperature
  reduction, the <code>anneal()</code> function multiplies the
  temperature by 0.95 and then rounds the result down to the nearest
  integer (if the result isn&#39;t already an integer). When the
  temperature reaches zero, annealing is immediately terminated.</p>
<p style="margin-left: 13px;"><b>Note:</b>  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 <code>anneal()</code> function performs the
  brute-force optimization to complete the annealing process.</p>
<p>After a temperature reduction, the <code>anneal()</code> 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 &quot;coin flip&quot; decides.</p>
<hr/>
<h1><a name="prerequisites">PREREQUISITES</a></h1>

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

199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
    return \@optimized_list;
} # end sub
 
####
# Private helper functions for use by this module:
 
# The use_brute_force() function takes a reference to an array of number
# specifications (which are references to hashes containing "LowerBound",
# "UpperBound", and "Precision" fields) and a reference to a cost function
# (which takes a list of numbers matching the specifications and returns a
# number representing a cost to be minimized).  The method tests every
# possible combination of numbers matching the specifications and returns a
# reference to an array containing the optimal numbers, where "optimal"
# means producing the lowest cost.
sub use_brute_force {
    my $number_specs = validate_number_specs($_[0]);
    my $cost_function = $_[1];
 
    my @optimized_list;
    my @lists;
    my @cursors;

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

229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
    } # end while
 
    push @lists, \@list;
} # next $number_spec
 
# Populate @cursors with the starting position for each list of numbers:
for (0..$#lists) {
    push @cursors, 0;
} # next
 
# Perform the tests:
my $lowest_cost = undef;
my $finished = $FALSE;
 
do {
    # Perform a test using the current cursors:
    my @candidate_list;
    my $cost;
 
    for my $dex (0..$#lists) {
        push @candidate_list, $lists[$dex]->[$cursors[$dex]];
    } # next $dex
 
    $cost = $cost_function->(\@candidate_list);
 
    unless (defined($lowest_cost) && $cost >= $lowest_cost) {
        $lowest_cost = $cost;
        @optimized_list = @candidate_list;
    } # end unless
 
    # Adjust the cursors for the next test if not finished:
    for my $dex (reverse(0..$#lists)) {
        my $cursor = $cursors[$dex];
 
        if ($cursor < $#{ $lists[$dex] }) {
            $cursor++;
            $cursors[$dex] = $cursor;
            last;
        }
        elsif ($dex == 0) {
            $finished = $TRUE;

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

373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
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.

t/annealing_tests.t  view on Meta::CPAN

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#!/usr/bin/perl
 
####
# annealing_tests.t:  Test the AI::SimulatedAnnealing module.
#
# Usage:
#
#     perl -w annealing_tests.t market_distances.csv
####
use 5.010001;
use strict;
use warnings;
use utf8;
 
use English "-no_match_vars";
use List::Util ("max", "min");
 
use AI::SimulatedAnnealing;

t/annealing_tests.t  view on Meta::CPAN

159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
 
    # Print the results for this probability to the console:
    say "\nProbability:  1/$p";
    printf("Coefficients:  a = %1.3f; b = %1.3f; c= %1.3f\n",
      $optimized_coefficients->[0],
      $optimized_coefficients->[1],
      $optimized_coefficients->[2]);
    say "Cost:  " . $cost_function->($optimized_coefficients);
} # next $p
 
# Perform an annealing test with integers that triggers brute-force analysis
# and uses an anonymous cost function that minimizes this sum:
#
#     (10 * abs(23 - val)) + (the total range of a, b, and c)
#
# where "val" is the result of following expression:
#
#     (a * (x ** 2)) + bx + c
#
# in which x = 3:
my $abc;