blib/lib/Algorithm/Evolutionary/Fitness/Knapsack.pm untested

filter: Statementstmt 0.0% 0 / 60 Branchbran 0.0% 0 / 10 Conditioncond 0.0% 0 / 3 MC/DCmcdc 0.0% 0 / 2 Subroutinesub 0.0% 0 / 8 Podpod 0.0% 0 / 3 totaltotal 0.0% 0 / 86 CC 6 SCAR 22.9
CC
6
Cov
0%
knapsack
20.0
new
12.0
_really_apply
2.0
CRAP 9.8
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???";