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