http://www.redcientifica.com/gaia/

http://www.redcientifica.com/gaia/ceno_c.htm


Notas sobre Computación Evolutiva

Manuel de la Herrán Gascón

Indice:


¿Qué son?

"Tenemos un problema ¡Que fastidio! Bueno, vamos a intentar solucionarlo. ¿Sabemos cómo hacerlo? No. entonces, a probar. ¿Podemos generar varias soluciones válidas a ese problema? Ya, claro que podemos, pero van a ser todas muy malas soluciones. Bueno, no importa. Las generamos: 40, 100, las que sean. ¿Alguna es mejor que otra? Todas son malas, pero unas son menos malas que otras. Cogemos las mejores, las otras las eliminamos. ¿Y ahora qué? Bueno, las podemos coger de dos en dos y mezclarlas a ver si sale algo bueno ¿Sí? Bueno, a veces funciona. Vamos a hacerlo otra vez. Y otra. También podemos mezclarlas de otra forma. ¡Oye esto se estanca, ahora son todas iguales! Entonces, vamos a coger de vez en cuando alguna de las malas, no sólo de las buenas. ¿Y si hacemos pequeños cambios al azar en pequeñas zonas de alguna solución, a ver si alguna da en el clavo? Vale... ¡Oye, esto está mejorando!"

Dentro de los paradigmas de aprendizaje automático, los algoritmos genéticos se presentan como uno de los más prometedores en el camino hacia la inteligencia artificial. Actualmente han demostrado su validez en múltiples áreas de aplicación, y en cualquier caso, poseen un gran interés por la evidente analogía que convierte al programador en un creador de "vida".

Los pasos que realiza un algoritmo genético son:

1.- Se genera un conjunto de 1-N soluciones válidas al problema. Valores típicos de N son desde 1 hasta 200. Cada una de estas entidades representa una solución distinta a un mismo problema. Esta(s) entidades se pueden generar al azar. También se pueden generar a partir de soluciones ya conocidas del problema, que se pretendan mejorar, o mediante posibles "trozos de soluciones" (más conocidos como bloques constructores), es decir, con lo que creemos que pueden ser elementos componentes de la solución final aunque no sepamos cómo combinarlos.

2.- Se evalúan las soluciones existentes, y se decide, en función de esta evaluación, dos cosas. Por una parte, cuáles soluciones van a sobrevivir y cuáles no; y por otra, cuáles se van a reproducir y cuáles no. En el caso de reproducirse, se especifica la potencia reproductora de la solución, de forma que es posible decidir que unas soluciones se reproduzcan más que otras.

3.- Tal como se ha establecido en el paso anterior, se eliminan ciertas soluciones y se mantienen otras, y se efectúa la reproducción o recombinación de genes (normalmente por parejas) de las entidades existentes. Por ejemplo, se realizan cruzamientos de patrones a partir de cierto punto elegido al azar, de forma que los nuevos patrones posean un segmento de cada uno de los progenitores.

4.- Se efectúan mutaciones (cambios al azar en los genes) de los nuevos patrones, según una tasa determinada. Algunos estudios aconsejan realizar mutaciones también sobre los padres.

5.- Se continúa en el paso 2 hasta que se cumpla el criterio de parada, que puede ser por ejemplo, que el peso o fitness de la mejor entidad supere cierto valor.

[ Volver al Indice ]


Dejar que sea el ordenador quien haga el trabajo

Los Algoritmos Genéticos (AG) se pueden entender como una estrategia más de búsqueda, al igual que las conocidas "a lo Ancho", "en Profundidad", Escalar-Colinas, Mejor-Primero, y A*. El algoritmo selecciona una serie de elementos tratando de encontrar la combinación optima de estos, utilizando para ello la experiencia adquirida en anteriores combinaciónes, almacenada en unos patrones genéticos. Sin embargo, en este caso, las posibilidades de esta metodología transcienden de la búsqueda heurística, debido a una razón de peso: el algoritmo no trabaja Top-Down, sino Bottom-Up: es decir, no es necesario disponer de un conocimiento profundo del problema a reslover, para que éste pueda ser descompuesto en sub-problemas, sino que se parte de estructuras simples que interactúan, dejando que sea la evolución quien haga el trabajo. Únicamente basta con ser capaces de identificar cualitativamente en que casos los patrones se acercan o se alejan de la solución buscada, para que el sistema se perfeccione automáticamente, desarrollando sus propios comportamientos, funcionalidades y soluciones. Ciertamente, se puede decir con humildad que esta técnica ha demostrado ya su relativa utilidad, en la vida biológica, creándonos a nosotros mismos.

[ Volver al Indice ]


Las bases de los Algoritmos Genéticos: Lucha por la supervivencia en un ambiente de escasez

Dada la elevada tasa -geométrica- de reproducción de todos los seres orgánicos (Malthus), su número tiende a crecer a ritmo exponencial, y dado que los alimentos, espacio físico, etc. no lo hacen en la misma proporción, y mientras esto ocurra, nacerán muchos más individuos de los que es posible que sobrevivan, y en consecuencia, como sea que generalmente se recurre a la lucha por la existencia, ya sea con individuos de la misma especie o de especies distintas, o simplemente con el entorno, intentando modificar sus características adversas, se desprende que un individuo, si actúa de un modo provechoso para él, tendrá una mayor probabilidad de sobrevivir, y será seleccionado naturalmente.

La teoría de la selección de las especies (Darwin) sostiene que aquellos individuos de una población que posean los carácteres más ventajosos dejarán proporcionalmente más descendencia en la siguiente generación; y si tales carácteres se deben a diferencias genéticas, que pueden transmitirse a los descendientes, tenderá a cambiar la composición genética de la población, aumentando el número de individuos con dichas características. De esta forma, la población completa de seres vivos se adapta a las circunstancias variables de su entorno. El resultado final es que los seres vivos tienden a perfecciónarse en relación con las circunstancias que los envuelven.

[ Volver al Indice ]


La genética, la reproducción sexual y las mutaciones

En un algoritmo genético se establece una relación entre cada una de las posibles soluciones a un problema, y un código genético, patrón o cadena de información, que de alguna forma las representa. Este código genético podrá sufrir mutaciones, transmitirse a la descendencia y combinarse con otros mediante reproducción sexual. El código es seleccionado naturalmente decidiendo si se mantiene o no en el sistema. También puede ser evaluado cuantitativamente, asignándole un peso.

En la reproducción sexual, la información genética de ambos progenitores se combina generándose el código genético de un nuevo individuo. Además, existe una cierta probabilidad de que en este proceso se produzca alguna mutación (variación al azar) del material genético resultante.

La reproducción sexual tiene la ventaja de que combina dos (o más) bloques de genes que ya han probado su efectividad, de manera que es posible que el patrón resultante herede las características deseables en ambos progenitores, en cuyo caso será seleccionado, aumentando la existencia de dichas características en la población. Precisamente, más del 95% de las especies vivas en el planeta poseen reproducción sexual.

Lo más sencillo es que el patrón represente directamente una solución. Por ejemplo, si la solución que busco es la secuencia de acciones con la que se consigue un determinado objetivo, el patrón 234, 523, 12, 765, 256 podría representar dicha secuencia de acciones, si se ha asignado previamente a cada número una acción.

Sin embargo, muchas veces esto no es posible, o no se encuentra utilidad en la combinación de las cadenas generadas (por ejemplo, si la si combinación de dos cadenas de información interesantes genera normalmente una cadena con un peso bajo), de forma que la reproducción sexual -por combinación- no representa ninguna ventaja. La solución es que las cadenas no representen directamente la solución buscada, sino que lo hagan de forma indirecta.

En la vida biológica ocurre algo así: en realidad, los genes, más que determinar directamente las características que definen un nuevo individuo, 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. Algunos aspectos fenotípicos, como el color de los ojos, pueden determinarse genéticamente de una forma bastante directa, pero la mayoría de las características de un ser vivo, como el tipo de sangre, el peso o la altura, no tienen una traducción genética tán sencilla, si bien es cierto que también muchas de las características de un ser vivo, como el peso, están influidas por el ambiente (por ejemplo, por la dieta).

De la misma forma, los patrones que nosotros creamos no siempre podrán representar directamente la solución buscada. Por ejemplo, en el problema del viajante, que debe recorrer varias ciudades hasta volver al punto de partida incurriendo en el mínimo coste, si las cadenas representan secuencias de ciudades en el orden en que se recorren, la probabilidad de que mediante la combinación de dos cadenas válidas, a partir de un punto al azar, se genere una cadena válida es baja: mucho más lo será el que la cadena herede las cualidades positivas de sus progenitores.

En estos casos, deberemos cambiar el planteamiento de trabajo, y hacer que el patrón no sea la solución en sí misma, sino "algo" que lo provoque, como un conjunto de métodos, directrices, reglas, etc de búsqueda de la solución, que sean fácilmente combinables. Rizando el rizo, ésta patrón puede ser el conjunto de parámetros que definen el modo de ejecución de otro algoritmo genético, con lo que tendremos AGs jerárquicos.

[ Volver al Indice ]


Limitaciones de la vida biológica y la fuente de la eterna juventud

Parece existir consenso en la comunidad científica en cuanto a que la información genética fluye únicamente en una dirección: desde los genes hacia afuera. Es decir, los carácteres adquiridos a lo largo de la vida no son heredados, ya que no existe ruta alguna que alcance y modifique los genes creados en la concepción. En la vida biológica no es posible la transmisión genética de las características adquiridas o aprendidas, pero esto sí es posible en la vida artificial. ¿Existirá alguna razón por la que podría no ser beneficioso? En cualquier caso nosotros los programadores no estamos obligados a observar dicha norma.

