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