Entradas desde el 20/10/2003 :

1- ¡¡Marchando una de genéticos!!

Al acercarte por primera vez al mundo de la computación evolutiva es difícil no perderte entre la maraña de aproximaciones que surgen ante ti. En principio te dan a elegir entre algoritmos genéticos, programación genética, programación evolutiva, sistemas clasificadores, y en el momento en que te despistes se han introducido en tu camino las redes neuronales, la lógica difusa, y un poquito escondida la teoría del caos. Dan ganas de salir corriendo, pero si te atreves a adentrarte un poco más encontrarás una idea muy sencilla, flexible y poderosa con la que se lleva investigando más de treinta años.
Todo comenzó en los años 60 cuando a John Holland se le ocurrió tratar de utilizar los fundamentos de la evolución de las especies para el desarrollo de programas informáticos. En un principio Holland tenía dos objetivos, por un lado utilizar el esquema evolutivo para implementar sistemas capaces de adaptarse dinámicamente a un entorno cambiante, y por otro diseñar sistemas artificiales que simulasen la evolución natural. El algoritmo propuesto era de una gran sencillez. Se comienza creando una población de individuos representados por una secuencia de bits de longitud fija (que correspondería a su material genético), a partir de esta población seleccionamos a algunos individuos para que se reproduzcan dando una mayor probabilidad de reproducirse a los "mejores individuos" (evidentemente primero hemos tenido que crear una función de evaluación nos diga cuales son esos "mejores individuos"). Ya tenemos una segunda generación, ahora debemos decidir que soluciones sobreviven (de nuevo la función de evaluación se ocupará de que los mejores individuos tengan mayor probabilidad de sobrevivir) y comenzar la siguiente iteración. Con el paso de las iteraciones nuestra población será probablemente cada vez mejor ya que en todo momento se ha favorecido a los mejores individuos frente a los peores.
En un principio este algoritmo no fue diseñado tanto para enfrentarse y solucionar un problema específico, como para simular modelos complejos cuyo comportamiento pudiese resultar de interés. Sin embargo en los años 70 y 80 se observó que la estructura de este algoritmo podía utilizarse para el diseño de potentes técnicas de exploración y optimización. Para ello se genera aleatóriamente una población inicial en la que el material genético de cada individuo representa una posible solución a un problema dado. A partir de aquí comenzamos a permitir que las soluciones combinen y muten sus genes recorriendo de esta forma el espacio de soluciones posibles, con el paso de las generaciones, nuestros individuos serán cada vez mejores e irán convergiendo poco a poco (al menos algunas veces) a una solución óptima.
Desde los años 90 el número de problemas a los que se han enfrentado los algoritmos genéticos (principalmente de optimización y de inteligencia artificial) no ha parado de crecer, creándose todo tipo de variaciones para adaptarse a las distintas características de estos. Asimismo otras ideas de similar planteamiento se han desarrollado en paralelo, todo ello ha dado lugar a un aluvión de definiciones englobadas bajo el nombre común de computación evolutiva.

2.- ¡Orden!¡Orden!

Bajo el término computación evolutiva se ha agrupado un conjunto de técnicas que tratan de imitar de alguna forma los métodos de evolución naturales. Todas las técnicas tienen en común cuatro propiedades:
- Una población de individuos inicial.
- Una función de evaluación que se ocupará de guiar el algoritmo.
- Un cierto dinamismo que hace que la población cambie (muriendo algunos elementos y naciendo otros nuevos).
- Y una noción de herencia que permitirá a los nuevos individuos mantener algunas de las características de sus padres.
Partiendo de esta base se nos presentan diversas opciones:

2.1 Algoritmos genéticos:

Los algoritmos genéticos parten de una población inicial donde cada individuo se representa con un código genético (típicamente una secuencia de bits) en la que se encuentra codificada su información. Sobre esta población se realiza una serie de operaciones, en primer lugar se seleccionan parejas de soluciones para que se reproduzcan (a este proceso se le llama cruce), siendo los hijos una mezcla del código genético de los padres. A continuación se producen una serie de mutaciones que alteran los genes de los recién nacidos y por último de entre toda la población se eligen aquellos que van a sobrevivir desechándose el resto (la población en un algoritmo genético típico permanece constante en todas las iteraciones). Tanto a la hora de la reproducción, como en el momento de elegir las soluciones supervivientes en cada iteración, se favorece a aquellos individuos que según la función de evaluación sean más fuertes. El algoritmo terminará cuando se llegue a un número de iteraciones seleccionado previamente, o cuando se observe tras una serie de iteraciones no se ha detectado ninguna mejora en la población. El pseudo código sería el siguiente:

