|
|
|
|
http://www.redcientifica.com/gaia/agsp_c.htm
Algoritmos Genéticos AvanzadosManuel de la Herrán Gascón
Indice:
Publicado en septiembre de 1997 en la revista "Solo Programadores" (nº 37)
.
- Introducción
- Vida Artificial y Algoritmos Genéticos
- Ventajas de los Algoritmos Genéticos
- El problema de la variedad
- El problema de la reproducción
- El problema de la selección
- Conclusiones
Un Algoritmo Genético es una técnica de resolución de problemas inspirada en la reproducción de los seres vivos. Pero una técnica muy especial, en la que las soluciones del problema son capaces de reproducirse entre sí, combinando sus características y generando nuevas soluciones. El funcionamiento básico es muy sencillo, pero existen algunos problemas. En este artículo se van a proponer algunas soluciones.
IntroducciónEn el número 36 (Agosto 1997) de Solo Programadores hablábamos de un programa de Vida Artificial. Este programa simulaba un mundo de dos dimensiones en el que convivían hormigas y plantas. Las plantas crecían al ser regadas. Las hormigas podían comer plantas, moverse, regar, pelearse, reproducirse, nacer y morir.
Existían varios tipos de hormigas, las rojas tenían más tendencia a luchar, las verdes eran más inclinadas a regar. Con el programa se podía estudiar la evolución en el tiempo del número de plantas y del número de hormigas de cada tipo. El esquema depredador-presa produce comportamientos cíclicos:
[ Volver al Indice ]
Vida Artificial y Algoritmos GenéticosUn Algoritmo Genético (AG) es como un mundo de Vida Artificial (VA) en el que se obliga a la evolución a seguir una dirección determinada, de manera que nos sirva para resolver algún problema. En la VA enfrentamos a las hormigas al problema de encontrar comida y librarse de la competencia de las otras hormigas. En un AG las "hormigas" se enfrentarán al problema que nosotros queramos.
En el CD-ROM que acompaña a esta revista se encuentra el programa de instalación y el código fuente en Visual Basic 4.0 para 16 bits de Ejemplos de Vida 2.0, que incluye, además del mundo artificial de hormigas, un AG capaz de adivinar frases.
Se trata de adivinar una frase que ha introducido el usuario. Aunque sea un caso poco práctico, el método de búsqueda que utiliza es independiente del objeto que se busca, y puede ser utilizado en otras aplicaciones más serias, como encontrar una combinación idónea de fármacos, o la toma de decisiones en gestión empresarial de franquicias.
El AG es el encargado de proponer distintas frases como solución al problema. Otro componente, llamado función de evaluación, de adecuación, o de aptitud, dirigirá la evolución del AG. Para ello, La Función de Evaluación (FE) dirá hasta qué punto es correcta una frase propuesta por el AG, es decir, evalúa la utilidad de la entidad.
Pasos de un Algoritmo Genético
1.-Se genera un conjunto de 1-N soluciones al problema. Normalmente, estas entidades se generan al azar.
2.-Se evalúan las soluciones existentes, de manera que se eliminan unas y se mantienen otras (o se limita el tiempo de ejecución).
3.-Se permite la reproducción o combinación de genes (normalmente por parejas) de las entidades existentes.
4.-Se efectúan mutaciones (cambios al azar) de los nuevos patrones, según una tasa determinada.
5.-Se continúa en el paso 2Nos referimos a las frases como entidades o agentes. También se les llama cadenas, patrones, soluciones, bichos, población o seres vivos artificiales. En la naturaleza, un genotipo es la información genética que al desarrollarse crea un fenotipo o ser vivo. Cuando esta distinción no existe, también se habla de genotipo, fenotipo o cromosomas.
En el programa, la Función de Evaluación (FE) devuelve un valor entre 0 y 1. A este número se le llama peso, adecuación o fitness. El 1 indica que se ha acertado la frase completa. Un peso 0.5 es señal de que se han adivinado la mitad de las palabras que componen la frase.
El AG funciona de la siguiente forma. En primer lugar, se generan varias frases al azar, por ejemplo, 40 frases, combinando palabras tomadas aleatoriamente de un diccionario.
Después se evalúan estas frases mediante la FE. En muchas frases no se habrá acertado ninguna palabra, y tendrán un peso 0. Otras, en cambio, podrían haber acertado en alguna y tendrán pesos más altos: 0.1, 0.2, ...
Ahora se ordenan las frases de mayor a menor peso y se eliminan las de menor peso. Por ejemplo, "sobreviven" las 20 primeras y "muere" el resto.
Es el momento de la reproducción. Las 20 frases que quedan se combinan entre sí, mezclando las palabras que las componen y generando nuevas frases. Por ejemplo, tomamos frases de dos en dos y generamos, por cada pareja, otra nueva pareja de frases con las palabras de una y otra intercaladas.
Al haber combinado frases de pesos altos, es muy probable que surjan frases todavía más cercanas a la solución. Ahora se vuelven a evaluar, ordenar y reproducir, repitiéndose el ciclo hasta encontrar la frase buscada. En la imagen, dos frases intercambian sus genes (palabras) creando dos nuevos seres.
A este algoritmo genético sólo le falta una cosa. Si en el conjunto inicial de 40 frases no existen las palabras que componen la frase buscada, por muchas combinaciones que hagamos, nunca llegaremos a la solución. Es necesario poder tomar palabras nuevas de vez en cuando.
Por esto, al generar nuevas frases, se permitirá que, con una cierta probabilidad, la palabra se tome al azar del diccionario y no de sus progenitores. A este valor se le llama tasa de mutación.
En el programa, una tasa de mutación negativa significa que no se efectuarán mutaciones, y se puede observar cómo el algoritmo converge hasta cierto valor que no puede superar.
Una tasa de mutación 0 ó 1 indica que existe mutación siempre, o lo que es lo mismo, que no existe reproducción como tal, sólo búsqueda al azar. Las características de los padres no se transmiten a los hijos, y el algoritmo convergerá muy lentamente.
Lo habitual es utilizar valores como 5 o 10 (una mutación cada 5 o cada 10 generaciones) y así el algoritmo convergerá mucho más rápido hacia la solución buscada.
[ Volver al Indice ]
Lo más sorprendente y útil de los AAGG es que no es necesario disponer de un conocimiento profundo del problema a resolver, sino que se parte de estructuras simples que interactúan, dejando que sea la evolución quien haga el trabajo. Un AG es un método de programación opuesto al habitual: en vez de descomponer un problema en sub-problemas, creamos los sub-problemas más sencillos que podamos imaginar y dejamos que se combinen entre sí.
Ventajas de los Algoritmos GenéticosÚnicamente basta con ser capaces de identificar cualitativamente en qué casos las cadenas se acercan o se alejan de la solución buscada, para que el sistema se perfeccione automáticamente.
Otra gran ventaja de los AAGG es que son adaptativos: son capaces de solucionar problemas que cambian en el tiempo.
La gran sencillez de los AAGG los hace muy atractivos para los programadores, pero existen casos en los que puede ser difícil, imposible o poco práctico aplicarlos. Se podría hablar del problema de la variedad, el problema de la reproducción y el problema de la selección, para los que se van a proponer algunas soluciones.
[ Volver al Indice ]
Un AG trata de explorar las regiones más prometedoras de un enorme espacio de posibilidades. Al encontrar una zona con pesos altos, ésta se explora más a fondo. Pero hay que evitar que el algoritmo se estanque en una determinada zona, produciendo multitud de cadenas muy parecidas.
El problema de la variedadEl aumento de variedad se consigue con las mutaciones, pero esto no suele bastar. Una solución es seleccionar un gran número de agentes, para evitar que un pequeño grupo repita sus características en una gran población. Otra opción que suele tener éxito es seleccionar, además de la población con mayor peso, una fracción de la de menor peso.
También se ha de procurar que, a la hora de la reproducción, los progenitores se tomen al azar y no en orden de pesos, ya que es más probable que frases de pesos parecidos posean palabras parecidas.
Otra elección más radical es hacer que si se reproducen dos cadenas iguales, los hijos sean mutaciones en todos sus elementos; o recorrer de vez en cuando toda la población eliminando cadenas idénticas.
También podemos generar ráfagas de mutaciones: en vez de establecer una probabilidad de mutación independiente para cada creación de una palabra, podemos hacer que si se produce una mutación en un elemento, el siguiente elemento tenga una probabilidad de mutación mayor. En la naturaleza las mutaciones se pueden producir, entre otras causas, por un exceso de radiación. Es lógico pensar que si no hay exceso para un gen, es menos probable que lo haya para el siguiente, y viceversa.
Pero, en definitiva, lo que se busca es que el cálculo del peso no sea independiente para cada cadena, sino relativo: que se le asigne un peso alto cuando es evaluada positivamente por sí sola, y además no existen cadenas que se le parezcan. Para ello podemos analizar las cadenas de mayor peso que una dada y disminuir el peso de esta cadena si existe un gran parecido con las demás cadenas.
En la vida natural ocurre esto mismo: ¿Por qué no somos todos altos, rubios, fuertes y guapos? ¿Por qué hay tantas especies en la naturaleza? Los seres parecidos compiten unos con otros, pero la diversidad y la especialización convive pacíficamente.
Todas estas opciones están contempladas en el programa ¿Qué criterio aplicar? Hay que tener en cuenta por una parte que trabajamos con azar, y que una sola ejecución no es muy significativa, y por otra, que puede haber opciones que "lógicamente" sean mejores, ya que disminuyen el número de ciclos necesarios para llegar al peso máximo, pero que en la práctica no son rentables por el incremento del tiempo de proceso debido a la complejidad de los cálculos.
Encontrar la combinación de parámetros óptima resulta por tanto, costoso. Pero existe una forma de automatizar la elección de estos parámetros. ¿Cuál será? Hablaremos de ello en el siguiente artículo de la serie.
[ Volver al Indice ]
Las características positivas de los individuos deben poder transmitirse a la descendencia. Esto lo hemos conseguido fácilmente en el caso de las frases, pero en otros problemas no será tan sencillo.
El problema de la reproducciónPor ejemplo, si estoy buscando la secuencia de acciones con la que se consigue un determinado objetivo (¡sí, sí, estamos hablando de programación automática!), el patrón 234, 523, 12, 765, 256 (¿códigos ensamblador?) podría representar dicha secuencia de acciones, suponiendo que se ha asignado a cada número una acción o instrucción.
Sin embargo, la probabilidad de que mediante la combinación de dos cadenas válidas de este tipo, se genere una cadena válida es muy baja. ¿Alguien ha cambiado alguna vez una línea de un programa al azar y el programa ha seguido funcionando?
Ésta parece una dificultad insalvable, pero no lo es. Una vez más, la vida natural nos da la pista: en realidad, los genes, más que determinar directamente las características que definen un nuevo individuo (color de los ojos, etc.), definen un conjunto de reglas de desarrollo que aplicadas y combinadas provocarán dichas características. Para ello, la dotación genética, que existe en todas las células de cada ser vivo, controla la realización de ciertas reacciones químicas, de manera que los genes son los que determinan, pero no directamente, la constitución y comportamiento de dicho individuo.
Supongamos que vamos a construir un AG que juegue al tres en raya. Debemos decidir qué tipo de información va a estar almacenada en las cadenas protagonistas del algoritmo. Lo más sencillo es que los patrones contengan cada una de las posiciones de las fichas colocadas. Por ejemplo, una serie válida es: (1,1)-(1,2)-(1,3). Esto significa que el individuo representado por esta cadena colocará su primera ficha en la posición (1,1), la segunda en (1,2) y la tercera en (1,3). Es posible que este individuo haya ganado alguna partida con esta secuencia, y por tanto sea seleccionado. Sin embargo, la información almacenada genéticamente no es representativa de cómo y porqué ganó, ya que depende completamente de los movimientos realizados por su contrincante. La repetición de la secuencia de movimientos (1,1)-(1,2)-(1,3) puede originar con facilidad partidas no válidas, al intentar colocar una ficha en una casilla ocupada, y evidentemente la combinación de dos cadenas con esta estructura raramente producirá una partida válida, mucho menos una cadena vencedora.
La solución al problema de la reproducción es encontrar una estructura de datos capaz de contener la información crítica necesaria para alcanzar el objetivo propuesto. Aquí entramos en el tema de los métodos de representación del conocimiento ampliamente estudiado en los sistemas expertos. En muchos casos, es suficiente un sistema de reglas.
En el tres en raya, podríamos tener reglas del tipo "si observo tal situación, realizo tal acción". Cada entidad estaría compuesta por un conjunto de reglas de este tipo. Al jugar una partida, la entidad, observa el estado del tablero, y si posee alguna regla que aplicar, la aplica. En caso contrario, juega al azar.
En este caso, en las entidades sí está almacenado el conocimiento clave para ganar el juego, que son las reglas, no los movimientos. Cada conjunto de reglas será una solución. El elemento mínimo que se combina o muta es una regla completa. Y una posible función de evaluación en este caso es provocar una partida entre dos entidades.
¿Entonces, el uso de reglas solucionará siempre el problema de la reproducción? Es difícil saber cuándo una estructura de datos es adecuada; sin embargo, sí existe una forma de saber por anticipado cuándo una estructura de datos no es adecuada.
El método es el siguiente: si al modificar un elemento cualquiera de una cadena seleccionada, la cadena resultante es pésima, entonces la estructura de datos elegida no es correcta, ya que los componentes de la cadena por sí sólos no contienen la información que hace que esa cadena sea seleccionada.
Expresado de una forma estricta: "Cuando el objetivo de una entidad se puede calcular como una función no-lineal de los componentes de la entidad, la estructura de datos es incorrecta"
En un problema de este tipo puede suceder que variaciones muy pequeñas de los valores de sus variables produzcan variaciones muy grandes en el resultado de la función resultado. El ejemplo por excelencia de problema no-lineal es la lotería. El cambio de uno sólo de los dígitos de nuestro billete puede producir cambios enormes en la cantidad que se recibe como premio.
El tres en raya con reglas es bastante lineal: cada regla, o es buena, o es mala. Si una entidad seleccionada posee 40 o 50 reglas, probablemente podamos cambiar una sin que se convierta en un pésimo jugador.
Pero en casi todos los problemas existe una cierta no-linealidad inevitable. Por ejemplo, pueden producirse por azar reglas muy interesantes, pero que no son seleccionadas porque necesitan de otras para demostrar su utilidad y producir un peso alto. Es decir, las no-linealidades son trozos de cadena cuya utilidad depende de los valores de otros segmentos, y que sólo son útiles cuando todos ellos contienen determinados datos, desapareciendo la utilidad al fallar uno de ellos.
Cuanta más no-linealidad exista, más lentamente convergerá nuestro AG. Esto es completamente inevitable, ya que no es posible encontrar algo si no sabemos qué es lo que estamos buscando. ¡Sin embargo, la naturaleza parece que sí lo consigue! ¿Cómo han podido generarse gradualmente órganos complejos, como los ojos, que no pueden depender de una única mutación, si solamente el órgano completo es útil al individuo? No siempre parece fácil explicar todos los rasgos que presenta un organismo con un mecanismo adaptativo.
En mi opinión, este planteamiento es erróneo. Los seres vivos sacan beneficio de cualquier órgano a medio formar. El sistema visual de la rana está "sintonizado" solamente a cuatro clases de estímulo, estos son: el contraste de luz y oscuridad; un borde de luz u oscuridad; una repentina disminución de la luminosidad; y el constante movimiento de un pequeño objeto negro. ¿De verdad únicamente el órgano completo (visión en colores) es útil al individuo?
Es habitual considerar nuestra inteligencia o la visión de un halcón como perfectas, en vez de simples estadios intermedios, que llegarán a niveles mucho más avanzados gracias a la evolución. La naturaleza es mucho más lineal de lo que parece, y nosotros podemos ser "la rana".
Bien, estamos resolviendo un problema con ciertas no-linealidades y por fin hemos conseguido que aparezcan juntos los valores deseados en los segmentos no-lineales. ¿Vamos a dejar que esta información tan valiosa se pierda en la siguiente generación? Si combinamos segmentos de la cadena de cualquier forma, es muy probable que dividamos el trozo no-lineal, perdiéndose todas sus propiedades.
¿Existe alguna forma en la que la naturaleza fuera capaz de evitar esto? Sí. Podemos hacer que segmentos con iguales valores en cadenas que se reproducen vean reforzada su unión, de forma que en toda la descendencia sucesiva aumente la probabilidad de que esos segmentos se hereden completos de un sólo progenitor, sin combinarse con los del otro.
Este criterio sería falso cuando se reprodujeran dos cadenas hermanas, ya que aunque tendrían segmentos iguales, esto no sería un indicador de rasgos positivos, sino que únicamente se trata de la parte que ambas han heredado del mismo progenitor.
Esta opción presupone que existe un número muy grande de cadenas y que la probabilidad de reproducción de una cadena con su hermana sea igual que con cualquier otra, cosa que no existe en la naturaleza, salvo quizá por el tabú del incesto.
Cada individuo posee una dotación genética doble.
Si la repetición de un segmento en los dos progenitores no fuera señal suficiente de que se trata de un rasgo valioso, se podría hacer que cada entidad tuviese una dotación genética doble, (dominante y recesivo) y obligar a una coincidencia en los cuatro segmentos.
En definitiva, se trata de tratar los segmentos no-lineales independientemente. Podríamos recorrer toda la población cada cierto tiempo, detectándolos. Una vez localizados, se puede provocar una microbúsqueda dentro del propio segmento no-lineal manteniendo constante la parte lineal, que por serlo, no afectará al peso resultante, hasta encontrar alguna combinación valiosa de los segmentos no-lineales.
[ Volver al Indice ]
En cada ciclo de un Algoritmo Genético se selecciona un subconjunto de las soluciones o individuos existentes, eliminando el resto. Los individuos seleccionados se reproducirán entre sí, generando nuevas soluciones.
El problema de la selecciónLa función que decide qué entidades serán seleccionadas, la llamada función de evaluación (FE), puede ser muy difícil o imposible de conseguir.
En el problema del viajante, que debe recorrer varias ciudades hasta volver al punto de partida incurriendo en el mínimo coste, la FE calculará la suma de las distancias entre las ciudades recorridas en el orden especificado y devolverá la inversa de este valor.
En el tres en raya, hemos hecho que las entidades jueguen partidas entre ellas. La entidad ganadora recibirá un peso alto y la perdedora uno bajo, que podría variar en función de lo que ha tardado en perder.
El caso de la programación automática, es más complicado. ¿Cómo definimos qué es lo que debe hacer un programa, sin tener que escribir ese programa? Se podrían ofrecer varios pares de conjuntos de datos de entrada y salida, y suponer que el programa es correcto cuando genera los datos de salida esperados en todos los ejemplos.
En general, los problemas en los que la meta buscada posea un carácter continuo (en los que el objetivo se pueda cumplir en distintos grados) serán más fáciles de resolver que aquellos en los que la meta buscada es todo-nada, es decir, en los que o se consigue el objetivo completamente o no se consigue en absoluto.
Finalmente, los problemas más espinosos de todos son aquellos en los que, al menos por ahora, la FE no es automatizable, como el caso de un programa capaz de crear música, ya que ¿dónde encontraremos a alguien dispuesto a escuchar y opinar acerca de interminables melodías inicialmente absurdas?
[ Volver al Indice ]
Los algoritmos genéticos tienen la ventaja de ofrecer un mecanismo adaptativo de resolución de problemas, de forma que aunque el problema cambie, éste se pueda seguir resolviendo. "Resolver un problema cambiante", llevado al límite, es igual a "Resolver cualquier problema". Según este planteamiento podríamos pensar en diseñar un esquema común que facilite a los agentes aprender en cualquier entorno de problema. En el próximo artículo nos centraremos en el aprendizaje y veremos los fundamentos de este esquema de aprendizaje válido para cualquier problema, basado en Vida Artificial y Algoritmos Genéticos.
ConclusionesEn el CD-ROM que acompaña a la revista se incluyen los códigos fuente completos en Visual Basic referentes a los programas mencionados en el artículo.
[ Volver al Indice ]
[ Home Page Castellano | Home Page English ] 
