El rincón de la simulación (métodos numéricos)

B

DISCLAIMER: Hago esto obligado por Jastro, me está apuntando con una pistola ahora mismo, si el hilo os parece un coñazo quejaros a él!!

Bueno, me parece que soy el único al que le interesa el tema, pero voy a abrir un hilo para ver si hay más gente que le puede interesar o que no conoce el mundillo de la simulación y quiere empezar (como yo, no es que sea un experto).

Qué es la simulación?

Tomando como referencia la wiki: "La simulación es el proceso de diseñar un modelo de un sistema real y llevar a término experiencias con él, con la finalidad de comprender el comportamiento del sistema o evaluar nuevas estrategias -dentro de los límites impuestos por un cierto criterio o un conjunto de ellos - para el funcionamiento del sistema"

Como vemos hay varios pasos:
Definición del proyecto: ¿Qué pregunta queremos responder? ¿Cuál es el sistema y cuál la hipótesis? (si la hay)
Creación de un modelo: Esto son los mimbres que usaremos para responder la pregunta, normalmente vamos a simplificar mucho la pregunta.
Recogida de datos (si vamos a intentar modelar un sistema real, aquí de momento será todo inventado pero bueno).
Implementación del modelo (o como se llame, la terminología no es lo mío). Esto incluye desde generación de números aleatorios, hasta picar código y montar el sistema, vaya, lo que haga falta.
Extracción de resultados
Representación de resultados Esta en concreto me interesa mucho a mí, cómo hacer que los resultados se entiendan incluso por alguien que no domina el modelo.

Para qué servirá este hilo?

Llevo un tiempo con ganas de simular unas cosillas que no pondré de momento aquí (no por nada de confidencialidad, sino porque es un poco demasiado chungo al menos para mí y no quiero que me estropeéis la diversión haciéndolo por mí xD). Me gustaría ir proponiendo proyectos por aquí, tanto yo como quien se apunte, e ir aprendiendo juntos distintos métodos tanto de modelar un sistema como de programar y representar. Sé que puede sonar paliza y muy chungo, pero a ver si entre todos los interesados puede salir algo chulo.

Pienso que de hecho no es imprescindible que todos lo hagamos todo, (quien quiera hacerlo todo es bienvenido, yo lo haré o intentaré), si alguien quiere dedicarse solo a buscar un modelo o un algoritmo mejor, y comentarlo, también estaría bien, si alguien quiere dedicarse solo a implementar el algoritmo en haskell y en matlab y comparar guay, y si alguien solo quiere al final representar los resultados de una manera chula (y enseñarme cómo se hace) perfecto. La idea es tener cosas que hacer que no sean solo viciar al Lego Marvel Superheroes. Por este motivo me gustaría que al empezar con un "proyecto", entre todos nos pongamos de acuerdo con entradas/salidas de cada parte, para poder hacer las cosas modularmente (por ejemplo problema -> algoritmo devuelve lista de posiciones de x manera -> dibujamos las posiciones en un plot) sin liarnos con el formato. También serviría por si alguien quiere probar con otro modelo, para poder meterlo sin cambiar I/O.

Si hay un problema gordo podríamos usar un github (no lo he usado mucho xD).

Otra cosa, me gustaría montarme un pequeño portfolio/blog con los resultados y proceso de las distintas simulaciones que haga por aquí y aparte, y si queréis puedo poner el trabajo que hagamos conjunto también, o no, como queráis.

Proyectos

Para que os hagáis una idea, aquí hay una minilista: http://raider.mountunion.edu/CINDRICBB/sp01/sim/possible_projects.html
Si se os ocurre uno interesante, comentadlo y lo iremos poniendo en la cola.
Ahora pondré la primera propuesta y esperaré a ver reacciones, si os mola el formato del hilo, si creéis que hay que cambiar cosas y tal.

Primera propuesta: Modelar el sistema que usa una colonia de unas 50-100 hormigas para encontrar comida y representarlo (a ver cuánto se parece a la realidad de manera cualitativa). BONUS: Hacer simulaciones en otro tipo de geometrías que no sean la plana, y con obstáculos, hacerlo "dinámico" (poder meter la comida mientras las hormigas se están moviendo). Mi idea sería usar la metaheurística Ant Colony Optimization (como veis, bastante directo) con un random walking. Ya me explayaría con esto si a alguien le interesa seguir con el hilo.

Espero que haya interés, la simulación es una disciplina mu chula, quizás mi propuesta es un poco insulsa pero para empezar creo que está bien xD.

9
B

Reservado.

Jastro

#1 Gran post, el tema de la simulación es la primera vez que lo oigo, puede hasta que me apunte y todo, buena iniciativa.

