Browsing articles tagged with " Algoritmos genéticos"

Una forma Natural de resolver la Innovación. Los Algoritmos Genéticos y la Competencia Interna

Dic 20, 2011   //   by wpuser   //   S.Expertos  //  Comentarios desactivados en Una forma Natural de resolver la Innovación. Los Algoritmos Genéticos y la Competencia Interna

Hace unos meses escribí un post explicando qué eran los Algoritmos Genéticos, y su funcionalidad. Releyendo a Jose Luís Larrea y sus cinco leyes de la innovación, no puedo dejar de pensar en cómo la Naturaleza, con sus métodos evolutivos, aplica la innovación en cada individuo que se genera.

La Innovación se basa en las siguientes cinco reglas :

La primera ley, el Círculo de Leonardo, pone de manifiesto que sólo es posible una innovación sostenible y que aporte valor si se equilibra la creatividad y la modelización sobre la base de unos valores. La segunda ley, el combate, evidencia que todo proceso de innovación pasa por gestionar las contradicciones inherentes a cualquier cambio, evolución y progreso.  La tercera ley, la aventura, tiene que ver con el reto de convivir con más preguntas que respuestas y disfrutar con ello. La cuarta ley proyecta el desafío de la innovación en el universo de los valores marginales.  Por último, la quinta ley, enfatiza la importancia del tiempo en cualquier proceso de innovación. Todas estas leyes se relacionan, formando la idea clave de una espiral de la innovación.

Por otro lado, la Naturaleza ha construido un método para ir aplicando respuestas a problemas del tipo n-complejos, de una forma sencilla: la Evolución. Y desde el Dpto. de Inteligencia Artificial en I3B, la emulamos en la aplicación de los mismo métodos como alternativa a búsquedas líneas o métodos heurísticos pesados y de poda, en base a Algoritmos Genéticos.

La relación de esta solución con las cinco leyes de la Innovación es clara. Por un lado, desde el punto de vista morfológico, los Algoritmos Genéticos se basan en un ciclo que copia, al igual que el lenguaje de la innovación, el funcionamiento de lo que nos rodea. Así, la Innovación tiene su inspiración en la serie de Fibonacci, en los fractales o en la armonía natural, pero no olvidemos que estos modelos se ha forjado gracias al intercambio genético entre individuos: dejamos de ser una copia exacta de nuestros antecesores, para ser mezclas genéticas de los mismos, con el objetivo de amoldarnos de manera más efectiva a un entorno hostil y variable, con un alto coste: la mortalidad. Lo mismo ocurre con los Algoritmos Genéticos, los mejores individuos sobreviven para dar lugar a nuevas generaciones, que a su vez, perecerán hasta que la adaptación llegue a unos umbrales mínimos de satisfacción. Al igual que en el Círculo de Leonardo, este tipo de soluciones tienen inherentes el lema de “se debe romper el orden para innovar”, principalmente porque el orden no existe, sino simplemente, un deseo innato de adaptación al medio.

Pero a su vez, dicho caos, determinado en cierta parte por el azar de la selección de los primeros individuos, se va modelando a lo largo de los distintos ciclos (generaciones), de acorde con una meta: seleccionar la solución o soluciones más adecuadas al problema.  Y en este proceso, existen contradicciones, como en todo proceso biológico, que el mismo sistema debe resolver, como lo son:

□        La evaluación de candidatos

□        La selección de los padres (¿Cuáles seleccionamos? ¿Los mejores? ¿Aleatoriamente?)

□        La mezcla de individuos

□        El salto generacional (el paso al siguiente ciclo), es decir, mantenemos los mejores individuos en la siguiente generación, o dejamos que sea la selección natural la que nos guíe, utilizando una selección de tipo torneo (“El Combate”)…

