Algoritmos Geneticos

Quizás no haya un tema que más controversia traiga en el mundo de los programadores como la inteligencia artificial, ¿Porqué decimos esto? El ser humano siempre ha sentido la necesidad de crear cosas, desde un simple juguete, hasta maquinas complejas, pero a medida que crea y crea cosas, nos sentimos frustrados ante la incapacidad que tenemos de crear inteligencia, parece que el secreto se nos escapa de las manos, con esta breve introducción pasaremos a analizar uno de los algoritmos mas interesantes que pueden existir: Los algoritmos genéticos. En su libro Inteligencia Artificial, el Dr. Nicolas A. Landa nos introduce al concepto de algoritmos genéticos:

“Los algoritmos genéticos provienen de un área de la inteligencia artificial conocida como computación evolutiva y están inspirados en la forma en que trabaja la evolución en la naturaleza”

Aunque particularmente soy de los que defienden el creacionismo, es interesante el enfoque u origen de este algoritmo, así que dicho en otras palabras, a través de los algoritmos genéticos se logra representar en un modelo computacional lo que supuestamente sucede en la evolución. La teoría evolutiva sostiene que los organismos que tienen ventajas evolutivas están destinados a predominar, ya que les permite reproducirse mas que aquellos organismos que carecen de tales ventajas. Los organismos mejor adaptados pasaran sus genes a la siguiente generación y esta estará mas adaptada y así sucesivamente, la evolución sera un paso gradual, he aquí donde se introduce un concepto fundamental de esta teoría: la mutación. Aunque no quisiera dar un repaso de biología, es necesario para comprender las bases que sustentan este algoritmo, comencemos con un elemento importante e indispensable en todos lo seres vivos.

Veamos los distintos conceptos que hayamos en el libro Inteligencia Artificial:

ADN: “Es una molécula [...]Contiene las instrucciones y la información necesaria para el desarrollo y el funcionamiento de los seres vivos. [...] El ADN esta organizado en cromosomas. Los diferentes organismos tienen distintas cantidades de cromosomas.”

CROMOSOMAS: “ Éstos son moléculas de ADN muy largas, y podemos considerarlos como una unidad organizada dentro de la célula. Los cromosomas son diferentes entre los organismos, y sus longitudes también pueden variar. [...] El cromosoma esta compuesto por diversos genes”

GENES: “[...] Contienen información sobre la herencia genética del individuo y determinan o influencian la forma en la que se comportará y se desarrollará. Además, pueden interactuar entre ellos y se consideran como la unidad de herencia. El gen está construido por los nucleótidos, los cuales son compuestos químicos. Los nucleótidos son: adenina, guanina, citosina y tiamina. Según la forma como estos se químicos estén combinados y agrupados, la información de guarda en el gen. ”

Una vez repasado estos conceptos (pueden buscar más información sobre el ADN) podemos comenzar a codificar un cromosoma en el ordenador. Si pensamos en la función de un algoritmo, la cuál es resolver problemas, podemos entonces decir que el cromosoma representara una solución posible al problema que estemos resolviendo. ¿Como se puede codificar el cromosoma? A través de una arreglo. Veamos un ejemplo de un arreglo de ocho (8) posiciones que representaría a un cromosoma con cinco (5) características: 01010111 En este caso cuando un característica esta activada, la posición de arreglo correspondiente se coloca uno (1), sino se encuentra activada se coloca cero (0). Al igual como señala la teoría evolutiva, el organismo con mejores características sera el organismo mas adecuado para sobrevivir, en los algoritmos genéticos las características señalaran cierto desempeño, si estas son útiles para resolver el problema en cuestión, entonces consideraremos al individuo con esas características como una posible solución.

Ahora bien, en su libro Inteligencia Artificial el Prof. Landa indica que la codificación del cromosoma puede variar según el propósito de la aplicación que estemos realizando:

“A veces nos conviene tener más información del cromosoma para que no solamente nos indique si se tiene determinada característica, sino también cómo es tal característica. Por ejemplo, en el cromosoma, podemos colocar un valor bool si el organismo tiene visión o indicar con un valor double el rango de la visión. La forma como llevemos a cabo esta codificación dependerá del tipo de aplicación que se esté creando” (Cursivas nuestras).

