Introducción a los algoritmos genéticos

Antecedentes

La teoría de la selección natural de Darwin y Wallace, además de explicar la evolución de los seres vivos tiene importantes aplicaciones prácticas cuando se utiliza para programar los llamados algoritmos genéticos o evolutivos. Los primeros trabajos en este sentido fueron los realizados en los años 50 del s.XX por el italo-noruego Nils A. Barricelli (1912-1993) que en 1953 se pagó una residencia en el Institute for advanced Study de Princeton - New Jersey (U.S.A.), donde comenzó a hacer simulaciones por ordenador en el “IAS computer” diseñado por el genial científico austro-húngaro John Von Neumann (1903-1957) y sus colaboradores. El acceso al ordenador le fue concedido con el fin de estudiar el rol de la simbiosis en el origen de la vida. Sus primeras publicaciones sobre estos trabajos fueron: Esempi numerici di processi di evoluzione, Methodos (1954), pp. 45-68. y “Symbiogenetic Evolution Processes Realized by Artificial Methods”, Methodos (1957) vol.9, n. 35-36, pp. 143-182. Algo posteriores son los primeros trabajos del británico Alex Fraser (1923-2002) quien investigó con el ordenador “SILIAC” de la Universidad de Sydney (Australia), como fruto de estos trabajos publicó "Simulation of genetic systems by automatic digital computers. I. Introduction," Aust. J. Biol. Sci., vol. 10, pp. 484-491, 1957. La investigación con los algoritmos evolutivos fue extendiendose durante los años 60 en diferentes grupos hasta que sus principios básicos fueron definitivamente formalizados y popularizados por el investigador norteamericano John Henry Holland (1929-), descubridor del teorema fundamental de los algoritmos genéticos, al publicar el libro “Adaptation in Natural and Artificial Systems”, The U. of Michigan Press (1975).

Introducción

Actualmente, se considera que estos algoritmos forman parte de la inteligencia artificial, que a su vez es una de las principales áreas de estudio de la Informática. Son métodos de optimización y/o búsqueda de soluciones que emplean la terminología y los razonamientos propios de la biología evolutiva, y que se aplican principalmente a solucionar diferentes problemas de biología, ingeniería, medicina, química, etc.

Las posibles soluciones se codifican sobre unas cadenas binarias a las que se llama cromosomas. Las poblaciones de cromosomas se someten a procedimientos que simulan mutaciones, cruzamientos y selección natural. A partir de aquí se originan generaciones consecutivas, que van evolucionando con cada iteración.

Los puntos básicos a la hora de resolver un problema con esta técnica son:
- Diseñar el cromosoma
- Establecer la población inicial
- La función de selección
- Los operadores genéticos
- La evaluación de los parámetros de control (tamaño población, etc.)

Digamos que en las poblaciones los individuos tienen cromosomas, los ejemplares de la población compiten entre sí por los diferentes recursos, de modo que aquellos individuos que se reproducen mejor deben ser los mejor adaptados y por tanto, los que propagan su material genético a la siguiente generación. Con cada generación se sustituye a la anterior población de cromosomas.

Otros puntos que se tienen que comentar son que no se garantiza que el algoritmo encuentre la solución óptima, sólo que sea aceptable, que se emplean operadores probabilísticos, ...

Antes de terminar con esta breve introducción vamos a escribir el pseudocódigo del conocido como algoritmo genético simple o canónico:

BEGIN /*Algoritmo genético simple*/
  Generar una población inicial
  Función de selección
  WHILE NOT Fin DO /*Nueva generación*/
   FOR Tamaño población / 2 DO
   BEGIN /*Ciclo reproductivo*/
   Seleccionar /*Dos individuos*/
   Cruzar /*Según probabilidad*/
   Mutar /*Según probabilidad*/
   Función de evaluación /*Mutantes*/
   Insertar decendientes
   END
   IF población converge THEN
   Fin:= trae
   ENDIF
   END
  END
END
Para tener una visión más amplia del tema se recomienda este link.
Un saludo