Algoritmos genéticos

A. K. Dewdney

Juegos de ordenador

Imaginemos un mar abstracto, habitado por organismos abstractos llamados---glóbulos vívos finitos". a los que por eufonía dejaremos en 'glovitos' . Cada glovito está dotado del más sencillo aparato de decisión posible. Los glovitos serían equivalentes biológicos de lo que en ciencias del cómputo se definirían autómatas finitos. Cada glovito contiene tan solo un unico cromosoma, consistente en una ristra de simbolos en los que está codificado el autómata. Los glovitos habitan en un caldo digital -el caldo primordial- que se encuentra en constante fluir. Para que el glovito sobreviva es preciso que logre predecir con exactitud los cambios que vayan a producirse en su ambiente.

En la sopa primordial que puse recientemente a fuego lento en mí ordenador, los glovitos que no acertaban a atinar en sus predicciones se extinguían. Los más acertados dejaban progenie, la cual lograría a veces mejorar el índice de acierto de sus ancestros. Al cabo, terminó por producirse evolutivamente una estirpe de individuos capaces de predicción perfecta.

Los glovitos y sus tendencias evolutivas ilustran con gran pulcritud una forma de programación conocida como algoritmo genético. Esta técnica, de la que fue pionero hará unos veinte años John H. Holland, de la Universidad de Michigan, permite en ocasiones resolver difíciles problemas, por obtención evolutiva de una sucesión de soluciones aproximadas. Emparejando unas con otras las mejores con las antiguas soluciones se obtienen soluciones aproximadas nuevas. No tarda mucho en aparecer una solución mejor que sus progenitoras, que pasa a encuadrarse entre las reproductoras preferentes.

Se han aplicado con cierto buen éxito algoritmos genéticos al reconocimiento de formas y patrones, a sistemas clasificadores, al funcionamiento de oleoductos, al diseño y distrihución de símbolos y a unos pocos problemas más. En mi sopa computarizada. esta técnica produjo una estirpe de glovitos de comportamiento superior. ¿Se debió tal éxito a la eficacia general de) método de algoritmo genético. o a la simplicidad de la tarea de predicción que debían afrontar los glovitos? Resulta dificil responder a esta pregunta. Los lectores interesados pueden reflexionar sobre ella y. si tienen a su alcance un ordenador, reproducir el fenómeno subyacente.

Un autómata finito puede encontrarse en un número de estados; la recepción de una señal de entrada lo hace pasar automaticamente de un estado a otro. La clase de autómatas utilizados en los glovitos también generan señales. En el seno del autómata, las señales recibidas se representan por símbolos. Cuando se recibe una señal, el autómata cambia de estado y emite una segunda señal.

Para representar el proceso tesulta adecuada una tabla de transiciones de estados. Por ejemplo, un autómata que pueda adoptar tres estados, A, B y C y sea capaz de manejar unos y ceros aferenles y eferentes, queda pulcramente representado por una tabla de 3 por 4. Para cada estado en que el autómata pueda encontrarse, y para cada símbolo que pueda rccibir, la tabla dispone de dos entradas. La primera da el correspondiente simbolo, de salida, la segunda, el estado que el autómata va a adoptar a continuación El autómata representado por esta tabla podría muy hien encontrarse en algún instante en el estado C. Si el autómata recibiera entonces un 1, la tabla diría que el autómata generaría un 0 y pasaría a adoptar el estado A.

Otra representación que los humanos encuentran más fácil de leer, es el diagrama sagital de transición de estados. En él los círculos representan estados y las flechas transiciones. Para denotar que un autómata pasa de un estado a otro cuando recibe un símbolo específico, se traza una flecha que vaya de uno, a otro, La flecha debe ir rotulada tanto con el simbolo de entrada, causante de la transición. como con el simbolo de salida resultante.

