viernes, 20 de abril de 2012

[MSDS] Sistemas Caóticos: Geografía Fractal

Un Sistema Caótico es un tipo de Sistema Dinámico . Los Sistemas Dinámicos son sistemas cuyo estado evoluciona con el tiempo.

El comportamiento en dicho estado se puede caracterizar determinando los límites del sistema, los elementos y sus relaciones; de esta forma se puede elaborar modelos que buscan representar la estructura del mismo sistema. Constan de ciertas condiciones iniciales las cuales fijan los estados subsecuentes del sistema.

Asi pues, un Sistema Dinamico se considera caotico cuando es muy sensible a las variaciones en las condiciones iniciales. Pequeñas variaciones en dichas condiciones iniciales pueden implicar grandes diferencias en el comportamiento futuro; complicando la predicción a largo plazo.

Sistemas Dinámicos y Teoría del Caos es la rama de las Matemáticas que trata acerca del comportamiento cualitativo a largo plazo de un sistema dinámico. No se trata de encontrar soluciones exactas a las ecuaciones que definen dicho sistema dinámico (lo cual suele ser imposible), sino más bien el poder contestar preguntas como "¿A largo plazo, se estabilizará el sistema? ¿Y si lo hace, cuáles serán los estados posibles?" o "¿Variará el estado a largo plazo del sistema, si cambian las condiciones iniciales?"

Una de las mayores características de un sistema inestable es que tiene una gran dependencia de las condiciones iniciales. Esto sucede aunque estos sistemas son en rigor determinísticos, es decir; su comportamiento puede ser completamente determinado conociendo sus condiciones iniciales. De un sistema del que se conocen sus ecuaciones características, y con unas condiciones iniciales fijas, se puede conocer exactamente su evolución en el tiempo. Pero en el caso de los sistemas caóticos, una mínima diferencia en esas condiciones hace que el sistema evolucione de manera totalmente distinta.

Geografía Fractal


Cuando observamos algún paisaje nunca nos detenemos a pensar en éste llego a tener tal forma. A grandes razgos, nos ponemos a pensar siempre en las fuerzas moldeadoras del planeta tales como el agua y aire (erosion), erupciones volcánicas, movimientos tectónicos, etcetera. Sin embargo, esas curvas graciosas que cubren nuestro planeta son el resultado de un equilibrio de una gran cantidad de variables.

Los relieves que rodean el planeta parecen no tener relación para muchos, sin embargo, cuando nos vamos alejando de la superficie podemos comenzar a notar cierto patron en dichos relieves, los cuales finalmente terminan teniendo un tamaño de kilometros, una forma bien definida y que parece tener cierto orden.

Canales de drenaje pluvial en una cordillera

Y dichas formas caprichosas son el resultado de la gran cantidad de energía que esta debajo de nosotros y que permanece en equilibrio, la cual se manifiesta mediante los terremotos. Las placas se tensan unas a otras, cuando la tensión en cierto momento alcanza un punto critico, esta es liberada, alterando a su vez el paisaje que la rodea y moldeándolo. Ejemplo son las montañas, islas y cordilleras. Podemos ver en las siguientes imágenes como, a pesar de tener formas irregulares a simple vista, en escalas mayores los relieves tienden a conservar un orden Fractal, el cual es mas obvio en las costas marítimas.



Un fractal es un objeto semigeométrico cuya estructura básica, fragmentada o irregular, se repite a diferentes escalas.

Asi por ejemplo: en un mapa mundial podemos ver islas de diferentes tamaños. Su distribución se rige por leyes potenciales rigen si tamaño y forma, por lo que nos encontramos de nuevo ante estructuras fractales. Mientras la distribución de los continentes e islas de gran tamaño son pocas, es muy alta la cantidad de islas y archipielagos.

Modelado de Relieves


El modelado computacional de relieves es un tema tanto sencillo, en su forma mas básica, la propiedad mas importante que necesita ser modelada es la elevación.

La forma más simple es generar una gradiente de grises aleatoriamente distribuida o de colores que después puede ser traducida cono un mapa de relieve o elevaciones para finalmente modelarse en 3D.

El método más utilizado es el llamado Perlin Noise. Este método genera una gradiente de ruido en grises la cual puede utilizarse para crear nubes, fuego o relieves.

Cuando se usa para crear relieves, las partes blancas son relieves altos, las partes negras son relieves bajos o por debajo del nivel del mar


