Kawabonga! Fase 3

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.

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:

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)² + (Pillo#1 - Pillo#2)² + (Vago#1 - Vago#2)²)
Raíz((13 - 5)² + (2 - 11)² + (2-5)²)
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 N_b: 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 N_b 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:

[X,Y,Z]
[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]

Forma de hacer el crossover

Las parejas son elegidas 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.