Existen otras muchas limitaciones en la vida natural o húmeda, que no existen en la vida seca: los seres de vida artificial no envejecen. Un patrón se puede mantener indefinidamente, sin que sus cualidades se deterioren.

[ Volver al Indice ]


Los fantásticos mutantes

Aunque es poco probable que un cambio cualquiera en un gen sea beneficioso, las mutaciones producen varias ventajas: dificultan el estancamiento de la población aumentando la variedad, de manera que ante un cambio brusco del entorno, la comunidad pueda adaptarse a la nueva situación; además, permiten la generación de cualquier segmento de patrón, de manera que si en el conjunto inicial de patrones no se encuentran todos los elementos necesarios para formar el óptimo, sea posible llegar a ella.

En algunos casos puede ocurrir que el patrón buscado pueda formarse fácilmente a partir de combinaciónes de patrones que no se consideran muy ventajosas. El algoritmo genético debe permitir la existencia de estos patrones. Este es uno de los principales problemas de los AG, e incluso de la teoría de la evolución: ¿Cómo han podido generarse gradualmente órganos complejos, como las plumas para el vuelo, si sólo el órgano completamente funcional es útil al individuo? No siempre es fácil explicar todos los rasgos que presenta un organismo con un mecanismo adaptativo.

[ Volver al Indice ]


Selección Natural y Selección Artificial

La principal diferencia conceptual entre la selección natural (o que se produce sin intervención del hombre), y la selección artificial que nosotros establecemos nuestras granjas o en nuestros programas, es que la selección natural no es propiamente una selección. Nosotros podemos seleccionar para la reproducción los seres que más nos interesan, ya sean las vacas más lecheras o los agentes software que mejor resuelven un problema. En cambio, en la naturaleza no existe -en principio- una inteligencia exterior que determine la dirección de la evolución. Y sin embargo la evolución sí se produce. Si efectivamente, no existe algo o alguien que controle la evolución de la vida en nuestro planeta, entonces nosotros mismos seríamos el ejemplo de un principio básico y universal: que la vida, la inteligencia, la consciencia y quién sabe qué otros tipos de complejidad en el futuro, son sucesos inherentes, inevitables y espontáneos de nuestro universo. A esto también se le ha llamado Darwinismo Universal, y supone que toda vida, en cualquier lugar, habría evoluciónado por medios darwinianos.

El programa Tierra es un ejemplo de cómo agentes software pueden evolucionar sin que sea necesaria una selección dirigida por una entidad externa. Tanto en este programa como en otros, existe una serie de componentes software de algún tipo capaces de reproducirse y sufrir mutaciones. En un algoritmo genético, los agentes deben resolver un problema particular, pero en Tierra los agentes no hacen nada más que reproducirse. El espacio de memoria limitado produce una selección natural, ya que sólo las mejores entidades podrán dejar descendencia en él. La existencia de pequeñas mutaciones aleatorias basta para generar agentes con características muy complejas, capaces de invadir o cooperar con otros agentes. Después de estudiar una de estas simulaciones, parece lógico suponer que en nuestro planeta haya podido suceder algo parecido. Está bastante extendida la idea de que las primeras entidades replicantes surgieron al azar, a partir de la combinación de elementos, y que la selección hizo el resto. Sin embargo Thomas Ray decidió que su programa comenzara con un primer agente capaz de copiarse a sí mismo, sin pretender que esta autocopia se produjera espontáneamente, como hizo Steen Rasmussen. Se plantea la cuestión de sí la probabilidad de aparición de los componentes básicos de la vida es demasiado baja para un solo planeta. Fred Hoyle sugiere la existencia de un bombardeo de material genético del exterior, -ya sea con o sin entidad consciente detrás de ello-, lo que daría un mayor margen, al haber podido surgir este "primer replicante" en cualquier otro mundo. Además, esto solucionaría algunos otros problemas, como los aparentes "saltos de complejidad" evolutivos. Es sorprendente la aparición de órganos complejos como los ojos, que difícilmente han podido surgir de una evolución gradual si no proporcionan ninguna ventaja al individuo hasta que no se encuentran formados por completo. El lamarkismo, es decir, la transmisión genética de los carácteres adquiridos, está resucitando, y Máximo Sandín ofrece otra interesante explicación a todas estas cuestiones mediante infecciónes de tipo vírico capaces de afectar rápidamente a gran parte de la población.

En mi opinión, la cuestión más apasionante de las difícilmente explicadas por el darwinismo es la de la aparición de sentimientos de placer y dolor en los seres vivos. Nosotros podemos asignar a cada agente una variable con un número llamada placer o dolor, pero no es necesario que la entidad tenga realmente esas sensaciones para que se comporte como si las tuviera. Tal vez podamos construir algún día robots que se comporten como seres humanos, pero ¿Podremos hacer que sientan? Y aunque pudiésemos, ¿Por qué hacerlo? ¿Por qué lo ha hecho la naturaleza con nosotros? Una cosa es la vida artificial como imitación de los procesos propios de la vida, y otra muy distinta y a la que aún no se ha llegado es la recreación de su esencia, (o a la demostración de que esta no existe). Las teorías sobre la vida y la evolución son difícilmente demostrables, y el debate es intenso. Podría parecer que estas cuestiones sólo atañen a los biólogos y filósofos, pero no es así. Recordemos que se trata de crear inteligencia en nuestros ordenadores imitando la forma en que lo hizo la naturaleza. Sin embargo, no podemos hacerlo sin más. Debemos captar al máximo la esencia de todo el proceso para evitar que nuestro ordenador tarde millones de años en llegar a la solución esperada.

[ Volver al Indice ]


¿Cuándo se pueden aplicar los Algoritmos Genéticos?

En primer lugar, en el problema a resolver, la meta ha de poder ser observada en grados cualitativamente comparables. Por otra parte, las principales dificultades a la hora de implementar un algoritmo genético son: Las condiciones que debe cumplir un problema para ser abordable por algoritmos evolutivos son:

En el algoritmo podremos variar a nuestro gusto:

Los algoritmos genéticos se pueden completar (y complicar) con multitud de aspectos conocidos de la vida biológica y otros incluso no existentes en la naturaleza, sin más límite que la imaginación, entrando en el mundo de la Vida Artificial, donde se pueden observar comportamientos sociales complejos.

[ Volver al Indice ]


¿Cómo programar Algoritmos Genéticos?

Hay dos aspectos importantes de la programación de Algoritmos Evolutivos que suponen ciertas diferencias con respecto a la programación habitual.

El primero es que es muchísimo más difícil detectar errores en la programación, ya que gran multitud de las líneas de código se utilizarán únicamente como mejoras sobre un esquema inicial de evolución, y en muchos casos el programa funcionará e incluso ofrecerá buenos resultados ejecutando funciones incorrectas, o que al menos no hacen lo que nosotros creemos que hacen.

Esto se puede resolver con más programación. Una posible solución es establecer dos modos de ejecución del algoritmo (Modo "Normal" y Modo "Detección de errores") de forma que en el segundo modo se ejecuten ciertas comprobaciones sobre los procesos ejecutados, realizando las pruebas en modo "Detección de errores" y distribuyendo la aplicación en modo "Normal". Esto se puede implementar mediante directivas de compilación o mediante una variable global que indique el modo de ejecución.

Pero hay aspectos mucho más interesantes. Si algo se aprende programando Algoritmos Evolutivos es que las ideas geniales no siempre lo son. Ya he comentado que gran multitud de líneas de código consisten en mejoras sobre un esquema inicial de evolución. Es muy corriente la existencia de parámetros que aunque disminuyen el número de ciclos necesarios para llegar al tipo de entidad que buscamos, en la práctica no son rentables dado el incremento de la duración de los ciclos.

Como en el caso anterior, la solución es todavía más programación. Cuando programemos una "idea genial" es interesante contemplar siempre en el programa ambas opciones, es decir, la inclusión o no de esa idea, y comparar los resultados en diversas situaciones. Aquí es donde está el verdadero problema, ya que opciones que pueden ser perjudiciales en ejecuciones cortas podrían ser muy útiles en ejecuciones más largas (problemas más complicados), y precisamente estas pruebas no siempre es posible hacerlas.

Lo mismo ocurre en la naturaleza: las "ideas geniales" para resolver problemas ecológicos pueden no serlo (y aquí se muestra una vez más la utilidad de las simulaciones por ordenador). En Australia se intentó combatir una plaga de conejos inoculándoles la enfermedad de la mixtomatosis. La población de conejos disminuyó drásticamente, pero al cabo de un tiempo se llegó a la misma población de conejos... ahora todos resistentes a la mixtomatosis. ¿Se produjo entonces una mutación justo cuando se necesitaba? Probablemente no, la mutación existía ya, la posibilidad estaba, latente, en algunos de los conejos, que rápidamente extendieron sus genes.

