Practica#3 Arte con Fractales (Presentacion) PARTE 2

Practica#3 Arte con Fractales PARTE 2 (Resumen)

El código que hemos investigado para hacer un fractal en forma de triángulo esta echo en lenguaje java, las librerías que se utilizan son las:  import java.applet.Applet;  e  import java.awt.Graphics.

El código está destinado a realizar el triángulo Sierpinski, el cual es un triángulo grande en el que se generara un triángulo justo en medio de este comenzando a generar más a sus lados con el mismo principio, todo esto será controlado por la variable de recursividad.

La parte más importante del código es la función “PaintRecursivo” ya que en esta podemos encontrar todas las formulas y la condición que permitirá realizar los vértices de los triángulos y pintara la figura autollamandose 3 veces para hacer los subtriangulos.

Hay infinidad de tutoriales para crear fractales y una de esas maneras es el editado de imágenes, esta forma llamo mi atención ya que anterior mente tenido cursos de editado de imágenes en photoshop pero no me enseñaron este concepto y es muy interesante como mediante la repetición de figuras de diferentes tamaños se pueden crear imágenes asombrosas.

Otra forma de crear fractales es con pintura al dibujar figuras de diferentes tamaños  y/o esculpiéndolas, el cual es uno de los métodos que más me han impresionado ya que es más difícil que solo editar una imagen;  algunos artistas para tener más profesionalismo y utiliza un programa generador de fractales y los moldea o mescla como ellos quieren quede su obra para darle un toque más personal. Aquí se anexa un video de la ex poción de fractales en buenos aires.

Practica #4 Robocup PARTE 2 (Resumen)

Para poder instalar la plataforma de simulación 2D de Robocup es necesario tener alguna versión de Linux instalada. Una vez ya instalada procedemos a instalar el simulador, para esto necesitaremos tener todos los repositorios actualizados e instalar los paquetes: rcssserver, rcsoccersim y rcssmonitor también descargar e instalar JDK6, NetBeans 7.1 y ATAN v0.4.3, como solo tenemos instalado el simulador pero no podemos hacer nada si no le cargamos algún programa para que simule. Para esto nos sirve la interfaz ATAN que ya tiene programada toda la parte de comunicación entre servidor y clientes, para simplemente programar nuestros equipos y ejecutar la simulación. También NetBeans para poder arrancar el programa. Para ejecutar el programa de prueba abrimos el NetBeans y creamos un nuevo proyecto (lo pueden llamar como gusten), debemos cargar a nuestro proyecto las librerías necesarias para la interfaz ATAN,que se encuentran en: “atan.jar” “atan_0.4.3 “ y “log4j-1.2.16.jar” una vez que tenemos cargadas todas las librerías necesarias, solo debemos importar el paquete simple y escribir dentro del método main las siguientes líneas: “Simple1Run.main(args);” y “Simple2Run.main(args);” que representan a los dos equipos que se simularan. Por ultimo lo que queda hacer es ejecutar el simulador con el comando “rcsoccersim” y regresar a la pantalla de simulación donde seleccionaremos la opción Kick_off y empezara el juego. 

Practica#4 Robocup PARTE 1 (Resumen)

Al equipo nos toco exponer el tema de Arte con Fractales por lo que nos toco hacer el resumen de la practica #4 que es Robocup

¿Que es Robocup?

Es una iniciativa científica (1997) que tiene el objetivo de avanzar en el ámbito de los robots inteligentes,

RoboCup es una iniciativa científica internacional con el objetivo de avanzar en el ámbito de los robots inteligentes. Busca promover a través de competencias integradas por robots autónomos.

Objetivo y categorías

Como ya se menciono se busca promover la competencia , el  primer objetivo que se tenia era que los robots fueran capaces de ganar a los campeones de fútbol mexicano, pero los objetivos se han ampliado como en:

• RoboCupSoccer : Creación de equipos formados por robots totalmente autónomos  cooperativos capaces de  implementar estrategias
• RoboCupRescue : Ayudar a las personas como por ejemplo protección civil para salvar así a las personas que se encuentren en peligro.
• RoboCup @ Home :  Ayudar a las personas en su vida cotidiana.
• RoboCupJunior :  Busca motivar a los jóvenes a aprender habilidad y conocimientos.

