PDF de programación - Algoritmos evolutivos en Perl

Algoritmos evolutivos en Perl

Juan J. Merelo Guervós

Copyright (C) 2002 J. J. Merelo Guervós. Permitida la redistribución ilimitada de copias literales y la traducción del
texto a otros idiomas, siempre y cuando se mantenga esta autorización y la nota de copyright.
Historial de revisiones
Revisión 1.1
Versión revisada para el congreso
Revisión 1.0
Submitted.
Revisión 0

26 Septiembre 2002

30 Julio 2002

26 de julio de 2002

En este artículo se describe el módulo Algorithm::Evolutionary, un módulo en Perl para algoritmos evolutivos,
diseñado con el objeto de que fuera fácilmente integrable con XML. Esto ha forzado a una serie de decisiones de
diseño, que se detallan en el artículo.

Tabla de contenidos

1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2. Estado del arte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3. Descripción de la biblioteca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4. Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5. Conclusiones, discusión y trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1. Introducción

En una aplicación Open Source, aparte del hecho de que exista en sí, se debe, desde nuestro punto de vista, probar tres
cosas: su necesidad, su calidad y su aplicabilidad.

En el mundo Open Source, no se trata simplemente de escribir una aplicación porque sí, sino de probar que realmente
es un producto para el cual existe un hueco; si no, se cae en el error de crear sin ton ni son, sin que se produzca
realmente un beneficio a la comunidad. En la sección Sección 1 presentaremos el panorama de las bibliotecas de
algoritmos evolutivos, mostrando que, hasta el momento, no se había hecho una biblioteca versátil para algoritmos
evolutivos en Perl

Por otro lado, habrá que probar que realmente lo diseñado corresponde a la necesidad existente, es decir, que cubre el
nicho que se le ha sido asignado, y que lo hace con un mínimo de dignidad. También a qué decisiones de diseño han

1

llevado estas especificaciones, y qué ventajas ha tenido el usar las herramientas que se han usado. Esto se describirá
en la sección Sección 2

Por último, ninguna herramienta, por muy Open Source que sea, sirve de nada si no ha sido usada en aplica-
ciones reales; en la sección Sección 3 describimos una serie de aplicaciones que han usado el módulo Algo-
rithm::Evolutionary .

Finalmente, termSección 4inaremos con una sección () en la que expondremos las líneas futuras de trabajo en esta
biblioteca.

2. Estado del arte

Los algoritmos evolutivos son métodos de optimización estocásticos basados en someter a un grupo de estructuras de
datos que representan soluciones a un problema determinado a una serie de operadores inspirados en la teoría de la
evolución de Darwin: mutaciones ciegas, recombinación, y selección de los más adecuados. Un algoritmo evolutivo
procedería de la forma siguiente:

1. Inicializar una población de n individuos aleatoriamente.

2. Evaluar los individuos, asignándoles un fitness, que representa su adecuación como soluciones del problema.

3. Escoger una parte de la población, que servirán como progenitores de la siguiente generación.

4. Someter a los progenitores a operadores de variación unarios (individuo por individuo) o n-arios (que usan varios

individuos, produciendo a su vez uno o varios individuos).

5. Insertar en la población estos nuevos individuos, sustituyendo, siguiendo algún criterio, una parte de la población.

6. Vuelta al segundo paso.

Actualmente, se considera que todos los algoritmos evolutivos forman parte de una misma familia, pero hay diferentes
tribus que difieren en cosas como las estructuras de datos que usan para representación, operadores de variación, y
método de selección, tal como se ve en la tabla siguiente. En realidad, es difícil encontrar un algoritmo de los anteriores
en estado puro, aunque cada cual designa su algoritmo con la tribu a la que más se parece:

2

Tabla 1. Tribus de algoritmos evolutivos

Representación
del problema
Cadena binaria Mutación y cros-

Operadores de va-
riación

(Gold-

sover

Métodos de selec-
ción
Selección de rue-
da de ruleta (a ve-
ces con elitismo)
tipos
Diferentes
de
selección:
lambda,mu;
lambda+mu...
Diversos tipos de
selección
Diversos tipos de
selección

Algoritmo

Algoritmos
genéticos
berg)
Estrategias
de
ción
berg/Schwefel)
Programación
evolutiva (Fogel)
Programación
genética (Koza)

