Algoritmos Genéticos: Búsqueda de soluciones en “paisajes” adaptativos complejos

Sep 5, 2011   //   by wpuser   //   S.Expertos  //  4 Comments

 

Los Algoritmos Genéticos son un método de encontrar soluciones a problemas complejos (NP completo) en base a la teoría evolutiva de Darwin, y su esencia y funcionamiento es muy sencillo:

darwin_game

darwin_game
  • Se generan una serie de individuos al azar, cada uno de los cuales, es una solución al problema.
  • Una función evaluadora “puntúa” a cada individuo, según un criterio (en este caso, el espacio libre que queda).
  • Se seleccionan los mejores individuos.
  • Se emparejan de forma selectiva los individuos seleccionados: Así, obtenemos una segunda generación de nuevos individuos (=soluciones), con las características (=genes) de los mejores “padres” de la solución anterior.
  • Se introduce cierto ruido, (para evitar mínimos locales), en forma de mutaciones, es decir, en este caso, modificando las características de los genes de algún individuo.
Los Algoritmos Genéticos son un método de encontrar soluciones a problemas complejos de una manera muy de acorde con las leyes naturales, principalmente, porque no se basan en el conocimiento del problema para su solución, sino que se articulan en base a una serie de ciclos en los cuales una serie de individuos “idean” una solución, son evaluados, se seleccionan las soluciones más adecuadas, y por medio de un intercambio de información (conocimiento), y algunas variaciones al mismo (valores marginales), se vuelve a generar otro ciclo que comienza de nuevo la búsqueda. Es decir, que una vez construida un algoritmo genético, éste sirve para cualquier tipo de problema, sólo hay que modificar la función evaluación del mismo.

ag_algoritmo

Con estos algoritmos, se consigue “navegar” por el espacio de soluciones ante un problema de una forma muy rápida, llegando de una manera muy eficiente a la solución, y además, evitando mínimos locales.

Un típico ejemplo es la selección de la “mejor” ruta del viajante, como se ve en el ejemplo de la siguiente figura:

Pero lo verdaderamente interesante de este método de búsqueda es lo siguiente:

□        El sistema no tiene implementada en su lógica de búsqueda la solución del problema.

Es decir, el sistema no busca una solución en base al conocimiento del problema, de hecho, ni siquiera conoce el problema, sólo, genera individuos al azar, y luego los evalúa… Pero no se implementa en ningún lugar qué es lo que se quiere conseguir.

□        Los resultados no son previsibles, no es un procedimiento “guiado”.

Al no existir ninguna restricción sobre cuál es el objetivo, el sistema intenta converger hasta llegar al mejor o mejores individuos, pero el resultado puede ser incompresible en contra de un método clásico, pero mejorar los resultados. Un ejemplo clásico suele ser la configuración de antenas en función de su entorno electromagnético. Como se ve en la figura, la forma de la antena es extraña, pero es la mejor de las soluciones, incluidas las determinadas de forma empírica.

Diseños industriales en base a AG.

Y precisamente, esta forma de dar solución a problemas de manera no guiada, sino determinada por la adaptación de los individuos (soluciones) al entorno (solución del problema), es dónde encontramos la ventaja frente a otros métodos, precisamente por el hecho de que los resultados no son esperados o calculados por medio de un intento de modelar las soluciones al problema. Son entornos dinámicos y evolutivos.

Si los individuos, en vez de tener en sus “genes” valores, como ciudades, en el ejemplo anterior, tendrían gramáticas, los sistemas pueden generar gramáticas de forma automática, con lo que, podemos, por ejemplo, a partir de una serie de datos, puntos, coordenadas, o valores, obtener las ecuaciones que los satisfagan. En este caso, podemos generar sistemas complejos (e incluso programas), que de forma automática, satisfagan una serie de restricciones, y con un objetivo determinado. (Estos métodos se denominan Computación Evolutiva, pero la base es la misma que los Algoritmos Genéticos).

En la siguiente figura, se puede ver un ejemplo de un solución ante una serie de puntos. (Una buena forma de determinar la correlación de las ecuaciones sobre las nubes de puntos es en base al coeficiente de Pearson):

 

Otro punto de interés es la unificación de dos componentes hasta ahora antagónicos en la forma de abordar problemas en “paisajes” adaptativos complejos (problemas NP-completo).

□        Por un lado, está la teoría clásica de Adam Smith, en el que prima la consecución de los objetivos.

  • Algoritmos que utilizan esta filosofía de “ataque” lo son la heurística voraz, o el método de temple simulado (simulated annealing), que no deja de ser un caso particular de Algoritmos Genéticos. En estas soluciones, un solo individuo intenta dar solución al problema moviéndose por el espacio de resoluciones.

