Ia En Haddd (algoritmos Geneticos)

[Vicente]

 Hola,

pues después de muuucho más tiempo del que deberían haber tardado, la librería de algoritmos genéticos de Haddd ha conseguido resolver su primer problema de forma evolutiva :) El problema era minimizar:

f(x) = x^4 - 12*x + 15*x^2 + 56*x - 60

(problema sacado de GA Playground)

El mejor resultado que ha obtenido es f(-1.22328540545332) = - 89.1388557774145 (a ver si lo he copiado bien ;))

Para la gente que sepa un poco del tema comento que tiene ahora mismo la librería (intentaré poner un mini tuto sobre algoritmos genéticos y estrategias evolutivas cuando termine de pulir todo para la gente que le interese meterse en esto de la IA):

Operadores disponibles:

- Mutacion: aleatoria, inserción, intercambio, inversión (binaria y de permutaciones), normal.
- Recombinación: aritmética, cruce de N puntos, discreta, lineal, PMX.
- Reemplazo: competencia (estrategia evolutiva), elitismo, descendientes (algoritmo genético puro).
- Selección: aleatoria, fitness (tanto por ruleta como por SUS), rangos (tanto por ruleta como por SUS), torneos.

Se implementa una solución clásica y básica: seleccionar progenitores, generar descendientes, mutar descendientes, seleccionar supervivientes, vuelta a empezar. Toda la población se trata como un conjunto (tengo que mirar otras formas de evolución más complejas).

Todo va tipado contra interfaces o clases abstractas: todos los operadores derivan de una clase abstracta AlgoritmoX (donde X es por ejemplo Mutacion) que define un método Y (en el caso de mutacion "Mutar") que se usa como delegado en la solucion evolutiva.

Los problemas se definen implementando una interfaz: IProblemaEvolutivo, que tiene una propiedad (Objetivo, si buscamos maximizar o minimizar) y dos métodos (CalcularFitness de un cromosoma y GenerarPoblacionInicial).

Las poblaciones, cromosomas y genes son tambien interfaces. De momento solo hay genes en coma flotante para el ejemplo de la ecuación, pero extenderlo es muy fácil (dejaré implementaciones de los tipos básicos que conozco: genes de coma flotante, enteros y booleanos).

A lo largo de mañana aparecerá la librería en la web de Haddd. Se aceptan comentarios, críticas, dudas,... Mi conocimiento del tema es bastante teórico, y todavía tengo que probar muchas clases, con lo cual puede haber gazapos (solo he probado unos cuantos operadores a fondo, hasta que los revise todos tela ;)). La implementación está hecha con genericos y es la primera vez que los uso, así que seguramente habrá cosas muy raras... El objetivo era dejar una librería extensible, y donde fuera bastante fácil definir problemas, así que si le echais un ojo a ver si se ha conseguido o no.

Bueno, mañana más, que la verdad que toy un poco dormidillo ya. Un saludo!

Vicente

[Mars Attacks]

 Pues me resulta muy interesante. ¿Cómo resuelven exactamente esa ecuación tus nenes?

[BeRSeRKeR]

 No me he enterado de nada pero bueno, a ver si de aquí a algún tiempo tenemos algún bicho con "vida propia". :D

¡Buen trabajo!. (mola)

[StraT]

 Ya disponible en la web oficial del motor Haddd http://www.mundosgm.com/haddd

Saludos

[Vicente]

 

Pues me resulta muy interesante. ¿Cómo resuelven exactamente esa ecuación tus nenes?

Hola,

lo que hago es buscar el mínimo de la función, no resolver la ecuación. Basicamente esto es lo que hacen:

• 1 - Se genera una población inicial de 10 cromosomas. Un cromosoma en este problema es un valor de la variable x. Los valores se generan al azar entre 2 y 5 (para que sean cromosomas "malos", ya que están bastante lejos de la solución óptima).
  
• 2 - Se generan 10 hijos. Para generar los hijos se usan 2 padres. Primero tenemos que seleccionar los dos padres, se eligen usando Rangos + SUS. Esto es: se ordenan los padres por lo buenos que son (para ver lo buenos que son, se sustituye su valor en la función y se calcula el resultado). Se les aplica una fórmula un poco fea que da a cada padre una probabilidad entre 0 y 1 de ser elegido y se eligen dos padres.
  
