« lib/Algorithm/Evolutionary/Individual/Tree.pm
↑ Summary
lib/Algorithm/Evolutionary/Individual/Vector.pm »
| 1 | use strict; # -*- cperl -*- | ||
| 2 | use warnings; | ||
| 3 | |||
| 4 | use lib qw( ../../../../lib ); | ||
| 5 | |||
| 6 | =head1 NAME | ||
| 7 | |||
| 8 | Algorithm::Evolutionary::Fitness::Knapsack - Fitness function for the knapsack problem | ||
| 9 | |||
| 10 | =head1 SYNOPSIS | ||
| 11 | |||
| 12 | my $n_max=100; #Max. number of elements to choose | ||
| 13 | my $capacity=286; #Max. Capacity of the knapsack | ||
| 14 | my $rho=5.0625; #Penalty coeficient | ||
| 15 | my @profits = qw( 1..100 ); | ||
| 16 | my @weights = qw( 2.. 101 ); | ||
| 17 | |||
| 18 | my $knapsack = Algorithm::Evolutionary::Fitness::Knapsack->new( $n_max, $capacity, $rho, \@profits, \@weights ); | ||
| 19 | |||
| 20 | =head1 DESCRIPTION | ||
| 21 | |||
| 22 | Knapsack function with penalties applied in a particular way. | ||
| 23 | |||
| 24 | =head1 METHODS | ||
| 25 | |||
| 26 | =cut | ||
| 27 | |||
| 28 | package Algorithm::Evolutionary::Fitness::Knapsack; | ||
| 29 | |||
| 30 | our ($VERSION) = ( '$Revision: 3.1 $ ' =~ / (\d+\.\d+)/ ) ; | ||
| 31 | |||
| 32 | use Carp qw( croak ); | ||
| 33 | use base qw(Algorithm::Evolutionary::Fitness::String); | ||
| 34 | |||
| 35 | =head2 new | ||
| 36 | |||
| 37 | Creates a new instance of the problem, with the said number of bits and peaks | ||
| 38 | |||
| 39 | =cut | ||
| 40 | |||
| 41 | sub new { | ||
| 42 | my $class = shift; | ||
| 43 | my ( $n_max, $capacity, $rho, $profits_ref, $weights_ref ) = @_; | ||
| 44 | |||
| 45 | if ( ((scalar @$profits_ref) != $n_max ) || | ||
| 46 | ((scalar @$weights_ref) != $n_max ) ) { | ||
| 47 | croak "Wrong number of profits"; | ||
| 48 | } | ||
| 49 | |||
| 50 | if ( (scalar @$profits_ref) != ( scalar @$weights_ref ) ) { | ||
| 51 | croak "Profits and weights differ"; | ||
| 52 | } | ||
| 53 | |||
| 54 | #Instantiate superclass | ||
| 55 | my $self = $class->SUPER::new(); | ||
| 56 | |||
| 57 | $self->{'capacity'} = $capacity; | ||
| 58 | $self->{ 'rho' } = $rho; | ||
| 59 | $self->{ 'profits'} = $profits_ref; | ||
| 60 | $self->{ 'weights'} = $weights_ref; | ||
| 61 | |||
| 62 | $self->initialize(); | ||
| 63 | return $self; | ||
| 64 | } | ||
| 65 | |||
| 66 | sub _really_apply { | ||
| 67 | my $self = shift; | ||
| 68 | return $self->knapsack( @_ ); | ||
| 69 | } | ||
| 70 | |||
| 71 | =head2 knapsack | ||
| 72 | |||
| 73 | Applies the knapsack problem to the string, using a penalty function | ||
| 74 | |||
| 75 | =cut | ||
| 76 | |||
| 77 | sub knapsack { | ||
| 78 | my $self = shift; | ||
| 79 | my $string = shift; | ||
| 80 | |||
| 81 | my $cache = $self->{'_cache'}; | ||
| 82 | if ( $cache->{$string} ) { | ||
| 83 | return $cache->{$string}; | ||
| 84 | } | ||
| 85 | my $profit=0.0; | ||
| 86 | my $weight=0.0; | ||
| 87 | |||
| 88 | my @profits = @{$self->{'profits'}}; | ||
| 89 | my @weights = @{$self->{'weights'}}; | ||
| 90 | |||
| 91 | for (my $i=0 ; $i < length($string); $i++) { #Compute weight | ||
| 92 | my $this_bit=substr ($string, $i, 1); | ||
| 93 | |||
| 94 | if ($this_bit == 1) { | ||
| 95 | $profit += $profits[$i]; | ||
| 96 | $weight += $weights[$i]; | ||
| 97 | } | ||
| 98 | } | ||
| 99 | |||
| 100 | if ($weight > $self->{'capacity'}) { # Apply penalty | ||
| 101 | my $penalty = $self->{'rho'} * ($weight - $self->{'capacity'}); | ||
| 102 | $profit = $profit - ( $penalty + log(1.0 + $penalty) / log(2.0) ); | ||
| 103 | } | ||
| 104 | |||
| 105 | #Y devolvemos la ganancia calculada | ||
| 106 | $cache->{$string} = $profit; | ||
| 107 | return $profit; | ||
| 108 | } | ||
| 109 | |||
| 110 | |||
| 111 | =head1 Copyright | ||
| 112 | |||
| 113 | This file is released under the GPL. See the LICENSE file included in this distribution, | ||
| 114 | or go to http://www.fsf.org/licenses/gpl.txt | ||
| 115 | |||
| 116 | CVS Info: $Date: 2010/09/24 08:39:07 $ | ||
| 117 | $Header: /media/Backup/Repos/opeal/opeal/Algorithm-Evolutionary/lib/Algorithm/Evolutionary/Fitness/Knapsack.pm,v 3.1 2010/09/24 08:39:07 jmerelo Exp $ | ||
| 118 | $Author: jmerelo $ | ||
| 119 | $Revision: 3.1 $ | ||
| 120 | $Name $ | ||
| 121 | |||
| 122 | =cut | ||
| 123 | |||
| 124 | "What???"; |