Con este método primeramente se establece un estado inicial, que generalmente es un cuadrado cuyas esquinas tienen asignados valores aleatorios de elevación. Después el cuadrado comienza a subdividirse en cuatro, y a cada nuevo cuadrado se le han de calcular sus nuevas alturas siguiendo un patrón, por ejemplo:


Las elevaciones iniciales son valores generados al azar, los valores intermedios son calculados iterativamente y su computo depende total mente de las condiciones inciales.

Ejemplo del proceso (Wikipedia | Fractal Landscape)


Uno de los problemas del método consiste en que utilizaba solo cuadrados, lo que en la generación de graficas por computadora no es muy atractivo actualmente. El método se complemento con un paso intermedio que agrega en lugar de cuadrados, rombos o diamantes también. A este método se le llamo Diamond-square algorithm.
El beneficio que se obtiene es la generación de gradientes un poco mas naturales, pero no discontinuas, que proporcionan relieves mas realisticos.

Gradiente generada con Diamond Square Algorithm

Si vemos los gradientes asi como asi, se nos hacen aburridos, poco atractivos... lo bueno viene cuando son interpretados por un programa tal como Octave o Matlab, el resultado es algo como esto:


Este tipo de diseño de terrenos es llamado Fractal Landscape, su objetivo es la generación de paisajes naturales mediante fractales. Aunque los paisajes fractales parezcan naturales a primera vista, la exposición repetida puede defraudar a quienes esperen ver el efecto de la erosión en las montañas. La crítica principal es que los procesos fractales simples no reproducen (y quizás no puedan hacerlo) las funciones geológicas y climáticas reales.

Con algo de texturizado y sombreado nos queda un paisaje geográfico bastante real.


Generando Paisajes Fractales


Tuve poco tiempo, base mi código en un tutorial sobre este tema.
Recibe 2 parámetros, la cantidad de iteraciones y el segundo es el nivel de "evolución del terreno".

Básicamente el código lo que hace es crear una matriz de 2x2, y que solo tiene ceros, es decir, comenzamos con una zona flat (un cuadrado de cero altura en todos sus lados).

Después vamos a utilizar la función interp2 que lo que hace es agregarme los subelementos a la matriz, es decir, de 2x2 ahora hace una matriz 3x3, en la siguiente iteración me genera una matriz 5x5 y así sucesivamente según el numero de iteraciones. Entre mayor sea el número de iteraciones, mayor sera el detalle del paisaje, pero tardara mas en diseñarlo y plotearlo.

Despues marcamos solo los subelementos internos, es decir, una vez creado el cuadrado principal, lo subdividimos y descartamos los nodos viejos y solo seleccionamos los nuevos para trabajar con ellos.


Después calculamos un valor random, que sera la nueva altura que le sumaremos o restaremos a los nodos marcados, este se multiplica por el factor de cambio del terreno, valores pequeños ofrecen poco cambio, pero, debido a la dinámica del código esto no se cumple necesariamente.

Por último, dividimos el factor de cambio entre 2 para disminuir en cada iteración el factor de cambio y hacer todo un poco mas natural.

Código
Para la demostración, correré el código a 6 iteraciones (las cuales son suficientes) y una razón de cambio pequeña, de 0.1


Primera Iteración


Segunda Iteración


Tercera Iteración


Cuarta Iteración


Quinta Iteración


Sexta Iteración


Podemos ver como se genero un terreno fractal a partir de una zona completamente flat. Por medio de estos algoritmos podemos producir ambientes naturales bastante realistas y en poco tiempo. En mi caso no pude, creo que el poder de calculo de mi computadora se quedo corto, entonces, con mas de 8 iteraciones se congelaba Octave y había que matar el proceso.
Y este es el mapa de Perlin Noise utilizando Diamond-Square


Podemos también definir el nivel del mar del terreno, por ejemplo, con esta instrucción le digo que todo valor menor a cero lo iguale a cero, para que cero sea mi limite inferior y por consiguiente, mi nivel del mar:
octave> w = m;
octave> w(w < -0.01) = -0.01;
Después de correr el código otra vez y poner las líneas anteriores, este es el resultado (podemos ver la zona plana):


Bueno, quedo hasta aquí en el tema de geografía fractal, espero les sea de interés y utilidad.

Referencias

lunes, 2 de abril de 2012

[MSDS] Tarea 3 Pruebas estadísticas para los números pseudoaleatorios

El objetivo de esta tarea es determinar si los generadores de números pseudoaleatorios incluidos en las librerias de los diferentes lenguajes de programación se apegan a alguna distribución y si los mismos presentan las características deseables de los números pseudoaleatorios.

