Informática evolutiva

1 Búsqueda, optimización y aprendizaje

Esta terna define los problemas a los que se pueden aplicar los algoritmos evolutivos, en cualquiera de sus formas. Por eso parece conveniente, antes que nada, describir el tipo de problemas a los que nos podremos enfrentar, mejor que presentarlos como la panacea que es capaz de encontrar la respuesta a la Pregunta Última sobre la Vida, el Universo y todo lo demás (además, todo el mundo sabe que es 42).

En realidad, los algoritmos de búsqueda abarcan prácticamente todo algoritmo para resolver problemas automáticamente. Habitualmente, en Informática se habla de búsqueda cuando hay que hallar información, siguiendo un determinado criterio, dentro de un conjunto de datos almacenados; sin embargo, aquí nos referiremos a otro tipo de algoritmos de búsqueda, a saber, aquellos que, dado el espacio de todas las posibles soluciones a un problema, y partiendo de una solución inicial, son capaces de encontrar la solución mejor o la única. El ejemplo clásico de este tipo de problemas se encuentra en los rompecabezas y juegos que se suelen abordar en inteligencia artificial. Un ejemplo es el problema de las 8 reinas, en el cual se deben de colocar 8 reinas en un tablero de ajedrez de forma que ninguna amenace a otra; o las torres de Hanoi, en el que, dada una serie de discos de radio decreciente apilados, hay que apilarlos en otro sitio teniendo en cuenta que no se puede colocar ningún disco encima de otro de radio inferior.

Este tipo de problemas es fácil de abordar usando algoritmos "clásicos", como por ejemplo algoritmos recursivos o de tipo voraz (greedy), sin embargo, hay otro tipo de problemas mucho más complicados, sobre todo los NP-completos (aquellos cuya complejidad crece con el tamaño del problema de forma exponencial) que no pueden ser abordados de esta forma. Algunos ejemplos de estos problemas serían los siguientes:

• 8-puzzle, en el cual, como se muestra en la ilustración 1, a partir de una configuración inicial donde hay 8 cuadros desordenados, hay que llegar a otra configuración donde estén ordenados, usando para el intercambio cualquier posición que se halle vacía. El problema de búsqueda en este caso consiste en encontrar un camino que vaya desde la configuración inicial hasta la final.
• Problema del viajante, en el cual, dadas una serie de ciudades separadas por distancias diferentes, hay que calcular un camino tal que la distancia total recorrida sea mínima, y no que no repita ninguna ciudad. Este problema es NP-completo, y es paradigmático de este tipo de problemas.
• Mastermind: En este juego, que se muestra en la figura 2, un jugador debe de averiguar una combinación de chinchetas de colores oculta por el otro jugador, y lo hace haciendo suposiciones sobre la combinación, y siendo contestado con una chincheta pequeña y blanca por cada acierto de color, y una negra por cada acierto de color o posición. Sólo una solución (entre 6⁴) es la correcta, pero el jugador que ha puesto la combinación oculta va orientando la búsqueda mediante las chinchetas blancas o negras. El problema se hace exponencialmente más difícil cuando se aumenta el número de colores, y la longitud de la combinación.

En muchos casos, la búsqueda está guiada por una función que indica lo buena que es esa solución, o el coste de la misma, o lo cerca que se está de la solución final, si es que se conoce; el problema se convierte entonces en un problema de optimización, es decir, encontrar la solución que maximiza la función objetivo, de evaluación o fitness o minimiza el coste. En términos formales, dada una función F de n variables x₁,x₂,..., x_n, optimizar la función consiste en encontrar la combinación de valores de x_i tales que F(x₁, x₂,..., x_n) = Máximo. Se puede hablar de maximizar en vez de minimizar sin perder generalidad, ya que maximizar F equivale a minimizar -F.

Generalmente, los problemas de optimización son tratados por la rama de las matemáticas denominada Investigación Operacional, aunque prácticamente todas las ramas de la ciencia y la ingeniería necesitan tratar con problemas de optimización en algún momento. Por ejemplo, en teoría de juegos se trata de maximizar la probabilidad de ganar, y en reconocimiento de patrones de minimizar el error de clasificación de un patrón desconocido (como una imagen de satélite digitalizada, o un canal procesado de una señal de un electroencefalograma).

