¿Cómo funcionan los algoritmos genéticos?

En el artículo anterior, me preguntaba si estaba ocurriendo algo con los algoritmos genéticos, si el hecho de que, tras años 'sin saber nada de ellos', ahora me los hubiese encontrado en muy breve plazo en dos lecturas actualizadas, significaba algún tipo de resurgimiento. Aunque en el artículo esbocé muy someramente en qué consistían, me quedé con las ganas de hacer una explicación básica pero algo más detallada sobre cómo funcionan estos algoritmos genéticos.

Y esa explicación sencilla es el objeto de este artículo. Y como apoyo tomo una de las dos lecturas que me 'avisaron' de ese posible renacimiento de los algoritmos genéticos, a saber, el libro 'Optical Character Recognition Systems for Different Languages with Soft Computing' de Arindam Chaudhuri, Krupa Mandaviya, Pratixa Badelia y Soumya K Ghosh. En el tercer capítulo de la citada obra se repasan diferentes algoritmos del campo del 'soft computing' que son aplicables al reconocimiento óptico de caracteres (OCR). Y como los algoritmos genéticos se encuadran en ese concepto, los autores hacen una breve revisión de conceptos.

Para ello, se apoyan en la siguiente figura (NOTA: la propiedad intelectual de esa figura es de los autores y la editorial Springer).

Los algoritmos genéticos fueron inicialmente propuestos por John Holland. En ellos, existe una población ('population') de soluciones candidatas al problema a resolver. Cada una de las soluciones posibles que conforman esa población se denomina individuo, criatura o fenotipo. Cada una de estos fenotipos está caracterizado por una serie de características que se denominan cromosomas y que, aunque depende del problema y algoritmo concretos, se intentan representar como cadenas digitales de unos y ceros.

Sobre cada población se aplica una función de evaluación ('evaluation') para obtener el valor de adecuación ('fitness value') de cada fenotipo como solución del problema, es decir, hasta qué punto resuelve o se acerca a resolver el problema que estamos tratando.

A su vez, cada población, una vez evaluada, y suponiendo que aún no damos por resuelto el problema,  se transforma, es decir, evoluciona, a una nueva población mediante la aplicación de los operadores genéticos ('genetic algorithm operators'). Estos operadores son reproducción ('reproduction'), cruce ('crossover') y mutación ('mutation'). Mediante la reproducción generamos individuos nuevos. Mediante el cruce se mezclan los materiales genéticos, es decir, creamos un nuevo individuo o fenotipo que usa parte de las características de uno de sus padres y parte de las características del otro. Mediante la mutación introducimos variaciones aleatorias en esos cromosomas, es decir, en las características del fenotipo, individuo o solución candidata.

¿Cómo funciona?

Para verlo nos apoyamos en la siguiente figura (NOTA: de nuevo, la propiedad intelectual de esa figura es de los autores y la editorial Springer).

• Generamos una serie de soluciones candidatas (población inicial) generalmente al azar.A partir de ahí funcionamos en bucle hasta alcanzar la solución perseguida.


• Primero aplicamos la función de evaluación a la población y encontramos el valor de adecuación de cada uno de sus individuos. Si alguna solución es suficiente, finalizaría el algoritmo. Si no, se seleccionan los individuos que tienen un mejor valor de adecuación.


• Con esos individuos seleccionados se realiza la reproducción y el cruce, para obtener nuevos individuos hijos.


• Al conjunto de individuos hijos se le aplican mutaciones aleatorias.


• Hecho esto, tenemos ya una nueva población, que pasaría a evaluarse y así continuaría el bucle.

Como se puede apreciar los algoritmos genéticos están claramente inspirados en lo que sabemos de genética y selección natural. Esa inspiración y paralelismo se refuerzan utilizando términos procedentes, en efecto, de la biología y la genética.

De todas formas, no perdamos de vista que son algoritmos matemático-informáticos, unos algoritmos no especialmente eficientes (más bien, bastante poco eficientes) pero que pueden producir soluciones que no encontraríamos mediante algoritmos más clásicos y deterministas.