Estos problemas tienen además una analogía y una "moraleja" que yo considero fundamental para el estudio de la evolución: en la Computación Evolutiva encontramos que reflexiones e hipótesis que a todas luces parecen ciertas, de una total evidencia para nuestra mente, resultan ser completamente falsas cuando las programamos. Parece que ocurre lo mismo trasladado al terreno de la evolución de las especies en la naturaleza, incluyendo la humana. El Lamarkismo o la transmisión de los carácteres adquiridos es una hipótesis con una lógica aplastante; y sin embargo resultó ser falsa. Bien, pues cuando queda establecido sin lugar a dudas que el lamarksimo no existe, surgen voces críticas que también con gran coherencia argumentan lo contrario. Esto es todavía más importante en aspectos como la cooperación. En mi opinión, en la Evolución (como en todo campo de estudio, pero tal vez aquí más que en ninguna otra parte), es muy aconsejable mantener un fuerte escepticismo, extraer conclusiones, por supuesto, pero sin olvidar nunca las otras alternativas.

[ Volver al Indice ]


Tipos de Algoritmos Evolutivos

La Computación Evolutiva (CE) es un término relativamente nuevo que intenta agrupar un batiburrillo de paradigmas muy relacionados cuyas competencias no están aún muy definidas. Hasta hace poco era común hablar de Algoritmo Genético (AG) en general, en vez de identificar diferentes tipos de CE, ya que el resto de los algoritmos se pueden interpretar como variaciones o mejoras de los algoritmos genéticos, más conocidos. En un Algoritmo Genético los elementos de las cadenas (genes) son típicamente bits, y en ciertos casos, valores numéricos o strings. Por su parte, en las Estrategias Evolutivas los elementos de las cadenas son valores reales que actúan como reglas que definen cómo va a actuar el individuo ante cierta situación, y en la Programación Genética son instrucciónes en un lenguaje de programación. Simulated Annealing se puede considerar una simplificación de los AG cuyo origen está en los procedimientos físicos de solidificación controlada. Los Clasificadores Genéticos solucionan problemas de reconocimiento de patrones mediante un entrenamiento basado en ejemplos, almacenando en las cadenas información que relacione los datos de entrada y la salida deseada. Finalmente, por razones conceptuales a mí me gusta considerar la Vida Artificial como un superconjunto de todas estas técnicas, aunque en la práctica constituyen disciplinas estancas.

Las nuevas ciencias siempre pasan por una fase inicial de desconcierto e inconsistencia hasta llegar a unas convenciones aceptadas por todos. Más o menos la clasificación aceptada en nuestros días es

El enfoque subsimbólico de la IA se carácteriza por crear sistemas con capacidad de aprendizaje. Éste se puede obtener a nivel de individuo imitando el cerebro (Redes Neuronales), o a nivel de especie, imitando la evolución (CE)

Aunque existen otros esquemas, por lo general, estos programas comienzan con una fase de inicialización de las entidades y su entorno, y seguidamente ejecutan repetidamente ciclos dentro de los cuales podemos distinguir tres etapas:

En realidad las dos primeras fases se pueden fundir en una, ya que no es estrictamente necesario asignar a cada entidad un peso, sino simplemente saber cuáles son mejores que otras, pero asignar pesos suele ser lo más cómodo. También podemos combinar la segunda y la tercera generando las nuevas entidades únicamente en la zona de memoria donde se encuentran los agentes a eliminar, y mantener así la población constante. En cualquier caso, siempre existirá alguna forma de evaluación, selección y reproducción. Cada uno de estos procesos se puede realizar de muchas formas distintas, independientemente del problema que se esté resolviendo.

Hay otra forma de enfocar estas aplicaciones. El planteamiento de la Computación Evolutiva es simular tan sólo los aspectos de la naturaleza que sean útiles para resolver problemas, pero no se pretende mantener una congruencia con el mundo real. Es por ello que los algoritmos de Computación Evolutiva se enfocan, por comodidad, desde el punto de vista del proceso. Existen unos operadores (como el cruce y la mutación) que son aplicados en serie a todas las entidades. Es decir, primero se evalúan todas las entidades, después se seleccionan las mejores, más tarde se reproducen; y llegados a este punto se vuelven a evaluar repitiéndo el ciclo.

El enfoque de la Vida Artificial es distinto, y muchas veces en Vida Artificial precisamente lo que se pretende es respetar al máximo la metáfora con el mundo real. Según este planteamiento, es preferible programar estas simulaciones desde el punto de vista de las entidades (los datos), siendo la propia entidad la que "decide" en cada momento cómo actuar. Es decir, primero se ejecuta durante unos instantes la primera entidad, luego la segunda, etc. hasta la última, y se vuelve a comenzar por la primera. Los dos estilos de programación pretenden simular un paralelismo: el primero es un paralelismo de procesos, el segundo es un paralelismo de entidades. El ideal sería disponer un procesador para cada entidad (paralelismo de entidades real) o un procesador especializado en cada proceso (procesador evaluador, procesador selector y procesador reproductor). A falta de ello, según el enfoque de la Vida Artificial, el programa podría repartir el tiempo de ejecución entre todas las entidades. En ese caso, la existencia de diversas capacidades de reproducción de un algoritmo de computación evolutiva sería equivalente a modificar de alguna forma las posbilidades del agente: cambiando la velocidad a la que se mueve, modificando la probabilidad de un contacto sexual con éxito reproductivo, o simplemente, asignando distintas ranuras de "tiempo de ejecución" a cada agente por cada ciclo, de forma que para un mismo periodo de tiempo real de simulación, los agentes disponen.

[ Volver al Indice ]


Opciones de un Algoritmo Evolutivo

En la siguiente tabla se resumen algunas opciones de un algoritmo evolutivo. Podemos idear muchas más. En general se trata de distintas formas de producir, o bien una convergencia más rápida hacia una solución, o bien una exploración más a fondo del espacio de búsqueda. Ambas cosas son deseables y contradictorias, por lo que se ha de llegar a un compromiso. Este compromiso es lo que antes he llamado cooperación. Por supuesto que todo esto no son más que metáforas. Se requiere de una fuerza conservadora (explotación-egoísmo), que beneficie a los mejores agentes, es decir, a los que mejor resuelvan nuestro problema. Esto es evidente, pero no basta. También es necesaria una fuerza innovadora (exploración-altruismo), que permita la existencia de agentes muy distintos, aún cuando su peso sea menor. Así se puede obtener la variedad suficiente para evitar una población estancada en un máximo local, y permitir la resolución de problemas cambiantes o con varios máximos. Esto ocurre de forma espontánea en la naturaleza por ser algo inherente a cada entidad, que puede ser seleccionado, pero resulta más cómodo programarlo de forma externa, es decir, haremos que nuestro programa seleccióne para la reproducción "los agentes buenos", pero también "unos cuantos de los malos" para mantener la variedad.

Opciones Generales
- Número de entidades.
- Número de elementos (genes, reglas) por cada agente.
Método de Evaluación: Asígnar un peso
- Desordenar las entidades antes de evaluarlas
- Diferentes formas de modificación de los pesos después de la evaluación. Por ejemplo, el peso de una entidad se puede calcular independientemente de las demás entidades, o se puede modificar posteriormente este valor, disminuyendo el peso si existe otra entidad muy parecida, analizando para ello un cierto subconjunto de la población vecina.
Método de Selección: ¿Quién muere? ¿Quién se reproduce?
- Con o sin reemplazamiento
- Método de la ruleta
- Método de los torneos
- Selecciónar el n% mejor y el m% peor
Método de Reproducción: Generar y mutar nuevos hijos - Los padres pueden tomarse por parejas o en grupos más numerosos, elegidos al azar o en orden de pesos
- En el caso de detectar que los progenitores son muy parecidos, se puede realizar una acción especial, como incrementar la probabilidad de mutación
- Las entidades pueden comunicar a otras su conocimiento, ya sea a toda o a una parte de la población, directamente o a través de una pizarra, (una especie de tablón de anuncios)
- Método de recombinación de genes: se puede tomar genes de uno u otro progenitor al azar, en un cierto orden, con uno, dos o más puntos de corte, etc.
- Tasa de mutación variable
- Fijar una tasa de mutación diferente para cada individuo o incluso para cada gen
- Hacer que sea más probable que se produzca una mutación en un gen si en su vecino ya se ha producido
- Sustituir por mutaciones genes sin utilidad, como reglas incorrectas o repetidas
- Tipos de mutaciones

Los tipos de mutaciones requieren de una mayor explicación. Cuando los genes son bits, una mutación consiste en invertir un bit, pero ¿cómo mutar genes cuando cada gen puede tomar mas de dos valores? Supongamos que tenemos un problema con tres variables de 8 bits cada una. Tendríamos cadenas como:

10001000-0101011111-11101110

Vamos a suponer que es probable que existan zonas de valores buenas y malas; es decir, que si el 7 es un buen valor y el 200 malo, será probable que también el 8 sea bueno y el 199 malo. Sería interesante que las mutaciones nos permitiesen movernos (cambiar de valor) lentamente y con exactitud si estamos en la zona buena, pero también rápida y bruscamente por si acaso nos encontráramos en la mala. Esto lo podemos conseguir precisamente cambiando un bit al azar, ya que nos movemos lentamente cambiando bits de la parte derecha, y rápidamente con los de la izquierda. En cambio, si la mutación consistiera en cambiar el valor de toda una variable por otro cualquiera, teniendo todos la misma probabilidad, podremos movernos rápidamente, pero no lentamente (al menos, con una probabilidad baja), con lo que perderíamos valores interesantes. Si las mutaciones consistieran en incrementar o restar uno de forma circular, podríamos movernos lentamente, pero no rápidamente, con lo que costaría mucho salir de la zona mala. En definitiva se trata de, dado un valor, definir la probabilidad de pasar a cada uno de los valores restantes.