Crear población inicial Evaluar la población Mientras No(condición salida) Seleccionar a los padres Combinar los genes de los padres para crear a los descendientes Mutar a los descendientes Evaluar la nueva población Elegir los individuos que sobrevivirán

Comentemos brevemente cada uno de los pasos a seguir para desarrollar un algoritmo genético:

Codificación de las soluciones: el primer paso a realizar es codificar las soluciones de forma que queden representadas por una secuencia constante de bits (también se puede trabajar con caracteres). La elección de esta codificación no es trivial, especialmente si estamos tratando un problema de optimización. Por ejemplo una codificación directa de los números enteros puede traernos problemas a la hora de que el algoritmo converja, ya que números consecutivos, como por ejemplo el 15 y el 16, al pasarlos a binario son "demasiado" diferentes (10000, 01111) con lo que una solución con el valor 15 en un campo, difícilmente llegará a evolucionar a una solución con el valor 16 (ya que debería cambiar simultáneamente todos los bits). A este problema se le conoce como "Picos de Hamming". Para disminuir su efecto podemos utilizar otras codificaciones. Por ejemplo codificando según los "Códigos de Gray" aseguramos que enteros consecutivos solo se diferenciarán en un bit.

Elección de la población inicial: en un algoritmo genético clásico se trabaja con una población constante. Cuanto mayor sea la población más exhaustivo será el estudio del problema, pero como pega también será mayor el tiempo necesario para la computación, y para la convergencia del algoritmo.
Existe una variante de los algoritmos genéticos (algoritmos generacionales) en la que la población tiene un margen de elasticidad que le permite cambiar durante la ejecución. Lamentablemente no hay una teoría clara sobre como debe variar esta función.

Elección de la función de evaluación: la función de evaluación debe reflejar qué características queremos que tenga nuestra población, para que nuestro algoritmo sea capaz de distinguir cuáles son los mejores individuos. Un algoritmo genético toma todas sus decisiones según esta función por lo que elegirla convenientemente es un factor clave. Lamentablemente hay pocas indicaciones sobre cómo elegirla, ya que depende por completo del problema a tratar.
Generalmente para problemas de optimización se elige una función constante, mientras que en Inteligencia Artificial se pueden utilizar funciones que dependan del entorno para que de esta forma el sistema pueda adaptarse.
Un caso específico en el que se está investigando actualmente son las funciones de coste colectivas, estas funciones evalúan como se complementan los individuos unos con otros, y no solo como es cada uno de ellos por separado. Usar este tipo de funciones requiere un tratamiento especial para detectar y premiar a los grupos de individuos que mejor se complementen entre sí. De nuevo la idea viene inspirada por la naturaleza. Una hormiga (o termita o abeja) puede parecernos un organismo muy limitado, sin embargo, hay pocas cosas tan eficientes como un hormiguero. De la misma forma podemos tratar de diseñar algoritmos genéticos cuyo objetivo no sea encontrar al mejor individuo posible, sino una población que cooperando obtenga todavía mejores resultados. Lamentablemente los algoritmos genéticos con este tipo de funciones son actualmente más un objetivo, que una realidad.

Reproducción o cruce: En este campo hay dos decisiones a tomar. En primer lugar debemos decidir cuantos descendientes queremos, y qué individuos van a reproducirse. Generalmente se fija factor de cruce constante, que representa la probabilidad de que dos individuos se crucen entre sí (suele ser alto entre 0.6 y 0.9), pero también se puede trabajar con probabilidades que dependan de la función de evaluación, favoreciendo que se reproduzcan los mejores individuos. La segunda decisión es como vamos a cruzar los individuos. La figura 1 presenta las tres posibilidades más comunes. Con el cruce simple se elige un bit a partir del cual se intercambian los genes de los "padres". En el cruce doble se eligen dos bits y se intercambia todo el material genético que haya entre ellos. Por último con el cruce con máscara se genera aleatóriamente un vector de máscara, de forma que si en una determinada posición el vector generado tiene un 1 se intercambian los bits, y si tiene un cero se mantienen.

