1use strict; 2use warnings; 3 4use lib qw(../../..); 5 6=head1 NAME 7 8Algorithm::Evolutionary::Op::Inverover - Michalewicz's inver-over Operator. 9 10=head1 SYNOPSIS 11 12 my $xmlStr3=<<EOC; 13 <op name='Inverover' type='binary' rate='1' /> 14 EOC 15 my $ref3 = XMLin($xmlStr3); 16 17 my $op3 = Algorithm::Evolutionary::Op::Base->fromXML( $ref3 ); 18 print $op3->asXML(), "\n"; 19 20 my $indi = new Algorithm::Evolutionary::Individual::BitString 10; 21 my $indi2 = $indi->clone(); 22 my $indi3 = $indi->clone(); 23 $op3->apply( $indi2, $indi3 ); 24 25=head1 Base Class 26 27L<Algorithm::Evolutionary::Op::Base> 28 29=head1 DESCRIPTION 30 31Inver-over operator for a GA. Created by Michalewicz et al., mainly 32for the travelling salesman problem. Takes two chromosomes, which are 33permutations of each other. 34 35There is some information on this operator in this interview 36with Michalewicz: L<http://www.dcs.napier.ac.uk/coil/news/feature48.html>. You can also download papers from his home page: L<http://www.cs.adelaide.edu.au/~zbyszek/Papers/>. 37 38=head1 METHODS 39 40=cut 41 42package Algorithm::Evolutionary::Op::Inverover; 43 44our ($VERSION) = ( '$Revision: 3.0 $ ' =~ /(\d+\.\d+)/ ); 45 46use Carp; 47 48use base 'Algorithm::Evolutionary::Op::Base'; 49 50#Class-wide constants 51our $APPLIESTO = 'Algorithm::Evolutionary::Individual::Vector'; 52our $ARITY = 2; 53 54=head2 new( $rate ) 55 56Creates a new Algorithm::Evolutionary::Op::Inverover operator. 57 58=cut 59 60sub new { 61 my $class = shift; 62 my $rate = shift || 0.5; 63 my $hash; 64 65 my $self = Algorithm::Evolutionary::Op::Base::new( 'Algorithm::Evolutionary::Op::Inverover', $rate, $hash ); 66 return $self; 67} 68 69=head2 create 70 71Creates a new Algorithm::Evolutionary::Op::Inverover operator. 72 73=cut 74 75sub create { 76 my $class = shift; 77 my $self; 78 bless $self, $class; 79 return $self; 80} 81 82=head2 apply( $first, $second ) 83 84Applies Algorithm::Evolutionary::Op::Inverover operator to a 85 "Chromosome". Can be applied to anything with the Atom method. 86 87=cut 88 89sub apply ($$$){ 90 my $self = shift; 91 my $p1 = shift || croak "No victim here!"; #first parent 92 my $p2 = shift || croak "No victim here!"; #second parent 93 my $child=$p1->clone(); #Clone S' (child) from First parent 94 my $i; #Iterator 95 96 97 #Check parents type and size 98 croak "Incorrect type ".(ref $p1) if !$self->check($p1); 99 croak "Incorrect type ".(ref $p2) if !$self->check($p2); 100 croak "Inver-over Error: Parents haven't sime size " if ($p1->length() != $p2->length() ); 101 my $leng=$p1->length(); #Chrom length 102 103 #Select randomly a atom c from S' (child) 104 my $c=int( rand( $leng/2 ) ); 105 my $c2; #The another atom c' (called c2) 106 107 #Build Algorithm::Evolutionary::Op::Inverover child 108 while ( 1 ) 109 { 110 if (rand() <= $self->rate) 111 { #Select c' (c2) from the remaining cities of S'(child) 112 $c2=int( rand( $leng - $c ) + $c); 113 $c2+=2 if (($c2 == $c+1) && ($c2 < $leng -2) ); 114 115 } 116 else 117 { #Assign to c' (c2) the 'next' atom to the atom c in the second parent 118 for ($c2=0;$c2 < $leng; $c2++) 119 { last if ( $child->Atom($c) == $p2->Atom($c2) );} 120 $c2= ($c2+1) % $leng; 121 } 122 123# print "\nc= $c c2= $c2 lneg= $leng atom(c2)=".$child->Atom($c2)." atom(c+1)=".$child->Atom(($c+1) % $leng)."\n"; 124 #Check if finish 125 last if ( ($child->Atom($c2) == $child->Atom( ($c+1)% $leng) ) || ($c+1==$leng) ); 126 127 # Inverse the section from the next atom of atom c to the atom c' (c2) in S' (child) 128 for ($i=0;$i+$c <= ($c2/2) ; $i++) 129 { 130# print "\n\tCambio de Atom(".($i+$c+1).")=".$child->Atom($i+$c+1)." por Atom(".($c2-$i).")=".$child->Atom($c2-$i); 131 my $aux=$child->Atom($i+$c+1); 132 $child->Atom($i+$c+1,$child->Atom($c2-$i) ); 133 $child->Atom(($c2-$i),$aux); 134 } 135 136 $c=$c2; 137 }#End-while 138 139 return $child; #return Child 140} 141 142 143=head1 Copyright 144 145 This file is released under the GPL. See the LICENSE file included in this distribution, 146 or go to http://www.fsf.org/licenses/gpl.txt 147 148 CVS Info: $Date: 2009/07/24 08:46:59 $ 149 $Header: /media/Backup/Repos/opeal/opeal/Algorithm-Evolutionary/lib/Algorithm/Evolutionary/Op/Inverover.pm,v 3.0 2009/07/24 08:46:59 jmerelo Exp $ 150 $Author: jmerelo $ 151 $Revision: 3.0 $ 152 $Name $ 153 154=cut 155