Cuando uno observa el comportamiento de animales aparentemente muy simples como las anémonas, descubre la cantidad de problemas complejos que son capaces de resolver. Esta capacidad es aún mayor en organismos mucho más complejos como los mamíferos, y en especial, los primates. ¿Cuál es la fuente de esta capacidad? La respuesta, mal que les pese a algunos, es la Evolución, la maestra Naturaleza que permite que sobrevivan sólo aquellos organismos que son capaces de resolver los problemas a los que se enfrentan.

Los investigadores dedicados a la teoría y búsqueda de algoritmos decidieron imitar a la naturaleza incorporando a los programas mecanismos evolutivos, de tal forma que el programa se adapte para resolver el problema que se le plantea.

Estos algoritmos genéticos permiten la exploración de un abanico de soluciones mucho más amplio del que podría diseñar y probar un programador humano. De forma indirecta, estos algoritmos con capacidad evolutiva pueden ayudarnos a comprender de una forma más precisa algunos de los mecanismos de evolución natural.

La evolución se basa esencialmente en dos procesos, la mutación y la reproducción, junto a la posterior selección de los más adaptados. En un programa, la selección es un proceso sencillo, basta con hallar una prueba de idoneidad adecuada, por ejemplo, para un algoritmo de ordenación basta con comprobar si la ordenación es la adecuada y que no ha tardado demasiado en realizarla.

Sin embargo, los procesos de mutación y reproducción no son tan fáciles de emular. La mutación, el más simple de los dos procesos, no puede realizarse tomando un programa en C y variando aleatoriamente algún elemento del programa. Si llevamos a cabo este proceso, el programa, con casi absoluta probabilidad, no funcionará. La reproducción es más compleja aún; imaginemos que mezclamos partes aleatoriamente elegidas de dos programas en C, casi nunca saldrá algo que se parezca ni remotamentamente a un programa en C, y si alguna vez se parece, no funcionará.

Por lo tanto, el primer escollo con el que se encontraron los investigadores que tuvieron esta idea fue el de ser capaces de diseñar programas capaces de evolucionar y reproducirse de forma eficaz.

El problema se resuelve haciendo que un patrón de números sea tanto el problema como la solución. Estos patrones de números pueden estar compuestos simplemente por ceros y unos. Estos ceros y unos representan estados elementales de una determinada característica o las respuestas a un determinado suceso.

Inicialmente, todos los individuos de este universo tienen una ristra de ceros y unos que es absolutamente aleatoria. Cada una de estas cadenas se evalúa comparándola con el ambiente. Todas aquellas cadenas que tengan coincidencia con el patrón de ambiente incrementarán su coeficiente de idoneidad. Este incremento será distinto dependiendo de la importancia del patrón de ambiente con el que se compare.

En estos patrones de ambiente, tan sólo unos pocos bits son importantes. Una vez evaluados los individuos se pasa a la reproducción de éstos, los más adaptados se cruzarán con los más adaptados y sobrevivirán, los de adaptación media tan solo sobrevivirán, y los menos adaptados morirán. La proporción de individuos que pertenece a cada una de las clases debe de estar prefijada y debe ser de tal forma, que el número de individuos que se reproduce y el número de individuos que muere es idéntico.

Esta condición es sólo necesaria si se quiere que la población no disminuya y puede ser eliminada con condiciones de reproducción múltiples, pero hace mucho más complejo el estudio de la evolución de estos individuos.

El método de apareamiento consiste en elegir una posición al azar. Con este límite se forma el primero de los individuos nuevos utilizando el segmento izquierdo del primero y el segmento derecho del segundo, y el segundo individuo se crea utilizando los otros dos segmentos de igual forma.

Para los algoritmos genéticos es necesario utilizar un elevado número de individuos con el fin de tener un número de individuos suficientes como para explorar todas las posibles soluciones. Curiosamente las condiciones de ambiente pueden ser contradictorias en alguna zona determinada, el algoritmo genético obtendrá la o las soluciones más idóneas.

Al principio de este artículo hemos indicado que las poblaciones evolucionaban gracias a dos procesos, la reproducción y la mutación, pero de esta segunda no hemos dicho nada. Hace años se pensaba que la mutación era el proceso más importante y casi todos los algoritmos genéticos que se desarrollaban tenían una reproducción asexuada y una alta mutación para adaptarse al ambiente. Sin embargo, se ha descubierto que cuando existe una reproducción sexuada como la descrita en párrafos anteriores, la mutación es poco importante y basta con que haya en cada generación un índice de mutación que afecte a un sólo bit de cada 1.000 o incluso menos, con el fin de mantener una cierta variabilidad en la población y que ésta pueda seguir evolucionando hacia una solución mejor.

Estos algoritmos genéticos se pueden parecer aún más evaluando la importancia de cada una de las reglas.

Esta evaluación es bastante sencilla, basta con estudiar cuántos individuos se han ajustado a cada una de las reglas, si pocos individuos han preferido adaptarse a la regla, es decir, a esa condición ambiental, esto significa que esta condición pierde importancia frente a las demás; o a la inversa, si hay muchos individuos que se ajustan, entonces esa regla se verá reforzada frente a las demás. De esta forma, no sólo los individuos se adaptan al ambiente sino que también lo modifican.

Con reglas tan sencillas se puede ver que cualquiera puede programar un algoritmo genético para resolver un problema, dejarlo que evolucione y encontrar un conjunto de soluciones que son, en el espacio de soluciones del problema, las más adecuadas. Programar un algoritmo de este tipo es cuando menos bastante divertido e instructivo.

Bibliografía

- Genetic Algorithms in Search. Optimization and Machine Learning. D. E. Goldberg, Addison-Wesley, 1989.

- Adaptation in Natural and Artificial Systems. J.H. Holland, MIT Press, 1992.