Evolu-
(Rechen-

Vector de reales
+
desviaciones
estándar

Mutación
gaus-
siana y crossover
aritmético (dife-
rentes tipos)

Números reales Mutación

Expresiones-S de
LISP representa-
das habitualmente
como árboles

Crossover,
de mutación

algo

Hasta julio de 2002, había pocos módulos Perl publicados suficientemente flexible para implementar la gama completa
de algoritmos evolutivos; la mayor parte de los esfuerzos han sido destinados a implementar programación genética en
Perl. El primer trabajo publicado sobre el tema es aparentemente el de Baldi y otros [baldi00], aunque el código en sí
no fue publicado, y no podemos aventurar ninguna hipótesis sobre sus características. En todo caso, posteriormente se
han publicado una serie de artículos que mencionan una implementación de Perl de un algoritmo evolutivo: Kunken
[glotbot01] describe una aplicación en la que hace evolucionar palabras que parecen escritas en inglés, a base de tratar
de generarlas con la misma frecuencia que en inglés. Esa misma aplicación es también mencionada por Zlatanov en
[zlatanov01], en donde implementa un sistema de programación genética para realizar la misma tarea.

Quizás el primer artículo que describe programación genética en Perl fue escrito por Murray y Williams [murray99-
ga], que, a pesar de su título, describen un sistema de programación genética, similar al mencionado en un artículo del
sitio Perl Monks ([gumpu01]). Otro módulo publicado en 2001 [ag01] implementa un algoritmo genético canónico,
sin muchas posibilidades de ampliación ni de adaptación.

Ninguno de los sistemas mencionados anteriormente usan plenamenta las capacidades del Perl para diseñar
una biblioteca orientada a objetos, adaptable y fácil de ampliar,
tal como se ha pretendido que sea Algo-
rithm::Evolutionary. El producto que más se acerca ha aparecido durante el año 2002, y se denomina myBe-
asties [myBeasties]. Este módulo implementa un mecanismo general de evolución de genotipos, y de asignación de
fenotipos a genotipos, así como un método para serialización usando ficheros de texto; los algoritmos (tipos de cromo-
somas y operadores que se le van a aplicar) se pueden describir mediante un fichero de texto. Aparentemente, trabaja
simplemente con cromosomas (que llama blobs) lineales, y, además, los operadores están asociados al cromosoma, no
son independientes. Aunque el módulo es bastante general, nosotros lo hemos encontrado un tanto complicado; habrá
que ver cómo evoluciona en el futuro.

Por otro lado, teniendo en cuenta que Algorithm::Evolutionary se ha concebido desde el principio para
trabajar con XML como formato de serialización, habrá que prestar atención a cómo se ha usado XML dentro de

3

los algoritmos evolutivos: pues bien, sucede que el reino del XML aplicado a algoritmos genéticos se ha mantenido
tradicionalmente aparte del anterior, aunque ha habido unos cuantos acercamientos al tema. El más notable es el
lenguaje EAML, descrito por Veenhuis y otros [EAML]. Este lenguaje, especificado como un grupo de etiquetas en
XML con un significado concreto y determinado, especifica un algoritmo evolutivo, a partir del cual se puede generar
código en C++. Este lenguaje trata de ser una descripción exhaustiva de un algoritmo evolutivo, pero no lo consigue,
porque, por ejemplo, los operadores de variación son etiquetas, en vez de ser atributos; los atributos pueden tener
cualquier valor, pero sólo se pueden usar las etiquetas especificadas en el diccionario; de esta forma, la introducción
de un nuevo operador significaría la modificación del diccionario. Tiene otros errores de diseño, pero, en todo caso,
es un paso en la dirección correcta. El dialecto usado en esta implementación en Perl/XML de un algoritmo genético
trata de evitar estos errores.

En los primeros meses del año 2002 han surgido otros muchos esfuerzos por combinar XML y algoritmos evolutivos.
Por ejemplo, se ha propuesto un servicio web basado en algoritmos evolutivos [eaWeb], al cual se proporciona una
descripciónd de las funciones a optimizar, y los parámetros del algoritmo evolutivo usando XML, y devuelve la
función optimizada. En el wiki XMLMen [XmlMen] también se exploran los diferentes paradigmas de especificación
de algoritmos evolutivos usando XML (inclusive una versión previa del usado en Algorithm::Evolutionary),
usando finalmente EAML [EAML] para hacer diferentes experimentos dentro de un sistema denominado Sutherland.
Otros sistemas basados en algoritmos evolutivos prometen, para versiones sucesivas, especificaciones XML de los
algoritmos o bien serialización XML. También eaLib [eaLib] incluye un método de serialización XML, pero se trata
de un método automático de serialización de objetos en Java, no uno específico que sea legible para alguien entendido
en algoritmos evolutivos.

Importante

En resumen, Algorithm::Evolutionary pretende llevar un paso más allá el estado