Mutación: Una vez cruzadas las soluciones sometemos a los descendientes a un proceso de mutación. Para ello elegimos un factor de mutación que representara la probabilidad de mutar cada uno de sus bits. El factor de mutación suele ser bastante más pequeño que el factor de cruce (entre 0.01 y 0.001), ya que un factor grande limita la convergencia de los algoritmos. Para aprovechar las posibilidades que ofrece la mutación en mayor medida, sin afectar a la convergencia, se puede utilizar un factor de mutación variable. En ese caso al principio asignaríamos un valor alto para favorecer la exploración del espacio de soluciones, y cada cierto intervalo lo decrementaríamos.

Elección de los supervivientes: para acabar debemos decidir que individuos constituirán la población de la próxima generación. Esta decisión depende mucho del objetivo del algoritmo. Si necesitamos una solución rápida podemos elegir directamente a los mejores individuos, de esta forma el algoritmo converge antes, pero explora menos el espacio de soluciones. Una opción para efectuar una exploración más amplia es realizar torneos entre la población. En esta variante creamos grupos de individuos aleatóriamente y los hacemos competir de forma que sobrevivan los mejores. La diferencia estriba en que cualquier solución puede sobrevivir si tiene la suerte de que sus contrincantes sean peores, de esta forma se favorece la diversidad genética.
La velocidad de convergencia es un arma de doble filo, queremos que nuestro algoritmo sea rápido, pero si nos enfrentamos a un problema de optimización y encontramos muy rápidamente una solución que parece la mejor, seguramente nos habremos dejado engañar por un óptimo local. Sin embargo si favorecemos que siempre haya una gran variedad genética muchas de las soluciones no nos resultarán útiles y estaremos desperdiciando nuestra capacidad de búsqueda. De nuevo, al igual que al elegir el factor de mutación, puede resultar interesante decidir dinámicamente, fomentando al principio la variedad genética y favoreciendo la convergencia en la fase final .
Si queremos utilizar el algoritmo genético para realizar una aplicación que se adapte a los cambios de su entorno, favorecer la convergencia hacia los mejores individuos es especialmente peligroso, ya que las soluciones que parecían buenas en un determinado instante, pueden dejar de serlo cuando se produzca un cambio. En estos casos es fundamental disponer en todo momento de una amplia diversidad genética que permita afrontar los cambios.

2.2 Programación evolutiva:

Fue creada en 1960 (simultáneamente a los algoritmos genéticos) por Lawrence J. Fogel.
El planteamiento es muy similar pero en este caso el método de reproducción no incluye el cruce entre individuos sino únicamente la mutación, es decir para generar descendientes un determinado individuo se duplica a sí mismo y posteriormente sufre algunas mutaciones. Se suele trabajar con factores de mutación variables. Eliminar el cruce permite que en programación evolutiva la representación de los individuos pueda ser bastante más compleja y flexible. La codificación de un individuo en un algoritmo genético trata de imitar a un genoma y es por tanto de longitud constante. En programación evolutiva no hay ninguna idea preconcebida de cómo ha de representarse un individuo, se pueden utilizar estructuras complejas como redes neuronales, grafos, árboles, etc. En cada caso concreto se deberá elegir una representación que se adapte convenientemente al problema.

2.3 Sistemas clasificadores de Aprendizaje (SC):

