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