Hemos supuesto que existen zonas de valores buenas y malas. Si esto no se cumpliera podríamos simplemente "incrementar uno" de forma circular, para recorrer todos los valores cuanto antes. En general se observa que las mutaciones a nivel de bit son las más adecuadas, aunque no siempre ocurre así. En cualquier caso, cuando combinemos dos cadenas deberemos actuar a nivel de variable, y combinar variables completas. De lo contrario estaríamos generando multitud de mutaciones simultáneas, rompiendo por cualquier lugar valores que pueden ser valiosos.

Programas autoconfigurables

¿Qué opciones son las buenas? Tal vez sea posible determinar a simple vista si una elección es adecuada, pero en la mayoría de los casos será necesario un tedioso proceso de prueba, ya que la bondad de unas puede depender de la elección de otras. Si algo se aprende programando algoritmos evolutivos es que las ideas geniales no siempre lo son. Es muy corriente la existencia de parámetros que aunque disminuyen el número de ciclos necesarios para llegar al tipo de entidad que buscamos, en la práctica no son rentables dado el incremento de la duración de los ciclos.

Ejecutar todas las posibles combinaciónes de opciones es inconcebible ¿No será posible analizar varias en un único algoritmo, en diferentes momentos? ¿Y que tal analizar varias opciones simultáneamente, en fracciones separadas de la población? Es decir, ¿Podemos crear algoritmos evolutivos autoconfigurables? Para responder a estas preguntas es interesante agrupar todos los aspectos y opciones en cuatro categorías, según la tabla.

Tipo gen Los aspectos de tipo gen serán aquellos que, como los genes, son diferentes dentro de un mismo individuo.
Tipo individuo Los aspectos de tipo individuo son aquellos que se mantienen iguales en un mismo individuo, pero difieren de unos agentes a otros.
Tipo isla Los aspectos de tipo isla son aquellos que son iguales para un subconjunto de individuos; de más de uno, pero sin llegar al total.
Tipo población Los aspectos de tipo población son los que deben ser iguales para toda la población.

Las opciones o aspectos de tipo gen pueden probarse introduciéndolos como parte de cada uno de los genes, dentro de cada uno de los genes. Si se quiere, se puede pensar en una matriz de dos dimensiones más que en una cadena de genes. Vamos a verlo en el caso de un programa que aprende a jugar al tres en raya. Cada uno de los genes es una regla que dice cómo jugar ante determinada situación. Antes de realizar un movimiento, el agente comprueba qué reglas puede usar y elige una de ellas. ¿Cómo elegirla? Podríamos pensar en asociar inicialmente a cada regla una prioridad arbitraria fija, y elegir la de mayor prioridad. Otra forma sería asignar a cada regla un peso que se incrementase cada vez que dicha regla fuera usada en una partida ganada, y aplicar la regla que en más victorias haya participado hasta el momento. Para llevar a la practica cualquiera o las dos opciones combinadas, bastará con incluir la información como parte de cada gen. Si antes cada gen era una regla, ahora cada gen será una regla, más un valor de prioridad, más un peso. Otra opción de tipo gen sería asignar una probabilidad de mutación distinta para cada elemento de la cadena, de forma que los genes, después de ser heredados, tengan diferentes probabilidades de mutarse. Si en un determinado momento, cierto valor de un gen se muestra como muy útil, puede ser interesante que su probabilidad de mutación disminuya, y viceversa.

Los aspectos de tipo individuo pueden probarse introduciéndolos como si fueran nuevos genes, a continuación de los que ya existen. La tasa de mutación, aunque suele ser igual para toda la población, y hemos visto que podría ser incluso diferente para cada gen, podría también ser distinta para cada individuo, de forma que los hijos de ciertos agentes tengan mayor probabilidad de poseer mutaciones. Por ejemplo, en el tres en raya, una entidad estará compuesta por un conjunto de reglas más una probabilidad de mutación. Este valor se podrá heredar y mutar, y si es útil, se verá seleccionado, igual que una regla cualquiera. Antes hemos hablado de asignar una prioridad a cada regla. La prioridad asociada a cada regla es un aspecto de tipo gen, pero la decisión de asociar o no prioridades a las reglas es un aspecto de tipo individuo, que debe afectar obligatoriamente a todas sus reglas.

Probar e implementar aspectos de tipo isla va a ser más complicado. Por ejemplo, supongamos que queremos comprobar que ocurriría si permitimos a nuestros bichos compartir su conocimiento, es decir, transmitirse información genética en forma de infección vírica, tal como relata Máximo Sandín. Podríamos crear varias islas o sub-grupos de agentes con distintas opciones, manteniéndolos separados por una barrera de algún tipo que no permita el contacto de unos con otros. Más tarde podríamos comparar el conocimiento obtenido en cada isla o incluso juntar de vez en cuando a algunos o a los mejores de cada grupo para la reproducción. Las opciones de tipo isla pueden ser evaluadas automáticamente sin modificar mucho el algoritmo, ya que es de esperar que los grupos con peores opciones se extingan. La idea general es que tanto para grupos como para individuos o genes, lo bueno sobrevive y lo malo perece. Para crear barreras, podemos definir tipos de especies distintas que sólo son capaces de reproducirse entre sí, poseyendo cada una de ellas, por ejemplo, distintos métodos de recombinación de genes, con uno, dos o más puntos de corte en el cruzamiento, o incluso concibiendo de forma distinta los puntos de comienzo y fin de las unidades mínimas que se recombinan (genes). Curiosamente, en este caso, el propio método de implementación de las barreras (tipos de reproducción incompatibles) es precisamente aquello que estamos probando. Para implementarlo podemos añadir un gen especial a cada agente de forma que sólo los agentes con el mismo valor en dicho gen sean capaces de recombinarse entre sí. Cada valor corresponderá con una opción diferente. Para probar más de una deberemos poner varios de estos genes, y obligar a una coincidencia en todos ellos.

Las opciones de tipo población sólo pueden probarse ejecutando algoritmos en paralelo. Estas opciones son las más generales, como el número total de agentes o el número de reglas que tiene cada individuo. Otro ejemplo de tipo población es el hecho de ajustar los pesos de los agentes, de forma que si ya existe otro agente parecido al que acaba de nacer, se disminuye el peso del nuevo agente. Esta opción no puede ser aplicada sólo a una parte la población, ya que se vería en obvia desventaja. Evaluar opciones de tipo población es lo más complicado. Deberemos crear algoritmos independientes y compararlos, por ejemplo, en el tres en raya, provocando una partida entre las mejores entidades de cada una de las simulaciones, es decir, creando otro plano superior de juego.

Algoritmos jerárquicos

Voy a cambiar de punto de vista para analizar las jerarquías dentro de los algoritmos evolutivos. En un algoritmo genético, la reproducción, selección, mutaciones, asignación de pesos, etc. se desarrollan a un sólo nivel o plano. Sin embargo, en el caso del tres en raya, existen varios planos.

En el plano más elevado, juegan el ordenador contra el hombre. Este juego puede interpretarse como un algoritmo evolutivo reducido a su mínima expresión, con una población de dos individuos, donde el algoritmo termina al finalizar la partida. En este tipo de problemas tienen bastante éxito los paradigmas en los que el ordenador trata de aprender observando el juego humano, pero no es este el caso. Para aprender, el ordenador crea un segundo nivel de juego, donde muchas entidades jugarán por parejas. Aquella entidad que más partidas gane será la que represente al ordenador en el juego contra el hombre. Pero todavía se puede hablar de un tercer nivel, ya que dentro de un mismo agente, cada una de las reglas puede poseer también un peso, y aunque las reglas no se reproducen combinando sus elementos (podrían hacerlo), es posible sustituir algunas cada cierto tiempo.

Ya que la entidad de nivel superior ha creado un sub-mundo o plano donde juegan varias sub-entidades, gracias a las cuales es capaz de aprender por su cuenta antes de jugar contra el hombre, estas sub-entidades podrían a su vez crear otros planos que les proporcionasen conocimiento, hasta que llegue el momento de jugar "de verdad". Es decir, una entidad, al igual que jugar, o reproducirse, podría también tener una acción que podríamos llamar "pensar" y que consistiera en experimentar partidas hipotéticas (hipotéticas para la entidad superior; a la inferior le parecerán las suyas tan reales como a cualquier otra), creando "mundos virtuales", de la misma forma que las personas imaginamos o creamos hipótesis para prever los acontecimientos.

Este sería además un esquema donde implementar el algoritmo minimax típico de los juegos, donde el agente evalúa posibles movimientos propios y del contrario a varios niveles de profundidad. Podemos combinar este tipo de jerarquías con las relativas a la elección de opciones de tipo población. Es decir, mientras buscamos la solución a nuestro problema inicial en los algoritmos o planos inferiores, podemos experimentar en un plano superior algunas opciones, las cuales pueden a su vez tener subopciones.

El "problema de la decepción", "epístasis" o "ausencia de bloques constructores"

Una cadena de un algoritmo evolutivo tiene varios elementos (genes) que corresponden con variables del problema a resolver. Puede haber genes cuyos valores sean intrínsecamente buenos o malos, es decir, buenos o malos independientemente de los valores del resto de la cadena. Vamos a darles un nombre a este tipo de genes, por ejemplo, genes no-vinculados. Consecuentemente, un gen cuya bondad o maldad dependa de los valores de algunos de los otros genes será vinculado.