El problema de optimización no siempre está formulado de una forma tan clara. En muchos casos, la forma de la función F no se conoce, y debe de aproximarse mediante polinomios o combinaciones de funciones conocidas; habría entonces que hallar los coeficientes de los polinomios o funciones que hacen que la función calculada se acerque lo más posible a la función objetivo. Cuando el problema se reduce a calcular una serie de coeficientes, se habla de optimización paramétrica.

En control industrial se plantean también problemas de optimización: como mantener el funcionamiento de una máquina dentro de su régimen óptimo, por ejemplo. Cada máquina suele tener una serie de parámetros variables, y lo que se desea optimizar es habitualmente la calidad del producto final o la rapidez a la hora de producirlo.

En algunos casos, la función de evaluación ni siquiera existe, o no es estática, sino que viene dada por el entorno de la solución. Por ejemplo, en un programa para jugar al Othello o reversi, el fitness vendrá dada por su puntuación a la hora de jugar con los demás jugadores. Un autor, Pollack hizo enfrentarse a unas estrategias de juego con otras, de forma que según van evolucionando, el fitness va variando. Este tipo de optimización se suele encontrar en problemas de vida artificial y el Dilema del Prisionero, usado para modelizar interacciones sociales.

El dilema del prisionero iterado es un juego en el cual se enfrentan dos jugadores, que representan dos presos en una cárcel, que se han puesto de acuerdo para fugarse; en cada iteración, cada jugador decide si se chiva al director de la cárcel, o coopera con el otro y se escapa. Si los dos cooperan, reciben una recompensa de 3; si uno de los dos se chiva, recibe todos los privilegios de un preso bueno en la forma de una recompensa de 5, y si los dos se chivan, reciben una recompensa, pero mucho menor, como aparece en la tabla. Si este juego se repite por un número finito y conocido de iteraciones, la estrategia óptima es siempre chivarse, porque consigues una recompensa asegurada de 1*número de jugadas, sin embargo, a largo plazo la estrategia óptima es cooperar, porque la recompensa es de 3. Con este juego se han hecho muchas variantes; un algoritmo debería de crear una estrategia de forma que maximice la recompensa de un jugador.

En los problemas de Biología que la Vida Artificial trata de resolver mediente simulaciones, el fitness viene siempre dado por el entorno, acercándose a la definición biológica de fitness, que no es otra cosa que el número posible de descendientes de un individuo (que no siempre es el mismo que el número real de descendientes).

En algunos se trata de optimizar F(C), donde C es una combinación de diferentes elementos que pueden tomar un número finito de valores; pueden ser combinaciones con o sin repetición, o incluso permutaciones, como en el caso del problema del viajante; en este caso se denominan problemas de optimización combinatoria.

No siempre, el espacio de búsqueda completo contiene soluciones válidas; en algunos casos, los valores de las variables se sitúan dentro de un rango, más allá del cual la solución es inválida. Se trata entonces de un problema de optimización con restricciones. En este caso, el problema consiste en maximizar F(x_i) dentro del subespacio. Un ejemplo de este problema es el de optimización de los horarios de clase de una institución de enseñanza; hay que disponerla de forma que un profesor no deba estar en dos sitios a la vez (un alumno, puede), que el número de horas libres entre clases sea mínimo, y que se cumplan las preferencias de todos los implicados. En este caso, la optimización se reduce a cumplir todas las restricciones.

Otro ejemplo clásico es el denominado job-shop scheduling, o disposición de una línea de montaje, en donde cada componente de la línea debe de estar ocupado el mayor tiempo posible y cumplir restricciones de tiempos de entrega, hay muchas formar de abordar problemas de optimización. Algunas de ellas se verán en las siguientes secciones

1.1 Método analítico

Si existe la función F, es de una sola variable, y se puede derivar dos veces en todo su rango, se pueden hallar todos sus máximos, sean locales o globales. Sin embargo, la mayoría de las veces no se conoce la forma de la función F, y si se conoce, no tiene porqué ser diferenciable ni siquiera una vez. Incluso el tratamiento analítico para funciones de más de 1 variable es complicado.

