next up previous contents
Next: Individuos de la población Up: Algoritmos Evolutivos. Objetos Evolutivos Previous: Innovaciones introducidas por Objetos   Índice General

Diseño y Desarrollo de Aplicaciones con Objetos Evolutivos

Objetos Evolutivos es una herramienta, desarrollada en C++ que define las interfaces para varias clases de algoritmos usados en computación evolutiva y al mismo tiempo, implementa dichos algoritmos. La biblioteca se encuentra disponible en http://www.sourceforge.net/projects/eodev/.

El desarrollo de cualquier programa conlleva dos fases: el diseño y la programación. Utilizando OE para desarrollar una aplicación evolutiva nos encontramos con estas dos fases, en las cuales primero se decide una representación adecuada al problema y los operadores genéticos a utilizar, y después se diseña un algoritmo evolutivo, utilizando los elementos anteriores del modo en que se haría cualquier otro algoritmo evolutivo.

Durante la fase de diseño, normalmente el objeto que se hará evolucionar queda definido por el problema a resolver. Por ejemplo, en el caso del problema del viajante de comercio (``Travelling Salesman Problem'', TSP) se podría utilizar una representación de modo que cada objeto solución sea un vector de enteros que contenga todas las ciudades [#!Booch94!#]. Los operadores genéticos utilizados para mutar y combinar las soluciones deberían tener en cuenta la disposición de las ciudades a visitar. El resto del diseño es, en general, independiente del problema: la selección de los individuos que se reproducirán, y el criterio de parada del algoritmo.

En la fase de programación, el algoritmo (basado en OE) se programará de forma similar a como se programaría otro algoritmo evolutivo, esto es, según un bucle del tipo:

  1. Crear una población inicial de OE (usando factorías o los constructores de cada objeto).
  2. Repetir hasta que el criterio de parada se cumpla:
    1. Evaluar cada individuo, comparándolos entre sí, para seleccionar los mejores.
    2. Aplicar los operadores genéticos, creando nuevas soluciones (incrementar la diversidad) y combinándolas (decrementar la diversidad).
    3. Sustituir los peores individuos en la población por los recién creados.

Aunque no hay un soporte teórico para probar el buen funcionamiento de OE, en el peor de los casos funcionaría como una búsqueda aleatoria, pero ya que utiliza recombinación de soluciones, los ``bloques constructivos'' que producen buenas soluciones se mezclan, con lo cual se alcanzan mejores soluciones.

Mientras que la codificación binaria está respaldada por el ``Teorema de los Esquemas'' [#!Holland75!#,#!Goldberg89!#], la ``Teoría del Análisis de Formas'' [#!Radcliffe91!#] da soporte teórico al uso de alfabetos no binarios. El Análisis de Formas generaliza el Teorema de los Esquemas tratando con la equivalencia de clases de cromosomas en lugar de cromosomas binarios. Un ejemplo es ``cromosomas que contienen una permutación en particular'' o ``cromosomas en los que el segundo componente es el doble que el primero''. El Análisis de Formas asegura que si se usan operadores independientes de la representación se pueden definir algoritmos independientes de la representación, que se comportarán de la misma forma que los AG estándar. En OE, puesto que el usuario no está obligado a utilizar una representación en cadenas binarias, y las soluciones a los problemas se codifican de forma natural, los bloques que forman las soluciones se encontrarán juntos de forma natural y se heredarán juntos.



Subsecciones
next up previous contents
Next: Individuos de la población Up: Algoritmos Evolutivos. Objetos Evolutivos Previous: Innovaciones introducidas por Objetos   Índice General
Francisco Javier Garcia Castellano
2000-12-14