Herramientas

  • Lenguaje de Programación: Python
  • Libreria generadora de números pseudoaleatorios: random.normalvariate(0,1) (Normal Estándar)
  • Distribución a evaluar: Normal
  • Libreria de Pruebas Estadisticas: Scipy
  • Graficador: GNUPlot

1. ¿Los números generados de acoplan a la distribución indicada?


Para realizar esta prueba primero realice un código en Python que, con la ayuda de la libreria random, nos permite generar números pseudoaleatorios.
En mi caso voy a generar números pseudoaleatorios que se acoplen a la distribución normal utilizando la función random.randomvariate(0,1), como vemos, los parámetros serán 0 y 1, esto es, significancia = 0 y una desviación = 1, para seguir una normal estándar.
Por default se generan 10000 números, ya que hay que tener una muestra bastante grande; pero es posible enviar la cantidad como parámetro también.
Además se implementa una prueba de Anderson (scipy.stats.anderson), al generar los números, éstos se van almacenando en una lista, la lista se envía a la prueba Anderson para que los valores sean evaluados y se deteminará si la muestra proviene de una distribución específica (en éste caso, la distribución normal).

Código Python


Una vez que corremos el código, se generará un archivo llamado data.dat, éste contiene los números generados, lo que haré después es graficarlos. Pensé en hacer un código que implementara canastas, sin embargo, decidí dejar el trabajo a GNUPlot, con el siguiente código se generaran canastas de 0.1 unidades de ancho, leeremos el archivo data.dat e iremos creando un histograma de frecuencias.
Adicional a eso, implemente en el archivo de GNUPlot la función de densidad de probabilidad de la distribución normal para ver el acople de la distribución de los números generados y la forma original de la distribución normal. La formula es la siguiente:


Código GNUPlot


Gráfica


Fueron generados 1 000 000 de números, se acomodaron por canastas y formaron un histograma, si lo comparamos con la gráfica normal estandar (en rojo, con líneas) podemos ver que se acoplan casi perfectamente, tentativamente podemos deducir que efectivamente los números generados por random.randomvariate() si se acoplan a la distribución normal.

Prueba Anderson


Los resultados de la prueba Anderson para la muestra de 1 000 000 fueron:


Las hipótesis relacionadas no fueron rechazadas para todos los niveles de significancia, entonces podemos terminar de deducir que los números si se acoplan a la distribución normal.

2. ¿Los números generados presentan características deseables de "números aleatorios"?


Para las pruebas de aleatoriedad decidi basarme en la pagina random.org y leer un poco sobre los test, entonces me puse implementar 2 de ellos:

1. Frecuency Monobit

El propósito de esta prueba es calcular la proporción de ceros y unos en una muestra dada de números pseudoaleatorios.
Se espera que la proporción sea aproximadamente el mismo, es decir, que la proporción de unos dea 1/2 y la proporción de ceros también.

2. Frecuency Block

El enfoque de la prueba es calcular la proporción de unos en una muestra dada e números aleatorios, pero esta ves, la secuencia es dividida en bloques más pequeños y del mismo tamaño.
El propósito de este ensayo es determinar si la frecuencia de unos en un bloque de M-bits es de aproximadamente M / 2, como sería espera que en el supuesto de aleatoriedad.

Código


Ésta es la implementación de las pruebas, para hacerlo un poco más equilibrado, decidí comparar 2 muestras diferentes de 10000 números pseudoaleatorios cada una. La primera es generada con random.normalvariate() redondeando algunos valores y aplicando algunas condiciones para obtener valores binarios 0 y 1. La segunda es generada con random.randint() poniendo como limites 0 y 1 obviamente.
Después ambas listas se envían a evaluar, primero por Frecuency Monobit y después por Frecuency Block:


Los resultados de las pruebas para ambas listas fueron:



Podemos ver como para la lista generada por random.normalvariate() la proporción es 1, podemos deducir que la probabilidad entre ceros y unos es idéntica, por lo que se trata de una librería que cumple con los estándares para la generación de números aleatorios. No sorprende que haya pasado ambas pruebas.
No podemos decir lo mismo de la librería random.randint() cuya proporción es bastante baja comparada con la anterior. Podemos ver que cumple con los estándares de la prueba monobit, pero la prueba de bloques fue un fracaso total, entonces es 50% menos confiable que la random.normalvariate() además del umbral que las separa a las dos por la prueba monobit.

Referencias