1use strict;
2use warnings;
3
4use lib qw( ../../../../lib ); # mainly to avoid syntax errors when saving
5
6=head1 NAME
7
8SimulatedAnnealing - An operator that performs the simulated annealing algorithm
9                          on an individual, using an external freezing schedule
10
11=head1 SYNOPSIS
12
13  #Define an algorithm
14  my $m  = new Algorithm::Evolutionary::Op::BitFlip; #Changes a single bit
15  my $freezer = new Algorithm::Evolutionary::Op:LinearFreezer( $initTemp );
16  my $sa = new Algorithm::Evolutionary::Op::SimulatedAnnealing( $eval, $m, $freezer, $initTemp, $minTemp, $numChanges );
17
18=head1 Base Class
19
20L<Algorithm::Evolutionary::Op::Base>
21
22=head1 DESCRIPTION
23
24Simulated Annealing
25
26=head1 METHODS
27
28=cut
29
30package Algorithm::Evolutionary::Op::SimulatedAnnealing;
31
32our $VERSION = '3.1';
33use Carp;
34
35use Algorithm::Evolutionary::Op::LinearFreezer;
36use base 'Algorithm::Evolutionary::Op::Base';
37
38
39=head2 new( $evaluation_function, $change_operator, $freezer[,
40    $initial_temperature] [,$minimum_temperature]
41    [,$number_of_changes], [,$verbose] )
42
43Creates a simulated annealing object
44
45=cut
46
47sub new {
48  my $class = shift;
49  my $self = {};
50  $self->{_eval} = shift || croak "No eval function found";
51  $self->{_op} = shift || croak "No operator found";
52  $self->{_freezer} = shift || croak "No freezer found";
53  $self->{_initTemp} = shift || 0.2;
54  $self->{_minTemp} = shift || 0.001;
55  $self->{_numChanges} = shift || 7;
56  $self->{_verbose} = shift || 0;
57
58  bless $self, $class;
59  return $self;
60}
61
62=head2 run( $individual )
63
64Applies the algorithm to the individual, returns the resulting
65    individual when the min temperature is reached. Same as C<apply> in other operators
66
67
68=cut
69
70sub run ($) {
71  my $self  = shift;
72  my $indiv = shift || croak "there is no individual";
73
74  #Evaluate
75  my $eval = $self->{_eval};
76  my $op = $self->{_op};
77  my $freezer = $self->{_freezer};
78  my $initTemp= $self->{_initTemp};
79  my $minTemp = $self->{_minTemp};
80  my $numChanges = $self->{_numChanges};
81  my $verbose= $self->{_verbose};
82
83  my $t = $initTemp ;
84  while ( $t > $minTemp ) {
85    for(my $j=0; $j < $numChanges; $j++) {
86
87      my $padre  =  $indiv->clone();
88      my $mutado = $op->apply( $padre );
89
90      #Calculate the original individual fitness, if it's necessary
91      my $fitness1;
92      if ( !defined ($indiv->Fitness() ) ) {
93	$fitness1 = $eval->( $indiv );
94	$indiv->Fitness( $fitness1 );
95      }
96      else
97	{$fitness1 = $indiv->Fitness(); }
98
99      #Calculate the mutated individual fitness, if it's necessary
100      my $fitness2;
101      if ( !defined ($mutado->Fitness() ) ) {
102	$fitness2 = $eval->( $mutado );
103	$mutado->Fitness( $fitness2 );
104      }
105      else
106        {$fitness2 = $mutado->Fitness();}
107
108      my $delta = $fitness1 - $fitness2;
109
110      print "Original=".$indiv->asString."\nMutated =". $mutado->asString."\n" if ( $verbose >= 2);
111      print "Fitness1: $fitness1 \tFitness2: $fitness2 \t delta=$delta \n" if ( $verbose >= 2);
112
113      if ( ($delta<0) || (rand()<exp((-1*$delta)/$t)) ) {
114	$indiv = $mutado;
115      }
116    }
117    $t = $freezer->apply($t);
118
119    print "T: \t$t \n" if ( $verbose >= 1);
120    print $indiv->asString, "\n" if ( $verbose >= 1);
121  }
122
123  return $indiv;
124}
125
126=head1 Copyright
127
128  This file is released under the GPL. See the LICENSE file included in this distribution,
129  or go to http://www.fsf.org/licenses/gpl.txt
130
131=cut
132