1.2 Métodos exhaustivos, aleatorios y heurísticos

Los métodos exhaustivos recorren todo el espacio de búsqueda, quedándose con la mejor solución, y los heurísticos utilizan reglas para eliminar zonas del espacio de búsqueda consideradas "poco interesantes". Algunos algoritmos de búsqueda, como el MiniMax, son de este tipo; se suelen utilizar en juegos para examinar y podar el árbol de posibilidades a partir de la jugada actual; Deep Blue, por ejemplo, juega de esta forma.

En los métodos aleatorios, se va muestreando el espacio de búsqueda acotando las zonas que no han sido exploradas; se escoge la mejor solución, y, además, se da el intervalo de confianza de la solución encontrada.

1.3 Subiendo al cerro,

En estos métodos, también denominados de hillclimbing, se va evaluando la función en uno o varios puntos, pasando de un punto a otro en el cual el valor de la evaluación es superior. La búsqueda termina cuando se ha encontrado el punto con un valor máximo. En general, un algoritmo escalador funciona de la forma siguiente.

Algoritmo escalador

1. Escoger una solución inicial (x_i,...,x_n)
2. Mientras que siga subiendo el valor de F, hacer
3. Alterar la solución (x'_i,...,x'_n) = (x_i,...,x_n) + (y_i,...,y_n), y evaluar F.
4. Si F(x'_i,...,x'_n) > F(x_i,...,x_n), hacer (x_i,...,x_n) = (x'_i,...,x'_n).
5. Volver a 2.

Estos algoritmos toman muchas formas diferentes, según el número de dimensiones del problema solución, el valor del incremento y en la dirección en la cual se tiene que dar. En algunos casos se utiliza el llamado Método Montecarlo (por el casino), en el cual se escoge la nueva solución de forma aleatoria.

El principal problema de este tipo de algoritmos es que se quedan en el pico más cercano a la solución inicial; además, no son válidos para problemas multimodales, en los cuales la función de coste tiene varios óptimos posibles.

1.4 Recocimiento simulado

Conocido como Simulated Annealing, en inglés, el nombre viene de la forma como se consiguen ciertas aleaciones en forja; una vez fundido el metal, se va enfriando poco a poco, para conseguir finalmente la estructura cristalina correcta, que haga que la aleación sea dura y resistente.

Este algoritmo se podría calificar como escalador estocástico, y su principal objetivo es evitar los mínimos locales en los que suelen caer los escaladores. Para ello, no siempre acepta la solución óptima, sino que a veces puede escoger una solución menos óptima, siempre que la diferencia entre ambos tenga un nivel determinado, que depende de un parámetro denominado temperatura (seguimos con la metáfora). El algoritmo de recocimiento simulado es el siguiente:

Algoritmo de recocimiento simulado

1. Inicializar la temperatura T, y la solución inicial (x_i,...,x_n) y evaluar F(x_i,...,x_n).
2. Repetir los pasos siguientes, hasta que la temperatura sea nula o el valor de F converja:
3. Disminuir la temperatura.
4. Seleccionar una nueva solución (x_i',...,x'_n) en la vecindad de la anterior (mutar la solución), y evaluarla.
5. Si F(x'_i,...,x'_n) > F(x_i,...,x_n), hacer (x_i,...,x_n) = (x'_i,...,x'_n), si no, generar un número aleatorio R entre 0 y 1. Si, entonces (x_i,...,x_n) = (x'_i,...,x'_n).

1.5 Técnicas basadas en población

Este tipo de técnicas pueden ser versiones de cualquiera de las anteriores, pero en vez de tener una sola solución, que se va alterando hasta obtener el óptimo, se persigue el óptimo cambiando varias soluciones; de esta forma es más fácil escapar de los mínimos locales tan temidos. Entre estas técnicas se hallan la mayoría de los algoritmos evolutivos.

1.6 Técnicas experimentales

