Hola este es el video de esta fase
Showing posts with label 1-Vic. Show all posts
Showing posts with label 1-Vic. Show all posts
Monday, March 23, 2009
Kawabonga! Fase 3
Breve descripción del medio ambiente
Breve descripción del problema de optimización.
Raíz((Rata#1 - Rata#2)2 + (Pillo#1 - Pillo#2)2 + (Vago#1 - Vago#2)2)
Raíz((13 - 5)2 + (2 - 11)2 + (2-5)2)
Raíz(64 + 81 + 9)
Raíz(154)
12.409
1/(1+12.409)
0.07457
Solución planteada al problema utilizando la técnica de Algoritmos Genéticos. Describe con detalle cada elemento del planteamiento.
Codificación del cromosoma.
Función a minimizar o maximizar. ¿Cómo se calcula?
f(x) = Suma(Función de similaridad (Mostrada arriba))
Forma de hacer la reproducción.
Forma de hacer el crossover
Forma de hacer la mutación
Dado p = 0.15 y un número r aleatorio entre 0 y 1, si r <>
Ejemplo de una generación de 4 elementos en la población
para el blog F
Conclusiones después de la programación
El Internet es un sistema global de redes interconectadas que intercambian datos.
El ambiente en particular son los blogs que son web escritas en [x]HTML y que utilizan el protocolo HTTP para transferir datos de una computadora llamada Servidor a otra llamada cliente.
El ambiente en particular son los blogs que son web escritas en [x]HTML y que utilizan el protocolo HTTP para transferir datos de una computadora llamada Servidor a otra llamada cliente.
Breve descripción del problema de optimización.
Se tiene una cantidad M de blogs inedexada.
Se selecciona un blog y se pretende encontrar el número N de blogs más parecidos.
La similaridad f(x) entre dos blogs queda definida de la siguiente manera:
Se selecciona un blog y se pretende encontrar el número N de blogs más parecidos.
La similaridad f(x) entre dos blogs queda definida de la siguiente manera:
| Blog | Rata | Pillo | Vago |
|---|---|---|---|
| Blog #1 | 13 | 2 | 2 |
| Blog #2 | 5 | 11 | 5 |
Se calcula la distancia euclideana de ambos blogs de acuerdo a la cantidad de veces que se repitan las palabras en cada uno de ellos.
Raíz((Rata#1 - Rata#2)2 + (Pillo#1 - Pillo#2)2 + (Vago#1 - Vago#2)2)
Raíz((13 - 5)2 + (2 - 11)2 + (2-5)2)
Raíz(64 + 81 + 9)
Raíz(154)
12.409
Se realiza una conversión del número, utilizando 1/(1+resultado)
1/(1+12.409)
0.07457
Al tener un resultado de 0 a 1, donde 0 significa que dos blogs no tienen nada en común, y 1 significa que dos blogs son idénticos, el propósito es encontrar un numero N de blogs que sean más parecidos un blog en específico.
Solución planteada al problema utilizando la técnica de Algoritmos Genéticos. Describe con detalle cada elemento del planteamiento.
Se elige Nb: El numero de blogs que contiene un individuo, cada individuo puede estar compuesto por dos o más blogs.
Se elige P: El tamaño de la población inicial.
Se selecciona un blog y se pretende encontrar el número N de blogs más parecidos. Donde N tiene que ser igual a Nb x P.
Se elige P: El tamaño de la población inicial.
Se selecciona un blog y se pretende encontrar el número N de blogs más parecidos. Donde N tiene que ser igual a Nb x P.
Codificación del cromosoma.
Un cromosoma o individuo puede estar compuesto por 2 o más blogs. Sea N una población de blogs y X,Y,Z,A,B,C blogs en N.
Algunos ejemplos son:
Algunos ejemplos son:
[X,Y,Z]
[A,B,C]
[X,B,Z]
[C,X,A]
[A,B,C]
[X,B,Z]
[C,X,A]
Función a minimizar o maximizar. ¿Cómo se calcula?
f(x) = Suma(Función de similaridad (Mostrada arriba))
Forma de hacer la reproducción.
Remainder stochastic sampling without replacement
Pselect = f(i)/suma(f)
Expected Count = parte entera de [Pselect*n] + "lanzamientos de monedas" con pesos iguales al residuo de [Pselect*n]
Pselect = f(i)/suma(f)
Expected Count = parte entera de [Pselect*n] + "lanzamientos de monedas" con pesos iguales al residuo de [Pselect*n]
Forma de hacer el crossover
Las parejas son elegidas de forma aleatoria.
El punto de cruce es elegido de forma aleatoria.
El punto de cruce es elegido de forma aleatoria.
Forma de hacer la mutación
Dado p = 0.15 y un número r aleatorio entre 0 y 1, si r <>
Ejemplo de una generación de 4 elementos en la población
para el blog F
| Individuo | f(x) | Pselect | Expected | Blogs to cross | Pair /cross point | New Generation |
| [X,Y,Z] | 1.5 | 0.375 | 0+1 | [X,Y,Z] | 4 / 2 | [X,Y,D] |
| [A,B,C] | 1 | 0.25 | 0+1 | [A,B,C] | 3 / 1 | [A,X,D] |
| [D,B,Z] | .5 | 0.125 | 0+0 | [E,X,D] | 2 / 1 | [E,B,C] |
| [E,X,D] | 2 | 0.5 | 0+2 | [E,X,D] | 1 / 2 | [E,X,Z] |
Conclusiones después de la programación
Después de haberlo programado llegamos a la conclusión de que la "dificultad" del algoritmo no radica en la programación (está parte resultó muy sencilla) sino en todo el proceso de diseño. Definir el problema, el formato del cromosoma, crossover, mutación, etcétera, porque si estos no son correctamente definidos, las soluciones a las que llega son erróneas.
Friday, February 27, 2009
Kawabonga! Parte 2
a. Breve descripción del medio ambiente.
El Internet es un sistema global de redes interconectadas que intercambian datos.
El ambiente en particular son los blogs que son web escritas en (x)HTML y que utilizan el protocolo HTTP para transferir datos de una computadora llamada Servidor a otra llamada cliente.
b. Breve descripción del problema de optimización
Dado un de blog y una cantidad M de blogs que podemos elegir para categorizar, encontrar los N blogs más parecidos al blog dado.
La distancia entre estos dos blogs será calculada como una distancia euclidiana a partir del número de palabras iguales que poseen.
Una vez que se tiene la distancia, la convertimos en un numero entre 0 y 1.
Al tener un resultado de 0 a 1 tenemos que 0 significa que dos blogs no tienen nada en común, y 1 quiere decir que dos blogs son idénticos, por lo que para encontrar los blogs más parecidos tendremos que maximizar el resultado.
c. Solución planteada al problema utilizando el método de recocido simulado.
1. Configuración
Una lista de N Elementos [E1,E2...En]
Cada elemento es una tupla de la forma (calificación, url_del_blog)
2. Re-ordenamientos
Se cambia el elemento con calificación menor por otro blog seleccionado al azar
3. Función objetivo
La función objetivo es la distancia (D)
f(x) = 1/(1+D)
D=Raíz(Suma((palabrai1-palabrai2)^2)) para i=[0,n]
4. Calendario de recocido
Temperatura Inicial = 1.0
Temperatura Final = 0.1x10^-6
Alpha = 0.9999
K = 2 (Número de iteraciones para cada temperatura)
e. Conclusiones después de la programación
Después de haber realizado la programación y haber llevado a cabo algunas corridas de prueba, concluimos que la eficiencia del algoritmo (al ser comparado con otros) depende en gran medida del espacio de búsqueda, ya que para espacios pequeños la implementación de 'brute force' es más sencilla e igual de útil. Sin embargo conforme ampliamos el espacio de búsqueda, las ventajas del recocido simulado se fueron haciendo más visibles.
El Internet es un sistema global de redes interconectadas que intercambian datos.
El ambiente en particular son los blogs que son web escritas en (x)HTML y que utilizan el protocolo HTTP para transferir datos de una computadora llamada Servidor a otra llamada cliente.
b. Breve descripción del problema de optimización
Dado un de blog y una cantidad M de blogs que podemos elegir para categorizar, encontrar los N blogs más parecidos al blog dado.
La distancia entre estos dos blogs será calculada como una distancia euclidiana a partir del número de palabras iguales que poseen.
Una vez que se tiene la distancia, la convertimos en un numero entre 0 y 1.
Al tener un resultado de 0 a 1 tenemos que 0 significa que dos blogs no tienen nada en común, y 1 quiere decir que dos blogs son idénticos, por lo que para encontrar los blogs más parecidos tendremos que maximizar el resultado.
c. Solución planteada al problema utilizando el método de recocido simulado.
1. Configuración
Una lista de N Elementos [E1,E2...En]
Cada elemento es una tupla de la forma (calificación, url_del_blog)
2. Re-ordenamientos
Se cambia el elemento con calificación menor por otro blog seleccionado al azar
3. Función objetivo
La función objetivo es la distancia (D)
f(x) = 1/(1+D)
D=Raíz(Suma((palabrai1-palabrai2)^2)) para i=[0,n]
4. Calendario de recocido
Temperatura Inicial = 1.0
Temperatura Final = 0.1x10^-6
Alpha = 0.9999
K = 2 (Número de iteraciones para cada temperatura)
e. Conclusiones después de la programación
Después de haber realizado la programación y haber llevado a cabo algunas corridas de prueba, concluimos que la eficiencia del algoritmo (al ser comparado con otros) depende en gran medida del espacio de búsqueda, ya que para espacios pequeños la implementación de 'brute force' es más sencilla e igual de útil. Sin embargo conforme ampliamos el espacio de búsqueda, las ventajas del recocido simulado se fueron haciendo más visibles.
Friday, January 30, 2009
Web Crawler + Applicacion Web
Un web crawler es un programa que navega de manera automática y sistemática por las páginas web, con el fin mostrar una relación entre palabras y URLs.
- Descripción detallada del medio ambiente.
El Internet es un sistema global de redes interconectadas que intercambian datos.
El ambiente en particular son lás páginas web escritas en (x)HTML y que utilizan el protocolo HTTP para transferir datos de una computadora llamada Servidor a otra llamada cliente. - Plataforma en la que se programara el medio ambiente y lenguaje de programación a ser utilizado.
Utilizaremos Python para hacer los prototipos del Web Crawler debido a que es un lenguaje que permite representar de manera sencilla los algoritmos además de contar con un gran numero de librerías y herramientas que facilitan la programación, como lo son avanzados profilers y debuggers.
Para la aplicación tenemos pensado utilizar LAMP (Linux, Apache, MySQL y P*) para hacer la aplicación que presentara los resultados y hará las búsquedas en las bases de datos. - ¿Cuáles problemas de optimización se encuentran en dicho medio?
Maximizar la rapidez de la búsqueda de resultados de acuerdo a los criterios establecidos por el usuario. Así como minimizar el número de resultados no útiles presentados. - ¿Qué conocimiento con incertidumbre necesita ser representado?
No sabe realmente a dónde se dirigen los links ni sabe si los links funcionan o seguirán funcionando en el futuro. Además de que no se puede saber si el Web Crawler se quedará ciclado en una cierta zona de la web.
Subscribe to:
Posts (Atom)