Los sistemas clasificadores fueron presentados de nuevo por John Holland en 1975. Básicamente son sistemas basados en reglas (classifiers) diseñados para interactuar con su entorno, y aprender de él mediante la asignación de pesos a cada regla y la creación de nuevas reglas a partir de las anteriores.
Las reglas tienen la forma de una sentencia lógica (condición / acción), identificando una condición con una acción a realizar en caso de que la condición se cumpla.
Un SC está dividido en tres subsistemas [Fig2], el sistema de rendimiento, el sistema de asignación de crédito y el sistema de descubrimiento de clasificadores. Su funcionamiento es el siguiente:
En primer lugar debemos generar una serie de reglas iniciales a partir de nuestros conocimientos del problema a tratar, y asignar a estas reglas un peso. A partir de aquí el sistema trabajará solo a partir de la información que reciba de su entorno. Para ello comparará la información recibida con las condiciones de los clasificadores, y seleccionará aquellos cuyas condiciones se cumplan. Los clasificadores seleccionados indicarán una serie de acciones a realizar, estas acciones pueden contradecirse entre sí por lo que el sistema deberá detectar las incompatibilidades, y en caso de qué se produzcan, seleccionar una de las acciones. A la hora de elegir se estudian los pesos asignados a cada acción dando preferencia al clasificador con mayor peso. Toda esta funcionalidad recae en el subsistema de rendimiento.
Hasta aquí el proceso es totalmente estático. Para ser capaz de evolucionar y aprender dinámicamente, un sistema clasificador va a aplicar dos técnicas: por un lado el sistema se realimenta con la información que recibe del exterior, y si considera que las decisiones que se tomaron fueron acertadas las premia incrementándoles el peso, (de la asignación y actualización de los pesos se ocupa el subsistema de asignación de crédito) y por otro se utiliza un algoritmo genético para crear nuevas reglas a partir de las mejores reglas existentes (ésta es la función del subsistema de descubrimiento de clasificadores). Las nuevas reglas sustituirán a las que tuvieran los pesos inferiores. El peso de las nuevas reglas se calcula a partir del peso de sus padres, en éste caso no se utiliza una función de evaluación clásica sino que se solicita al subsistema de asignación que se ocupe de ello. Dado que para saber si una regla es útil es necesario observar cómo se comporta a lo largo del tiempo no se generan nuevas reglas constantemente sino cada cierto intervalo, de esta forma todas las reglas tienen la oportunidad de demostrar su utilidad.

Gracias a los subsistemas de asignación y de descubrimiento, un SC es capaz tanto de aprender nuevas reglas, como de variar dinámicamente sus preferencias entre ellas, y por tanto puede adaptar su comportamiento al entorno que le rodea.
Los sistemas clasificadores han demostrado su utilidad en líneas tan diversas como robótica, teoría de juegos y simulación de sistemas económicos.

2.4 Programación genética:

La programación genética es una rama de la computación evolutiva en la que los individuos que componen la población son programas ejecutables en vez de secuencias de bits como en los algoritmos genéticos. Esta nueva variante fue presentada por John R. Koza en 1982. Los programas se representan como árboles sintácticos. En estos árboles, una llamada a una función viene representada por un nodo del árbol y los argumentos de la función son sus nodos hijos. Por ejemplo, la función f(x,y)=sin(x)*(9+y) vendría representada por el siguiente árbol:




El proceso comenzaría definiendo una serie de funciones con las que se quiere realizar el programa. A continuación se genera una población inicial de árboles que utilizan estas funciones. Sobre esta población se aplican las mismas operaciones que en los algoritmos genéticos, es decir, cruce (o reproducción), mutación y selección de los supervivientes. La operación de reproducción funciona intercambiando subárboles entre distintas soluciones, la mutación cambia aleatóriamente alguno de los nodos, y para la selección de los individuos que sobreviven a la siguiente generación se utiliza (como en los algoritmos genéticos) una función de evaluación capaz de evaluar la bondad de los programas. Típicamente la función de evaluación suministrará al programa una serie de datos de entrada y comprobará las salidas con los resultados deseados.
Pongamos un ejemplo. Una de las aplicaciones con las que se está trabajando dentro de la programación genética es el diseño de circuitos. Supongamos que queremos diseñar un circuito que implemente una determinada función f(x). Comenzamos eligiendo los elementos con los que lo vamos a construir (por ejemplo resistencias, condensadores, transistores etc.) y combinamos los elementos (siguiendo algún patrón que consideremos adecuado en caso de tenerlo) para crear la población inicial. Todos los individuos son circuitos reales, y por tanto podemos estudiar su comportamiento. Para evaluarlos comparamos su salida con la función f(x) que debían implementar, y a partir de aquí nos comportamos como en un algoritmo genético, cruzando y mutando las soluciones hasta encontrar un circuito que implemente f(x) con un margen de error satisfactorio.

3.- Análisis crítico de la computación evolutiva:

La computación evolutiva en todas sus ramas lleva tras de sí un bagaje de 30 años de investigación durante los que se ha enfrentado, muchas veces con gran éxito, a una amplísima variedad de problemas englobados normalmente en dos campos principales: optimización e inteligencia artificial.
Dentro de la optimización su marco de aplicación son aquellos problemas donde el diseñador se encuentra con un espacio de soluciones posibles que aparentemente le sobrepasa (problemas NP-completos, es decir cuya complejidad aumenta exponencialmente al aumentar el tamaño del problema) por lo que inicialmente es incapaz de calcular una solución correcta (si te enfrentas a un problema NP-completo para un n suficientemente grande estudiar todas las soluciones posibles, incluso con la máquina más potente, llevaría más tiempo que la edad del universo). Sin embargo el diseñador sabe cómo debe comportarse la solución que busca y por tanto es capaz de evaluar qué soluciones son buenas y cuáles son malas.
Ante esta clase de problemas, con los que la potencia de cálculo bruta se muestra ineficaz, nos vemos obligados a utilizar alguna heurística que nos permita acotar el espacio de búsqueda. El objetivo no es tanto encontrar la mejor solución posible como conseguir una solución lo suficientemente buena en un tiempo de búsqueda aceptable. En este campo la utilización de computación evolutiva ha conseguido espléndidos resultados.
En inteligencia artificial se ha utilizado la computación evolutiva para tratar de conseguir sistemas capaces de adaptarse por sí mismos a cambios en su entorno, e incluso de aprender nuevos comportamientos. Se han realizado aplicaciones en robótica, desarrollo de juegos, y simulación y predicción de sistemas complejos.
En otros muchos campos hay investigaciones prometedoras donde se han adaptado los fundamentos de la computación evolutiva a un sin fin de problemas.
Ante todo este éxito aparente surge una pregunta ¿por qué la computación evolutiva continua desarrollándose principalmente en el ámbito de la investigación y no en el de las aplicaciones?.

3.1 ¿Qué opinan las matemáticas?

Desde el comienzo de la utilización de los algoritmos genéticos se ha echado en falta una base matemática que nos permita prever de antemano cuál va a ser su comportamiento. John Holland en 1975 presentó un análisis matemático de los algoritmos genéticos orientados a la optimización. Para conseguir que este análisis fuera posible tuvo que realizar una serie de simplificaciones, como tomar una población infinita y estudiar los comportamientos cuando el tiempo tendía a infinito. Sin embargo los resultados que se obtienen cuando la población es finita y el algoritmo se ejecuta un tiempo determinado puede desviarse considerablemente del comportamiento indicado por el trabajo de Holland, por lo que no resultan fiables sus predicciones.
La dificultad de modelar matemáticamente los algoritmos genéticos radica en la aleatoriedad de sus decisiones, ya que muchas se toman al azar (por ejemplo los bits que intercambian dos soluciones para crear descendientes, o la posibilidad de que se produzca una mutación).
Ante la ausencia de garantías matemáticas los defensores de la computación evolutiva apelan a los resultados obtenidos, pero mucha gente se muestra escéptica.
Recientemente, se han abierto líneas de investigación en algoritmos genéticos que tratan de caracterizar matemáticamente su comportamiento a partir de la teoría del Caos.

3.2 Partir (casi) de cero

Treinta años de investigación dan para muchas cosas, multitud de teorías, ejemplos, aplicaciones, éxitos, fracasos, etc. En el caso de la computación evolutiva, podrías pasarte años estudiando los resultados obtenidos, pero cuando llega el momento de utilizarla para un propósito específico nos encontramos con que falta una teoría global que permita elegir fácilmente entre el aluvión de decisiones que se deben tomar, en vez de ello encuentras un trabajo puntual en el que ciertas decisiones fueron exitosas, y otro en el que tomando las decisiones contrarias se alcanzó igual éxito. ¿Qué decisiones tomamos? Las decisiones correctas dependen del problema con el que estemos tratando. La eficiencia que pueda tener el cálculo (por ejemplo con algoritmos genéticos) al aplicarlos a un nuevo problema, se supedita en gran medida a que elijamos cuidadosamente la representación de las soluciones, la función de coste, la población inicial, las probabilidades de mutación y de cruce, la elección de las parejas que van a cruzarse y la elección de las soluciones supervivientes a cada generación. Para algunos problemas algunas de estas decisiones resultan sencillas, casi evidentes, pero otras veces son mucho menos obvias y requieren demasiado trabajo, además todas las decisiones se relacionan entre sí, con lo que no se pueden analizar por separado. Muchos diseñadores consideran que tomar estas decisiones convenientemente requiere más trabajo que calcular la solución utilizando otros métodos tradicionales.