En algunos casos, solo el ojo humano es capaz de evaluar lo apropiada que es una solución a un tema determinado, por ejemplo, en problemas de diseño o de calidad. En este caso, se pueden utilizar cualquiera de las técnicas expuestas anteriormente, pero a la hora de evaluar una solución, un experto o experta tendrá que darle una puntuación. Por ejemplo, es lo que se usa cuando uno se prueba ropa para dar con la combinación correcta de colores y estilos.

2 La evolución

Cambiemos totalmente de tercio, y después de ver tipo de problemas a los que se pueden aplicar los algoritmos evolutivos, se va a estudiar qué es lo que inspira dichos algoritmos, la Naturaleza, ese fenómeno natural denominado evolución, y si optimiza o no.

La teoría de la evolución (que no es tal teoría, sino una serie de hechos probados), fue descrita por Charles Darwin (ilustración 3) 20 años después de su viaje por las islas Galápagos en el Beagle, en el libro Sobre el Origen de las Especies por medio de la Selección Natural. Este libro fue bastante polémico en su tiempo, y en cualquier caso es una descripción incompleta de la evolución. La hipótesis de Darwin, presentada junto con Wallace, que llegó a las mismas conclusiones independientemente, es que pequeños cambios heredables en los seres vivos y la selección son los dos hechos que provocan el cambio en la Naturaleza y la generación de nuevas especies. Pero Darwin desconocía cual es la base de la herencia, pensaba que los rasgos de un ser vivo eran como un fluido, y que los "fluidos" de los dos padres se mezclaban en la descendencia; esta hipótesis tenía el problema de que al cabo de cierto tiempo, una población tendría los mismos rasgos intermedios.

Fue Lendel (4ilustración) quien descubrió que los caracteres se heredaban de forma discreta, y que se tomaban del padre o de la madre, dependiendo de su carácter dominante o recesivo. A estos caracteres que podían tomar diferentes valores se les llamaron genes, y a los valores que podían tomar, alelos. En realidad, las teorías de Lendel, que trabajó en total aislamiento, se olvidaron y no se volvieron a redes cubrir hasta principios del siglo XX. Además, hasta 1930 el geneticista inglés Robert Aylmer no relacionó ambas teorías, demostrando que los genes mendelianos eran los que proporcionaban el mecanismo necesario para la evolución.

Más o menos por la misma época, el biólogo alemán Walther Flemming describió los cromosomas (figura 5), como ciertos filamentos en los que se agregaba la cromatina del núcleo celular durante la división; poco más adelante se descubrió que las células de cada especie viviente tenían un número fíjo y característico de cromosomas.

Y no fue hasta los años 50, cuando Watson y Crick descubrieron que la base molecular de los genes está en el ADN, ácido desoxirribonucleico (figura 6). Los cromosomas están compuestos de ADN, y por tanto los genes están en los cromosomas.

La macromolécula de ADN está compuesta por bases púricas y pirimidínicas, la adenina, citosina, guanina y timina. La combinación y la secuencia de estas bases forma el código genético, único para cada ser vivo. Grupos de 3 bases forman un codon, y cada codon codifica un aminoácido (el que exprese ese aminoácido o no depende de otros factores); el código genético codifica todas las proteinas que forman parte de un ser vivo. Mientras que al código genético se le llama genotipo, al cuerpo que construyen esas proteínas, modificado por la presión ambiental, la historia vital, y otros mecanismos dentro del cromosoma, se llama fenotipo.

No toda la cadena de ADN codifica proteínas, es decir, no todos son genes; las zonas que codifican proteínas se llaman intrones, las zonas que no lo hacen, exones. La cantidad de ADN basura aumenta desde los seres vivos más simples, como las bacterias, donde no hay nada, hasta los seres humanos, donde gran cantidad del ADN no codifica. Un gen comienza con el sitio 3' o aceptor y termina con el sitio 5' o donante. Proyectos como el del Genoma Humano tratan de identificar cuáles son estos genes, sus posiciones, y sus posibles alteraciones, que habitualmente conducen a enfermedades.

