PDF de programación - TALLER DE ALGORITMOS EVOLUTIVOS

TALLER DE ALGORITMOS EVOLUTIVOS


Introducción

Durante la última década los métodos de optimización han cobrado más importancia
debido, a que con ellos se pueden resolver ciertos problemas de ingeniería que sólo
pueden abordarse mediante aproximación en los computadores actuales.

Los paradigmas evolutivos actuales están inspirados en la teoría de la evolución de
Darwin e intentan emular en lo posible a la Naturaleza. De esta forma, los cromosomas
y los genes se suelen asociar de alguna forma a cadenas de bits o a vectores de números
reales. Por otra parte, diversas estrategias de selección imitan la selección natural.

Un buen tutorial sobre computación evolutiva se puede conseguir en
http://geneura.ugr.es/~jmerelo/ie/ags.htm

Anatomía de un algoritmo evolutivo

Los algoritmos evolutivos son métodos sistemáticos para la resolución de problemas de
búsqueda y optimización que aplican a estos los mismos métodos de la evolución
biológica: selección basada en la población, reproducción sexual y mutación.

Los algoritmos evolutivos son métodos de optimización, que tratan de hallar (xi,...,xn)
tales que F(xi,...,xn) sea máximo. En un algoritmo evolutivo, tras parametrizar el
problema en una serie de variables, (xi,...,xn) se codifican en un cromosoma. Todas los
operadores utilizados se aplicarán sobre estos cromosomas, o sobre poblaciones de
ellos. Hay que tener en cuenta que un algoritmo evolutivo es independiente del
problema, lo cual lo hace un algoritmo robusto, por ser útil para cualquier problema,
pero a la vez débil, pues no está especializado en ninguno.

Las soluciones codificadas en un cromosoma compiten para ver cuál constituye la mejor
solución (aunque no necesariamente la mejor de todas las soluciones posibles). Las
otras soluciones, ejercerán presión selectiva de forma que sólo los mejor adaptados
(aquellos que resuelvan mejor el problema) sobrevivan o leguen su material genético a
las siguientes generaciones, igual que en la evolución de las especies. La diversidad
genética se introduce mediante mutaciones y reproducción sexual.

En la Naturaleza lo único que hay que optimizar es la supervivencia, y eso significa a su
vez maximizar diversos factores y minimizar otros. Un algoritmo evolutivo, sin
embargo, se usará habitualmente para optimizar sólo una función, no diversas funciones
relacionadas entre sí simultáneamente. La optimización que busca diferentes objetivos
simultáneamente, denominada multimodal o multiobjetivo, también se suele abordar
con un algoritmo evolutivo especializado.

Por lo tanto, un algoritmo evolutivo consiste en lo siguiente: hallar de qué parámetros
depende el problema, codificarlos en un cromosoma, y aplicar los métodos de la
evolución: selección y reproducción sexual con intercambio de información y
alteraciones que generan diversidad. En las siguientes secciones se verán cada uno de
los aspectos de un algoritmo evolutivo.

Bucle general de un algoritmo evolutivo

Un algoritmo evolutivo sigue generalmente los siguientes pasos:


1. Generar una POBLACIÓN aleatoria de N individuos
2. Evaluar los individuos de la POBLACIÓN de acuerdo a la función de fitness
3. Repetir durante GENERACIONES iteraciones:

a. Aplicar el operador de selección para elegir S individuos de la

POBLACIÓN

descendencia

b. Aplicar los operadores genéticos a esos S individuos para generar la

c. Evaluar los nuevos individuos de acuerdo a la función de fitness
d. Reemplazar los peores individuos en POBLACIÓN por los individuos

recién creados


Esquemáticamente, podríamos verlo según la siguiente figura:







Tipos de individuo

Mientras que un algoritmo genético simple utiliza individuos que codifican las variables
(que se comentaban anteriormente) como cadenas binarias, otros tipos de algoritmos
evolutivos pueden utilizar estructuras complejas como vectores de números reales, redes
neuronales, grafos, árboles, etc.

En cada caso se debe elegir una representación que se adapte convenientemente al
problema.


Operadores genéticos

En la Evolución, una mutación es un suceso bastante poco común (sucede
aproximadamente una de cada mil replicaciones). En la mayoría de los casos las
mutaciones son letales, pero en promedio, contribuyen a la diversidad genética de la
especie. En un algoritmo genético tendrán el mismo papel, y la misma frecuencia (es
decir, muy baja).

Una vez establecida la frecuencia de mutación, por ejemplo, uno por mil, se examina
cada bit de cada cadena cuando se vaya a crear la nueva criatura a partir de sus padres.
Si un número generado aleatoriamente está por debajo de esa probabilidad, se cambiará
el bit (es decir, de 0 a 1 o de 1 a 0). Si no, se dejará como está.