Cuando el programa se inicia, de manera aleatoria se crea un conjunto de individuos cuyos cromosomas poseen características al azar. Siguiendo el modelo de la teoría evolutiva, el siguiente paso en el algoritmo, es un ciclo donde se revisa cada cromosoma y se verifica su grado de adaptación, posteriormente se dejan a aquellos individuos que posean los cromosomas con el mejor grado de adaptación. Después se procede a un cruce, lo que en la naturaleza es la reproducción, entre los organismos cuya adaptación sea mejor, para que la siguiente generación tenga mejores o iguales características adaptativas. El fin del ciclo evolutivo llegara cuando se encuentre un individuo cuyas características sean adecuadas para el problema que estamos planteando.

El Prof. Landa nos sigue sumergiendo en cada uno de estos pasos, veamos a que nos referimos con nivel de adaptación:

“[...] Cada organismo puede tener una variable, y el valor de esta variable será el grado de adaptación o de éxito que tiene el individuo. La forma como se calcule ese valor dependerá de cada aplicación. Entonces, debemos preguntarnos cuáles son las cualidades que consideramos mejores dentro de nuestro algoritmo. Por ejemplo, si el sistema necesita mantener un dispositivo a una temperatura en particular, los cromosomas que den comportamientos que lleven a valores cercanos a esa temperatura serán los mas exitosos.” (Cursivas nuestra).

Ya analizado el primer paso, podemos pasar a la selección de los individuos que serán los padres de la siguiente generación. Para la selección mencionare varios métodos principales:

Elitismo: Este método de selección consiste en agarrar a los dos organismos con mayor grado de adaptación y combinarlos para dar resultado a una nueva generación, los demás individuos con un grado de adaptación inferior al de la pareja escogida es descartado. Este método sin embargo es muy poco usado, ya que aunque aumenta el desempeño del algoritmo, tiende a llegar siempre a un óptimo local, descartando posibles soluciones óptimas.

Ruleta: Este método de selección consiste en asignar una probabilidad a cada individuo en base a su grado de adaptación, como si de una ruleta rusa se tratara. Los individuos con mejor grado de adaptación tienen mayores probabilidades de ser escogidos, pero a diferencia del elitismo, no se descartan individuos , todos participan. Este método suele ser el más utilizado.

Torneo: Este método de selección consiste en tomar de la población total a un par de individuos (aunque pudieran ser más), al igual que un torneo, estos se enfrentan ante un función que determina quien es el ganador y el perdedor, el ganador se queda en la población y tiene oportunidad de volver a concursar en la próxima ronda, el perdedor se pasa a una pila, por ultimo se toma al individuo que haya sobrevivido a todas las rondas, o dicho de otra manera haya ganado el torneo.

Una vez seleccionado los individuos que se van a reproducir, debemos hacer el crossover o cruce, pero para ello es necesario como indica el Prof. Landa, la proporción de cruce o crossover-rate, veamos que nos dice al autor sobre este valor:

“La proporción de cruce nos dice la probabilidad que existe de que dos cromosomas crucen su información para crear un nuevo organismo.”

Una vez que conocemos el valor del crossover-rate, podemos continuar con el crossover, para ello existen distintos mecanismos. Analizaremos los 3 que aparecen en el libro Inteligencia artificial:

Punto sencillo: “ Se selecciona un posición al azar en el cromosoma. Se toman del primer padre los genes que van desde en inicio hasta la posición y se colocan en el hijo. Luego se toman los genes que van desde la posición al fin del cromosoma del segundo padre y se colocan en el hijo”

Dos puntos: “[...] en este caso se seleccionan dos puntos al azar dentro cromosoma. El padre uno pone sus genes desde el inicio del cromosoma hasta la primera posición, y desde la segunda posición hasta el fin del cromosoma. El segundo padre coloca sus cromosomas entre las dos posiciones”

Múltiples puntos: “[...] se selecciona al azar cuál es el padre que aporta su información genética para un gen en particular.”

Ahora bien hasta el momento hemos dejado un concepto parte de la teoría evolutiva por fuera, la mutación, y justo cuando se realiza el crossover que se puede producir una mutación, para ello se usa un valor denominado relación de mutación, este valor indica que posibilidad tiene un gen de mutar o no. Un dato interesante, ¿Como muta un gen en un cromosoma, en el algoritmo genético? Si el arreglo de cromosoma contiene información binaria pues de hace un negación del valor actual, 0 -> 1, 1->0. Si el arreglo de cromosomas fue construido con otra estructura sencillamente la mutación dará como resultado un valor en el rango de valores posibles.

Fin del articulo.
La mayoría de las referencias fueron tomadas del libro Inteligencia Artificial del Dr. Nicolás Landa. Todos los derechos reservados.

Cualquier sugerencia es bien recibida. Gracias.
Pronto un prototipo de este algoritmo en C,C++.