Todos estos hechos forman hoy en día la teoría del neo-darwinismo, que afirma que la historia de la mayoría de la vida está causada por una serie de procesos que actúan en y dentro de las poblaciones: reproducción, mutación, competición y selección. La evolución se puede definir entonces como cambios en el pool o conjunto genético de una población.

Un tema polémico, con opiniones variadas dependiendo de si se trata de informáticos evolutivos o de biólogos o geneticistas, es si la evolución optimiza o no. Según los informáticos evolutivos, la evolución optimiza, puesto que va creando seres cada vez más perfectos, cuyo culmen es el hombre; además, indicios de esta optimización se encuentran en el organismo de los animales, desde el tamaño y tasa de ramificación de las arterias, diseñada para maximizar flujo, hasta el metabolismo, que optimiza la cantidad de energía extraída de los alimentos. Sin embargo, los geneticistas y biólogos evolutivos afirman que la evolución no optimiza, sino que adapta y optimiza localmente en el espacio y el tiempo; evolución no significa progreso. Un organismo más evolucionado puede estar en desventaja competitiva con uno de sus antepasados, si se colocan en el ambiente del último.

2.1 Mecanismos de cambio en la evolución

Estos mecanismos de cambio serán necesarios para entender los algoritmos evolutivos, pues se trata de imitarlos para resolver problemas de ingeniería; por eso merece la pena conocerlos en más profundidad. Los mecanismos de cambio alteran la proporción de alelos de un tipo determinado en una población, y se dividen en dos tipos: los que disminuyen la variabilidad, y los que la aumentan.

Los principales mecanismos que disminuyen la variabilidad son los siguientes:

• Selección natural: los individuos que tengan algún rasgo que los haga menos válidos para realizar su tarea de seres vivos, no llegarán a reproducirse, y, por tanto, su patrimonio genético desaparecerá del pool; algunos no llegarán ni siquiera a nacer. Esta selección sucede a muchos niveles: competición entre miembros de la especie (intraespecífica), competición entre diferentes especies, y competición predador-presa, por ejemplo. También es importante la selección sexual, en la cual las hembras eligen el mejor individuo de su especie disponible para reproducirse, y que da lugar a vistosos despliegues, luchas y documentales del National Geographic.
• Deriva génica: el simple hecho de que un alelo sea más común en la población que otro, causará que la proporción de alelos de esa población vaya aumentando en una población aislada, lo cual a veces da lugar a fenómenos de especiación, por ejemplo, por el denominado efecto fundador.

Otros mecanismos aumentan la diversidd, y suceden generalmente en el ámbito molecular. Los más importantes son:

• Mutación: la mutación es una alteración del código genético, que puede suceder por múltiples razones. En muchos casos, las mutaciones las elimina la ADN-polimerasa, la navaja del ejército suizo del ADN, que igual duplica, que corrije, que desinvierte un cacho genético mal colocado, también puede sácer que ocurran en zonas no codificadoras. En muchos otros casos, las mutaciones, que cambian un nucleótido por otro, son letales, y los individuos ni siquiera llegan a desarrollarse, pero a veces se da lugar a la producción de una proteína que aumenta la supervivencia del individuo, y que, por tanto, es pasada a la decendencia. Las mutaciones son totalmente aleatorias, y son el mecanismo básico de generación de variedad genética. A pesar de lo que se piensa habitualmente, la mayoría de las mutaciones ocurren de forma natural, aunque existen sustancias mutagénicas que aumentan su frecuencia.
• Poliploidía: mientras que las células normales poseen dos copias de cada cromosoma, y las células reproductivas una (haploides), puede suceder por accidente que alguna célula reproductiva tenga dos copias; si se logra combinar con otra célula diploide o haploide dará lugar a un ser vivo con varias copias de cada cromosoma. La mayoría de las veces, la poliploidía da lugar a individuos con algún defecto (por ejemplo, el tener 3 copias del cromosoma 21 da lugar al mongolismo), pero en algunos casos se crean individuos viables. Un caso conocido de mutación fue el que sufrió (o disfrutó) el mosquito Culex pipiens, en el cual se duplicó un gen que generaba una enzima que rompía los organofosfatos, componentes habituales de los insecticidas;
• Recombinación: cuando las dos células sexuales, o gametos, una masculina y otra femenina se combinan, los cromosomas de cada una también lo hacen, intercambiándose genes, que a partir de ese momento pertenecerán a un cromosoma diferente. A veces también se produce traslocación dentro de un cromosoma; una secuencia de código se elimina de un sitio y aparece en otro sitio del cromosoma, o en otro cromosoma.
• Flujo genético: o intercambio de material genético entre seres vivos de diferentes especies. Normalmente se produce a través de un vector, que suelen ser virus o bacterias; estas incorporan a su material genético genes procedentes de una especie a la que han infectado, y cuando infectan a un individuo de otra especie pueden transmitirle esos genes a los tejidos generativos de gametos.