Los autómatas finitos comienzan a funcionar partiendo siempre de un estado específico, llamado inicial. Cada vez que un imaginario reloj da un golpe de péndulo, llega un nuevo símbolo, se emíte otro nuevo símbolo y se adopta un nuevo estado. Los autómatas que he utilizado para mis glovitos reciben y envían todos dos únicos simbolos, siempre los mismos: 0 y 1.

¿Cómo ha de interpretarse el com. portamiento de los glovitos, si tan poco se conoce de la biología de esas criaturas? En ello precisamente reside el placer de la abstracción. Los símbolos recibidos por el autómata son meros mensajes sensorios (percepciones) procedentes del entorno. Correlativamente, un símbolo de salida puede entenderse por la respuesta que el organismo da al estado más reciente de su ambiente.

Tan versátil es la noción de glovito, que sus entradas y salidas pueden representar gran diversidad de fenómenos biológicos específicos. Por ejemplo, una señal de entrada podría representar un gradiente térmico o químico. El correspondiente símbolo de salida podría ser una orden dirigída a un efector que controlase las vibraciones de cilios, o que tuviera a su cargo un mecanismo de esporulación. Una tarea que reviste gran importancia para todo ser vivo que desee evolucionar hasta un nivel minimamente aceptable (catedrático de universidad, pongarnos por caso) es es la predicción de los cambios de su entorno. Para los glovitos, su ambiente vital consiste en una secuencia, aparentemente interminable, de signos 0 y 1. En la medida en que los símbolos recibidos sean indicativos de acontecimientos importantes, comportará sin duda cierta ventaja que el glovito tenga capacidad de predecir cuál será el proximo simbolo, y tanto más si en alguna interpretación específica del funcionamiento del glovito se vieran reforzadas sus propias posibilidados de superviviencia.

La mayoría de los glovitos son bastante ineptos en lo tocante a predecir el comportamiento del entorno. Por ejemplo, el glovito descrito por la tabla de transiciones dada responde a la secuencia de señales ambientales

0111000010110...

con las salidas

10000011001000.......

En cada etapa de su funcionamiento, la salida del glovito es su pronóstico de cuál será la próxima señal que llegará procedente del entorno. Para hallar el número de pronósticos correctos, se desplaza la secuencia de salida un símbolo hacia la derecha, y se la compara. bit a bit, con la secuencia de entrada,

Contemos el número de símbolos concordantes. En este caso, el glovito tan sólo predijo correctamente seis de los doce símbolos que le fueron llegando, puntuación no superior a lo que sería de esperar pronosticando al puro azar. Es fácil pedir demasiado a los autómatas finitos. En efecto, no hay derecho a exigirle a un glovito que sea capaz de pronosticar correctamente las señales de medios ambientales. Intentemos reflexionar por un momento sobre esta cuestión.

¿Por qué habrá de constar toda secuencia correctamente predicha de una ristra fija de símbolos, interminablemente repetida? Por ejemplo, el glovito de tres estados que antes fracasó en la prueba de predicción que le propusimos, triunfa brillantemente en la siguiente secuencia ambiental:

0100110100110100l1 . . .

Pero aquí la sucesión de valores ambientales desfila al compás de un sencillo redoble, a saher, 010011. Existen varias docenas de glovitos triestado, pero tan solo unos pocos son capaces de predecir correctamenie esta secuencia. Los glovitos de más de tres estados con capacidad de predicción perfecta para una sucesión ambiental determinada son raros, y escasean tanto más cuanto mayor es el número de estados.

La predictibilidad depende fuertemenle del período de la sucesión. Si la serie fundamental de símbolos es sufícientemente larga, ningún glovito número prefijado, n, de estados conseguirá jamás llegar a pronosticarla perfectamente.

Existe, evidentemente, una relación entre el número de estados que puede adoptar un glovito y la máxima longitud del período que es capaz de pronosticar perfectamente. Seguramente los lectores gusten de descubrir por sí mismos tal relación. ¿Cuál es la máxima longitud de período que puede pronosticar un glovito de n estados?