La propiedad de ser o no vinculado puede aplicarse también a un conjunto de elementos de la cadena, si tienen en cuenta todos ellos juntos, como un único gen, sin requerir que sean contiguos. Imaginemos un problema en el que todos los genes fueran no-vinculados: ¡No sería necesario un algoritmo evolutivo! Para encontrar los valores óptimos de las variables, bastaría con analizar independientemente todos los posibles valores de cada gen, manteniendo constante el resto de la cadena con cualquier valor. Imaginemos ahora que todos los segmentos son vinculados, menos dos, es decir, todos los genes son intrínsecamente buenos o malos, excepto dos, que dependen de otros. Sí, pero ¿de cuáles? ¿El uno del otro? ¿Ambos de todos los restantes? Si la bondad de cada uno de estos dos segmentos sólo dependiera de sí mismo y del valor del otro podrían ser tratados en conjunto como un único gen no-vinculado, y aplicar el mismo proceso. Si la bondad de los genes vinculados dependiera de todos los demás podremos utilizar el mismo método, teniendo la precaución de calcular primero los valores de los segmentos no-vinculados.

Imaginemos ahora el caso extremo de que todos los genes sean vinculados, y todos dependan del valor de todos los demás. Este no sería un problema irresoluble, pero sí el peor que nos podríamos encontrar, no sólo para las técnicas evolutivas, sino para cualquier otro método. Sería algo así como buscar un objeto con los ojos cerrados, y la mejor forma de tratarlo sería, lógicamente, una búsqueda secuencial. En cualquier caso, lo que más nos interesa es buscar segmentos y grupos de segmentos no-vinculados, aunque sean grandes, ya que si podemos dividir la cadena en varios segmentos no-vinculados podremos aplicar un algoritmo independiente para cada segmento, en el que el resto de la cadena sea siempre fijo, con un valor cualquiera, y obtener la solución mucho más rápido.

Para saber si un elemento (o un conjunto de elementos) es no-vinculado podríamos fijar valores al azar para el resto de la cadena, evaluar las cadenas que resulten de todas las posibles combinaciónes de valores para el conjunto de elementos elegido y almacenar el orden de las cadenas ordenadas según su peso. Si repitiendo el proceso utilizando distintos valores en el resto de la cadena, siempre obtenemos las cadenas en el mismo orden, entonces estaremos ante un segmento no-vinculado. Otra forma sería comprobar estadísticamente si en distintos ciclos del algoritmo, los mismos valores para un segmento producen posiciones relativas parecidas dentro de la lista de agentes ordenados por peso. Por ejemplo, si una variable puede tomar valores de 1 a 10, podemos almacenar, para cada valor, cuál es la posición media que ocupa la cadena que la contiene, dentro de la lista de cadenas ordenadas por pesos, en cada uno de los ciclos.

Otra forma de encontrar las vinculaciones sería definirlas al azar y actuar como si de hecho existiesen, comprobando si de esta forma se obtienen mejores resultados. Por último, voy a presentar la que me parece la forma más fácil de todas. Para el algoritmo es mucho más sencillo encontrar los valores óptimos de los segmentos no-vinculados que los de los vinculados. Por tanto, después de unos cuantos ciclos, los genes de valores más homogéneos tendrán una mayor probabilidad de ser más no-vinculados que el resto. Los genes vinculados se comportan en realidad como un único gen, por lo que se ha de evitar su división. Se me ocurre que podríamos obtener alguna ventaja si obligamos a que exista una especie de cohesión entre los genes vinculados, es decir, entre los segmentos de valores más heterogéneos, de forma que se hereden y muten juntos, simultáneamente, con una mayor probabilidad.

[ Volver al Indice ]


El problema de la variedad

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, produciendo multitud de cadenas muy parecidas. De igual forma, se ha de evitar lo contrario, que el algoritmo distribuya tan uniformemente el espacio de búsqueda que casi se dejen de explorar las mejores zonas. Se trata de econtrar un equilibrio, la mejor de las opciones en cada caso.

[ Volver al Indice ]


Soluciones al problema de la variedad

Se trata de conseguir un equilibrio entre exploración y explotación, o la velocidad optima de convergencia del algoritmo, para que siga las direcciónes más prometedoras pero sin olvidar otras posibilidades que a la larga pueden producir mejores resultados; llegar al optimo rápidamente sin pero quedarse estancado en un máximo local.

El algoritmo genético básico o canónico, en el que siempre se seleccionan los mejores individuos, tiende por lo general a la homogeneización de la población. Se trata por tanto de aumentar la variedad seleccionando algunos de los individuos que no son los mejores.

El aumento de variedad se consigue con las mutaciones, pero esto no suele bastar, y no es aconsejable excederse en las mutaciones. Una posible solución sería seleccionar un gran número de agentes, para evitar que un pequeño grupo repita sus características en una gran población, pero esto no es suficiente a largo plazo.

Lo que se debe hacer es seleccionar, además de la población con mayor peso, una fracción de la de menor peso. Si sólo seleccionaramos unos pocos de los mejores, los muy buenos, a no ser que el problema sea muy simple, el algoritmo probablemente nunca funcione como esperamos, ya que se quedará estancado en un máximo local. La especialización es peligrosa. La analogía con la vida es inevitable.

En realidad, lo más adecuado se resume en la siguiente frase "seleccionar de todo un poco, y esto sobre todo al principio, pero teniendo una mayor preferencia por los mejores, y esto sobre todo al final". Vamos ver porqué.

Seleccionar a los peores es anti-intuitivo; es obvio que es una mala estrategia. En cambio seleccionar a los mejores es intuitivo, pero no suele ser apropiado salvo en problemas sencillos. Si sólo seleccionaramos unos pocos de los mejores, y estos se reprodujeran entre sí, obtendríamos una población relativamente similar a la anterior. Repitiendo este proceso, al final obtendríamos una población completamente homogenea. A este tipo de selección se le llama elitismo, y al proceso que origina se le llama convergencia del algoritmo, y no es intrinsecamente malo. Al contrario, en muchos algoritmos se considera la convergencia de la población como criterio de parada. Y en los últimos ciclos del algoritmo, la única estrategia que tiene sentido es el elitismo, ya que a fin de cuentas, lo que queremos es la mejor solución.

Sin embargo, una convergencia demasiado rápida implica una menor exploración del espacio de búsqueda, con lo que el algoritmo puede quedarse estancado en un máximo local. Esto se va a entender muy facilmente con una analogía.

Imaginemos un grupo de exploradores recorriendo una zona desconocida buscando el mejor emplazamiento para colocar un campamento. Un coordinador recibe por radio los comentarios de cada explorador acerca de la zona en la que se encuentra. Por ejemplo, supongamos que los exploradores deben evaluar las zonas en que encuentran asignándoles un valor de 0 a 10. Si alguno de ellos describe a su zona con un valor de 8 ¿tiene sentido enviar a todo el resto de exploradores a buscar en zonas próximas a ella? ¿o sería mejor mantener algunos donde se encuentran, por si acaso aparece algo todavía mejor? Evidentemente, esto depende de las puntuaciones de las otras zonas, del tiempo límite que se disponga para encontrar la solución, etc. En cualquier caso, no será algo tán sencillo como seleccionar únicamente las mejores soluciones, será necesario arriesgarse a buscar en otras zonas.

Otro problema asociado al elitismo es que impide la resolución de problemas cambiantes. No se suele tener muy en cuenta este criterio debido a que la mayoria de las aplicaciones de los algoritmos genéticos, o bien son problemas estáticos, o bien se consideran como tales a la hora de resolverlos, dejando para el futuro resolver problemas del futuro.

En definitiva, la selección se puede hacer de una forma tan radical como seleccionar el 40% mejor y el 10% peor, pero existen otros métodos que seleccionan "de todo un poco" teniendo cada cadena una probabilidad de ser seleccionada proporcional a su peso, mediante el método de la ruleta o de los torneos. En el método de la ruleta, se calcula el peso relativo de cada patrón (igual al peso propio dividido entre el sumatorio de todos los pesos), con lo que la suma de los pesos relativos es 1. Posteriormente se asigna a cada entidad un trozo de los valores entre 0 y 1 del tamaño de su peso relativo, y se generan números al azar entre 0 y 1; los individuos con esos valores serán seleccionados.

El método de los torneos consiste en agrupar individuos en subconjuntos creados al azar y seleccionar al mejor de cada subconjunto.

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 agentes de pesos parecidos posean genes parecidos.

Otras opciones son 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 una de cada dos cadenas idénticas o muy parecidas.

También podemos generar ráfagas de mutaciones: en vez de establecer una probabilidad de mutación independiente para cada creación de un elemento de la cadena, 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 tántas especies en la naturaleza? Los seres parecidos compiten unos con otros, pero la diversidad y la especialización convive pacíficamente.

¿Qué criterio aplicar? Hay que tener en cuenta 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 (cosa que podría no ocurrir si tuviésemos un paralelismo real).

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, que es tomarlos del resultado de la ejecución de otro algoritmo genético, con lo que tendríamos algoritmos genéticos jerárquicos.

[ Volver al Indice ]


El problema de la reproducción

Las características positivas de los individuos deben poder transmitirse a la descendencia.

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.

Se trata de elegir las mejores soluciones, para que al reproducirse, generen otras nuevas que combinen los aspectos positivos de cada progenitor. El problema es encontrar un mecanismo de combinación de información de dos (o más) individuos, de manera que el (o los) individuos resultantes posean, al menos en la mayoría de los casos, tántas o más cualidades positivas que sus progenitores, y por tanto se encuentren tánto o más cercanos al objetivo que ellos.