• 3 - Una vez tenemos los dos padres, se genera el hijo descendiente. El descendiente se calcula generando un número al azar entre [-valor, 1+valor]. Este número se llama por ejemplo "factor". Pues para ver lo que vale el hijo se hace: ValorPadre1 * factor + ValorPadre2 * (1 - factor). Ya tenemos al hijo.
  
• 4 - Una vez tenemos los 10 hijos, se mutan. Para mutarlos se les añade un valor al azar sacado de una distribución normal con media 0 y varianza 1 (no tengo yo muy claro que la rutina que uso para generar estos números esté muy bien la verdad...).
  
• 5 - Una vez tengo a los hijos mutados, elijo que 10 cromosomas sobreviven de los 20 que tengo (tengo 10 padres y 10 hijos mutados). En un algoritmo genético puro, sobrevivirian los 10 hijos mutados, pero en este problema he usado otra forma que se llama "elitismo": sobreviven los 9 mejores hijos y el mejor padre. Esto lo hago por si acaso me salen hijos muy malos, no irme hacia atrás en la evolución.
  
• 5 - Repetir esos pasos  muchas veces. El algoritmo acaba cuando pasan 500 generaciones sin que me salga un cromosoma mejor que el mejor que ya tenía (500 generaciones sin mejora genética). Normalmente el algoritmo tarda entre 200 y 700 generaciones en encontrar el mejor cromosoma (el -1.22xxx ese).
  

Voy a ponerme para seguir probando a ver si maximizan o minimizan una función con varias variables y resuelven también encontrar el camino más corto entre varios puntos (un TSP). Si resuelven esos dos problemas, más o menos se puede decir que ya están pasables. Después comentaré todo y pongo el mini tuto.

He sacado bastante info de esta web:

http://www.geatbx.com/docu/algindex-01.html#TopOfPage

Un saludo!

Vicente

[Grugnorr]

 Y la aplicación a la IA de un juego?  :P

[Vicente]

Y la aplicación a la IA de un juego?  :P

Eso es lo que estoy intentando aprender yo tambien ;) Todo lo que sé de IA es de la universidad, así que para juegos ni idea. En los Computer Gaming Gems hablan algo de usar redes neuronales para IA en juegos, y en amazon he visto varios libros que usan estas técnicas para juegos, así que a ver si estos dias los compro aprovechando reyes y tal, y cuando me los traigan pues a leer y leer... Hombre, como mínimo los puedes usar para encontrar caminos entre 2 puntos ;) (es mejor usar A* que los genéticos, pero bueno, ya se les encontrará más utilidades seguro). Un saludo!

Vicente

[tywok_]

 el archivo que habeis subido parece corrupto (nooo)  

[Mars Attacks]

 Gracias por la explicación. No sé muy bien qué es el SUS que comentas, pero el resto me ha parecido un método heurístico más que interesante, jejeje.
La aplicación en un juego... se la das tú ;)

Tal vez en un juego de estrategia en tiempo real sirva para desarrollar la unidad que mejor optimice sus recursos, por ejemplo.

Edito: creo que en la ecuación te falta un ^3 en el segundo miembro ;)

[StraT]

 Solucionado, no se que pasa, aseguraos de reoleadear bien la pagina.

Saludos

[Vicente]

 

Gracias por la explicación. No sé muy bien qué es el SUS que comentas, pero el resto me ha parecido un método heurístico más que interesante, jejeje.
La aplicación en un juego... se la das tú ;)

Tal vez en un juego de estrategia en tiempo real sirva para desarrollar la unidad que mejor optimice sus recursos, por ejemplo.

Edito: creo que en la ecuación te falta un ^3 en el segundo miembro ;)

Hola,

si, la verdad es que como método de búsqueda es bastante curioso. Los genéticos sirven sobre todo para buscar en espacios con un alto número de dimensiones, ya que pueden buscar en paralelo sobre el espacio de forma muy rápida (la explicación técnica es el "teorema de esquemas", la tengo en apuntes de la uni, pero la asignatura no tiene los apuntes subidos a la web :().

Normalmente por lo que he leido se usan para controlar otros agentes: por ejemplo, para supervisar el entrenamiento de redes neuronales. Pero ya me informaré más (hasta que me llegue el pedido de amazon nada).

Lo de la ecuación pues no lo se la verdad, suena lógico... He estado mirando de donde lo he copiado y siempre tienen x en el segundo término, voy a probar con x^3 a ver que sale...

El rangos + SUS te lo comento un poco (explicación pesada y fea para quien se la quiera saltar ;)). Básicamente, para seleccionar a los padres, lo que se hace es dividir la probabilidad como si fuera una tarta. Nosotros tenemos una tarta y a cada padre le toca un pedazo de la tarta (una probabilidad entre 0 y 1). La probabilidad de todos los padres tiene que sumar 1.