En resumen, la selección natural actúa sobre el fenotipo y suele disminuir la diversidad, haciendo que sobrevivan solo los individuos más aptos (aunque esta frase, bien mirada, es una redundancia: ¿Sobreviven los mejores o son los mejores porque sobreviven?); los mecanismos que generan diversidad y que combinan características actúan habitualmente sobre el genotipo.

3 Evolución de la informática evolutiva

Ya que se han descrito cuales son los mecanismos de la evolución, y una amplia gama de problemas que pueden o no tener relación entre sí, llega la hora de contar, desde sus principios, como evolucionó la idea de simular o imitar la evolución con el objeto de resolver problemas humanos.

Las primeras ideas, incluso antes del descubrimiento del ADN, vinieron de Von Neumann, uno de los mayores científicos de este siglo. Von Neumann afirmó que la vida debía de estar apoyada por un código que a la vez describiera como se puede construir un ser vivo, y tal que ese ser creado fuera capaz de autorreproducirse; por tanto, un autómata o máquina autorreproductiva tendría que ser capaz, aparte de contener las instrucciones para hacerlo, de ser capaz de copiar tales instrucciones a su descendencia.

Sin embargo, no fue hasta mediados de los años cincuenta, cuando el rompecabezas de la evolución se había prácticamente completado, cuando Box comenzó a pensar en imitarla para, en su caso, mejorar procesos industriales. La técnica de Box, denominada EVOP (Evolutionary Operation), consistía en elegir una serie de variables que regían un proceso industrial. Sobre esas variables se creaban pequeñas variaciones que formaban un hipercubo, variando el valor de las variables una cantidad fija. Se probaba entonces con cada una de las esquinas del hipercubo durante un tiempo, y al final del periodo de pruebas, un comité humano decidía sobre la calidad del resultado. Es decir, se estaba aplicando mutación y selección a los valores de las variables, con el objeto de mejorar la calidad del proceso. Este procedimiento se aplicó con éxito a algunas industrias químicas.

Un poco más adelante, en 1958, Friedberg y sus colaboradores pensaron en mejorar usando técnicas evolutivas la operación de un programa. Para ello diseñaron un código máquina de 14 bits (2 para el código de operación, y 6 para los datos y/o instrucciones); cada programa, tenía 64 instrucciones. Un programa llamado Herman, ejecutaba los programas creados, y otro programa, el Teacher o profesor, le mandaba a Herman ejecutar otros programas y ver si los programas ejecutados habían realizado su tarea o no. La tarea consistía en leer unas entradas, situadas en una posición de memoria, y debían depositar el resultado en otra posición de memoria, que era examinada al terminarse de ejecutar la última instrucción.

Para hacer evolucionar los programas, Friedberg hizo que en cada posición de memoria hubiera dos alternativas; para cambiar un programa, alternaba las dos instrucciones (que eran una especie de alelos), o bien reemplazaba una de las dos instrucciones con una totalmente aleatoria.

En realidad, lo que estaba haciendo es usar mutación para generar nuevos programas; al parecer, no tuvo más éxito que si hubiera buscado aleatoriamente un programa que hiciera la misma tarea. El problema es que la mutación sola, sin ayuda de la selección, hace que la búsqueda sea prácticamente una búsqueda aleatoria.