Liga de Simulación de soccer 2D por computadora

Simula a dos equipos de soccer los cuales son simulados por una computadora

Practica#3 Arte con Fractales PARTE 1(Resumen)

¿Que es un fractal?

El concepto de fractal fue desarollado por el experto en matematicas Benoit Mandelbrot que fue el responsable de desarrollar en 1975. 

Un fractal es una figura, que puede ser espacial o plana, formada por componentes infinitos. Su principal característica es que su apariencia y la manera en que se distribuye estadísticamente no varía aun cuando se modifique la escala empleada en la observación.
Son calificados como semi geométricos (por su irregularidad no pertenecen a la geometría tradicional).

¿Que se puede hacer con fractales?

Los fractales son utilizados en diferentes ciencias como :

•Comunicaciones : modelado del trafico de redes
•Informática : técnicas de comprensión (audio y video)
•Robótica : robots fractales
•Infografía: paisajes fractales y otros objetos
•Biología : crecimiento tejido, organización celular evaluación de poblaciones depredador-presa
•Matemáticas: convergencia de métodos numéricos
•Música: composición musical
•Física: transiciones de fase en magnetismo
•Química: Agregación por difusión limitada (DLA)
•Geología: Análisis de patrones sísmicos, fenómenos de erosión y modelos de formaciones geológicas
•Economía : Análisis bursátil y mercado

Arte: Esta imagen fue creada apartir de fractales es una tormenta.

Con los fractales tambien podemos simular los formaciones de la naturaleza en este caso las hojas.

¿Como se ve una imagen creada con fractales?

Las imagenes creadas con fractales estan compuestas por  un objeto de el mismo, pero en diferentes tamaños.
Algunos de los ejemplos mas conocidos son : El triangulo de Sierpinski y Mandelbrot. Existen muchos otros ejemplos con fractales que son realmente llamativos y sorprendentes.

Triangulo de Sierpinski

 Mandelbrot

Herramientas para crear fractales

1.Turtle Graphics Render:  Herramienta en línea para crear fractales con formulas.
2. ChaosPro: Software que realiza fractales tanto en 2D y 3D para uso Windows
3.GIMP: Software gratuito para edición y creación de imágenes.
4. Fractint: Software libre para PC de IBM y ciertas con capacidad de hacer fractales.
5.GNU XaoS: Software que permite analizar los fractales haciendo acercamientos.
6. Apophysis: Software que te permite editar las llamas fractales de funciones interadas.
7.Mandelbulber: Software con la misma función que el Apophysis pero aun en desarrollo.

Referencias

•Defincion.de. (s.f.). Fractal. Obtenido de Definicion.de: http://definicion.de/fractal/

•Increible Seattle Fractals. (2012). fractal programas y generadores de software. Obtenido de Increible Seattle Fractals: http://fractalarts.com/ASF/download.html

•Wikipedia. (23 de octubre de 2013). Fractal. Obtenido de Wikipedia: http://es.wikipedia.org/wiki/Fractal

•xatakaciencia. (02 de marzo de 2012). ¿Qué son los fractales y cómo se construyen? Obtenido de xatakaciencia: http://www.xatakaciencia.com/matematicas/que-son-los-fractales-y-como-se-construyen

Practica #3 Arte con fractales (presentación) PARTE 1

En esta practica #3 realizamos una presentación del tema, a continuación dejamos dicha presentación y mas adelante se subirá un resumen del mismo. 

Practica #2 : K-means

Introducción

Un agrupamiento consiste en formar grupos de elementos con características en común (similitud), de tal forma que se podría decir que se analiza un elemento para determinar si pertenece o no a un grupo. Los grupos que obtendremos de los agrupamientos deben ser todos sus elementos parecidos de tal forma que todos elementos que conformen el grupo deberán ser similares.

En esta entrada realizaremos un algoritmo de agrupamiento denominado K-means el cual como ya mencionamos consiste en agrupar vectores por su similitud con los centroides (grupos). El contexto con el cual trabajaremos K-means sera determinar si una persona es apta o no es apta para realizar un trabajo.