3.3 ¡Fuera, Fortuna! ¡Vete, ramera!

¡Fuera, Fortuna! ¡Vete, ramera! Vosotros, dioses,
reunidos todos en un sínodo general, arrebatadle su poder,
romped todos los radios y llantas de su rueda
y haced rodar a la redonda bribona desde el cielo colina abajo
hasta los mismos demonios.
William Shakespeare

Shakespeare no es el único que desconfía de la diosa fortuna. Son muchos los diseñadores que se niegan a confiar en ella para alcanzar el éxito en su trabajo. Y si bien no es cierto que la computación evolutiva sea un proceso totalmente aleatorio, ya que sigue una estructura determinada y sobre todo razonada, no se puede negar que muchas de las decisiones puntuales las acaba tomando el azar. Eso sí, no le damos a la Diosa tanto poder como parece, le dejamos elegir pero siempre bajo el yugo de las probabilidades que nosotros imponemos.
Uno de los principales problemas que surge al no tomar nosotros mismos las decisiones sino limitarnos a darles una probabilidad distinta a cada una es la dificultad para reproducir los experimentos. Este es un factor clave para la ingeniería, ya que al realizar un experimento se pueden observar anomalías que requieran un estudio detallado. Para realizar este estudio necesitamos ser capaces de duplicar todas y cada una de las condiciones que produjeron la anomalía, ¿cómo podemos hacerlo si las condiciones se han producido aleatóriamente?. Una posible solución a este problema es utilizar funciones aleatorias pero reproducibles. Un ejemplo sería la función random en C. Si comenzamos la ejecución de nuestro programa asignando siempre la misma semilla (es decir inicializando la función random con el mismo valor) obtendremos siempre la misma secuencia de valores, con lo que podremos reproducir la ejecución del programa.

3.4 Contestar sin saber ¡y acertar! :

Una última razón para que la computación evolutiva se haya asentado como herramienta de investigación, y su éxito en este campo sea mucho mayor que como herramienta para el desarrollo de aplicaciones, es que las aplicaciones suelen desarrollarse en aquellas áreas donde se ha obtenido previamente un firme conocimiento. La computación evolutiva (al igual que por ejemplo las redes neuronales) nos permite ir más allá. Con ella podemos enfrentarnos a problemas qué no sabemos resolver, desarrollando un programa capaz de solucionarlo por nosotros. Resulta evidente porqué un planteamiento como éste ha tenido tanto éxito en el ámbito de la investigación, donde debes enfrentarte a problemas que no conoces lo suficiente.


Lecturas recomendadas:


- "Festschrift Conference in Honor of John H. Holland". En la página:
http://www.pscs.umich.edu/jhhfest/abstracts.html están todos los resúmenes de los artículos discutidos en esta conferencia, y la mayoría de los artículos completos. Es una recopilación de los mejores artículos divulgativos sobre algoritmos genéticos.

- Página de enlaces de la Universidad Complutense. Hay enlaces a todos los campos que se tratan en el artículo.
http://moebius.bio.ucm.es/pie/enlaces

- Todo tipo de información sobre computación Evolutiva en "The Hitch Hiker's Guide to Evolutionary Computation". En la página: ftp://ftp.cerias.purdue.edu/pub/doc/EC/Welcome.html

- Holland, J. (1992). "Adaptation in Natural and Artificial System". MIT Press.

- Koza, J. (1992). "Genetic Programming: On the programming of computers by means of natural selection". Bradford Books, Cambridge.

Autores:

Javier Resano Ezcaray Departamento de Arquitectura de Computadores y Automática Universidad Complutense de Madrid

José Luis Delgado Leal Coordinador de la sección de Arquitectura de Ordenadores Universidad Antonio de Nebrija