PDF de programación - Sistemas complejos. Algoritmos evolutivos y bioinspirados

Sistemas complejos. Algoritmos
evolutivos y bioinspirados

Taller de herramientas para sistemas
complejos: algoritmos evolutivos

Pedro A. Castillo Valdivieso
Baeza, 13 de marzo de 2006

Contenidos del taller

(cid:137) Introducción
(cid:137) Estructura de un algoritmo evolutivo
(cid:137) Material para este taller
(cid:137) ¿Qué es Algorithm::Evolutionary?
(cid:137) Uso de individuos binarios
(cid:137) Uso de un operador de mutación
(cid:137) Uso de un operador de cruce
(cid:137) Ejemplo. Algoritmo genético simple
(cid:137) Ejemplo. Algoritmo evolutivo

Taller de herramientas para sistemas complejos: algoritmos evolutivos

2

1

Introducción

Los algoritmos evolutivos están inspirados en la

evolución natural

Son métodos para resolución de problemas que aplican

los métodos de la evolución biológica:

• selección basada en población
• reproducción sexual
• mutación

Un tutorial sobre computación evolutiva:

http://geneura.ugr.es/~jmerelo/ie/ags.htm

Taller de herramientas para sistemas complejos: algoritmos evolutivos

3

Introducción

Los AE son métodos de optimización

•
•
•

Parametrizar el problema en una serie de variables
Codificar las variables en un cromosoma (solución)
Aplicar operadores de variación a estas soluciones

Las soluciones compiten, y sólo las mejores (las que

resuelven mejor el problema) sobreviven

El AE se usará normalmente para optimizar sólo una

función (frente a los algoritmos multiobjetivo)

Taller de herramientas para sistemas complejos: algoritmos evolutivos

4

2

Bucle general de un AE

generar

población inicial

y evaluarla

selección

reproducción

(cruce y mutación)

no

si

¿criterio de
optimización
alcanzado?

evaluación de
los nuevos
individuos

reemplazo

Devolver el

mejor individuo

Taller de herramientas para sistemas complejos: algoritmos evolutivos

5

Elementos del AE: individuos

Las soluciones candidatas codifican las variables del problema.

Hay que elegir la representación más adecuada al problema.

•
•
•
•
•
•

Cadenas binarias
Vectores de números reales
Redes neuronales artificiales
Grafos
Árboles de decisión
Etc, etc.

Taller de herramientas para sistemas complejos: algoritmos evolutivos

6

3

Elementos del AE: operadores genéticos

Generan nuevos individuos a partir de los que ya están

en la población

MUTACIÓN:
Modifica sólo unos genes del cromosoma.
Contribuye a la diversidad de la población

0 1 0 0 1 1

0 1 1 0 0 1

CRUCE:
Intercambio de material genético entre cromosomas.
Tomar dos padres, cortarlos por N puntos, e intercambiar genes

0 1 0 0 1 1
1 0 1 0 0 1

1 0
0 1

0 0 1 1
1 0 0 1

Taller de herramientas para sistemas complejos: algoritmos evolutivos

7

Elementos del AE: evaluación (fitness)

Decodificar el cromosoma para extraer las variables del

problema

Evaluar el problema con esas variables.

Obtener una puntuación (fitness).

El valor de fitness determina qué individuos se van a

reproducir y cuáles se eliminarán

Taller de herramientas para sistemas complejos: algoritmos evolutivos

8

4

•

•

•

•

Material para este taller

Documentación

Intérprete de lenguaje Perl

Paquete de la librería Algorithm::Evolutionary

Ejemplos utilizados

http://geneura.ugr.es/~pedro/cursos/baeza/ae/

Taller de herramientas para sistemas complejos: algoritmos evolutivos

9

¿Qué es Algorithm::Evolutionary?

Librería de programación para hacer computación evolutiva

Diseñada y desarrollada por Juan Julián Merelo

http://opeal.sourceforge.net

•

•
•

Abstrae las características de los paradigmas evolutivos,
permitiendo resolver problemas de forma rápida y casi sin
escribir código
Es fácil programar cualquier tipo de algoritmo evolutivo
Están disponibles todas las representaciones para los
individuos y todos los operadores genéticos

Taller de herramientas para sistemas complejos: algoritmos evolutivos

10

5

Instalación y configuración de Perl

Perl es un lenguaje interpretado
En cuanto a sintáxis se parece al lenguaje C

En Unix / Linux se encuentra instalado por defecto.
Para instalar una versión para Windows, podemos descargar:

http://www.activestate.com

Para ampliar conocimientos sobre el lenguaje (características,

estructuras de datos y de control, etc) podemos descargar
un tutorial de:

http://geneura.ugr.es/~pedro/cursos/perl/

Taller de herramientas para sistemas complejos: algoritmos evolutivos

11

Creación y ejecución de programas Perl

El aspecto de un programa muy sencillo es el siguiente:

#!c:/perl/bin/perl.exe

print ‘’ hola mundo ! ‘’ ;

Para ejecutarlo, tenemos que abrir una ventana de

comandos para llamar al intérprete de Perl

C:\> perl.exe

miprograma.pl

Taller de herramientas para sistemas complejos: algoritmos evolutivos

12

6

Instalación de la librería

C:\> perl.exe -MCPAN -e shell

Taller de herramientas para sistemas complejos: algoritmos evolutivos

13

Ha terminado de
instalar la librería.

Todo está listo

¿Cómo usar la librería?

Usar un editor de textos para crear el programa Perl

A partir de un ejemplo que funcione, programar nuestra