No conviene abusar de la mutación. Es cierto que es un mecanismo generador de
diversidad, y, por tanto, la solución cuando un algoritmo genético está estancado, pero
también es cierto que reduce el algoritmo genético a una búsqueda aleatoria. Siempre es
más conveniente usar otros mecanismos de generación de diversidad, como aumentar el
tamaño de la población, o garantizar la aleatoriedad de la población inicial.

El cruce consiste en el intercambio de material genético entre dos cromosomas. Es el
principal operador genético, hasta el punto que se puede decir que no es un algoritmo
genético si no tiene cruce, y, sin embargo, puede serlo perfectamente sin mutación.
Para aplicar el cruce se escogen aleatoriamente dos miembros de la población, los dos
cromosomas se cortan por N puntos, y el material genético situado entre ellos se
intercambia. Lo más habitual es un cruce de un punto o de dos puntos





El cruce es el encargado de mezclar bloques buenos que se encuentren en los diversos
progenitores, y que serán los que den a los mismos una buena puntuación. La presión
selectiva se encarga de que sólo los buenos bloques se perpetúen, y poco a poco vayan
formando una buena solución.

Evaluación de las soluciones

Durante la evaluación, se decodifica el gen, convirtiéndose en una serie de parámetros
de un problema, se halla la solución del problema a partir de esos parámetros, y se le da
una puntuación a esa solución en función de lo cerca que esté de la mejor solución. A
esta puntuación se le llama fitness.

El fitness determina siempre los cromosomas que se van a reproducir, y aquellos que se
van a eliminar, pero hay varias formas de considerarlo para seleccionar la población de
la siguiente generación.

El material para el taller

La documentación sobre algoritmos evolutivos y Perl, el intérprete del lenguaje, el
paquete de la librería Algorithm::Evolutionary, y los ejemplos que veremos en este
taller se encuentran en http://geneura.ugr.es/~pedro/cursos/baeza/ae/


¿Qué es Algorithm::Evolutionary?

Es una librería de programación escrita en Perl para hacer computación evolutiva,
diseñada y desarrollada por Juan Julián Merelo ( http://opeal.sourceforge.net ).

Los principios del diseño son:

• Es fácil programar cualquier tipo de algoritmo evolutivo.
• Todas las representaciones para los cromosomas y todos los operadores son

posibles.

• Un dialecto XML denominado EvoSpec se puede usar como lenguaje para
descripción de algoritmos evolutivos y para la representación del estado del
algoritmo.


Muchos investigadores opinan que los distintos paradigmas de computación evolutiva
sólo difieren en cuanto a la representación y a los operadores de individuo y de
población. La librería de computación evolutiva que utilizaremos abstrae las
características de cada paradigma, permitiéndonos resolver problemas de optimización
de forma rápida y casi sin tener que escribir código.

En Algorithm::Evolutionary tanto los individuos, como los operadores o los algoritmos
son objetos, los cuales, se pueden combinar para crear algoritmos evolutivos a medida.


Instalación y configuración de Perl

En este taller utilizaremos Perl como lenguaje de programación.

Perl es un lenguaje de script, lo cual quiere decir que no hace falta generar un fichero
binario para poder ejecutar las instrucciones que hemos codificado usando este lenguaje.

Perl tiene características de muchos lenguajes de programación (buscando tomar lo
mejor de cada uno), pero al que más se parece en cuanto a sintáxis es al C.

El lenguaje se encuentra instalado en cualquier sistema Unix / Linux. Para instalarlo en
Windows, podemos descargar la versión de ActiveState (
http://www.activestate.com/store/languages/register.plex?id=ActivePerl ) o una
copia ya descargada de la página
http://geneura.ugr.es/~pedro/cursos/baeza/ae/ActivePerl-5.8.7.815-MSWin32-x86-211909.msi

La instalación se realiza de forma automática, asociando los ficheros con extensión .PL
al intérprete de Perl.

El aspecto del programa en Perl más sencillo es el siguiente (en Linux):

#!/bin/perl
print "hola \n";

si estamos trabajando bajo Windows, debemos indicarle en la primera línea el PATH
absoluto hasta el programa PERL.EXE
#!c:/perl/bin/perl.exe
print "hola \n";

Como vemos en la segunda línea (donde se imprime información), hay que terminar
cada sentencia de programa con un punto y coma (;).
Los comentarios en Perl se introducen poniendo al principio de la línea que será
comentada un símbolo #

La ejecución del programa la haremos desde una ventana MSDOS (ejecutar el programa
cmd), de la siguiente forma:
C:\> perl.exe ejemplo.pl

Con Perl se puede programar casi todo (hay librerías -módulos- para casi cualquier cosa
que se nos ocurra), pero hay aplicaciones que requieren mucha rapidez en las cuales es
mejor utilizar programas compilados (la ejecución a través del intérprete introduce
retardos).

Para ampliar conocimientos sobre el lenguaje, podemos visitar la siguiente página en la
que se introduce el lenguaje http://geneura.ugr.es/~pedro/cursos/perl/


Instalación