En esta entrada podrás encontrar:

• Marco teórico - Contendrá información acerca del tema.
• Desarrollo- Contendrá la programación de las funciones mas importantes y una explicación detallada de nuestro caso de estudio.
• Resultados
• Conclusiones
• Referencias

Marco Teórico

Un agrupamiento consiste en formar grupos de elementos, donde estos elementos deberán ser similares. Los grupos que se formen de este proceso deberán ser todos sus elementos parecidos(similares) de tal forma que el grupo no tendrá elementos que no seas similares.

Existen diferentes tipos de grupos que se pueden generar por ejemplo:

• Partición: Busca grupos y estos grupos son representados por objetos (centroides), donde calculamos la similitud y asignamos los grupos.

• Traslape : El algoritmo actualiza el agrupamiento.

• Jerarquico: Agrupa y forma nuevos elementos , separando los grupos ya formados, para asi poder originar otros.

• Difuso: Permite que un elemento quede en mas e un grupo

Un vector de características es aquel que contiene la información de un elemento en este caso como dice su nombre sus características, las cuales nos servirán para comparar mas adelante con las características de los centroides (los grupos) y así determinar a que grupo pertenece cada elemento.

Para calcular la similitud (distancia) entre vectores veremos 3 formas:

• Distancia Euclidiana : Es el espacio entre dos puntos 

donde:
Pn = características del vector que se esta analizando

Qn= características del centroide que se esta analizando.

• Indice de Jaccard : Comparación de dos elementos para determinar si son parecidos o no.

c/a+b+c

donde:

a = numero de características del vector que se esta analizando

b= numero de características del centroide.

c= La suma total de todas las características.

• Cosenoidal: Compara los elementos para determinar la similitud , calculando el coseno del angulo entre los vectores.

cos( Vdx, Vdy) = Vdx < Vdy / ||Vdx|| ||Vdy||

donde:
Vdx < Vdy  = Se obtiene el angulo entre un par de vectores
||Vdx|| ||Vdy|| = se obtiene la norma de cada vector.

K-means es un algoritmo de agrupamiento el cual consiste en tener un numero n de vectores a comparar con un numero n de centroides (grupos) y a partir de esa comparación obtener la similitud para así sabrá a que grupo pertenece el vector.

A continuación un ejemplo de K-means :

Vectores	Centroides
P1 (12,5)	C1 = (4.2, 1.5)
P2 (5,6)	C2 = (1.5 , 4)
P3 (4,2)
P4 (1,4)
P5 (6,3)
P6 (9,6)

Cálculos para la distancia:

P(1,C1) = ((12-4.2)² + (5-1.5)²)^1/2 =  8.54

 P(1,C2) = ((12-1.5)² + (5-4)²)^1/2 =  10.54

P(2,C1) = ((5-4.2)² + (6-1.5)²)^1/2 =  4.57

P(2,C2) = ((5-1.5)² + (6-4)²)^1/2 =  4.03

P(3,C1) = ((4-4.2)² + (2-1.5)²)^1/2 =  0.53

 P(3,C2) = ((4-1.5)² + (2-4)²)^1/2 =  3.30

P(4,C1) = ((1-4.2)² + (4-1.5)²)^1/2 =  4.06

P(4,C2) = ((1-1.5)² + (4-4)²)^1/2 =  0.5

P(5,C1) = ((6-4.2)² + (3-1.5)²)^1/2 =  2.34

 P(5,C2) = ((6-1.5)² + (3-4)²)^1/2 =  4.60

P(6,C1) = ((9-4.2)² + (6-1.5)²)^1/2 =  6.57

P(6,C2) = ((9-1.5)² + (6-4)²)^1/2 =  7.76

P(n,C)	C1	C2
12,5	8.54	10.54
5,6	4.57	4.03
4,2	.53	3.30
1,4	4.06	.5
6,3	2.34	4.60
9,6	6.57	7.76

C1	C2
12,5	5,6
4,2	1,4
6,3
9,6

