Inteligencia Artificial: Algoritmos Genéticos

Hola a todos, ya había dejado las publicaciones, pero estoy de regreso espero poder escribir un poco más en los siguientes meses o que la tesis me lo permita.
Bien, en esté post continuaré con el tema que había dejado abierto: Inteligencia Artificial. En esta ocasión les explicaré de manera general como funciona un algoritmo genético, para que sirve, y las ventajas de su uso.



Para comenzar explicaré que los algoritmos genéticos basan su funcionamiento en la idea de la herencia genética. Es decir, se basan en la idea de que los padres traspasan cierta información a través de los genes a sus hijos, como son rasgos o habilidades. Lo que les permite mejorar la especie con el paso de las generaciones.



Lo anterior ocurre como una mezcla dos materiales genéticos a través de cada generación, es decir el padre y la madre. La ventaja principal de este proceso es la evolución, pues aquellos individuos con mejor material genético o con mejores habilidades y rasgos tienen mayor capacidad de sobrevivir, o aparearse traspasando nuevamente su material genético a sus hijos.

Bien, tomando en cuenta lo anterior, los algoritmos genéticos son una forma de resolver problemas que tienen múltiples soluciones("buenas o malas" pero al fin soluciones). Un ejemplo común en el área de inteligencia artificial, es el "problema del viajero", el cual tiene que pasar por X número de ciudades y escoger la ruta más corta para recorrerlas todas.

Del ejemplo anterior, podemos ver que si existen 2 ciudades (A) y (B). Sólo hay 2 posibles soluciones:
 (A->B) o (B->A). Sin embargo si el número de ciudades aumenta, las posibles soluciones también por ejemplo para 3 ciudades las posibles soluciones serían:

• (A->B->C)
• (A->C->B)
• (B->A->C)
• (B->C->A)
• (C->A->B)
• (C->B->A)

Para 4 Ciudades las posibles soluciones son 24, para 5 son 120. Y quizás muchos dirán: "Bien, con un bucle (FOR o WHILE) queda solucionado el problema revisando todas las posibles soluciones hasta encontrar la mejor". El problema comienza cuando el numero de ciudades aumenta más, por ejemplo supongamos que nuestro viajero quiere visitar solo 20 ciudades distintas, el número de soluciones sería de 2.432902008*10exp18. Es decir, ¡el viajero tardaría más tiempo en encontrar el camino más corto, que en recorrer la ruta más larga!!. Problemas como el anterior son muy comunes por ejemplo:

• Rutas de entrega en empresas de paquetería o aerolíneas.
• Organización de horarios.
• Reducción de gastos de materiales(¿Como acomodar las piezas para gastar menos material?).
• Organización de información para reducir el acceso de los datos.

Por suerte, los algoritmos genéticos nos pueden dar una mano con este problema. Ahora voy con lo más importante, ¿Cómo funcionan?.

Los algoritmos se componen principalmente de 5 pasos que son:

• Representar la solución
• Mutación
• Cruza
• Selección de padres
• Reemplazo

Representación

Los algoritmos genéticos funcionan a partir de un grupo de elementos denominados fenotipo, donde cada fenotipo representa una solución al problema planteado. Para el ejemplo del viajero que tiene que visitar 3 ciudades (C->B->A) sería el fenotipo. Mientras que el grupo de fenotipos es denominado población.

La representación de las soluciones puede ser de dos formas, a nivel de fenotipo que es el más cercano a la realidad o a nivel genotipo el cual codifica la solución como una serie de números binarios (Esta representación debe tomar en cuenta que todas las posibles soluciones tienen que poder representarse y que todas las combinaciones sean válidas).

El genotipo esta compuesto de genes donde cada gen es la posición y los posibles valores que pueden tomar son llamados alelos 0 y 1.

Mutación

Bien, ya que tenemos la representación, es necesario un proceso de mutación, que al igual que en la genética   permite a los individuos encontrar nuevos caminos de evolución sin estancarnos en lo mismo.

Este proceso es muy simple y solo consiste en seleccionar un individuo de la población y cambiar alguno de sus genes de manera aleatoria. Aunque este proceso parezca simple le da variedad a la población lo que aumenta la posibilidad de encontrar una mejor solución.

Cruza

La cruza es seleccionar 2 o más elementos de la población  y realizar una mezcla de los genes que componen a cada uno, generando un nuevo elemento. Existen diversos tipos de cruza sin embargo la más simple es la selección aleatoria de un grupo de genes de la siguiente forma.

Reemplazo

Del grupo total del individuos padres e hijos, se seleccionan a los mejores evaluando a cada uno de ellos.
Los mejores sobreviven para el siguiente ciclo, donde se ejecutarán los mismos pasos. El algoritmo puede detenerse en un número definido de ciclos o cuando la mayoría de soluciones sean muy parecidas. Todo depende de la complejidad del problema.


Como pueden darse cuenta el mecanismo de los AG's es relativamente sencillo. y  no esta cerrado a que se realicen mejoras. De hecho, existe una gran cantidad de trabajos dedicados exclusivamente a proponer mecanismos más confiables y fáciles de implementar.

En los siguientes días espero poder subir un algoritmo en java para que observen el funcionamiento.