PD: me encanta lo de que te tengo amenazado jajajaja :D

1 1 respuesta
B

#3 se puede hacer también más técnico e ir a generación de muestras aleatorias, métodos numéricos puros (cálculo matricial e interpolación), pero me parece más interesante esto. Además son técnicas que siempre pueden ir bien también a la hora de desarrollar un juego (bueno, todo puede ir bien a la hora de desarrollar un juego xD), y por lo que veo en la taberna indie no mucha gente está metida en estas cosas (tampoco es que sean esenciales).

Otra simulación divertida puede ser coger un cruce de vuestro pueblo, hacer una estimación de cuántos coches pasan por cada carril por hora (más o menos fiel a la realidad) y mirar la utilidad de sustituir el semáforo por una rotonda, dependiendo del radio de la rotonda.

Jastro

Curioso #1

Tienes 4 favoritos, eliminando el tuyo y el mio, hay 2 personas mas interesadas, que no han dicho nada.

Comenten, no dejen que la labor del Duronman se pierda :(

1 respuesta
B

Cojo sitio por aquí que suena interesante :D

1 respuesta
charl1

El conocimiento es poder, cojo sitio.

1 respuesta
B

#5 uno de ellos es oip que me dijo que está muy liado.

#6 #7 os parece bien mi propuesta de las hormigas? En principio yo iré comentando mi plan y que quien quiera se apunte, me gustaría si veis cosas mejorables que las comentárais y todo eso.

Mi idea de modelo: el suelo es una cuadrícula por el que se mueven las hormigas "en turnos", es decir todas dan un paso a la vez (pueden haber varias en la misma posición). Cuando están suficientemente cerca de la comida la encuentran y ya saben llegar. Cada hormiga cuando va andando deja un "rastro" que se va difuminando (como una temperatura). A la hora de escoger, las hormigas prefieren seguir hacia adelante que volver atrás, y prefieren seguir un rastro "caliente" antes que uno frío. Como veis la idea es simple. Pero pienso que puede dar juego, y ver si puede ser que las hormigas se queden dando vueltas, o si hay un "agujero" (las hormigas entran pero no salen) puede ser que todas se caigan... ¿Qué os parece? Es una simplificación bastante bestia de la realidad pero que puede llevar a resultados "interesantes"

3 1 respuesta
Nucklear

A mi estas cosas me encantan pero me parecen muy complejas y requieren tiempo que no tengo. De todas formas estaré pendiente y me leeré vuestro código para ir introduciéndome. Ademas tanto mi novia como mi hermano tienen métodos numéricos en la carrera con buenos profesores así que si me surgen dudas tengo donde preguntar.

1 respuesta
B

#9 si tienen dudas y quieres preguntarme también adelante, la verdad es que modestia a parte creo que se me dan bastante bien (luego programar bien y ordenadito ya es otra cosa xD, pero la idea la tengo)

1 respuesta
B

#10: y en principio parece sencillo de programar.

Cuál es tu idea, poner varios spots de comida? O solo uno?

1 respuesta
Meleagant

Yo tuve una asignatura optativa sobre esto en la carrera, pero me parece que no vimos muchos.

Hacíamos simulaciones con MatLab de, por ejemplo, cómo evolucionaba la población de lobos y conejos en un lugar suponiendo que los lobos sólo comían conejos, o de dos recipientes con agua interconectados y cómo evolucionaba su capacidad abriendo más o menos los grifos.

Pero de ahí a lo de las hormigas, ya me pierdo xD

1 respuesta
B

#11 me gustaría poder poner varios, y ver como un "mapa de calor" de los caminos que siguen los bichejos, si se pudiera ver a tiempo real molaría mucho también. Mi duda es a la hora de volver al hormiguero, no sé si tiene más sentido que desanden sus pasos o que tomen la directa. También estaría bien (esto es fácil) jugar con distintas topologías, una esfera, un toro, una botella de Klein, una cinta de Möbius. Para esto no es necesario 3D, simplemente identificar bordes del cuadrado (ya lo explicaré si eso, es topología "elemental" ) . El problema en los últimos dos casos es que debería haber un "debajo" y un "arriba" del cuadrado, si no no tiene mucho sentido:

Personalmente (no soy ningún experto así que acepto recomendaciones) creo que podría ser relativamente sencillo usando algún lenguaje orientado a objetos. Pero para que salga en una pantallita los cuadraditos volviéndose rojos (o negros, vaya), la verdad es que no sé ni por dónde empezar a mirar xD.

#12 el de los lobos y los conejos es un clásico, yo hice una de cómo evolucionaría una pandemia según las vacunas, la tasa de mortalidad, de contagio... xD la presentación fue bastante graciosa: "Y vemos aquí como muere toda la población mundial"

1 respuesta
esvarianzza

#8

Entonces cada hormiga sería una célula, y calcularía su siguiente posición en el mapa (en una de las 8 cuadrículas que le rodean) probabilísticamente teniendo en cuenta el querer ir hacia delante y el rastro caliente ¿sí?

1 respuesta
B

#14 exacto. Se podría hacer de manera "continua", es decir escoger el ángulo de giro dentro de una distribución triangular, por ejemplo, pero sería liar un poco las cosas. Si os parece mal o tenéis una propuesta distinta me gustaría oírla eh!

2 respuestas
esvarianzza

#15

Está interesante, sobre todo si se modeliza bien el tema de los rastros. Y con representacion gráfica puede estar muy chulo.

Yo apenas he tocado MatLab, así que si sale para adelante creo que voy a aprender bastante.

B

#13: suena muy bien. Del tema las topologías si que no tengo ni idea, la verdad (nunca estudié ese tipo de cosas en profundidad). Supongo que la representación no será demasiado complicado en algo tipo Matlab.

esvarianzza

#15

Pensándolo un poco, el hacerlo de forma continua creo que es cuando realmente el asunto empieza a tener chicha, aunque no se como sería el overhead de hacerlo así.

Se genera el mapa con tantas hormigas dentro del hormiguero y un punto de comida (luego se pueden añadir más).
Las hormigas se representan en x, y, theta (ángulo respecto a x) y booleano de comida (la tiene o no).
El hormiguero es un área, x1,y2, x2,y2, x3,y3 , x4,y4, int número de hormigas dentro, e int comida dentro
La comida es un área, x1,y2, x2,y2, x3,y3 , x4,y4, int unidades de comida restantes.
Podrían tener otras formas que no fuesen un cuadrado ofcors.

Van saliendo de una en una(o el número que sea) del hormiguero, para la salida no se tiene en cuenta la dirección(aleatoria) pero sí el rastro del entorno del hormiguero.
Cada vez que se mueve una hormiga genera un segmento, x1, y1, x2, y2, con un tiempo de vida(turnos) y un booleano comida (si lo hace una hormiga con o sin comida).
Si hay 50 hormigas se estarían generando 50 segmentos por turno.
Cuando la hormiga tiene comida se aumenta la intensidad del rastro (valor y duración).

La parte divertida al hacerlo de forma continua es como tratar las intersecciones de la hormiga con un rastro, por un lado como se enfoca el análisis de si intersecta o no el camino de la hormiga con ninguno, uno o más rastros (que sólo analice los de su entorno), y por otro como cambia la dirección de la hormiga respecto a cada uno de esos rastros, teniendo en cuenta que si no tiene comida sigue el sentido de los no comida, y el sentido opuesto de los con comida, y viceversa si sí tiene comida.

Cuando hubiese un camino establecido hacia la comida con cientos de rastros entrecruzándose habría que empezar a limitar el número de rastros que analiza (sólo los más intensos/nuevos)

Whattajsay?

1 respuesta
B

#18 me gusta tu idea pero me parece más complicada. De hecho en un principio mi idea era parecida, y además que el rastro conforme pasaba el tiempo no solo disminuyera sino que se difuminara (se ensanchara, vaya)... Pero eso sí que es añadir complicación innecesaria.

De hecho el segmento solo necesitaría 3 datos igual que la hormiga (si suponemos que todas van a la misma velocidad). ¿Y qué propondrías tú si una hormiga se encuentra a medio segmento con un rastro? Porque si el rastro es un segmento esa es la única oportunidad de seguirlo que tiene, entonces debería parar a medio camino y volver a decidir ahí, no? Si lo difuminamos entonces sí que puede "detectar" un rastro aunque no esté encima suyo.

Lo bueno de hacerlo por diversión es que se pueden probar las dos maneras, la de la cuadrícula es bastante sencilla de hacer creo, y podemos comparar las soluciones.

1 respuesta
esvarianzza

#19

Algo así, cada vez que intersectase torcería proporcionalmente hacia el sentido correcto y volvería a recalcular el trozo que le queda por andar en ese turno.
Por ejemplo, si una hormiga perdida se encuentra perpendicularmente con el sendero hacia la comida, empezaría a atravesar rastros que harían que no llegase a salir por el otro lado, sino que le llevaría "la corriente".

Quizá lo de trabajar con cuadrícula lo simplifica y a la vez lo hace más asequible para cosas como esa difusión de los rastros, aunque no se si con las hormigas funciona así en la realidad, pero oye, ¿quién dice que no son hormigas mutantes con feromónas mejoradas? :D

Qué lenguaje proponéis?

2 respuestas
B

#20 yo en Matlab puedo hacer un prototipo rápido (sólo cálculos) en 2 tardes, pero tb me molaria probar y hacerlo en python o Java... Tampoco soy un experto programador así que como digáis!

B

#20 como actualización, estoy en ello, de momento genero la comida y el hormiguero como círculos (no sé cómo guardar eficientemente áreas en MATLAB). Y me he tomado la libertad de hacer una cosa un poco distinta a lo que comentabas, y es que la hormiga irá detectando segmentos cercanos (el radio de "olfato" se puede seleccionar). Mañana me explico más que estoy muy cansado... (no de esto xD)

edit: El código para encontrar la distancia de la hormiga a un segmento (es una proyección ortogonal a la recta y si se sale del segmento se trunca) ¿Por qué no me va el code ??

function [dist, t] = ProjectToSegment(z0,z1,z2)
    t = real((z0-z1)*conj(z2-z1))/(abs(z1-z2)^2);
    if t < 0
        t = 0;
    elseif t > 1
        t = 1;
    end
    dist = abs(z0 - t*z1 - (1-t)*z2);
end
1 respuesta
esvarianzza

#22

Suena bien eso del olfato :)

