| 1 | use strict; | ||
| 2 | use warnings; | ||
| 3 | |||
| 4 | use lib qw( ../../../../lib ); # mainly to avoid syntax errors when saving | ||
| 5 | |||
| 6 | =head1 NAME | ||
| 7 | |||
| 8 | Algorithm::Evolutionary::Op::CX (Cycle crossover) - 2-point crossover operator; Builds offspring in such a way | ||
| 9 | that each gene comes from one of the parents. Preserves the absolute position of the elements | ||
| 10 | in the parent sequence | ||
| 11 | |||
| 12 | =head1 SYNOPSIS | ||
| 13 | |||
| 14 | my $op4 = new Algorithm::Evolutionary::Op::CX 3; | ||
| 15 | |||
| 16 | my $indi = new Algorithm::Evolutionary::Individual::Vector 10; | ||
| 17 | my $indi2 = $indi->clone(); | ||
| 18 | my $indi3 = $indi->clone(); | ||
| 19 | $op3->apply( $indi2, $indi3 ); | ||
| 20 | |||
| 21 | =head1 Base Class | ||
| 22 | |||
| 23 | L<Algorithm::Evolutionary::Op::Base|Algorithm::Evolutionary::Op::Base> | ||
| 24 | |||
| 25 | =head1 DESCRIPTION | ||
| 26 | |||
| 27 | Cycle Crossover operator for a GA. It is applied to chromosomes that are | ||
| 28 | a permutation of each other; even as the class it applies to is | ||
| 29 | L<Algorithm::Evolutionary::Individual::Vector>, it will issue lots of | ||
| 30 | "La jodimos!" messages if the parents do not fulfill this condition. | ||
| 31 | |||
| 32 | Some information on this operator can be obtained from | ||
| 33 | L<this | ||
| 34 | evolutionary computation tutorial|http://www.cs.bham.ac.uk/~rmp/slide_book/node4.html#SECTION00444300000000000000> | ||
| 35 | |||
| 36 | =head1 METHODS | ||
| 37 | |||
| 38 | =cut | ||
| 39 | |||
| 40 | package Algorithm::Evolutionary::Op::CX; | ||
| 41 | |||
| 42 | our $VERSION = '3.2'; | ||
| 43 | |||
| 44 | use Carp; | ||
| 45 | |||
| 46 | use base 'Algorithm::Evolutionary::Op::Base'; | ||
| 47 | |||
| 48 | #Class-wide constants | ||
| 49 | our $APPLIESTO = 'Algorithm::Evolutionary::Individual::Vector'; | ||
| 50 | our $ARITY = 2; | ||
| 51 | |||
| 52 | =head2 new | ||
| 53 | |||
| 54 | Creates a new Algorithm::Evolutionary::Op::CX operator. | ||
| 55 | |||
| 56 | =cut | ||
| 57 | |||
| 58 | sub new { | ||
| 59 | my $class = shift; | ||
| 60 | my $hash = { numPoints => shift || 2 }; | ||
| 61 | my $rate = shift || 1; | ||
| 62 | my $self = Algorithm::Evolutionary::Op::Base::new( __PACKAGE__, $rate, $hash ); | ||
| 63 | return $self; | ||
| 64 | } | ||
| 65 | |||
| 66 | =head2 create | ||
| 67 | |||
| 68 | Creates a new Algorithm::Evolutionary::Op::CX operator. But this is just to have a non-empty chromosome | ||
| 69 | |||
| 70 | =cut | ||
| 71 | |||
| 72 | sub create { | ||
| 73 | my $class = shift; | ||
| 74 | my $self; | ||
| 75 | $self->{_numPoints} = shift || 2; | ||
| 76 | bless $self, $class; | ||
| 77 | return $self; | ||
| 78 | } | ||
| 79 | |||
| 80 | =head2 apply | ||
| 81 | |||
| 82 | Applies Algorithm::Evolutionary::Op::CX operator to a "Chromosome", a bitstring, really. Can be | ||
| 83 | applied only to I<victims> with the C<_bitstring> instance variable; but | ||
| 84 | it checks before application that both operands are of type | ||
| 85 | L<Individual::Vector|Algorithm::Evolutionary::Individual::Vector>. | ||
| 86 | |||
| 87 | =cut | ||
| 88 | |||
| 89 | sub 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(); #Child | ||
| 94 | my $i; #Iterator | ||
| 95 | my $j; #Iterator | ||
| 96 | my $changed; | ||
| 97 | |||
| 98 | #Check parents type and size | ||
| 99 | croak "Incorrect type ".(ref $p1) if !$self->check($p1); | ||
| 100 | croak "Incorrect type ".(ref $p2) if !$self->check($p2); | ||
| 101 | croak "Algorithm::Evolutionary::Op::CX Error: Parents don't have the same size " if ($p1->length() != $p2->length() ); | ||
| 102 | |||
| 103 | my $leng=$p1->length(); #Chrom length | ||
| 104 | my $no='x';#-( $leng );#Uninitialized gene mark | ||
| 105 | |||
| 106 | #Init child | ||
| 107 | for ($i=0;$i < $leng; $i++) | ||
| 108 | { $child->Atom($i, $no);} | ||
| 109 | my %visto; | ||
| 110 | map( $visto{$_}++,@{$p1->{_array}} ); | ||
| 111 | #Build child | ||
| 112 | # print "CX \$leng = $leng\n"; | ||
| 113 | $changed=$i=0; | ||
| 114 | while ($changed < $leng ) { | ||
| 115 | my $found=0; | ||
| 116 | #Looking for the next element in cycle | ||
| 117 | for ($j=0; $j < $leng ; $j++) { | ||
| 118 | if ( $p1->Atom($j) == $p2->Atom($i)) { | ||
| 119 | $found=$j; | ||
| 120 | last; | ||
| 121 | } | ||
| 122 | } | ||
| 123 | #Look if the next element in cycle was found | ||
| 124 | if ($found) { | ||
| 125 | $child->Atom($found, $p1->Atom($found)); | ||
| 126 | # print "Found $found valor ", $child->Atom($found), "\n"; | ||
| 127 | $i=$found; | ||
| 128 | $changed++; | ||
| 129 | } | ||
| 130 | else { #End of the cycle, get the genes from the second parent | ||
| 131 | $child->Atom(0, $p1->Atom(0) ); $changed++; | ||
| 132 | for ($i=1;( $i < $leng ) && ( $changed < $leng ) ; $i++) { | ||
| 133 | if ($child->Atom($i) eq $no ) { | ||
| 134 | # print "Cambiando $i valor ", $p2->Atom($i), "\n"; | ||
| 135 | $child->Atom($i,$p2->Atom($i)); | ||
| 136 | $changed++; | ||
| 137 | } | ||
| 138 | } | ||
| 139 | } | ||
| 140 | }#End-while | ||
| 141 | map( $visto{$_}++,@{$child->{_array}} ); | ||
| 142 | for (keys %visto) { | ||
| 143 | if ($visto{$_} ne 2 ) { | ||
| 144 | print "La jodimos!\n"; | ||
| 145 | } | ||
| 146 | #print "$_ visto $visto{$_}\n"; | ||
| 147 | }; | ||
| 148 | for ( $i = 0; $i < $leng; $i ++ ) { | ||
| 149 | if ($child->Atom($i) eq $no ){ | ||
| 150 | print "Messed up!\n"; | ||
| 151 | } | ||
| 152 | } | ||
| 153 | return $child; #return Child, explicative comment if I've ever seen one | ||
| 154 | } | ||
| 155 | |||
| 156 | =head1 Copyright | ||
| 157 | |||
| 158 | This file is released under the GPL. See the LICENSE file included in this distribution, | ||
| 159 | or go to http://www.fsf.org/licenses/gpl.txt | ||
| 160 | |||
| 161 | =cut |