Actualizar centroides:

C1(x) = (12+4+6+9)/4 = 7.75

C1 (y) = (5+2+3+6)/4 = 4

C1 = (7.75 , 4)

C2(x) = (5+1)/2 =3

C2(y) = (6+4) /2 = 5

C2 = (3,5)

Desarrollo

Nuestro contexto de agrupamiento consiste en agrupar a un grupo de personas para determinar si son aptos o no para un trabajo.

Nuestros vectores de características se realizaron a partir de una serie de preguntas donde las respuestas podían ser "si o no", donde si es 1 y 0 es no.

1.       ¿Cuenta con un título?

2.       ¿Cuenta con maestría?

3.       ¿Cuenta con doctorado?

4.       ¿Tiene experiencia?

5.       ¿Tiene disponibilidad de tiempo?

6.       ¿Vive cerca?

7.       ¿Ha trabajado en esta área?

1 =  Si                    0= No

Individuo	Preg.1	Preg.2	Preg.3	Preg.4	Preg.5	Preg.6	Preg.7
1	1	1	1	0	1	0	0
2	1	1	0	1	1	0	1
3	1	0	0	1	1	1	1
4	0	0	0	0	1	1	0
5	1	0	0	1	1	0	1

El equipo opto por utilizar la distancia euclidiana para calcular la similitud, por que es la que nos pareció mas sencilla y es con la que mas trabajamos en clase.

A continuación mostraremos algunos fragmentos de código:

Generación de centroides

Nosotros generamos los centroides asignándole nosotros mismos valores estáticos y los pusimos dentro de un arreglo.

C1 = 1111111

C2 = 0000000

Calculo de similitud entre vectores

Utilizamos la formula de la distancia euclidiana y al final imprimimos los valores para cada uno de los vectores con cada uno de los centroides.

Asignación de grupos

Aquí a través de unos if comparamos cada uno de los resultados obtenidos en el calculo de la distancia euclidiana y seleccionar el menor de estos.

Actualización de los centroides

Como se puede observar actualizamos los valores de arreglo donde guardamos los centroides, sumando los valores de cada una de las características de cada vector.

Si deseas descargar el código completo  haz Click aqui

Resultados

Parámetros

Núm. K (grupos)	2 (aptos y no aptos)
Núm. De Interacciónes	1

El criterio de terminación sucede cuando todos los vectores han sido agrupados y se calcula la actualización de los centroides.

Nota: Ya que es un grupo pequeño y los valores del vector son únicamente 1 y 0, no es necesario hacer demasiadas interacciones.

Los mejores grupos encontrados fueron :

C1 (apto)

1110100

1101101

1001111

1001101

C2 (no apto)

0000110

los resultados son algo predecibles ya que a simple vista podemos agrupar los vectores, por lo mismo solo se realizo una Interacción.

Conclusión

K-means es un método de agrupamiento muy fácil de implementar y sobre todo muy útil por ejemplo para agrupar correos o en una empresa agrupar piezas, entre muchas otras cosas mas.

El algoritmo se puede complicar cuando hay muchos vectores a agrupar, ya que se requiere un numero mayor de cálculos y mas interacciones.

Esperamos que esta entrada pueda ser de gran utilidad.

Referencias

Garza, S. E. (15 de octubre de 2013). Similitud Cosenoidal. Obtenido de elisa.dyndns: http://elisa.dyndns-web.com/saraelena/material/sistadap/cosim.pdf

Rojas, J. C., & Ponce Medellin, I. R. (s.f.). Programacion del algorito de agrupamiento K-means en SQL. Recuperado el 20 de 10 de 2013, de CENIDET: dsc.itmorelia.edu.mx/~jcolivares/documents/kmeanSQL.doc‎

Wikipedia. (7 de septiembre de 2013). Distancia Euclidiana. Obtenido de Wikipedia: http://es.wikipedia.org/wiki/Distancia_euclidiana

Wikipedia. (5 de marzo de 2013). Indice de Jaccard. Obtenido de Wikipedia.

Practica #1 ACO

Introducción