Explícame las z.
Mi idea era que con la posición absoluta de la hormiga, y la absoluta del inicio del segmento, teniendo en cuenta que son segmentos muy pequeños, podías sacar directamente la hipotenusa. Sencillito vaya.
Creo que tu estás metiendo ya algo más en esta parte.

1 respuesta
B

#23 Bueno, sí que es cierto que al ser segmentos muy pequeños se podría aproximar, pero miro directamente la distancia al segmento. Puede ser que tengas un extremo del segmento justo al límite de la distancia de "olfato", pero que el centro del segmento lo tengas más cerca (ímaginate un círculo que representa el alcance del olfato de la hormiga). Mi idea es que de algún modo la hormiga mire qué rastro tiene más cerca y eso modifique su elección de camino, y si llega a cruzarse vuelva a modificar su camino como comentamos el otro día. Si haces el alcance del olfato suficientemente pequeño, entonces sólo influirá cruzarse con otros segmentos, si es mayor habrá más hormigas influyendo.

Las z, es simple cuestión de que no tenía ganas de usar vectores y he usado complejos xD, no sé si mejora o empeora en tiempo y precisión pero para este nivel no creo que afecte. z0 es el punto en el que está la hormiga (en el plano complejo z0 = x0 + iy0, en el plano (x0,y0)), z1 es el inicio del segmento y z2 el final del segmento (también en los complejos).

Una ecuación que describe el segmento es z = z1t + z2(1-t) con t entre 0 y 1. Fíjate que si t vale 0 z vale z2 y si t vale 1 z vale z1 (esto lo podría cambiar para que sea más intuitivo). Si t es menor que 0 o mayor que 1 entonces estamos en la recta definida por esos dos puntos y no por el segmento. La distancia de z0 al segmento es la mínima distancia entre z0 y z = z1t + z2(1-t) , esto se puede derivar e igualar a 0 y nos sale una t. Si la t está entre 0 y 1 el punto más cercano está dentro del segmento, si es menor que 0 o mayor que 1 entonces será uno de los extremos. Y eso es lo que hago ahí.

Entonces si la distancia al segmento es menor que el radio de olfato significa que capta un trozo más grande de segmento, y se sentirá más atraída por ese segmento que por uno que tenga más lejano (también teniendo en cuenta lo fuerte que huele, es decir cuánto hace que no pasan hormigas por ahí).

La explicación es liosa, con un dibujo se entiende mejor:

La hormiga z0 alcanza a menos con su olfato pero huele muy bien el segmento, la hormiga z0' aunque alcance muy lejos no huele tan bien el segmento (en principio todas alcanzan lo mismo pero para no llenar el dibujo de líneas mal hechas todas apelotonadas lo he puesto así xD). En el caso de la hormiga z0, t estaría entre 0 y 1 en cambio para la hormiga z0' t valdría 0.

Este punto indicado por t pienso usarlo para que sea la referencia de a dónde va la hormiga, una vez olidos los segmentos. En principio lo más pesado ahora es tener una estructura de datos limpia (que se me da fatal) para no complicarme mucho la vida a la hora de llamar a funciones y guardar datos...

1 respuesta
esvarianzza

#24