En el caso de no existir reproducción, sólo mutaciones, también debemos encontrar un tipo de mutaciones que en un número suficiente de casos permitan mantener e incluso aumentar la bondad de la entidad mutada.

Sin embargo, en muchos problemas es muy difícil dar con una estructura de datos y un modo de reproducción que se comporte de esta forma. Por el contrario, con frecuencia ocurre que en la combinación de soluciones no sólo no se mantienen las cualidades positivas de los progenitores, sino que además se generan con frecuencia soluciones no válidas, cuya aproximación al objetivo buscado es nula.

Por ejemplo, si estoy buscando la secuencia de acciones con la que se consigue un determinado objetivo (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. Cambiando una línea de un programa al azar, lo más probable es que el programa deje de funcionar

[ Volver al Indice ]


Soluciones al problema de la reproducción

El problema de la reproducción aparece cuando la estructura de datos elegida no es la adecuada. En la mayoría de los casos, las estructuras de datos más sencillas e intuitivas no contienen información acerca de porqué esa solución ha sido seleccionada, y por tanto no es posible transmitir a la descendencia características positivas de los individuos progenitores ya que éstas no están representadas en ningún lugar, y cualquier método de reproducción elegido no producirá los efectos deseados.

É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 algoritmo genético 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 ámpliamente 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.

Para que el algoritmo funcione como deseamos, la reproducción y las mutaciones deberían producirse de tal forma que mantengan, en la mayoría de los casos, las cualidades positivas de los individuos. Se trata de que los individuos, en conjunto, sean cada vez mejores. Pensemos en el caso de las mutaciones. Dada una cadena, una mutación consistirá en modificar al azar uno de los elementos de esa cadena. Para que todo marche bien sería muy interesante que los valores de los genes sean buenos o malos, independientemente de los valores de otros genes, o al menos, que sean lo más independientes posible.

¿Como saber cuándo una estructura de datos no es adecuada? Un método es el siguiente: si al modificar un elemento cualquiera de una cadena seleccionada (buena) existe una probabilidad alta de que la cadena resultante sea 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.

Es decir, "Cuando el objetivo (peso) de una entidad se puede calcular como una función en la que variaciones muy pequeñas de los valores de sus variables (valores de los genes) producen con una probabilidad alta, variaciones muy grandes en el resultado de la función, la estructura de datos es incorrecta". Una variación muy pequeña sería cambiar el valor de un gen.

El ejemplo por excelencia de este tipo de problemas 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. Un algoritmo genético que trate de predecir el número premiado de esta forma nunca tendrá demasiado éxito.

En el tres en raya con reglas en geenral ocurre que cada regla, o es buena, o es mala, independientemente de las demas. 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 este inconveniente de forma inevitable. Por ejemplo, en juegos complicados como el ajedrez, 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, existen 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.

Cuanto más ocurra esto, más lentamente convergerá nuestro algoritmo genético. 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 o las plumas para el vuelo, que no pueden depender de una única mutación, si sólamente 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 organo a medio formar. Un pato puede huir de un depredador terrestre alzando el vuelo tan sólo un metro. 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 probablemente sea mucho más progresiva y constante de lo que parece, y nosotros podemos ser "la rana".

El método de reproducción

Bien, estamos resolviendo un problema con un algoritmo genético y por fín hemos conseguido que aparezcan juntos los valores deseados en los segmentos dependientes. ¿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 que nos interesa, perdiéndose todas sus propiedades.

¿Existe alguna forma en la que la naturaleza fuera capaz de evitar esto?

Supongamos una población con alta tasa de natalidad y mortalidad en la que un individuo adquiera una rara y muy interesante combinación de genes. Si existe reproducción sexual, al combinar sus genes con los de su pareja es posible que estas cualidades se pierdan, pero si el número de hijos el suficientemente grande, es posible que se pueda repetir en el descendiente la misma combinación.

Si tomamos un segmento cualquiera de genes de uno de los descendientes vivos de este mutante, es mas probable (aunque ciertamente, no mucho mas) encontrar exactamente este segmento interesante que cualquier otro, simplemente porque si el descendiente está vivo, es mas probable que sea uno de los herederos de dicha característica.

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.

Esto sería muy interesante en las últimas fases de la evolución (en la solución de un problema). Lo normal es que en el conjunto de la población se hayan formado varios "tipos" parecidos de individuos (por ejemplo, en una población de 200 individuos, de uno a cinco "tipos") cada uno de los cuales ha encontrado un máximo local de la función que representa el problema, e intenta maximizar el peso en su zona. En cada "tipo" no es interesante combinar las cadenas de cualquier forma, sino manteniendo las características comunes del "tipo".

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.

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 independientes de forma independiente. 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 independiente, manteniendo constante el resto, que por serlo, no afectará al peso resultante, hasta encontrar alguna combinación valiosa.

Vamos a ver este tema con más profundidad. Una cadena de un algoritmo genético tiene varios elementos, que corresponden con las variables del problema a resolver. Cuando se muta, se muta un elemento, y en la reproducción, se combinan subcadenas de elementos completos. Es decir, un elemento (gen) es la unidad minima que se recombina o muta.

Un elemento puede estar o no "vinculado" (por llamarlo de alguna forma) con otros. De igual forma, un conjunto de elementos puede estar o no "vinculado" con otro conjunto.

¿Que es eso estar "vinculado" o "no vinculado"? Los valores para un elemento "no vinculado" son siempre intrinsecamente "buenos" o "malos" independientemente de los valores del resto de la cadena. En cambio, en un elemento "vinculado" ocurre lo contrario: cierto valor del segmento vinculado será bueno o malo (es decir, producirá un peso alto o bajo) en función de los valores de otros segmentos. Un segmento pude ser "relativamente vinculado" en función del grado en que se cumpla esta propiedad.

La propiedad de ser o no vinculado puede aplicarse a un conjunto de elementos, si se tienen en cuenta todos ellos juntos, como un unico segmento. Un conjunto de elementos (no tienen por que se contiguos) será "no vinculado" si cualquier serie de valores para esos elementos es siempre intrinsecamente "buena" o "mala" independientemente de los valores del resto de la cadena.

Nos interesa buscar segmentos y grupos de segmentos "no vinculados" con el resto de la cadena, ya que si podemos dividir la cadena en varios segmentos "no vinculados", podremos aplicar un algoritmo genético independiente para cada segmento (en el que el resto de la cadena es siempre fijo, con un valor cualquiera, y en realidad es como si no existiera, salvo para la evaluación) y obtener la solucion mucho mas rapido.

Hay varias cuestiones pendientes:

1.- Cómo detectar segmentos no vinculados
2.- Cómo tratar un algoritmo genético en el que se han detectado segmentos no vinculados
3.- Cómo tratar segmentos "poco vinculados"

1.- Cómo detectar segmentos no vinculados

A veces se sabe por intuicion si un segmento es no vinculado según esta definición intuitiva: aquellos que son buenos o malos independientemente del resto serán no vinculados. Pero lo más interesante es encontrar un método automático que permita detectarlo.

Para saber si un elemento (o un conjunto de elementos) esta "no vinculado" con el resto de la cadena podemos hacer lo siguiente:

-Selecciónamos el conjunto de elementos a analizar
-Fijamos valores cualesquiera al azar para el resto de la cadena
-Evaluamos las cadenas que resultan de todas las posibles combinaciónes de valores para el conjunto de elementos elegido, dejando el resto fijo tal como se ha indicado
-Ordenamos las cadenas segun su peso (fitness) de mayor a menor

Ahora repetimos el proceso utilizando otros valores cualesquiera al azar en el resto de la cadena, distintos a los ya usados. Si siempre que hagamos esto, obtenemos las cadenas en el mismo orden (teniendo en cuenta el caso particular en el que el orden no importa si dos cadenas tienen exactamente el mismo valor de peso), entonces estamos ante un segmento "no vinculado".

Así se detectan segmentos no vinculados en un algoritmo genético.

Supongamos una cadena de 4 genes teniendo cada uno de ellos 8 bits, es decir, 256 posibilidades en cada gen.

G1 G2 G3 G4

Vamos a analizar si G1 es "no vinculado". Para ello, dejamos fija la parte G2 G3 G4 con cualquier valor y probamos todas las combinaciónes de G1 

c1 = 0 5 98 66
c2 = 1 5 98 66
c3 = 2 5 98 66
c4 = 3 5 98 66
c5 = 4 5 98 66
c6 = 5 5 98 66
c7 = 6 5 98 66
.
.
.
c256 = 255 5 98 66

despues evaluamos y ordenamos estas cadenas por pesos de mayor a menor. Podriamos obtener por ejemplo las cadenas en este orden con los siguientes pesos: 

c37 = 140
c2 = 70
c98 = 70
c44 = 30
c23 = 20
.
.
.

Ahora lo hacemos con otros valores de G2 G3 G4: en vez de 5 98 66, esta vez probamos con 81 29 120. Después de crear las cadenas, evaluarlas y ordenarlas, podríamos obtener: 

c37 = 200
c2 = 120
c98 = 120
c44 = 30
c23 = 10
.
.
.
Esto ya sería un buen indicio de que se trata de un segmento no vinculado. Para obtener una mayor seguridad, podemos repetir el proceso para unas cuantas combinaciónes de valores de G2 G3 G4. Si la clasificación de las cadenas siempre aparece en el mismo orden, es decir, si cada valor del segmento es mejor o peor que otros valores, independientemente de los valores del resto de la cadena, el segmento es no vinculado y puede tratarse independientemente. En el ejemplo habría que fijar el valor de este segmento en 37, ya que es el que mayor peso produce en todos los casos.

En realidad, sí puede existir una "dependencia" entre los valores del resto de la cadena y los valores del segmento que estamos analizando, es más, esta dependencia existe prácticamente siempre; por eso hablo de "vinculacion" (por denominarlo de alguna forma) y no de "dependencia". Por ejemplo en el segundo caso los pesos que obtienen son mucho mas altos; pero lo que importa no es si se obtienen pesos más o menos altos, en realidad no importa el valor del peso: sólo el orden de las cadenas clasificadas en orden de pesos. Se trata de algo cualitativo y no cuantitativo.

Es evidente que podemos encontrar casos en que se cumpla la regla de la "no vinculación", pero no de forma absoluta. Si el orden de las cadenas no cambia, salvo eu unos pocos casos, se tratará de un segmento "poco vinculado".

2.- Cómo tratar un algoritmo genético en el que se han detectado segmentos no vinculados

Si hemos detectado segmentos o grupos de segmentos no vinculados puros, lo más apropiado será dividir la cadena en dichos grupos y tratarlos independientemente, como se ha explicado antes, como si cada uno fuera un problema a resolver con un algoritmo genético de forma totalmente independiente, uniendo finalmente las soluciones en una única cadena.

3.- Cómo tratar segmentos "poco vinculados"

Como normalmente no tendremos la seguridad de que un conjunto de elementos sea no vinculado, o tal vez sepamos que no lo es mas que en cierto grado, se podrían utilizar algoritmos genéticos a dos niveles. En el nivel bajo se aplicaría un algoritmo genético a cada segmento. En el nivel alto se tomarían segmentos completos como si fueran genes, y la unidad minima a recombinar o mutar a nivel alto seria un segmento "no vinculado" completo.

Lo más interesante es que se podrían hacer mas niveles: dentro de un segmento "no viculado", que se trata como un algoritmo genético totalmente independiente, se podría seguir la misma filosofía y buscar dentro de el "segmentos no vinculados" aplicando a cada uno de ellos un algoritmo genético.

A pesar de la relativa belleza del esquema que se está explicando, parece obvio que puede suponer una sobrecarga de cálculo muy grande, que tal vez no merezca la pena. Evidentemente, si el problema a resolver es tal que todos los elementos están vinculados, estaremos perdiendo el tiempo.

Seria interesante disponer de un metodo que no fuera tan estricto y que no hiciese tantas comprobaciones, niveles y subniveles. Lo interesante sería hacer más o menos lo mismo, o utilizar de alguna forma este conocimiento, pero en un solo algoritmo genético.

Con esto volvemos a la idea inicial: que los segmentos relacionados deben traterse juntos. Podriamos obligar a que existiera una especie de "cohesión" entre los genes "vinculados" entre si, de forma que si dos genes no son ni buenos ni malos independientemente, pero tomados como un grupo de dos genes, ese grupo si sea siempre o bueno o malo.

La "cohesión" haria lo siguiente:

-Es mas probable que esos genes entre los que existe cohesión se hereden juntos, es decir, los bloques con cohesión (no tienen por que ser contiguos) se heredan todos (o ninguno) con una mayor probabilidad. Por ejemplo, tenemos 10 genes con cohesión: si el primero de ellos se hereda seguro, aumenta la probabilidad de que se herede cada uno de los restantes. y al contrario: si el primero no se hereda, la probabilidad de que el resto se herede disminnuye mucho

-Es mas probable que esos genes entre los que existe cohesión se muten juntos, es decir, Por ejemplo, tenemos 10 genes con cohesión: si el primero de ellos se muta seguro, aumenta la probabilidad de que se mute cada uno de los restantes. y al contrario: si el primero no se muta, la probabilidad de que el resto se mute disminuye mucho

[ Volver al Indice ]


El problema de la selección

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.

La 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. ¿Cómo podemos saber cuáles son las mejores soluciones? ¿Cuáles son las que más se acercan al objetivo buscado? ¿cuáles producirán un convergencia hacia la resolución del problema?

El problema se agrava cuando el algoritmo genético está dirigido por un objetivo que no posee naturaleza más o menos continua. Cuando el objetivo puede ser logrado en diversos grados, el algoritmo puede esforzarse en conseguir que el objetivo se cumpla en el máximo grado posible, detectando pequeñas variaciones. Pero si el estado buscado fuera todo-nada, es decir, si ocurre que: una de dos, o se consigue el objetivo completamente o no se consigue en absoluto, no es posible que la evolución produzca gradualmente entidades cada vez más cercanas al objetivo.

[ Volver al Indice ]


Soluciones al problema de la selección

La función de evaluación más corriente consiste en asignar a cada solución un peso o valor en función del grado en que se acerca al objetivo. Una vez hecho esto, se ordenan todas las soluciones según este criterio. Finalmente, se selecciona un número determinado de soluciones, comenzando por las primeras de la lista.

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 de forma que los recorridos cortos posean un peso mayor que los largos.

Sin embargo, como se trata de seleccionar unas soluciones y eliminar otras, no es necesario conocer cuantitativamente (con un número) el grado en el que cada solución se acerca a la solución buscada. Basta con conocer cualitativamente qué soluciones se aproximan más que otras.

De esta forma, podemos agrupar las soluciones por criterios de proximidad física o azar y hacer que "jueguen", "peleen" o demuestren de alguna forma cuáles son las mejor preparadas en función del objetivo buscado.

En el tres en raya cada conjunto de reglas es una solución (agente), y 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, cada entidad sería un programa o conjunto de instrucciónes. Pero, ¿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 ]


