Evolución de los Algoritmos Geneticos

El origen de lo que se conoce como computación evolutiva hay que buscarlo en su razón de ser: los conocimientos sobre evolución se pueden aplicar en la resolución de problemas de optimización. Fue en las décadas de 1950 y 1960 cuando varios científicos, de modo independiente, comenzaron a estudiar los sistemas evolutivos, guiados por la intuición de que se podrían emplear como herramienta en problemas de optimización en ingeniería. La idea era “evolucionar” una población de candidatos a ser solución de un problema conocido, utilizando operadores inspirados en la selección natural y la variación genética natural.

Fue Rechenberg quien, en la década de 1960 (1965, 1973) introdujo las “estrategias evolutivas”, método que empleó para optimizar parámetros reales para ciertos dispositivos.

La misma idea fue desarrollada posteriormente por Schwefel (1975, 1977). El campo de las estrategias evolutivas ha permanecido como un área de investigación activa, cuyo desarrollo se produce, en su mayor parte,  de modo independiente al de los algoritmos genéticos (aunque recientemente se ha visto como las dos comunidades han comenzado ha colaborar). Fogel, Owens y  Walsh (1966), fueron los creadores de la “programación evolutiva”, una técnica en la cual las candidatas a soluciones a tareas determinadas, eran representadas por máquinas de estados finitos, cuyos diagramas de estados de transición se evolucionaban mediante mutación aleatoria, seleccionándose el que mejor aproximara. Una formulación más amplia de la programación evolutiva, es un campo de investigación que también continúa en activo (ver, por ejemplo, a Fogel y Altman 1993). Estas tres áreas, estrategias evolutivas, algoritmos genéticos, y programación evolutiva, son las que forman la columna vertebral de la Computación Evolutiva, y de ellas parten los caminos hacia  todos los campos de investigación inspirados en nuestros conocimientos sobre Evolución.

Pero muchos otros investigadores desarrollaron su trabajo en los algoritmos para la optimización y el aprendizaje inspirados en la evolución. Cabe resaltar nombres como los de Box (1957), Friedman (1959), Bledsoe (1961), Bremermann (1962), y Reed, Toombs y Baricelli (1967). Sin embargo, su trabajo no ha tenido, ni con mucho, la atención que han recibido las estrategias evolutivas, programación evolutiva, y los algoritmos genéticos.

Hay que recordar además a los biólogos evolucionistas que han utilizado el ordenador para simular la evolución para realizar experimentos controlados (Baricelli 1957, 1962; Fraser 1957 a,b; Martin y Coreman 1960). Pero habría que esperar hasta que la computación electrónica se desarrollara, para poder apreciar la consolidación definitiva de la computación evolutiva.

Centrémonos en los Algoritmos Genéticos. La primera mención del término, y la primera publicación sobre una aplicación del mismo, se deben a Bagley (1967), que diseñó algoritmos genéticos para buscar conjuntos de parámetros en funciones de evaluación de juegos, y los comparó con los algoritmos de  correlación, procedimientos de aprendizaje modelizados después de los algoritmos de pesos variantes de ese periodo. Pero es otro científico el considerado creador de los Algoritmos Genéticos: John Holland, que los desarrolló, junto a sus alumnos y colegas, durante las décadas de 1960 y 1970. En contraste con las estrategias evolutivas y la programación evolutiva, el propósito original de Holland no era diseñar algoritmos para resolver problemas concretos, sino estudiar, de un modo formal, el fenómeno de la adaptación tal y como ocurre en la naturaleza, y desarrollar vías de extrapolar esos mecanismos de adaptación  natural a los sistemas computacionales.

El libro que Holland escribió en 1975  Adaptación en Sistemas Naturales y Artificiales presentaba el algoritmo genético como una abstracción de la evolución biológica, y proporcionaba el entramado teórico para la  adaptación bajo el algoritmo genético. El Algoritmo Genético de Holland era un método para desplazarse, de una población de cromosomas (bits) a una nueva población,  utilizando un sistema similar a la “selección natural” junto con los operadores de  cruces, mutaciones e  inversión inspirados en la genética. En este primitivo algoritmo, cada cromosoma consta de genes (bits), y cada uno de ellos es una muestra de un alelo particular (0 o 1). El operador de selección escoge, entre los cromosomas de la población, aquellos con capacidad de reproducción, y entre éstos, los que sean más “compatibles”, producirán más descendencia que el resto. El de cruce extrae partes de dos cromosomas, imitando la combinación biológica de dos cromosomas aislados (gametos). La mutación se encarga de cambiar, de modo aleatorio, los valores del alelo en algunas localizaciones del cromosoma; y, por último, la inversión, invierte el orden de una sección contigua del cromosoma , recolocando por tanto el orden en el que se almacenan los genes.

La mayor innovación de Holland fue la  de introducir un algoritmo basado en poblaciones con cruces, mutaciones e inversiones. Es más, Holland fue el primero en intentar colocar la computación evolutiva sobre una base teórica firme (Holland, 1975).

Hasta hace poco, esta base teórica, fundamentada en la noción de “esquemas”, fue la estructura sobre la que se edificaron la mayoría de los trabajos teóricos sobre algoritmos genéticos en las décadas siguientes.

En estos últimos años se ha generado una amplia interacción entre los investigadores de varios métodos de computación evolutiva, rompiéndose las fronteras entre algoritmos genéticos, estrategias evolutivas y programación evolutiva. Como consecuencia, en la actualidad, el término “algoritmo genético” se utiliza para designar un concepto mucho más amplio del que concibió Holland.