Fase 3 - Proyecto

Aqui les dejamos nuestra aportación y la docu de nuestra tercera fase. Saludos :) Cualquier duda aquí estamos...


Breve descripción del medio ambiente.

Para este avance del proyecto, desarrollamos un ambiente representado por una matriz de ocho por ocho. Sin embargo dicha matriz, estará dividida en cuatro cuadrantes que serán generados como cuatro ambientes subordinados. Cada cuadrante estará dividido en pequeñas matrices de cuatro por cuatro. En principio cada cuadrante tendrá una figura de dos por dos elementos justo al centro. El ambiente también limita la cantidad de movimientos posibles para cada figura independiente, en los movimientos adyacentes posibles sin romper la pequeña figura de cuatro elementos “nano”.

Descripción detallada del problema de optimización.

Lo que el agente en principio debe de optimizar es la secuencia para generar nuevas figuras a partir de varios elementos independientes “nano”. Esto se optimiza con base en los movimientos posibles de las piezas “nano” independientes para que se genere una pieza final en unidad con los cuatro cuadrantes.

Supongamos que tenemos una figura dada inicial, con base en el ambiente. Y con respecto a las distintas piezas que se pueden mover a distintos lados. El problema de optimización está representado de la siguiente manera:

Figura inicial:
0 0 0 0 0 0 0 0
0 1 1 0 0 1 1 0
0 1 1 0 0 1 1 0
0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0
0 1 1 0 0 1 1 0
0 1 1 0 0 1 1 0
0 0 0 0 0 0 0 0

Figura final:
0 0 0 0 0 0 0 0
0 0 1 1 1 1 0 0
0 0 1 0 0 1 0 0
0 0 1 0 0 1 0 0

0 0 1 0 0 1 0 0
0 0 1 0 0 1 0 0
0 0 1 1 1 1 0 0
0 0 0 0 0 0 0 0


Movimiento uno:
0 0 1 0 0 0 0 0
0 0 1 0 0 1 0 0
0 1 1 0 0 1 1 1
0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0
0 1 1 1 0 1 1 0
0 1 0 0 0 0 1 0
0 0 0 0 0 0 1 0

Movimiento dos:
0 0 1 0 0 0 0 0
0 0 1 0 0 1 1 0
0 1 1 0 0 1 0 0
0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 0
0 1 0 0 0 1 1 1
0 1 1 1 0 1 0 0
0 0 0 0 0 0 0 0

En el ejemplo es visible que el movimiento dos genera en cada uno de los cuadrantes da un resultado más aproximado al final, por lo que las diferentes evaluaciones de selección son con base en esa relación y el que más acercado esté a la figura final será el segundo como el elegido a la selección final. Aunque en el ejemplo sólo se utilizan un par de movimientos, la implementación genera cuatro movimientos posibles. Sin embargo, la optimización con algoritmos genéticos radica en que las configuraciones más aproximadas a la final, son las que se presentan en la siguiente generación para ser producto de una evolución.

Solución planteada usando recocido de simulado.

Codificación del cromosoma.

Para la codificación de los cromosomas se tomarán en cuenta el número de cuadrantes que se generan con respecto al ambiente. Esto quiere decir que serán cuatro elementos dentro de un arreglo general que conserva toda la configuración final.

Está representado de la siguiente manera, por cada cromosoma.

[{0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0}]



Función a maximizar o minimizar.

f(x) = Número de elementos correctos con respecto a la figura final.

-Implementación.

for(chr = 0; chr < MAXPOPUL; chr++)
sum += fx[chr];
avg = (sum / MAXPOPUL);

Reproducción.


-Implementación
for(chr = 0; chr < MAXPOPUL; chr++) //Expected count & Pselect
{
PSelect[chr] = (fx[chr] / (float)sum);
ExpectedC[chr] = (fx[chr] / (float)avg);
ActualC[chr] = (ExpectedC[chr] >= 1.0)? 1 : 0;
}
Crossover.

El crossover se realiza con base en el intercambio de cada uno de los cuadrantes. Se toman los dos cuadrantes y se intercambian entre ellos con los dos cuadrantes restantes. La forma en la que se selecciona el punto de cruce es aleatoria así como las parejas a ser cruzadas.

Mutación.

Para la mutación se considero una probabilidad de 1/1000. Con el objetivo de hacer una mutación en generaciones que estén más aproximadas al resultado final afectando de manera positiva a los cromosomas. Siempre y cuando los elementos de la generación no sean válidos u obtengan un valor menor en comparación al estado final.

Ejemplo.

Cromosoma f(x) Pselect Expected Blog to cross Cross Point Next Generation
[{0 0 0 1 1 1 1 0 0 0 0 0 0 0 0} {0 0 0 0 1 1 1 0 0 1 0 0 0 0 0} {0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0}]
5 .2 .83 0 2 [{0 0 0 1 1 1 1 0 0 0 0 0 0 0 0} {0 0 0 0 1 1 1 0 0 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0}]

[{0 0 0 1 1 1 1 0 0 0 0 0 0 0 0} {0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0} {0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0}{0 0 0 0 1 1 1 0 0 1 0 0 0 0 0}] 8 .32 1.3 3 1 [{0 0 0 1 1 1 1 0 0 0 0 0 0 0 0} {0 0 0 0 1 1 1 0 0 1 0 0 0 0 0} {0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0} {0 0 0 0 0 1 1 0 0 1 0 0 0 1 0}]

[{0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 1 1 0 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0}]
7 .28 1.16 1 1 [{0 0 0 1 1 1 1 0 0 0 0 0 0 0 0} {0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0} {0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0}{0 0 0 0 1 1 1 0 0 1 0 0 0 0 0}]

[{0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0} {0 0 0 0 0 0 0 0 0 1 0 0 1 1 1}]
5 .2 .83 0 3 [{0 0 0 0 1 1 1 0 0 1 0 0 0 0 0} {0 0 0 0 0 1 1 1 0 1 0 0 0 0 0} {0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0} {0 0 0 0 0 1 1 0 1 1 0 0 0 0 0}]



Conclusiones después de la programación.
Los algoritmos genéticos son una nueva forma de ver como se optimizan la forma de formar figuras. Lo más interesante de nuestra solución radica en la capacidad de generar una figura final con varias figuras independientes. Lo interesante es que, los elementos “nano” tienen que buscar una solución óptima de cómo llegar a crear con el menor esfuerzo o menor número de movimientos para generalizar las partes particulares. Sin embargo, nos dimos cuenta que la solución con algoritmos genéticos generaría una solución rápida para formar las figuras debido a la cantidad de cromosomas que se generan, por lo que estos algoritmos no generan una buena forma de implementación para nuestro problema.