Tipos de Aplicaciones

Cualquier problema puede verse como un problema de algunos de estos tipos:

Supongamos que somos un grupo de Boy-Scouts que deben encontrar la ubicación óptima para el campamento antes de que caiga la noche. Los exploradores se dispersan en el terreno y envían periódicamente por radio sus informes a un coordinador que decidirá finalmente dónde instalar el campamento.

Este problema puede verse como un problema de:

  • Búsqueda de la mejor zona
  • Clasificación de las zonas con vistas a elegir la mejor
  • Predicción de los beneficios obtenidos según la zona elegida
  • Optimización del uso de los recursos (exploradores) para conseguir el objetivo buscado

    [ Volver al Indice ]


    Equivalencias entre tipos de Aplicaciones

    Existen equivalencias entre unos y otros tipos. Una predicción es una clasificación en la que interviene el tiempo, y una predicción también se puede interpretar como una búsqueda dentro del espacio de posibles estados futuros o como un problema de minimización del tiempo empleado en esta búsqueda.

    [ Volver al Indice ]


    Algoritmo Evolutivo como un método de optimización

    Interpretar un algoritmo evolutivo como un método de optimización es lo más intuitivo. La función de evaluación devuelve valores altos para las soluciones buenas, con lo que cada vez tendremos mejores soluciones, y en eso consiste precisamente optimizar.

    [ Volver al Indice ]


    Algoritmo Evolutivo como un método de búsqueda

    Para considerar un algoritmo evolutivo como un método de búsqueda, simplemente tenemos que hacer que la función de evaluación devuelva valores mas altos cuanto más cerca estemos de aquello que se está buscando. Podemos identificar cada cadena del algoritmo con una posición en un espacio imaginario, que será el espacio de búsqueda. Si las cadenas tuvieran dos elementos, tendríamos un espacio de dos dimensiones. Con tres elementos, tendríamos un espacio tridimensional, y así sucesivamente. Normalmente tendremos muchas más dimensiones, pero basta con pensar en dos o tres dimensiones y extrapolar el concepto de "movimiento por el espacio" para interpretar correctamente la idea. Por ejemplo, una mutación de un gen desplazaría a la cadena a una posición distinta en uno de los ejes.

    Evidentemente, se debe poder reconocer hasta que punto estamos próximos a aquello que buscamos. No es posible encontrar algo si no sabemos que es lo que estamos buscando. Hay un caso en el que, al menos en apariencia, esta regla tiene una excepción. En algunos sistemas de reconocimiento de patrones como algunas redes neuronales no supervisadas, existe la posibilidad de aprender sin ningún entrenamiento y sin supervisión alguna. ¿Qué es lo que aprende entonces la red? La respuesta está en la propia definición de los que hace la red: reconocer patrones. La red hace precisamente eso: reconocer series, secuencias de datos repetidas, sean del tipo que sean; regularidades presentes en los datos, categorizándolas en clases no determinadas a priori.

    [ Volver al Indice ]


    Ejemplos de Aplicaciones

    [ Volver al Indice ]


    El problema del viajante: Travel Salesman Problem (TSP)

    Es el problema de un viajante que debe recorrer varias ciudades hasta volver al punto de partida incurriendo en el mínimo coste.

    El problema del viajante es un problema NP-Completo. En un problema NP-Completo, el espacio de estados del problema crece de forma exponencial (o asimilable a exponencial, como por ejemplo, factorial) ante incrementos lineales del número de elementos que intervienen en el problema.

    Uno de los mejores métodos para resolverlo consiste en una red neuronal de tipo "chicle".

    En mi opinión, el algoritmo "chicle" es una estrategia que se puede aplicar con una red neuronal u otros métodos como por ejemplo la computación evolutiva. Dada una gran red de nodos de ciudades, el algoritmo tipo chicle realiza una agrupacion inicial de estas ciudades en "aglomeraciones de ciudades" de forma que el problema complejo se convierte en un problema más sencillo (es una variante del metametodo "divide y vencerás") donde los nodos no tienen porqué ser realmente ciudades, pero cada nodo sí debe ser representativo de un grupo de ciudades reales. Una vez optimzado el camino mejor en esta red pequeña, se amplia el zoom de forma que ahora se tiene en cuenta una hipotética red de nodos más parecida a la red real. Mediante sucesivos refinamientos, se llega finalmente a la solución relativa a las ciudades reales. Este método fué descrito por Ignacio Olmeda en unos cursos que impartió en la Universidad Carlos III, pero desconozco el autor original.

    Implementación del problema del viajante mediante algoritmos evolutivos

    La función de evaluación calculará la suma de las distancias (o costes, asimilable a distancias) entre las ciudades recorridas en el orden especificado y devolverá la inversa de este valor de forma que los recorridos cortos posean un peso mayor que los largos.

    Para implementar el problema del viajante mediante algoritmos evolutivos, existen varios problemas de representación. Vamos por partes.

    Primer problema:

    Imaginemos que todas las ciudades están conectadas con todas las demás. Si asignamos un número a cada ciudad, cualquier cadena formada por números no es una cadena válida. Por ejemplo, si tenemos 6 ciudades numeradas de la 1 a la 6.

    153246 es una cadena valida, pero
    121222 no es valida, ya que se repiten ciudades

    La solución a esto es lo siguiente: dejamos que el algoritmo genere en cada posición un número cualquiera 1-6 pero interpretamos esos números de manera distinta según la posición de la cadena en la que se encuentren, por ejemplo, en la cadena:

    136211

    el primer digito representa una ciudad del 1-6, es decir, la ciudad 1. El segundo dígito indica el número de ciudad, pero numeradas teniendo en cuenta sólo las ciudades que no se han utilizado ya. Como la ciudad 1 ya se ha usado, solo nos quedan las ciudades 2-3-4-5-6 y las numeramos asi: 1-2-3-4-5. Como quedan valores disponibles (queda uno, el 6) asiginamos esos valores restantes de forma cíclica, es decir, 

    las ciudades restantes son 2-3-4-5-6
         representadas por 1-2-3-4-5
                         y 6

    como aparece un 3, ese valor representa la ciudad 4

    Para el tercer digito, hemos usado ya las ciudades 1 y 4 asi que quedan libres las ciudades 2-3-5-6 

    las ciudades restantes son 2-3-5-6
         representadas por 1-2-3-4
                         y 5-6

    como el dato es un 6, hace referencia a la ciudad 3

    Con esto es evidente que el ultimo de los datos es indiferente ya que no aporta información: solo queda una ciudad y ya se sabe a qué ciudad hay que ir.

    En la practica implementar este metodo es sencillisimo, muchisimo mas que explicarlo:

    ciudad_real_a_visitar = numero_contenido_en_cadena_genetica MOD numero_de_ciudades_restantes

    MOD es "resto de la division". Basta con esa operacion, teniendo la precaución de comenzar a codificar por el número 0.

    Segundo problema:

    Ahora supongamos que no todas las ciudades están conectadas con todas las demás. La solución es la misma: tener en cuenta en la codificación que el número almacenado en el gen representa una de las varias ciudades diponibles desde ese nodo, numeradas de forma circular.

    ciudad_real_a_visitar = numero_contenido_en_cadena_genetica MOD numero_de_ciudades_destino_posibles_desde_ese_nodo

    Ya que es evidente que las primeras ciudades se ven beneficiadas en cuanto a la probabilidad de ser elegidas en primer lugar, podría ser una buena idea ordenar y renumerar las ciudades en orden creciente de distancia desde el nodo actual justo antes de interpretar el siguiente gen de la cadena.

    [ Volver al Indice ]


    Referencias

    ArtículoSanto, David. irbis@lsi.eee.ufg.br Algoritmos Genéticos para Linux. GALOPPS. Abril 1999. Revista Linux Actual, nº6.

    Internetftp://ftp.de.uu.net/pub/research/softcomp/EC/EA/papers/intro-spanish.ps.gz
    Pérez Serrada, Anselmo. Una introducción a la Computación Evolutiva. Marzo, 1996. Es una obra muy completa, que sirve además como introducción al tema. Muy recomendable para quien se disponga a programar algoritmos evolutivos.

    Internethttp://www.fciencias.unam.mx/revista/soluciones/N17/Indice.html
    Revista Soluciones Avanzadas, No. 17, enero, 1995 con varios artículos sobre Algoritmos Genéticos de Carlos Coello Coello, Carlos Zozaya Gorostiza y David E. Goldberg

    Artículohttp://www.redcientifica.com/gaia/cesp_c.htm
    Herrán, Manuel de la. Computación Evolutiva. Revista Solo Programadores nº 43. Ed. Towercom. Marzo 1998.

    Internethttp://www.lania.mx/~ccoello/gene.html
    Lista de Investigadores que trabajan en Computación Evolutiva y otras Técnicas Heurísticas en Latinoamérica y España

    Internethttp://www.cs.unibo.it/~gaioni
    Raffaele Gaioni. The GA Technical Reports Home Page" and "The GA Pratictioners Home Page. La más completa selección de documentos (disponibles) sobre evolutionary computation y la más completa lista de email y home page de las personas que se encuentran investigando en ello.

    Internethttp://www.etsimo.uniovi.es/ftp/pub/EC/FAQ/www/top.htm
    Guía del Autoestopista de la Computación Evolutiva ("The Hitch-Hiker's Guide to Evolutionary Computation") Heitkötter, Jörg and Beasley, David, eds. FAQ de comp.ai.genetic con definiciones y clasificaciónes de los términos más comunes en Computación Evolutiva

    Internethttp://research.de.uu.net:8080/encore
    ftp://zeus.etsimo.uniovi.es/pub/EC/Welcome.html
    Encore, the Electronic Appendix to "The Hitchhiker's Guide to Evolutionary Computation" by Jörg Heitkötter

    Internethttp://alife.santafe.edu/~joke/zooland/
    http://www.krl.caltech.edu/~brown/alife/zooland/
    http://research.de.uu.net:8080/zooland/
    http://www.dl.ac.uk/CCP/CCP14/ccp/web-mirrors/alife/zooland/zooland/
    ftp://ftp.de.uu.net/pub/research/ci/Alife/zooland/
    Zooland, "The Artificial Life Resource" by Jörg Heitkötter

    ArtículoHolland, John H. Algoritmos Genéticos. Revista Investigación y Ciencia, Septiembre 1992. Fantástico resumen del "padre" de los algoritmos genéticos.

    Internethttp://www.geocities.com/CapeCanaveral/9802/
    Matemáticas Aplicadas Vida Artificial (Blanca Cases gzamora@comunet.es) y Algoritmos Genéticos (Pedro Larrañaga CCPLAMUP@SI.EHU.ES) Universidad del País Vasco (UPV-EHU). Ofrecen en el web unos artículos muy interesantes. No hay que perderselo.

    Internethttp://metricanet.com/people/jjf/gp/spanish_frames/index.html
    El Cuaderno de Programación Genetica Vida Artificial, Algoritmos Genéticos e Inteligencia Artificial por JJ Fernández jjf@jjf.com.

    LibroSierra Molina, Guillermo, y otros. 1995. Sistemas expertos en contabilidad y administración de empresas. Editorial Ra-Ma. Algoritmos Genéticos, Redes Neuronales y otras técnicas de resolución de problemas, explicado de una forma clara y sencilla.

    ArtículoHolland, John H. Adpatation in Natural and Artificial Systems. University of Michigan Press. 1975.

    ArtículoHerrán, Manuel de la. Algoritmos Genéticos Avanzados. Revista Solo Programadores nº 37. Ed. Towercom. Septiembre 1997. Más de Algoritmos Genéticos

    Internethttp://ccp.servidores.net/aagg/
    Algoritmos Genéticos Aplicación de los Algoritmos Genéticos en la búsqueda de la ruta óptima en una red, por Carlos Costa Portela c.c.portela@ieee.org (código fuente).

    Internethttp://www.lcc.uma.es/personal/alba/services/nag2.html
    Genetic Algorithms In The World Página en castellano. Links a Algoritmos Genéticos.

    Internethttp://www.lania.mx/~ccoello/genetic.html
    Apuntes de computación evolutiva en español de Carlos Coello Coello

    Internethttp://www.lania.mx/~ccoello/bibgen.html
    Bibliografía para el curso de Introducción a la Computación Evolutiva de Carlos Coello Coello

    ArtículoSchwefel, Hans-Paul y Rudolph, Günter Contemporay Evolution Strategies 1998.

    LibroMichalwicz. 1996. Genetic Algorithms + Data Structures = Evolutionary Programs. Editorial Springer Berlag 3ª ed.

    LibroBaeck. 1996. Evolutionary Algorithms in theory and practice. Oxford NY.

    LibroFogel, DB. 1995. Evolutionary Computation: toward a new philosophy of machine intelligence. IEEE press.

    LibroBaek, Fogel, Michalwicz (Eds). 1997. Handbook of Evolutionary Computation. Oxford NY.

    LibroGoldberg. 1989. GA in search, optimization and Machine Learning. .

    Internethttp://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html
    TSP Library of sample instances for the TSP (El problema del viajante: Travel Salesman Problem)

    [ Volver al Indice ]

    [ Home Page Castellano | Home Page English ]
    • Traduccion