Más o menos simultáneamente, Bremmerman trató de usar la evolución para "entender los procesos de pensamiento creativo y aprendizaje", y empezó a considerar la evolución como un proceso de aprendizaje. Para resolver un problema, codificaba las variables del problema en una cadena binaria de 0s y 1s, y sometía la cadena a mutación, cambiando un bit de cada vez; de esta forma, estableció que la tasa ideal de mutación debía de ser tal que se cambiara un bit cada vez. Bremmerman trató de resolver problemas de minimización de funciones, aunque no está muy claro qué tipo de selección usó, si es que usó alguna, y el tamaño y tipo de la población. En todo caso, se llegaba a un punto, la "trampa de Bremmerman", en el cual la solución no mejoraba; en intentos sucesivos trató de añadir entrecruzamiento entre soluciones, pero tampoco obtuvo buenos resultados. Una vez más, el simple uso de operadores que creen diversidad no es suficiente para dirigir la búsqueda genética hacia la solución correcta; y corresponde a un concepto de la evolución darwiniano clásico, o incluso de libro de comic: por mutación, se puede mejorar a un individuo; en realidad, la evolución actúa a nivel de población.

El primer uso de procedimientos evolutivos en inteligencia artificial se debe a Reed, Toombs y Baricelli, que trataron de hacer evolucionar un tahúr que jugaba a un juego de cartas simplificado. Las estrategias de juego consistían en una serie de 4 probabilidades de apuesta alta o baja con una mano alta o baja, con cuatro parámetros de mutación asociados. Se mantenía una población de 50 individuos, y aparte de la mutación, había intercambio de probabilidades entre dos padres. Es de suponer que los perdedores se eliminaban de la población (tirándolos por la borda). Aparte de, probablemente, crear buenas estrategias, llegaron a la conclusión de que el entrecruzamiento no aportaba mucho a la búsqueda.

Los intentos posteriores, ya realizados en los años 60, ya corresponden a los algoritmos evolutivos modernos, y se han seguido investigando hasta nuestros días. Algunos de ellos son simultáneos a los algoritmos genéticos, pero se desarrollaron sin conocimiento unos de otros. Uno de ellos, la programación evolutiva de Fogel, se inició como un intento de usar la evolución para crear máquinas inteligentes, que pudieran prever su entorno y reaccionar adecuadamente a él. Para simular una máquina pensante, se utilizó un autómata celular. Un autómata celular es un conjunto de estados y reglas de transición entre ellos, de forma que, al recibir una entrada, cambia o no de estado y produce una salida. En la figura 7, se muestra un autómata con estados etiquetados por letras mayúsculas y representados por círculos, las reglas de transición, con líneas que los unen, los símbolos de entrada son 0 y 1, y los símbolos de salida con letras mayúsculas.

Fogel trataba de hacer aprender a estos autómatas a encontrar regularidades en los símbolos que se le iban enviando. Como método de aprendizaje, usó un algoritmo evolutivo: una población de diferentes autómatas competía para hallar la mejor solución, es decir, predecir cual iba a ser el siguiente símbolo de la secuencia con un mínimo de errores; los peores 50% eran eliminados cada generación, y sustituidos por otros autómatas resultantes de una mutación de los existentes.

De esta forma, se lograron hacer evolucionar autómatas que predecían algunos números primos (por ejemplo, uno, cuando se le daban los números más altos, respondía siempre que no era primo; la mayoría de los números mayores de 100 son no primos). En cualquier caso, estos primeros experimentos demostraron el potencial de la evolución como método de búsqueda de soluciones novedosas.

Más o menos a mediados de los años 60, Rechenberg y Schwefel describieron las estrategias de evolución. Las estrategias de evolución son métodos de optimización paramétricos, que trabajan sobre poblaciones de cromosomas compuestos por números reales. Hay diversos tipos de estrategias de evolución, que se verán más adelante, pero en la más común, se crean nuevos individuos de la población añadiendo un vector mutación a los cromosomas existentes en la población; en cada generación, se elimina un porcentaje de la población (especificado por los parámetros y µ), y los restantes generan la población total, mediante mutación y crossover. La magnitud del vector mutación se calcula adaptativamente.