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

Imágen de pdf Sistemas complejos. Algoritmos evolutivos y bioinspirados

Sistemas complejos. Algoritmos evolutivos y bioinspiradosgráfica de visualizaciones

Actualizado el 21 de Marzo del 2018 (Publicado el 26 de Septiembre del 2017)
505 visualizaciones desde el 26 de Septiembre del 2017
287,7 KB
13 paginas
Creado hace 15a (09/03/2006)
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
  • Links de descarga
http://lwp-l.com/pdf7046

Comentarios de: Sistemas complejos. Algoritmos evolutivos y bioinspirados (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad