Sim Talk es una interesante y divertida iniciativa de Jacob Ingalls (twitter), dedicando este podcast a la simulación, con entrevistas periódicas a especialistas (empresarios, académicos y usuarios en general) de la simulación. Este primer episodio es con una entrevista al Dr. Jeremy Tejada de la empresa SIMCON.
Los invito a seguir este podcast en el siguiente link.
El problema original fue publicado por la revista InfORMS en Octubre de 2014. A continuación su versión en español.
Cuatro combatientes debaten entre quién de ellos es el más fuerte. La figura 1 muestra a los cuatro combatientes: Allan, Barry, Charles y Dan.
Cada luchador tiene diferentes habilidades de ataque y resistencia. Al inicio de la batalla tienen diferentes puntos de resistencia: Allan tiene 10, Barry tiene 12, Charles tiene 16 y Dan tiene 18. Además, cada luchador tiene diferentes puntos de ataque: Allan tiene 4, Barry tiene 3, Charles tiene 2 y Dan tiene 1.
La batalla tiene lugar en varias rondas, cada una consistente en un solo ataque. En cada ronda, una atacante aleatorio y un defensor aleatorio son elegidos.
Cuando el atacante ataca a un defensor, el defensor pierde puntos de resistencia en la cantidad equivalente a los puntos de ataque del contrincante. Por ejemplo, si Allan es el atacante y Barry es el defensor, Barry perdería cuatro puntos de resistencia.
Los combatientes continúan atacando y defendiendo aleatoriamente en las rondas siguientes hasta que sólo queda un luchador, quien entonces es declarado ganador. Se elimina un luchador de la batalla cuando sus puntos de vida se convierten en cero (o menos).
Pregunta: ¿Qué peleador es más probable que gane la batalla?
Un simple ejercicio de simulación, la respuesta se publicará en una semana.
En el link de final de página se encuentra una macro sencilla que permite simular múltiples repeticiones de un combate entre los cuatro jugadores. El código que realiza la simulación se explica a continuación: En síntesis, una vez borrado el resultado de la ronda anterior, se elige un atacante y un defensor de manera aleatoria y se hace un ataque por un valor entre 1 y el mínimo entre el número de puntos de defensa y el número de puntos de ataque. Este valor se resta al jugador de defensa y se repite el proceso hasta que solo quede un jugador con puntos. Esto se contabiliza dentro del tablero de mando al inicio del archivo. Al final, luego de al menos 1000 repeticiones, se establece el jugador que más partidas ha ganado, que bajo las configuraciones descritas arriba es Charles con una probabilidad del 32.5%.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
Sub start() Dim rng As Range Dim sim As Worksheet Set sim = Sheets("sim") sim.Range("B4:F4").Select Selection.ClearContents Range("A1").Select frm1.Show If frm1.Label2.Caption = 999 Then Exit Sub End If For t = 1 To frm1.TextBox1.Value sim.Range("A8:I2000").Select Selection.ClearContents sim.Range("A1").Select flag = 999 i = 1 While flag > 1 If i = 1 Then v = 4 Else Set rng = sim.Range(Cells(i + 6, 6), Cells(i + 6, 9)) Maximum = Application.WorksheetFunction.Max(rng) v = Application.WorksheetFunction.CountIf(rng, ">0") End If flTemp = 1 While flTemp = 1 atacker = Int(Rnd() * 4) + 1 If (sim.Cells(i + 6, 5 + atacker) > 0) Then flTemp = 999 atackName = sim.Cells(1, 1 + atacker) End If Wend flTemp = 1 While flTemp = 1 target = Int(Rnd() * 4) + 1 If (sim.Cells(i + 6, 5 + target) > 0 And target <> atacker) Then flTemp = 999 targetName = sim.Cells(1, 1 + target) End If Wend sim.Cells(i + 7, 1) = i sim.Cells(i + 7, 2) = atackName sim.Cells(i + 7, 3) = targetName If (i = 1) Then sim.Cells(i + 7, 4) = sim.Cells(2, 1 + target) sim.Cells(i + 7, 5) = sim.Cells(3, 1 + atacker) sim.Cells(i + 7, 6) = sim.Cells(2, 2) sim.Cells(i + 7, 7) = sim.Cells(2, 3) sim.Cells(i + 7, 8) = sim.Cells(2, 4) sim.Cells(i + 7, 9) = sim.Cells(2, 5) If sim.Cells(2, 1 + target) - sim.Cells(i + 7, 5) < 0 Then sim.Cells(i + 7, 5 + target) = 0 Else sim.Cells(i + 7, 5 + target) = sim.Cells(2, 1 + target) - sim.Cells(i + 7, 5) End If Else sim.Cells(i + 7, 4) = sim.Cells(i + 6, 5 + target) sim.Cells(i + 7, 5) = sim.Cells(3, 1 + atacker) sim.Cells(i + 7, 6) = sim.Cells(i + 6, 6) sim.Cells(i + 7, 7) = sim.Cells(i + 6, 7) sim.Cells(i + 7, 8) = sim.Cells(i + 6, 8) sim.Cells(i + 7, 9) = sim.Cells(i + 6, 9) If sim.Cells(i + 6, 5 + target) - sim.Cells(i + 7, 5) < 0 Then sim.Cells(i + 7, 5 + target) = 0 Else sim.Cells(i + 7, 5 + target) = sim.Cells(i + 6, 5 + target) - sim.Cells(i + 7, 5) End If End If 'sim.Cells(i + 8) = i Set rng = sim.Range(Cells(i + 7, 6), Cells(i + 7, 9)) Maximum = Application.WorksheetFunction.Max(rng) v = Application.WorksheetFunction.CountIf(rng, ">0") If v < 2 Then flag = 1 tSim = 0 For k = 1 To 4 If sim.Cells(i + 7, 5 + k) > 0 Then winner = sim.Cells(7, 5 + k) wc = k + 1 End If tSim = tSim + sim.Cells(4, 1 + k) Next k sim.Cells(4, wc) = sim.Cells(4, wc) + 1 sim.Cells(4, 6) = tSim + 1 End If i = i + 1 Wend Next t MsgBox ("Done!") End Sub |
El siguiente video fue creado por el equipo de visualización del centro nacional de supercomputación (Barcelona supercomputing center) BSC-CNS. En él se describe cómo la simulación basada en agentes es utilizada para modelar el comportamiento de las sociedades primitivas, su relación con el entorno, el clima, la disponibilidad de alimentos, la rivalidad con otras tribus y la consecuente evolución en la zona de Gujarat (India) 10,000 años atrás.
Múltiples experimentos fueron realizados implementando además algoritmos de inteligencia artificial, lo que combinado con el paradigma de simulación permite que los agentes interactúen, aprendan y perfeccionen sus decisiones a partir de la experiencia y su visión (limitada) del entorno. Las simulaciones fueron realizadas en el supercomputador MareNostrum del BSC. Esta investigación se enmarca dentro del proyecto Simulpast, una iniciativa del programa Consolider liderada por el investigador ICREA Marco Madella.
Mayor información sobre este proyecto en el siguiente link.
Los invito a ver este excelente video:
Recientemente trabajé en un proyecto con estudiantes de la universidad de Seúl (Korea) para desarrollar un simulador que pudiese implementar diferentes algoritmos de organización de la producción en un taller tipo Flow-Shop.
El modelo fue desarrollado en AnyLogic utilizando simulación a base de agentes. Los trabajos y las máquinas se representan por agentes y deben organizar la producción (secuencia de trabajos) según la metodología previamente definida. Estas metodologías pueden ser:
El modelo permite agregar variabilidad al tiempo de trabajo, lo que repercute en la organización original requiriendo que periódicamente los algoritmos deban ser re-ejecutados para evaluar el plan de trabajo.
Una etapa futura de este proyecto consiste en agregar múltiples máquinas por estación, almacenamientos temporales (buffers) y estratégias de re-organización que combinen las heurísticas descritas arriba con mecanismos de negociación entre los agentes de manera que las estaciones resuelvan horizontes relativamente cortos de planificación de manera autónoma.
Un video de este modelo se presenta a continuación.
En Stream Systems hemos diseñado un nuevo producto llamado SimOpti, un simulador en línea destinado a terminales de petróleo que permite analizar diversos escenarios y optimizar la configuración de tanques, rutas, oleoductos entre otros en un ambiente seguro, confiable y eficiente. El siguiente es un video tipo tablero (white board) que explica con un sencillo ejemplo el tipo de aplicaciones que se pueden resolver con este sistema.
El lanzamiento de este producto esta planeado para el 28 de septiembre de 2016.
Para aquellos familizarizados con la programación, es común la utilización de clases en la manipulación de objetos. Una clase en términos generales es una plantilla de código donde se crean los objetos del programa. Los objetos son entidades personalizadas con atributos y operaciones específicas (para entender con mayor detalle el concepto de clases y objetos sugiero leer los siguientes artículos: conceptos y ejemplo sencillo ).
Un concepto similar a una clase es un agente. Los agentes son plantillas genéricas que permiten capturar atributos (parámetros, variables, colecciones, etc.), realizar calculos, gráficos, animaciones e incluso incrustar grupos de agentes adicionales. Todas estas funcionalidades son igualmente posibles en una clase Java, así que porqué utilizar una u otra figura?
Desde el punto de vista de complejidad y curva de aprendizaje, el agente es mejor opción ya que todas sus propiedades son creadas con solo arrastrar el ícono del elemento requerido. Por ejemplo, si se quiere agregar una variable, se arrastra el ícono correspondiente, se cambia el tipo de valor (doble, string, etc.) y se re-nombra. Igual con colecciones, poblaciones, estadísticas, etc. (ver animación).
La misma operación en una clase requiere de cierto conocimiento de programación para poder definir correctamente las variables, tipo de acceso, funciones, etc. En otras palabras, todo debe hacerse mediante código (ver animación).
Una clase puede volverse confusa para un usuario si desde su diseño no ha sido bien estructurada. Una práctica recomendada por muchos usuarios es utilizar agentes de manera general, incluso convertir las clases Java en agentes (AnyLogic ofrece esa posibilidad como se observa en la imagen siguiente)
Otro beneficio relacionado con el uso de agentes es las poblaciones. Grupos de agentes pueden ser almacenados y manipulados en poblaciones, las cuales tienen incluso funciones pre-definidas que permiten organizar, filtrar, etc. Las clases Java no pueden almacenarse igual y deben ser (si se requiere) añadidas a colecciones.
A pesar de ser recomendados los agentes, dado que se pueden realizar las mismas actividades existen casos en los que es mejor utilizar clases, a continuación algunos ejemplos:
El software de simulación Simio presenta su versión gratuita PLE (Personal Learning Edition) que permite crear modelos con todas las funcionalidades de la versión profesional, no obstante aplican ciertas limitaciones para guardar modelos de gran tamaño.
Al igual que otros software de simulación (ejemplo: Arena, Promodel, AnyLogic), Simio entra en la era de las versiones gratuitas como una iniciativa para popularizar el uso de la simulación en todas las disciplinas lo cuál es una noticia muy positiva para quienes trabajamos en este campo.
El software puede ser descargado en el siguiente link
Recientemente tuve la oportunidad de dar una charla sobre las ventajas de utilizar R como soporte para profesionales en Analytics y Simulación.
Si bien existen diferentes software especializados para realizar análisis de datos cada uno con sus ventajas y desventajas, en los últimos años los especialistas de diversas disciplinas han coincidido en la necesidad de estandarizar procesos y análisis en un solo lenguaje, la gran mayoría han optado por R (Python es otra buena alternativa). Esta presentación pretende mostrar las ventajas del lenguaje R (y algunas aplicaciones) como herramienta de soporte a profesionales que requieren manipulación y análisis de datos, en mi caso particular como consultor en optimización y simulación.
A continuación el material de soporte de la presentación.
La empresa británica Lanner lanzó a comienzos de Junio de 2016 su nueva versión de su software de simulación Witness Horizon. Esta versión cuenta con varias mejoras, entre ellas:
El siguinte video es un breve demo de las nuevas funcionalidades en 3D
Una lista mas completa de especificaciones puede ser consultada en el siguiente link
A continuación un segundo video donde se presentan con más detalle varias de las funcionalidades de la nueva versión.
Una vez construido un modelo de simulación es necesario ejecutar un Análisis Resultados para garantizar la robustez de del modelo y la validez de los hallazgos.
El análisis de resultados consiste en ejecutar múltiples repeticiones de un experimento haciendo o no cambios a una o varias variables de manera que se describa el comportamiento general del modelo y se identifiquen los patrones de los resultados dados diferentes valores de las variables de entrada. Si estas repeticiones se hacen con cambios incrementales en las variables de entrada, se conoce como Análisis de Sensibilidad. Si las variables de entrada tienen una distribución de probabilidad asociada se puede generar una secuencia combinada basada en dicha distribución, lo que se conoce como Monte Carlo. Cuando las variaciones son estratificadas (escalas uniformes) sin importar la distribución asociada se conoce como Variación de Parámetros.
AnyLogic en su versión PLE permite realizar Variación de Parámetros y Optimización. Versiones más avanzadsa como la versión profesional permiten además realizar Comparación de Experimentos, Monte Carlo, Análisis de Sensibilidad, Calibración y Experimentos personalizados (ver imagen).
Siendo la variación de parámetros el único tipo de experimento disponible en la versión PLE para la fase post-simulación a continuación se explica cómo hacer muestreo y análisis de resultados usando este módulo y algunas maneras de implementar rutinas que incrementen su funcionalidad.
Al construir un modelo de simulación se debe establecer todo el espectro y distribución de las variables de entrada (parámetros). Para ello utilizamos muestreo y análisis estadístico. Esta parte pre-simulación será tratada en otro post.
Al finalizar el modelo, se deben ejecurar múltiples repeticiones con diferentes valores aleatorios y parámetros para establecer el rango total de salida. Idealmente se deben simular todos los escenarios posibles, sin embargo, en muchas ocasiones el número total de escenarios es tan alto que simular el espectro completo tarda demasiado. En estos casos es recomendable utilizar muestreo sobre los parámetros para elegir combinaciones estadísticamente representativas.
A continuación se explican los diferentes tipos de muestreo.
Muestreo Aleatorio: Consiste en generar muestras eligiendo números al azar sobre la distribución de probabilidad acumulada. Esta técnica requiere un elevado número de muestras para conseguir una representación adecuada de la variable en estudio (cientos o miles de repeticiones).
Muestreo Estratificado: Consiste en segmentar la variable en grupos o estratos y elegir valores aleatorios al interior de cada sub-grupo para la simulación. Los estratos son generados a partir de información típica de la distribución observada. Requiere también de un elevado número de repeticiones aunque menor que el muestreo aleatorio.
Muestreo por Hipercubo Latino: Consiste en asignar distribuciones de probabilidad a cada variable de entrada y distribuir cada una en un número de intervalos equiprobables. Luego se eligen valores al interior de cada grupo y se combinan con las demás dimensiones de las otras variables, para obtener vectores completamente independientes y aleatorios como entradas del modelo. Dado que cada muestra es independiente, se requieren menos repeticiones pues se asume que una serie completa de experimentos con esta entrada es estadísticamente independiente.
Un inconveniente típico en este último método es que la representatividad de los resultados solo se puede evaluar luego de ejecutar todos los experimentos y en caso de no ser satisfactoria, se debe volver a empezar aumentando la cantidad de intervalos equiprobables. Una solución a este inconveniente es la utilización del Hipercubo Latino Escalable.
En otras ocasiones no es necesario conocer todo el espectro sino un segmento de él. Si el segmento es contínuo (ejemplo una variable puede distribuirse entre 100 y 200 visitas por hora pero solo se desea evaluar el impacto de mas de 160 visitas al día) se considera como una variación de parámetros con menos combinaciones. Cuando las variaciones son discontinuas y combinadas, es mejor definir los escenarios previamente y luego ejecutar experimentos basados únicamente en la matriz de entrada. En AnyLogic esto se implementa fácilmente utilizando bases de datos o archivos externos.
Una vez se elige un nuevo experimento de tipo variación de parámetros, AnyLogic crea una nueva sesión en blanco donde se define la memoria total a utilizar, el agente de referencia (usualmente Main) y la forma como los parámetros van a interactuar (ver imagen). Estos parámetros pueden ser fijos o variables en un rango, es decir se fija un valor único o el valor inferior y superior, así como el paso (step) para su variación uniforme.
De esta forma, si se tiene un modelo con 10 parámetros de entrada de las cuales 2 se planean fijas y 8 variables con 10 pasos por cada una, se deben tener al menos 100 millones de experimentos para cubrir una sola repetición de todas las simulaciones.
Un ejemplo es el siguiente modelo en el cuál un taller cuenta con cuatro estaciones de trabajo en serie, cada una con un buffer de entrada con capacidad limitada. Las estaciones cuentan con un tiempo de procesamiento tn (9, 12, 8 y 14 minutos respectivamente) distribuido triangularmente más o menos 10% (ver imagen del modelo).
Luego de haber ingresado 1000 unidades al sistema el modelo se detiene y verifica los indicadores claves de rendimiento. Estos son:
Si suponemos que las capacidades de cada buffer pueden variar entre 1 y 20 unidades lo que representa 20 pasos ya que los variaciones son discretas, se cuenta en total con 160,000 diferentes configuraciones para evaluar todo el espacio (sin réplica).
Para comprobar esto creamos un experimento tipo variación de parámetros y asignamos los siguientes valores (ver imagen).
Hacemos click en Create default UI para crear la interfaz. Luego añadimos 5 estadísticas locales (statComplete, statWIP, statCycleTime, statTotalTime, statDiffQ) en las cuales guardaremos el resultado de cada experimento así como tres histogramas (WIP, tiempo de ciclo y tiempo total).
En la sección indicando qué hacer luego de cada simulación (After simulation run) añadimos el siguiente código:
|
1 2 3 4 5 6 7 8 |
statComplete.add((double)root.sink.count()/(double)root.totalUnits*100); statWIP.add(root.statWIP.mean()); statCycleTime.add(root.statCycleTime.mean()); statTotalTime.add(root.totalTime); statDiffQ.add(root.statDiffQ.mean()); dataWIP.add(root.statWIP.mean()); dataCycleTime.add(root.statCycleTime.mean()); dataTotalTime.add(root.totalTime); |
Y finalmente ejecutamos el experimento (ver imagen inferior).
Como se puede observar ejecutar 160 mil experimentos tomó cerca de 8 minutos (478.1 segundos), y los estadísticos permiten establecer que:
Según se requiera se pueden crear experimentos específicos de optimización que arrojen la configuración indicada para por ejemplo minimizar el tiempo total de ciclo o minimizar el tiempo total de operación o minimizar el trabajo en proceso (otros post se dedicarán a la creación de experimentos de optimización).
A continuación explicaremos dos formas de realizar el muestreo de manera que el tiempo total de experimentación se reduzca.
Creamos un hipercubo latino utilizando R y transferimos estos valores a AnyLogic para ejecutar específicamente simulaciones de estas configuraciones.
En primer lugar creamos un nuevo experimento de tipo variación de parámetros. Esta vez no asignamos variabilidad a los parámetros de entrada (ver imagen). Creamos la interfaz haciendo click en Create default UI.
Un inconveniente que tiene esta técnica es que la cantidad de experimentos (dimensiones del cubo) son definidas a través de la cantidad de réplicas (o usando la forma libre), en este caso escogemos un total de 2000 experimentos para representar el espacio total de 160,000 (representando un 1.25% del total de la población).
A continuación cargamos la librería RCaller y la importamos al experimento. Así mismo definimos las acciones a realizar antes y después de cada simulación pasar los parámetros y capturar las estadísticas (ver imágen siguiente).
Al igual que en la variación de parámetros, en este experimentos creamos cinco estadísticos y tres histogramas.
Adicionalmente creamos tres variables: totalExperimentos (int), dimensions (int) e hypercube (int[][]). Finalmente creamos una función llamada getHyperCube con el siguiente código:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
try { RCaller caller = new RCaller(); RCode code = new RCode(); caller.setRscriptExecutable("C:/Program Files/Microsoft/MRO/R-3.2.4/bin/x64/Rscript.exe"); code.clear(); code.R_require("lhs"); code.addRCode("a<-randomLHS(" + dimensions + ", 4)"); code.addRCode("a<-round(a*15+1,0)"); caller.setRCode(code); caller.runAndReturnResult("a"); double[][] d = caller.getParser().getAsDoubleMatrix("a"); for(int i=0; i<dimensions; i++){ for(int j=0; j<4; j++){ hypercube[i][j]=(int)d[i][j]; } } } catch (Exception e) { System.out.println(e.toString()); } |
Esta función se ejecuta al inicio de toda la serie de experimentos para crear el hipercubo en R (utilizando el paquete lhs) e importarlo a AnyLogic para almacenarlo en la variable local hypercube. Este hypercubo en realidad es una matriz donde cada fila representa la configuración de los buffer de cada experimento a correr.
Al ejecutar el experimento encontramos:
Si bien las distribuciones no reflejan los mismos límites superiores e inferiores de la variación de parámetros anterior, los valores hallados se aproximan bastante, con un tiempo de simulación 23 veces inferior. Esta técnica es particularmente útil cuando se cuenta con capacidad limitada de computación y experimentos complejos donde el espectro completo puede tomar días enteros en ser simulado por tanto una muestra con resultados similares en menor tiempo es muy necesaria.
En este caso asumimos que solo deseamos simular las siguientes configuraciones:
En este caso el total de experimentos a realizar es 440 (11*4*1*10).
Creamos entonces un experimento tipo variación de parámetros de forma libre con 440 repeticiones (ver imagen) y añadimos un archivo de Excel donde hemos creado previamente las 440 configuraciones.
En las acciones antes y después creamos el siguiente código que permite leer el archivo de Excel y llenar la variable local hypercube con todas las configuraciones requeridas. Adicionalmente capturamos las estadísticas de rendimiento al finalizar cada experimento.
Ejecutamos el experimento.
Esta vez el experimento tomó solamente 2.3 segundos (sin repetición). El usuario puede repetir varias veces la matriz Excel y aumentar el número de experimentos en AnyLogic para añadir repeticiones.
El modelo soporte, la librería RCaller y el archivo Excel pueden ser descargados en el siguiente link.