El problema del viajero (TSP) consiste en una especie de grafo o mapa la cual tiene diferentes  vértices, los cuales tenemos que recorrer pasando por cada uno de ellos, con el menor costo posible. El problema del viajero es importante ya que con el podemos ver los diferentes posibilidades de resolver un problema y darnos cuenta que hay maneras mas eficientes para llegar a la "meta", algunas aplicaciones que podría tener seria en las búsquedas de información encontrar el camino mas corto para llegar a la información deseada, para los mapas digitales que permiten encontrar la ruta mas rápida de llegar a cierto punto, entre otros mas.

El problema del viajero puede resultar tedioso ya que si hay muchos vértices hay muchos mas caminos que recorrer y soluciones, esto hace que el problema se vuelva mas largo.

El algoritmo de ACO es un algoritmo un tanto complejo, que permite encontrar la mejor ruta para llegar a la meta, el problema de  ACO es una colonia de hormigas  en la cual una hormiga va buscando el mejor camino y a la vez deja una feromona para que las demás hormigas sigan su camino.

ACO puede utilizarse para resolver el problema del viajero por que al igual que las hormigas van recorriendo los caminos para encontrar una solución optima.

En esta entrada vas a poder encontrar:

• Marco Teórico contiene una explicación de el problema del viajero y de ACO. Así mismo se incluye un ejemplo de fuerza bruta.
• Desarrollo contiene la información mas relevante de como se elaboro el algoritmo en el se incluyen códigos y capturas de pantalla.
• Resultados
• Conclusiones
• Referencias 

Marco Teórico

El problema del viajero (TSP) es  un un tipo de problema de complejidad NP-completo. El problema del viajero consiste en recorrer todas las ciudades pasando una vez por cada una de ellas y volver donde inicio el recorrido, en el menor costo y tiempo posible.

Usa una estructura de datos de vecindad y heuristicas simples, también se utilizan métodos de búsqueda local. Se realiza una instancia.

La instancia de este problema consiste en dar un grafo donde cada vértice es una ciudad y las aristas son los caminos los cuales tienen cierto peso (que es el costo) el numero de vértices varia según el caso, en el caso de programación se utiliza una matriz la cual contiene números que representan los costos del recorrido.

Este problema se puede resolver por fuerza bruta pero no es muy recomendable, ya que se tiene una instancia se sacan todas las posibles soluciones del problema sumando los costos de cada camino y el resultado mas pequeño es el camino mas corto.

Aquí dejamos un ejemplo:

Instrucciones: Resolver el ejercicio por fuerza bruta. 

Reglas: Pasar por las 4 ciudades (A,B,C,D) solo una vez y volver a la ciudad de inicio, con el menor costo posible.

Respuestas:

Estas son todas las posibles soluciones:

A,B,C,D 4+2+5=11
A,B,D,C 4+6+5=15
A,C,D,B 1+5+6=12 
A,C,B,D 1+2+6=9
A,D,C,B 2+5+2=9
A,D,B,C 3+6+2=11

B,A,C,D 4+1+5=10
B,A,D,C 4+3+5=12
B,D,C,A 6+5+1=12
B,D,A,C 6+2+1=8
B,C,A,D 2+1+3=6
B,C,D,A 3+5+3=11

C,A,B,D 1+4+6=11
C,A,D,B 1+3+6=10
C,B,D,A 2+6+3=11
C,B,A,D 2+4+3=9
C,D,A,B 5+3+4=12
C,D,B,A 5+6+4=15

D,A,B,C 3+4+2=9
D,A,C,B 3+1+2=6
D,B,A,C 6+4+1=11
D,B,C,A 6+2+1=9
D,C,A,B 5+1+4=10
D,C,B,A 5+2+4=11

Como se puede observar hay dos caminos cortos con un costo de 6.

ACO significa Ant Colony Optimization que en español significa optimización de colonia de hormigas. ACO se basa en el compartimiento de las hormigas para resolver problemas de optimización y búsqueda  Es también metahuristico ya que se utiliza para buscar soluciones.

ACO fue propuesto en 1991 por Dorigo Etal

El proceso que sigue ACO es el siguiente:

pseudocódigo

1. Inicio 
2. Inicio de parámetros
3. if (condición del Fin)
4. Búsqueda de soluciones
5. búsqueda local
6. actualización de una feromona
7. else (fin)

Las formulas mas importantes para resolver este algoritmo son las siguientes:

• Proceso de decisión (selección de arista)
  

donde:

pi,a es la probabilidad de escoger la rama a estando en el 

punto de decisión i, y

„τi,a es la concentración de feromona en la rama a

• Actualización de la feromona

Txy = es la cantidad de feromonas depositadas para un estado de transición xy

p= es el coeficiente de evaporación de las feromonas.

Desarrollo

La manera en que resolvimos el problema del viajero fue la siguiente:

Creamos una instancia del problema por medio de una matriz donde los datos (números) de la matriz son los "costos" de los caminos segun sea el caso.

Se crea una condición principal la cual determina el final del programa y del ciclo. En esta condición las hormigas buscan el mejor camino (el mas optimo) para su recorrido.

Se hace una búsqueda de las diversas soluciones, en ella las hormigas buscan todos los caminos posibles de una forma probabilista tomando con mayor probabilidad el camino que mas feromonas tenga.

Se realiza una búsqueda local de soluciones, en esta las hormigas buscan el mejor camino que este mas cerca en los cuales se encuentre una mayor cantidad de feromona, indicando que por ahí pasaron mas hormigas recientemente.

Por ultimo se actualizaran los parámetros  en este paso las hormigas se impregnan mas de feromona o se evapora ya que no utilizan el camino.

A continuación se muestran algunos fragmentos de código de algunas de las funciones de ACO

•  Genera instancias

• Actualización de feromona

•  Selección de aristas 

A continuación generaremos dos instancias una para 4 ciudades y otra 10 ciudades.

Parámetros de ACO

En esta parte realizamos varias iteraciones y reportaremos algunos datos relevantes.

	Numero de Hormigas	Tasa de evaporación	Cantidad de feromona depositada (Q)	Influencia de la feromona( ɑ)	Influencia del nodo( β)
Instancia 1 (4 ciudades)	4	.01	2.00	3	2
Instancia 2 (10 ciudades)	4	.01	2.00	3	2

Resultados

Como se puede observar en la siguiente iteración el numero de ciudades es 4, se utilizaron 4 hormigas y el camino mas corto fue de 13.

 En esta segunda iteración se realizo con 10 ciudades y 4 hormigas, el camino mas corto fue de 20

Conclusión:

Aunque el algoritmo se nos hizo algo tedioso, mas que nada por el lenguaje y al dificultad de las formulas, es un algoritmo muy útil y practico para encontrar soluciones optimas.

REFERENCIAS

Tarapacá, U. d. (2013). Aplicación de un algoritmo ACO al problema de taller de flujo de permutación con tiempos de preparación dependientes de la secuencia y minimización de makespan. Obtenido de Ingeniare. Revista chilena de Ingenieria: http://www.scielo.cl/scielo.php?pid=S0718-33052011000200010&script=sci_arttext

Cordon, O. (s.f.). Sistemas complejos, algoritmos evolutivos y bioinspirados. Obtenido de http://sci2s.ugr.es/seminars/5/Curso%20Baeza%20Oscar.pdf

Diaz, J. C. (s.f.). Una hiperheurística para la solución del Problema del Viajante Asimétrico . Obtenido de Monografias: http://www.monografias.com/trabajos35/viajante-asimetrico/viajante-asimetrico.shtml

Mora, A. (28 de noviembre de 2011). Optimizacion basada en colonias de hormigas. Obtenido de SildesHare: http://www.slideshare.net/Slidemora/optimizacin-basada-en-colonias-de-hormigas

Wikipedia. (20 de junio de 2013). Algoritmo colonia de hormigas. Obtenido de Wikipedia: http://es.wikipedia.org/wiki/Algoritmo_colonia_de_hormigas

Wikipedia. (4 de abril de 2013). Problema del viajante. Obtenido de Wikipedia: http://es.wikipedia.org/wiki/Problema_del_viajante