función de fitness, elegir el tipo de dato (individuo) que
se ajuste al problema, y usar los operadores genéticos
adaptados a esa representación

Ejecutar en una ventana de comandos

C:\> perl.exe miprograma.pl

Taller de herramientas para sistemas complejos: algoritmos evolutivos

14

7

Definición de individuos binarios

Un algoritmo genético clásico usa individuos binarios.

#!c:/perl/bin/perl.exe

use Algorithm::Evolutionary::Individual::BitString;

my $indiv =

Algorithm::Evolutionary::Individual::BitString->new (10);

print $indiv->Atom( 7 ) ;
print $indiv->asString() ;

Taller de herramientas para sistemas complejos: algoritmos evolutivos

15

Uso de un operador de mutación

Debemos incluir el módulo “Mutation”.

#!c:/perl/bin/perl.exe

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

my $mutar = Algorithm::Evolutionary::Op::Mutation->new( 0.1 );
my $indiv =

Algorithm::Evolutionary::Individual::BitString->new( 8 );

my $mutado = $mutar->apply( $indiv );

print $indiv->asString() ;
print $mutado->asString() ;

Taller de herramientas para sistemas complejos: algoritmos evolutivos

16

8

Uso de un operador de cruce

Debemos incluir el módulo “Crossover”.

#!c:/perl/bin/perl.exe

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

my $cruce = Algorithm::Evolutionary::Op::Crossover->new( 1 );
my $i1 = Algorithm::Evolutionary:: Individual::BitString->new (8);
my $i2 = Algorithm::Evolutionary:: Individual::BitString->new (8);

my $hijo1 = $cruce->apply( $i1, $i2 );
my $hijo2 = $cruce->apply( $i2, $i1);

print $i1->asString() ;
print $i2->asString() ;
print $hijo1->asString() ;
print $hijo2->asString() ;

Taller de herramientas para sistemas complejos: algoritmos evolutivos

17

Resolver un problema con un algoritmo genético

máximo en (0,0)

con f(0,0) = 1

Taller de herramientas para sistemas complejos: algoritmos evolutivos

18

9

Resolver el problema con un algoritmo genético

Debemos seleccionar el tipo de individuo, los operadores y

programar la función de fitness:

•

Cadenas binarias

Individual::BitString

• Operadores genéticos adaptados a la codificación binaria

Op::Mutation
Op::Crossover

•

La función de evaluación es la función a optimizar

Taller de herramientas para sistemas complejos: algoritmos evolutivos

19

Elementos del algoritmo genético

Los módulos necesarios para este ejemplo
use Algorithm::Evolutionary::Individual::BitString;
use Algorithm::Evolutionary::Op::Easy;
use Algorithm::Evolutionary::Op::Mutation;
use Algorithm::Evolutionary::Op::Crossover;

La población de soluciones

my @pop;
my $i;
for ( $i=0 ; $i < $popSize ; $i++ ) {
my $indi = Algorithm::Evolutionary::

Individual::BitString->new( $numBits ) ;

$pop[$i] = $indi ;

}

Taller de herramientas para sistemas complejos: algoritmos evolutivos

20

10

Elementos del algoritmo genético

La función de evaluación (fitness)
my $funcionMarea = sub {

my $chrom = shift;
my $str = $chrom->Chrom();
my $fitness = 1;
my $l2=length($str)/2;
my $x=eval("0b".substr ($str, 0, $l2));
my $y=eval("0b".substr ($str, $l2));
my $max=(2 ** ($l2) )-1;
$x=$x/$max;
$y=$y/$max;
my $sqrt=sqrt( ($x*$x) + ($y*$y) );
if($sqrt !=0 ){ $fitness = sin( $sqrt ) / $sqrt; }
return $fitness;

# los pasamos al rango [0,1]

};

Taller de herramientas para sistemas complejos: algoritmos evolutivos

21

Elementos del algoritmo genético

El bucle del algoritmo

my $generation = Algorithm::Evolutionary::Op::Easy->new(

$funcionMarea , 0.2 , [$m, $c] ) ;

do {

$generation->apply( \@pop );
$numGens -- ;

} while( $numGens > 0 );

Una vez terminado, mostramos la mejor solución

print "La mejor solución encontrada es: ";
print $pop[0]->asString() ;

Taller de herramientas para sistemas complejos: algoritmos evolutivos

22

11

Resolver el problema con un algoritmo evolutivo

Resolver la función marea utilizando codificación real

Vectores de números reales

Individual::Vector

Operadores genéticos adaptados a la codificación real

Op::GausianMutation
Op::VectorCrossover

El resto del algoritmo queda igual que el estudiado antes

Taller de herramientas para sistemas complejos: algoritmos evolutivos

23

Elementos del AE…

Los módulos necesarios para este ejemplo
use Algorithm::Evolutionary::Individual::Vector;
use Algorithm::Evolutionary::Op::Easy;
use Algorithm::Evolutionary::Op::GaussianMutation;
use Algorithm::Evolutionary::Op::VectorCrossover;

La función de fitness (marea)

my $funcionMarea = sub {

my $indi = shift;
my ( $x, $y ) = @{$indi->{_array}};
my $sqrt = sqrt( $x*$x+$y*$y);
if( !$sqrt ){ return 1; }
return sin( $sqrt )/$sqrt;

};

Taller de herramientas para sistemas complejos: algoritmos evolutivos

24

12

Elementos del AE…

Los operadores genéticos
my $m =

Algorithm::Evolutionary::Op::GaussianMutation->new(0, 0.1);

my $c =

Algorithm::Evolutio