Los glovitos son algo más que autómatas finitos que se esfuerzan por predecir su entorno, pues tienen un cromosoma. Por algún procedimiento (que veremos más adelante) los glovitos engendran periódicamente nuevos glovitos.

Al examinar el cromosoma del glovito y ponerlo en relación con el automata finito correspondiente, vemos de qué modo los genes hereditarios determinan el comportamienlo de la progenie. Comencemos con la tabla de transiciones de estados y vayamos separando. una por una, las filas. de arriba abajo. Unamos las filas, pegando la cola de cada una con la cabeza de la siguicnte y, finalmente, el comienzo con el fin de la tira así obtenida-

El resultado será un cromosoma circular. Antes de llevar a cabo esta última operación de empalme, el cromosoma de nuestro ejemplar triestado se nos presenta como una ristra de 12 genes:

1 B 1 C 0 C 0 B 1 A 0 A

En puridad, los símbolos de esta serie son alelos. Un alelo es una forma es~ pecífica de gen, que se asienta en un locus determinado. Los genes pueden por tanto, especificarse tanto por su nombre como por su emplazamiento, o locus.

Así pues, el séptimo símbolo, contando desde la izquierda, controla el símbolo de salida de un glovito cuando éste se encuentra en estado B y se recibe un 1 procedente del en- torno. Aquí, el locus es 7.

Hace poco preparé en mi ordenador personal una sopa primordial, con 10 glovitos tetraestado. No habían transcurrido 1000 de las unidades de tiempo. que llamo cronones, cuado ninguno de los glovitos originales permanecía con vida. Todos habían sido remplazados por otros de mayor habilidad de predicción. La pantalla de mi ordenador iba mostrando las puntuaciones máxima y minina alcanzadas por la poblacíón existente en ese momento. La puntuación mínínima fluctuaba fuertemente; la máxima, en cambio, fue trepando poco a poco (véase la figura). Justanente cuando comenzaba yo a desesperar de que pudiera evolucionar un predictor perfecto apareció uno súbitamente y, a partir de ahi, la puntuacion máxima quedó estancada en 100.

Todo lo cual suscita la cuestión de cómo evolucionan exactamente los glovitos en mi caldo computarizado. Periódicamente, un rayo cósmico atraviesa la sopa e impacta al azar en un cromosoma, en un lugar igualmenle aleatorio. El resultado de ello es que un gen específico pasa de un alelo a otro. Por ejeraplo. en el siguiente cromosoma, que pertenece a un glovito de cuatro estados, el gen sustituido en el locus 3 controla el símbolo de salida correspondientc a la transición desde el estado A, cuando a la criatura le llega un 1.

0 D 1 C 0 D 0 B 1 A 0 C 1 B 1 A

Un rayo cósmico impacta en este gen, y modifica ligeramente su cromosoma:

0 D 0 C 0 D 0 B 1 A 0 C 1 B 1 A

La otra fuente de variación del acervo génico de los glovitos es el apareamiento. Durante la estación de procreación. el glovito de máxima puntuación intercambia genes con otro elegido al azar. La descendencia porta un cromosoma compuesto. Parte de él proviene del progenitor superior, la otra. del ganador en la lotería de apareamiento. La composición se asemeja al fenómeno de entrecruzamiento que se da en los cromosornas reales. En los cromosomas de los glovitos. el entrecruzamiento puede ilustrarse combinando el primero de los cromosomas antes mencionados (sin alteración) con otro

    1 A 1 B 0 D 1 A 0 C 1 D 1 B
         ^       ^
         |       |  
   

Las flechas indican los puntos de entrecruzamiento, elegidos de forma estocástica. El eromosoma descendiente es idéntico al del segundo progenitor hasta llegar al primer punto de cruzamiento. Entre dicho punto y el segundo es idéntico a la correspondiente porción del cromosoma del primero. Tras el segundo punto es nuevamente idéntico al cromosoma del segundo progenitor (véase la figura 3)

