Sexto Ejercicio

En este ejercicio utilizaremos el paquete de perl Algorithm::Evolutionary para implementar un algoritmo genético para minimizar la función de Griewank. Usaremos codificación binaria para los cromosomas.

use Algorithm::Evolutionary::Individual::BitString;
use Algorithm::Evolutionary::Op::Easy;
use Algorithm::Evolutionary::Op::Mutation;
use Algorithm::Evolutionary::Op::Crossover;

# Definición de la función de Griewank:
# -------------------------------------
# f(x) = 1/4000*sum(xi^2) - prod(cos(xi)/sqrt(i)) + 1
#
# -600 <= x(i) <= 600
# i = 1..n (n = número de dimensiones del problema)
#
# Mínimo global: f(x) = 0 se alcanza con x = (0, ..., 0)
#

# Parámetros del algoritmo

# Tamaño de la población
my $popSize=100;

# Número de dimensiones del problema (en cada cromosoma
# se codificarán este número de reales)
my $dimensiones = 3;

# Número de bits con los que se codificará cada dimensión
# Cada cromosoma: ($dimensiones*$numBitsPorDimension)bits
my $numBitsPorDimension=10;

# Número de generaciones
my $numGens = 100;

# Función de Griewank:
my $funcionGriewank = sub {
#Cogemos el individuo a evaluar
my $chrom = shift;
my $str = $chrom->Chrom();
#Extraemos los números reales de la cadena binaria
my @vector;
my $pos=0;
while($pos<length($str)){
 my $x = eval("0b".substr($str,$pos,$numBitsPorDimension));
 @vector = (@vector,$x);
 $pos += $numBitsPorDimension;
}
#Los normalizamos y los pasamos al rango [-600,600]
my $max=(2**$numBitsPorDimension )-1;
for(my $i=0;$i<=$#vector;$i++){
 $vector[$i]=(($vector[$i]/$max)*1200)-600;
}
# Calculamos la función
my $suma = 0;
my $prod = 1;
for (my $i=0;$i<=$#vector;$i++){
 $suma += $vector[$i]**2;
 $prod *= cos($vector[$i]/sqrt($i+1));
}
$suma = $suma/4000;
my $fitness = $suma-$prod+1;

return $fitness;
};

# Muestra los números reales que componen un cromosoma
sub componentesSolucion{
#Cogemos el individuo a evaluar
my $chrom = shift;
my $str = $chrom->Chrom();
my $resultado = "";
#Extraemos los números reales de la cadena binaria
my @vector;
my $pos=0;
while($pos<length($str)){
 my $x = eval("0b".substr($str,$pos,$numBitsPorDimension));
 @vector = (@vector,$x);
 $pos += $numBitsPorDimension;
}
#Los normalizamos y los pasamos al rango [-600,600]
my $max=(2**$numBitsPorDimension )-1;
for(my $i=0;$i<=$#vector;$i++){
 $vector[$i]=(($vector[$i]/$max)*1200)-600;
 $resultado = "$resultado$vector[$i], ";
}

print substr($resultado, 0, length($resultado)-2);
};

# Creación de la población inicial
my @pop;
for ( 0..$popSize ) {
my $indi = Algorithm::Evolutionary::Individual::BitString->
 new( $dimensiones*$numBitsPorDimension ) ;
push( @pop, $indi );
}

# Inicializamos el fitnes de la población inicial
for ( @pop ) {
if ( !defined $_->Fitness() ) {
 my $fitness = $funcionGriewank->($_);
 $_->Fitness( $fitness );
}
}

# Definición de los operadores genéticos
my $mutacion = Algorithm::Evolutionary::Op::Mutation->new(0.1);
my $cruce = Algorithm::Evolutionary::Op::Crossover->new(2);

# Elección del algoritmo
my $generation = Algorithm::Evolutionary::Op::Easy->
new( $funcionGriewank , 0.2 , [$mutacion, $cruce] ) ;

# Bucle general del algoritmo
do {
$generation->apply( \@pop );
print "$numGens : ", $pop[0]->asString(), "\n" ;
$numGens -- ;
} while( $numGens > 0 );

# Mejor individuo encontrado
print "\nLa mejor solución encontrada es:\n\t ";
print $pop[0]->asString() ;
print "\nComponentes de la mejor solución: \n\t ";
componentesSolucion($pop[0]);