Vale realmente has tomado una aproximación completamente distinta de la que tenía yo en mente, por eso me ha costado entenderlo. Yo pensaba en la hormiga atravesando segmentos y en redireccionarla basándonos en direcciones y sentidos de esos segmentos, pero sin dirigirse hacia el segmento. Tu ves el segmento, y te aproximás hacia la parte más cercana de este. Resultados parecidos pero cálculos bastante distintos.

Creo que he entedido el planteamiento.

¿Cómo vas a enfocar la parte de los pesos absolutos de los segmentos ( f(tiempo,intensidad)) y los pesos respecto de la hormiga ( g(distancia, f))?

Eso sí, la forma en que has hecho la proyección es todavía un misterio divino :_D
¿conj funciona como un conjugado y abs como un módulo?

1 respuesta
B

#25 pues vaya xD, perdona por liarla, aunque en principio si haces el radio de olfato suficientemente pequeño será lo mismo (si solo lo nota en la intersección es como si tuviera radio 0). Igualmente quiero que modifique un poco la trayectoria al cruzarse o por lo menos que se pueda activar la opción.

Conj es el conjugado complejo y abs es el módulo efectivamente. En vectores la fórmula de la proyección es:

t = <z0-z1, z2-z1>/<z1-z2,z1-z2>

donde <,> es el producto escalar. En los complejos para que salga bien tienes que tomar la parte real del producto de uno por el conjugado del otro. Sobre los pesos mañana comento!

1 respuesta
esvarianzza

#26

No hombre, si es hasta mejor, como dices, con un radio de olfato pequeño probablemente se aproxime más a la realidad, es justo lo que he pensado cuando lo he entendido :D

Vale, no conocía la librería, la verdad es que queda bastante fino.

1 respuesta
hda

#1 Pillo sitio.

Aunque todavía no está cerrado, lo más seguro es que termine haciendo un máster en física computacional (hice DAI, trabajé de ello, ahora hago físicas), me interesan tanto nuevos materiales (cerámicas superconductoras, grafeno...) como fusión.

Y bueno, he de decirlo, que para uno que tengo... el único sobresaliente en una troncal que he logrado hasta la fecha es en métodos numéricos (en el enlace se ve el programa de la asignatura; botón derecho-> abrir en nueva pestaña).

Por tanto, siento curiosidad por este hilo :D

1 respuesta
B

#27 aún hay que mejorarlo no obstante (a lo mejor debería preferir ir hacia el extremo más cerca de z2 que es el final, en lugar de hacia el segmento, pero bueno, son detalles menores). Otra cosa interesante de los complejos es que un giro es multiplicar por un número complejo (en lugar de una matriz).

Mi idea es que si en el instante t0 la hormiga está encarada en el ángulo theta0, y no hay segmentos por ahí seleccione su nuevo ángulo acorde con una función de distribución de probabilidad tipo A-B|theta0 - theta| (es decir que la probabilidad de dar media vuelta sea 0 y la de seguir adelante sea la más alta).

Por otro lado tenemos una serie de vectores que indican las direcciones a los distintos segmentos de rastro, los cuales podemos sumar de manera ponderada (la ponderación depende de la distancia y de la intensidad del rastro). El vector suma nos indica otra dirección y otra altura, y podemos crear otra distribución de probabilidad. Hacemos la media aritmética (o geométrica, depende de cuánto queramos putear a la hormiga) entre las dos distribuciones, normalizando, y seleccionamos un número al azar de esa nueva distribución. ¿Qué os parece? Si en cada turno la hormiga se mueve mucho, quizás deberíamos dividir su avance en 3 partes y recalcular para que no se pase de largo, pero con una velocidad razonable creo que es suficiente con hacer el cálculo una sola vez (y sumar vectores es sencillo a nivel de cálculo).

#28 me alegra que te interese! Yo seguramente haga mi doctorado en matemática computacional xD. Métodos numéricos es generalmente en mates una de las más odiadas pero mira, los designios del señor son inescrutables. Si quieres proponer proyectos molaría!

Resa

Edit: Me confundi de hilo, sorry. Si algun mod ve esto que borre el post.

#31 Bueno, yo postee al tuntun sin leer el hilo porque tuve un puesto de trabajo en el departamento de simulacion de una empresa y crei que el tema iba por ahi xd

#33 Si, luego de leerlo me he interesado, de hecho lo que mas me gusta del tema es modelizar cosas. Sin embargo ahora mismo estoy liado con el PFC y el trabajo. Haber si acabo con el PFC este mes y luego me puedo dedicar a aprender algo de matlab entre otras cosas. Haber si me puedo unir para el mes que viene.

1 2 respuestas