|
|
|
|
http://www.redcientifica.com/gaia/ejv2_c.htm
Indice:
Ejemplos de Vida. Palabras y Frases
- Palabras y Frases y WordEvol de Stephen Prata
- Palabras y Frases
- Opciones que permite el programa para aumentar la variedad
- Otros aspectos a tener en cuenta
- Bajar código fuente
Palabras y Frases y WordEvol de Stephen PrataPalabras y Frases es un programa inspirado en otro programa, llamdo WordEvol.
El programa WORDEVOL proviene del libro "VIDA ARTIFICIAL" de Stephen Prata, editado por Anaya en 1993. Su distribución gratuita está autorizada, y su venta no.
El autor de WORDEVOL es Stephen Prata, y para su diseño se basó a su vez en el libro "El relojero Ciego" (The Blind Watchmaker) de Richard Dawkins.
Este programa sirve para comprobar los efectos de la selección acumulativa frente a simples mutaciones aleatorias, en la búsqueda de una cadena de caracteres determinada.
En WordEvol se trata de adivinar una secuencia de caracteres. Para ello se comparan dos posibles métodos: puro azar, que equivale a simples mutaciones, y azar dirigido por los resultados anteriores, que equivale a la selecci¢n de las especies aplicada sobre mutaciones genéticas, y que en este caso consiste en seleccionar las cadenas más aptas, es decir, las que más se acercan al resultado buscado. Cada mutación consiste en el cambio al azar de una letra. Las cadenas experimentan pequeñas mutaciones. Hay que observar que si las mutaciones fueran grandes, el resultado no ser¡a tán bueno.
Palabras y Frases
Nota importante: Si la frase que se ha de buscar posee palabras que no existen en el diccionario, se introducirán automáticamente en él, de forma que cualquier palabra, aunque sea inventada, siempre existirá en el diccionario.
Este es un Algoritmo Genético donde se trata de adivinar una frase que ha introducido el usuario. El Algoritmo Genético es el encargado de proponer distintas frases como solución al problema. Una Función de Evaluación dirigirá la evolución de la población de frases. Para ello, La Función de Evaluación dirá hasta qué punto es correcta una frase, es decir, evalúa la utilidad de la entidad. En este caso, la bondad de una frase se calcula comparando cada palabra con la palabra correspondiente en la frase buscada, según su posición.
Con una función de evaluación así, la única utilidad de este algoritmo es ilustrar el funcionamiento de los algoritmos evolutivos. Sin embargo, este mismo código se puede reutilizar facilmente para ser aplicado a otros problemas, probablemente realizando cambios en los tipos de datos manejados y sustituyendo la Función de Evaluación por otra que refleje el problema concreto que se quiera resolver.
Nos 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 devuelve un valor entre 0 y 1. A este número se le llama peso. 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 Algoritmo Genético funciona de la siguiente forma. En primer lugar, se generan varias frases al azar, por ejemplo, 40 frases, combinando palabras tomadas aleatoriamente de un dicciónario.
Después se evalúan estas frases mediante la Función de Evaluación. 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 surgan 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.
Pero en un algoritmo genético existe otro componente. Si en el conjunto inicial de 40 frases no existen las palabras que componen la frase buscada, por muchas combinaciónes 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 dicciónario 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.
Un Algoritmo Genético 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.
El aumento de variedad se consigue con las mutaciones, pero esto no suele bastar.
Opciones que permite el programa para aumentar la variedad- 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. Caso A)
- Selecciónar, además de la población con mayor peso, una fracción de la de menor peso. Caso D)
- 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. (Elección de padres al azar)
- Hacer que si se reproducen dos cadenas iguales, los hijos sean mutaciones en todos sus elementos (Padres idénticos producen mutaciones)
- 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. (Frecuencia de mutación acumulada)
Otros aspectos a tener en cuenta- Trabajamos con azar, y una sola ejecución no es muy significativa
- 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.
- El tamaño de la población es constante y puede ser 40, 80, 160 ó 320. El número de nacimientos es igual al de defunciones.
- El numero maximo de palabras del dicciónario es 2086.
- La frase a buscar es de una longitud máxima de 1000 palabras.
- Para reproducirse, se toman siempre dos frases como progenitores.
- En cada nacimiento nacen el número de frases necesarias para que la población se mantenga constante.
- Es posible que una frase no muera nunca. Las frases seleccionadas no solo se reproducen, sino que además no mueren.
Este programa y sus ficheros fuente son gratis y de libre distribución. El código fuente está disponible y puede ser modificado, distribuido, o utilizado en otros programas citando al autor o autores.
Bajar código fuentePara obtener la última versión del programa, para sugerir posibles ampliaciones, si se detectara algún error en la programación o si desea comunicar que se va a ampliar o utilizar una parte o todo este programa, no dude en ponerse en contacto con el autor en la dirección: E-mail
Pulse aquí para bajar el código fuente.
[ Home Page Castellano | Home Page English ]