□        Por otro lado, el equilibrio de John Nash, en el que encontramos una teoría de colaboración, y como ejemplo, encontramos la teoría de juegos, o incluso sistemas paralelos como redes neuronales o bayesianas en competición colaborativa.

Los Algoritmos Genéticos aúnan las dos vías, en un ciclo evolutivo, en el que, por una parte, se buscan soluciones en paralelo primando la consecución de un objetivo, el de minimizar el error, y por otro, al final de cada ciclo, se comparte la mejor información para comenzar un nuevo ciclo con los mejores conocimientos (nótese el plural) del ciclo anterior.

En definitiva, los AG son un método de búsqueda que tiene las siguientes ventajas:

•Trabajan con un conjunto de puntos, no con un único punto y su entorno (su técnica de búsqueda es global.).

•Utilizan operadores probabilísticos, no deterministas.

•Son intrínsecamente paralelos. Los AG tienen descendencia múltiple, pueden explorar el espacio de soluciones en múltiples direcciones a la vez.

•Se desenvuelven bien en problemas con un paisaje adaptativo complejo. Escapan de mínimos globales.

•Habilidad para manipular muchos parámetros simultáneamente.

•Los AG no saben nada de los problemas que deben resolver.

y también sus desventajas:

•Hay que definir bien la representación del problema.

•El problema de cómo escribir la función objetivo debe considerarse cuidadosamente para que se pueda alcanzar una mayor aptitud.

•Deben elegirse cuidadosamente los otros parámetros de un AG -el tamaño de la población, el ritmo de mutación y cruzamiento, el tipo y fuerza de la selección

Existe un problema típico para evaluar los algoritmos de solución de problemas complejos (el “Hello Word” de los NP-completos), que es el problema de la mochila. Existen en el mercado numerosos programas que resuelven problemas logísticos de este tipo (se puede ver una relación de los mismos en la página:

http://www.mecalux.es/navigation/event/detailinterview.jsp?idinterview=28623096).

La definición del problema es la siguiente:

“El problema de la mochila consiste en llenar una mochila con n objetos. Cada objeto i tiene un peso determinado ci siempre positivo y una utilidad o valor asociado, también positivo, bi. Se ha de considerar además que la mochila tiene una capacidad limitada P, por tanto, se han de escoger aquellos objetos xi que maximicen la utilidad de quien llena la mochila sin exceder su capacidad”.

Ahora procederemos a formular el problema de la mochila:

Maximizar [Sumatoria (bi*xi) desde i= 1 hasta n]

sujeto a: xi Є {0,1} con i =1, …, n

Sumatoria (ci*xi) desde i=1 hasta n < P

En concreto, vamo a resolver un caso particular, según el siguiente enunciado:

Tenemos 10 cajas con los siguientes pesos:

5, 7, 12, 14, 23, 4, 6, 9, 4 ,6 kilos, y un contenedor que sólo puede contener 55 kilos.

¿Cuál es la mejor distribución?

Definición de la función a maximizar:

i = {1, 2, 3, 4, 5, 6, 7, 8, 9 ,10}

bi = 1    mismo valor para todos los pesos

ci = {5, 7, 12, 14, 23, 4, 6, 9, 4 ,6}

P = 55

En la tabla adjunta, se muestra una comparativa de los resultados con distintas técnicas de búsqueda: (Por ejemplo , con Algoritmos Heurísitcos , en conctretpo Bakctraking y Teoría de Grafos y  con Solver…):

Sin embargo, si dejásemos que sólo la selección natural y el emparejamiento influyesen en la “aventura” de encontrar las mejores soluciones, estaríamos perdiendo información, y sobre todo, tendríamos un gran problema, los mínimos locales.

Un sistema de este tipo, al llegar a un mínimo local (una colina, pero no la montaña), podría estacionarse en dicha solución, y propagar los genes del mejor individuo infinitamente al resto de generaciones, es decir, a sus descendientes hasta que nos detendríamos en un punto que no es el óptimo. Otros métodos han dado solución a este problema  generando saltos, que permitan evitar las “colina”, por ejemplo, el “temple simulado” (simulated annealing), pero la ventaja de los AG es que, en vez de ser un único individuo el que realiza la búsqueda, esta se realiza en paralelo por varios “agentes” a la vez.

 

minimos_locales

Los AG se están aplicando en múltiples aplicaciones, optimización, procesos industriales, interacción hombre-máquina, medicina, minería de datos….

Los problemas de optimización complejos, ya tienen un buen método de resolución, rápido y eficaz, los Algoritmos Genéticos…

En Ibermática, hemos aplicado estos métodos a aplicaciones como la optimización de colocación de piezas en superficies 2D, dentro de entornos industriales, o la selecciones de los mejores métodos de análisis en entornos de datos muy variables y complejos, de forma automática.

4 Comments