Para dividir la tarta tenemos dos formas: por fitness o por rangos. Por fitness es que el pedazo de tarta de un padre es proporcional a lo bueno que es el padre:

Pi = Fi / Sum Fi
(Pi = probabilidad del padre i
Fi = fitness del padre i
Sum Fi = Sumatorio del fitness de todos los padres)

Esa formula es para maximizar, para minimizar usamos 1/Fi y Sum 1/Fi

Repartir por fitness tiene dos problemas muy grandes:

- Si todos los individuos tienen el mismo fitness (o casi el mismo), la probabilidad que se le da a cada uno es casi la misma. Esto hace que la evolución se estanque, ya que no queda muy claro quien es mejor o peor.
- Si un individuo es muy bueno y los demás muy malos, el bueno se lleva casi toda la probabilidad, con lo cual será elegido casi siempre como padre, sus hijos serán muy parecidos a él, y la evolución se vuelve a estancar.

Para solucionar eso se divide la tarta usando rangos. Ordenamos los padres por fitness, y el trozo de tarta que le toca es proporcional a la posicion que ocupa en la ordenación. Esto es:

Pi = (2 - Beta) / n + 2 * R(i) * (Beta - 1) / n * (n - 1)

Donde R(i) es el rango del padre i, usease, su posición en el array, Beta es el número de veces que vamos a seleccionar al mejor individuo de todos (en teoría), y n es el número de padres. Beta está en el intervalo (1, 2]. El mejor valor de Beta es 2, lo que nos deja la fórmula así:

Pi = 2 * R(i) / n (n - 1)

La probabilidad del mejor (el que tiene rango n-1, que el rango empieza en 0 como los arrays) es : Pmejor = 2 / n -> si hacemos n elecciones, sale 2 veces.

Lo bueno de los rangos es que hacen que cualquier diferencia entre dos cromosomas se tenga en cuenta, y evita que un individuo muy bueno acapare todas las elecciones. Lo malo es que tenemos que ordenar un array, que es lento. Para solucionar esto existe la selección por torneos (más adelante).

Y luego está lo del SUS: SUS es Muestreo Universal Estocástico (creo: Stochastic Universal Sampling). La cosa es: una vez tenemos nuestra tarta dividida, tenemos dos formas (otra vez ;)) de elegir a los padres:

- ruleta de la fortuna: generas un número aleatorio entre 0 y 1 para cada padre, y te quedas con el padre donde haya caido ese número en la tarta.
- SUS: generas un número aleatorio al azar entre 0 y 1/n (n = número de padres). Te quedas con ese padre, y ahora, para elegir los demás padres, vas sumando a ese primer número 1/n y cogiendo el padre donde haya caido el número.

Existe una demostración de porque SUS es mejor, pero no la conozco.

La selección de torneos es que para seleccionar a los padres, haces un "torneo". Tienes un parámtro, k, que es el tamaño del torneo. Para seleccionar a los padres, simplemente haces un torneo por cada padre a seleccionar. En el torneo participan k padres al azar de entre todos, y gana el mejor (el que tenga el fitness mejor). La selección por torneos es muy rápida, y en teoria, torneos con k = 2 es lo mismo que rangos + SUS con beta = 2 (tiene demostración esto también). En la práctica a mi rangos + SUS me van mejor.

Pues poco más, espero que se entendiera algo ;) El enlace que puse está bastante bien la verdad, que pena que mi universidad no tenga los apuntes en web... (que les costará). Un saludo!

Vicente

[Mars Attacks]

 ¡Bua! Me lo voy a tener que leer dos o tres veces para enterarme de todo, gracias :D

Lo de la ecuación, tiene que estar mal escrita en la web original si está así, ya que

f(x) = x^4 - 12*x + 15*x^2 + 56*x - 60