1A1CODOB0C1D1B0C

Antes de decidirine a redactar y poner a prueba el programa primordial era yo un tanto escéptico acerca del va lor del apareamiento por cruce. Descubrí con sorpresa, sin embargo, que si el primer progenitor es razonablemente acertado en sus pronósticos, la descendencia tiende a serlo también. Los lectores pueden juzgar por si mismos preparando un programa que llamaremos AUTOSOPA.

Al listarlo el programa no excede demasiado de una página.
  • Consta de cuatro módulos in mersos en un bucle. Es preciso estable- cer un límite que defina la puntuación máxima. En tanto la puntuación má xima sea inferior al límite, el programa debe continuar funcionando a traves de sus cuatro módulos.
  • En el primero de los módulos se de- termina la puntuación de los 10 glovitos sobre una secuencia de 100 símbolos ambientales.
  • El segundo módulo sirve para identificar los glovitos que obtienen la puntuaciones mínima Y máxima resultante.
  • En el tercer módulo, el glovito de máxima puntuación es apareado con un compañero seleccionado al azar. El fruto de esta unión reemplaza al glovito de puntuación mínima.
  • En el cuarto y último módulo llega un rayo cósmico, que alcanza a un glovito cualquiera y provoca una mutación.
  • Justamente antes de que el programa vaya a invocar al tercer módulo (el de aparcamiento) se selecciona un número al azar. Si el número queda por debajo de cierto umbral, se pasa por alto el módulo de apareamiento y se ejecuta inmediatamente el móduio de mutación. Este umbral puede ajustarse al valor que se desee.

    Pero ciertos valores dan mejores resultados que otros. Si el módulo de apareamiento es ejecutado con excesiva frecuencia, la pequeña población queda rápidamente dominada por los genes del glovito de máxima puntuación. El fondo de recursos genéticos pierde variedad, y la evolución se decelera hasta un penoso arrastrar, o llega a detenerse completamente. En todo caso, la evolución se va haciendo cada vez más lenta conforme aumentan las puntuaciones. El glovito de máxima puntuación permanece en escena durante períodos cada vez más largos, porque resulta cada vez menos probable que lleguen a evolucionar glovitos superiores a él.

    En AUTOSOPA resulta conveniente utilizar cuatro tablas. Se llaman crom, estado, tanteo y e.

    • La tabla crom es una matriz bidimensional que consta de 10 glovitos y 16 genes. Crom (ij) corresponde i-ésimo gen del j-ésimo glovito.
    • Las tablas de estado y
    • tanteo con- tienen el estado actual y la puntuación de los 10 glovitos.
    • La cuarta tabla, e, contiene la cadena de caracteres básica utilizada para generar los símbolos del entorno. Esta lista se da mediante el teclado, al comienzo del programa.
    La evaluación de los glovitos se efectúa merced a un bucle doble. El bucle externo engendra 100 símbolos ambientales y el bucle interior incrementa el tanteo de cada glovito si éste atina a pronosticar correctament el signo si guiente. Podemos someter adecuadamente a prueba los glovitos de cuatro estados sobre entornos de período seis. Ello supone un problema de mediana dificultad. La evolución de predictores perfectos en un ambiente de período ocho puede exigir sesiones de funcio namiento del programa de todo un día; en cambio, los ambientes de período cuatro apenas si suponen dificultad al guna.

    En este primer módulo conviene utilizar dos trucos.

    El primero de ellos permite hacerse con el siguiente símbolo ambiental a partir del índice i del bucle exterior, calculando i módulo seis, o sea, el resto de la división de i entre seis. El número obtenido puede utilizarse como índice en la tabla e. Al ir recorriendo los valores de 1 a 100, el índice computado va repasando la tabla "e" una y otra vez, generando así la secuencia adecuada de símbolos ambientales. Conocido el indice del símbolo actual resulta fácil calcular cuál será el índice siguiente, y consultar la tabla. Tal simbolo se compara entonces, por turno. con la predicción hecha por cada glovito.

    El segundo truco permite al programa hallar rápidamente el estado consecutivo del glovito. y determinar cuál será su salida, sin más que inspeccionar el cromosoma, En lugar de representar los cuatro estados por A, B, C y D, en la tabla "estado" se utilizan como elementos los números 0, 1, 2 y 3. Llamando simb al símbolo de ambiente, la salida engendrada por el i-ésimo glovito puede hallarse usando primero una sencilla fórmula:

    l = 4 X estado(i) + 2 X simb.

    Seguidamente es preciso identificar el contenido de crom(i,l)

    El locus l del cromosoma del í-ésimo glovito emite su salida cuando la criatura se encuentra en el estado i y está recibiendo el símbolo de entrada simb. El estado si guiente ocupa el locus l + 1

    El módulo que determina los glovitos que encabezan y cierran la tabla de clasificación por tanteo se vale de un ejercicio frecuente en los cursos elementales de programación: dada una tabla de n números. escribir un programa que determine el máximo de todos ellos. Para resolverlo se da a una variable llamada max el valor inicial O, y se revisa la tabla mediante un bucle simple. Cada elemento de la tabla se va comparando con max. Si el elemento resulta ser mayor que max, el valor de éste es remplazado por el de tal elemento. Convendría también guardar el índice del elemento dentro de la tabla.

    El mismo programa, con una leve modificación, sirve para hallar el tanteo mínimo. Esta vez será preciso dar a una variable, min, el valor inicial 100 e irla rempiazando por el valor de los elementos que vayan siendo menores que ella.

    El tercer módulo se encarga de aparear el g)ovito de máxima puntuación con un individuo seleccionado al azar en la población. La única dificultad que plantea este segmento del programa estriba en la selección de los puntos de cruzamiento. Me parece que lo más sencillo es seleccionar al azar dos enteros c1 y c2, en el intervalo de 1 a 16. En el caso de que c1 fuese mayor que c2, se intercambiarían sus valores. Los lectores podrán comprobar que con un poco de finesse bastan tres bucles, que vayan de 1 a c1, de cl a c2 y de c2 a 16, para disponer de toda la maquinaria necesaria para trasladar elementos de crom situados en las hileras inseminantes hasta la fila destinataria. que está ocupada por el glovito condenado a desaparecer, por tener puntuacíón mínima. En el cuarto módulo tendrían que seleccionarse al azar un índice de glovito y un locus dentro de su cromosoma. La paridad de locus determina si quien ha de mutar habrá de ser un gen de estado o un gen de salida. Si el valor es 0, será preciso sumar 1 (módulo 2) al número ya almacenado allí. Por así decirlo. este proceder -vuelca--el bit. Si el valor de locus (módulo 2), fuese 1, es preciso sumar 1 (módulo 4 ) al elemento de la tabla. De este modo se cambia el valor almacenado.

    ¿He hecho trampa? Sin duda, mal puede decirse que sea aleatorio el sis- temático cambio de estado, de 0 a 1, y luego a 2 y a 3. y nuevamente a 0. Replico que es suficíentemente aleatorio: el número de estados es lo suficientemente pequeño para que uno no pueda esperar que el resultado final del programa sea muy diferente del obtenido cuando prevalezcan estados seleccionados más aleatoriamente. En realidad, yo había hecho también un poco de trampa al elegir c1 y c2 tan descuidadamente: tal método garantiza a ciertas subcadenas ventajas con respecto a otras. Pero, lo mismo que antes, me parece que las diferencias entre AUTOSOPA y un procedimiento de selección del cruzamiento estadísticamente corregido serían muy ligeras. Tanto de un modo como de otro se hacen con los genes tantos malabarismos y se han fragmentado tantas veces los cromosomas, que al glovito de cabeza de tabla le costaría mucho trabajo reconocer a sus propios nietos.

    Las únicas partes de AUTOSOPA todavía no especificadas son su comienzo y su final. Los glovitos que inicialmente ocupen el caldo primordial deberían haber sido seleccionados al azar. Para determinar cada uno de los genes de cada glovito se tendría que elegir un entero dentro de la gama apropiada y serle asignado a ese gen. Finalmente cuando un glovito exceda por primera vez el límite establecido en el bucle exterior, AUTOSOPA debería imprimirlo.

    Es preciso prevenir a los lectores dispuestos a embarcarse en esta aventura genuina de que hay en ella no poca exploración. Puede ocurrir que algunos de los exploradores lieguen a padecer de adicción.

    La presencia de evolución, y su ritmo, son cuestiones a elucidar. Cuando el período del entorno sea demasiado largo para que llegue a evolucionar un predictor perfecto de cuatro estados, ¿hasta qué punto llegan a aproximársele los glovitos? ¿De qué forma influyen los cambios de la longitud del período en la duración del tiempo requerido para que llegue a evolucionar un predictor perfecto?

    No hay nada en la descripción de mi AUTOSOPA que impida generalizar el programa para glovitos de 5 ó 6 estados. Se puede incluso modificar el programa para ex- plorar ambientes no periodicos, o bien ambientes que ocasionalmente cambien la serie básica de símbolos.

    El caldo de autómatas se inspiró en un libro aparecido a comienzos del decenio de 1961). Titulada "Artificial Intelligence through Simulated Evolution", la obra describe una serie de experimentos sobre la evolución de los autómatas, efectuados por Lawrence J. Fogel, Alvin J. Owens y Michael J. Walsh. A los autómatas se les pedía que pronosticasen secuencias periódicas, y se los permitía evolucionar de modo simiiar al de nuestros glovitos. Sin embargo, en aquel austero estudio, a los autómatas no se les permitía el apareamiento ni el entrecruzamiento de genes

    Fue Holland quien me sugirió que añadiera a la sopa de autómatas el ingrediente del entrecruzamienlo genético. Como ya hice notar, Holland es el padre reconocido del algoritmo genético. Los especialistas de este sistema. cuyo número crece constantemente, se reunieron en una pionera conferencia a gran escala, debidamente financiada, en la Carnegie-Mellon University. Allí analizaron un amplio abanicu de teoría y aplicaciones.

    Un problema analizado en diversos artículos, puede servir de interesarte introducción a la materia de la programación genética. Se llama "problema del viajante de comercio", y lanza el siguienic reto: dado el mapa de n ciudades- enlazadas por una red de carreteras, hallar el mínimo circuito que pase por todas ellas. (....) Casi todos los especialistas del arte de los algoritmos genéticos están dispuestos a conceder que el problema del viajante de comercio es uno de los más grandes retos que tienen planteados.

    Existen (...) algoritmos genéticos que aportan un aceptable rendimiento en este problema.

    Empero, ningún algoritmo genético ha sido capaz hasta ahora de conquistar una solución al problema del viajante, en ninguno dc los sentidos de "solución" aceptados comúnmente. Ello es debido, sin duda alguna, a la intrínseca dificultad del problema. Por tratarse de uno de los problemas que en teoría de computación se denominan NP-completos. es muy posible que sea su destino el permanecer por siempre insoluble en la práctica.

    Enero 1986

    Dewdney - Abr 1986

    En el número de enero de este año se presentaron los "g1ovitos": glóbulos vivos finitos que tratan de pronosticar los cambios de su ambiente. En el caldo informático primordial, en cada generación, el más atinado en su predicción cruza su cromosoma con el de un glovito seleccionado al azar. De este modo van evolucionando predictores cada vez más atinados, hasta que se engendra uno perfecto.

    Un glovito es, en esencia, un autómata finito. Es decir, tiene un número finito de estados, y por cada señal que recibe (un 0 o un 1) emite una señal y adopta un nuevo estado. La señal que cada glovito emite durante su ciclo de funcionamiento es su predicción de cuál será la próxima señal que reciba del entorno.

    No faltaron lectores que propusieron a sus glovitos tareas de predicción imposibles. Jamás podrá evolucionar un glovito capaz de predecir una secuencia aleatoria de bits. Ni llegan a desarrollarse glovitos capaces de predecir números primos. Resulta perfectamente razonable pedirle a un glovito que vaticine una secuencia repetitiva de dígitos binarios. Por ejemplo, existe un glovito tetraestado capaz de predecir la secuencia 01100010 de ocho símbolos repetidos. Sin embargo, hasta una secuencia repetitiva puede rebasar la capacidad de predicción de un glovito si su período básico es demasiado largo respecto del número de estados del glovito. Por ejemplo, ningún glovito de 4 estados predecirá la secuencia repetitiva 010010111. ¿Por qué no?

    La respuesta más sencilla a esta cuestión comporta un proceso que llamaré inducción trepadora. Imaginemos un glovito de un solo estado. Podría predecir la repetición sin fin de la ristra fundamental 01. Para cada una de las dos posibles señales que el glovito pueda recibir hay una respuesta: si se recibe un 0, el glovito emite un 1 y luego vuelve a asumir el mismo estado. Si recibe un 1, emite un 0. Si el período fundamental tiene tres símbolos - supongamos que sea 011- no le es posible al glovito predecirlo, sencillamente porque el autómata no dispone de repertorio de respuestas lo suficientemente abundante. Por otra parte, un glovito de 2 estados dispone de cuatro posibles respuestas, dos para cada estado.

    Así, puede predecir una serie repetitiva de cuatro símbolos, aunque no una serie de cinco; cuando llegue el quinto símbolo, el glovito habrá de repetir una de las respuestas anteriores. El razonamiento es obvio. Un glovito de n-estados puede predecir cadenas de hasta 2n símbolos, pero no las series que tengan longitudes de 2n + 1 símbolos, o mayores. Se puede pasar un rato ameno preparando períodos de 8 símbolos, y construyendo seguidamente, a mano, el glovito tetraestado capaz de predecirlo.

    El predictor perfecto así obtenido es esencialmente único. Cabe medir el éxito de¡ programa AUTOSOPA comparando el predictor perfecto obtenido de él por evolución con el glovito ya construido. Varios lectores hallaron procedimientos para hacer que AUTOSOPA funcionase más rápido. Por ejemplo, no tiene mucho objeto poner a prueba la tanda actual de 100 símbolos ambientales si la cadena básica solamente tiene una longitud de seis símbolos. Una repetición de la cadena producirá 12 símbolos ambientales, los cuales deberían bastar para casi todos nuestros propósitos. Philip Kaaret, de la Universidad de Princeton, ha señalado que el programa puede abreviarse también si en lugar de dársele puntuación a todos los glovitos de una población cada vez que se ejecuta el bucle principal solamente se le otorga a dos. Después de todo, únicamente dos glovitos (como máximo) habrán cambiado, a saber, el de puntuación mínima, que se ha remplazado por un nuevo híbrido, y uno de los restantes glovitos, que ha podido sufrir el impacto de un rayo cósmico.

    Las aceleraciones que se obtienen, sea al abreviar la secuencia de ensayo ambiental, sea prescindiendo del ensayo para los glovitos antiguos, resultan sensiblemente equivalentes. Quedará así tiempo suficiente para hacer evolucionar glovitos n-estado que predigan secuencias repetitivas básicas de hasta 2n símbolos.

    Por lo que dice en su carta, parece que Ed Coudal, de Park Ridge, Illinois, sentía cierta renuencia a enviar directamente el glovito de mínima puntuación a engrosar el coro celestial. Optó por cruzarlo en cada ciclo con el glovito de puntuación máxima. Obedeciendo a este ingenioso plan, Coudal logró producir, en menos de 40 generaciones, glovitos capaces de predecir una ristra fundamental formada por seis símbolos.

    Vuelta a Portada 1