Y en todo este proceso, el sistema siempre está “viajando” por el mapa de soluciones, sin dejar de sondear, de forma paralela, como si de un laboratorio se tratase, las distintas posibilidades de solución, pero controlando, por medio de su función de evaluación, que dichas contradicciones no desvíen la atención de sistema a la función objetivo, es decir, como dice la tercera ley, “la organización innovadora aprende con el tiempo a manejar un tamaño óptimo, entre el tiempo de las preguntas y el tiempo en encontrar las respuestas…“.

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. Para evitar esta situación,  existe otro componente en los Algoritmos Genéticos,  “marginal”, pero sumamente importante, que es la mutación. De vez en cuando, un individuo modifica alguno de sus genes, saliéndose de la normalidad de sus “hermanos”, y compartiendo con el resto un nuevo componente no tenido en cuenta hasta entonces, y que quizás, sea el que haga que la búsqueda de la solución “salte” de la colina a la montaña. Al igual que la cuarta ley de la innovación dice que “El desafío de la innovación está en el universo de los valores marginales“, el verdadero desafío matemático en la fortaleza de los Algoritmos Genéticos está en su capacidad de marginal de modificar valores puntuales en individuos puntuales. Y es precisamente esta capacidad la que permite un salto de rendimiento con respecto a otras técnicas, como las búsquedas aleatorias o ascenso a la colina (Hill Climbing).

Por último, y como relación con la quinta ley de la innovación, “el Tiempo“, está demostrado que los Algoritmos Genéticos encuentran soluciones en un entorno multivariable y complejo, de una forma óptima (ver la Figura abajo), precisamente, por la conjunción de los puntos explicados anteriormente.

 

Los Algoritmos Genéticos son un método de encontrar soluciones a problemas complejos de una manera muy acorde con las leyes de la innovación, 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. Este proceso es muy similar al de espiral de la innovación, que no deja de ser una evolución en ciclos de preguntas/respuestas.

La “poética de la innovación” nos habla de los principios inspiradores de la innovación, de la conceptualización de los sistemas de innovación sobre la base de unos valores, con los motores de la tecnología, el conocimiento y la cooperación, y con el impulso y dirección del liderazgo cooperativo.

Y efectivamente, la colaboración, hoy en día es un valor en alza (Web 2.0), y una parte indispensable en los procesos de gestión y de innovación. Pero la teoría de la evolución aplicada, (que es cómo podríamos llamar a los Algoritmos Genéticos), tiene un componente más, a mi parecer, muy importante, y poco implementado, tanto en la gestión de proyectos, como en otros ámbitos: el de la competencia interna (la externa es obvia, y peleamos todos los días contra ella).

¿Qué es, a mi parecer, la competencia interna?: En los Algoritmos Genéticos, en cada ciclo, se gestionan múltiples soluciones a un problema (un número variable de individuos por generación), y no existe comunicación entre los distintos individuos que la gestionan, sino que cada uno de ellos y de forma egoísta (otra vez Smith), intentan optimizar los recursos para obtener la mejor solución, sin interesarse por lo que están haciendo otros individuos a su alrededor. Eso es competencia interna, puesto que existe un componente de “prestigio social” inherente a ver quién es el que encuentra la mejor solución, quién es el mejor individuo.

Y es al finalizar el ciclo, cuando dicha información “egoísta”, se comparte (se ordena por la función evaluadora), se seleccionan los mejores individuos, y bien, por selección aleatoria, por torneo, u otros métodos, se mezcla  la información genética de los mismos (por pares), para dar lugar a dos nuevos individuos, diferentes que los padres, pero enriquecidos por la colaboración.

En definitiva, se produce un intercambio de información (colaboración), después de un proceso de competición interna entre individuos (=conjuntos de genes) que buscan la mejor solución. Y esta acción redunda en el siguiente ciclo, pues en paralelo, la información se va optimizando y compartiendo.

Lo usual, es que cuando abordamos un proyecto, de cualquier naturaleza, se designe un equipo (uno sólo), que comienza a trabajar, y llega hasta el final, como bien sepa o pueda (=temple simulado). Pero, ¿no sería interesante emular a la evolución, y crear un modelo de varios equipos, que vayan ideando soluciones puntuales en cada ciclo del proyecto, de forma independiente, y que, después, las pusieran en común, se seleccionasen las mejores, se mezclasen entre ellas y volviese a comenzar el ciclo? Tendríamos un modelo en el que se trabajaría con las bases del conocimiento, la competencia, y la colaboración. Un modelo completo…con resultados efectivos… aunque quizás con mayor coste. No debemos olvidar que la Naturaleza no optimiza recursos (la polinización es un ejemplo claro de derroche), pero asegura resultados, y a la larga, quizás, esto justifique la inversión.

(más información sobre artículos relacionados en www.i3b.ibermatica.com/i3b/articulos)

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.