es lo mismo que

f(x) = x^4 + 15*x^2 + 44*x  - 60

y lo lógico es escribir los factores en orden decreciente. Vamos, que si no lo tienen así será porque lo copiarían mal o por algún problema con el formato.

Gracias de nuevo :)

Y recordad: por el culo te la hinco.

[Warchief]

 En los juegos, bueno en mi caso lo aplicaré al pfc para que la IA aprenda del jugador. Aún no está claro cómo, ya que no tenemos definidas las estrategias ni parámetros, pero por ahí van los tiros. El único problema en mi juego es que los casos de prueba son muy pequeños (partidas del jugador), así que habrá que hacer algunas modificaciones.

[Vicente] 10 individuos no son pocos? Puede que para la ecuación sean suficientes, pero para otros problemas más complejos? (no has contado nada del coste computacional, cómo ha ido la cosa?)

Para los que os guste el tema (aquí si que están los aptes de mi uni xd):
http://et.evannai.inf.uc3m.es/docencia/cb/...sparencias.html

Saludos.

[Vicente]

 Hola,

he estado probando lo de la ecuación, y no es x^3, con x^3 me sale el mínimo muy lejos de 0.88 que es el mejor mínimo que he sacado con el GA Playground (copio directamente de sus notas):

The GA Playground: Single Variable Function Minimization
Minimize f = X^4 - 12*x + 15*x^2 + 56*x - 60

Problem Specific Notes:

    * The problem definition file is SingleVarMin.par
    * The analytically found minimum is x = -0.870173

No entiendo la verdad porque no han agrupado términos...

Respecto a la población, como dice Warchief 10 son muy pocos, pero para este problema va bastante bien. No le he puesto el profiler, pero tarda entre 1 y 2 segundos en encontrar el mínimo (de media entre 200 y 700 generaciones). Y eso que no he hecho ni una optimización (por ejemplo para la selección estoy ordenando todo el rato el array de padres) y va en modo debug... Así que de momento estoy muy contento con el rendimiento :)

Para otros problemas no debería haber ningún problema en definir poblaciones mayores (el código no asume nada de nada sobre el tamaño de la población). El TSP va bien de momento, pero sigue siendo un problema bastante pequeño. Cuando lo resuelva bien para un número pequeño de ciudades (estoy probando con un octógono, que es fácil comprobar cual es el camino más corto), probaré a poner algo grande, no se 150 ciudades o algo así. Con ese problema si que debería necesitar poblaciones más grandes, y con permutaciones de 150 elementos debería tardar bastante más.

Supongo que además del tamaño, el rendimiento morirá en dos sitios en particular: los sort, y las operaciones con los genes, porque la interfaz IGen obliga a estar haciendo casts para sumar, multiplicar,... Además de que para clonar cromosomas tengo que serializarlos a memoria y luego desserializarlos en un objeto (no conseguí hacerlo con el MemberwiseClone...). El tema de la interfaz IGen es porque no existe nada en C# que unifique los números (a parte de object) y que tenga definido los operadores matemáticos (y no puedo hacer una interfaz o una clase abstracta con métodos estáticos como son los operadores). De momento creo que eso no tiene solución (si a alguien se le ocurre que lo diga). Lo de los sorts supongo que definiré atributos auxiliares donde guardaré las poblaciones ordenadas para no repetir ordenaciones todo el rato, aunque si en el TSP grande va bien no creo que optimice demasiado.

En cuanto lo tenga con el TSP lo subo también por si alguien le quiere echar un ojo. Si habéis visto los ficheros MinimizeSingleVar.cs y PruebaEvolutiva.cs definir un problema y resolverlo es bastante sencillo (por si alguien se anima a probar, que entre varios los fallos se sacan más rápido :) ).

Y poco más, Warchief, tu que conoces el tema, si les pudieras echar un ojo y darme tu opinión te estaría muy agradecido :) Un saludo!

Vicente

P.D.: a ver que hay en tus apuntes, me los voy a empollar :)

[Mars Attacks]

he estado probando lo de la ecuación, y no es x^3, con x^3 me sale el mínimo muy lejos de 0.88 que es el mejor mínimo que he sacado con el GA Playground (copio directamente de sus notas):

No entiendo la verdad porque no han agrupado términos...

Porque no se han dado cuenta del error y lo han resuelto así :)