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.
Showing posts with label 2 - Los Olvidados. Show all posts
Showing posts with label 2 - Los Olvidados. Show all posts
Tuesday, March 24, 2009
Tuesday, March 3, 2009
Fase 2 - Proyecto
Aqui les dejamos la descripción de neustro proyecto para esta fase.
Breve descripción del medio ambiente.
Para este avance del proyecto, desarrollamos un ambiente representado por una matriz de 10 por 10. En principio está llena de ceros, excepto por la parte donde inician los elementos “nano”. La posición inicial, se encuentra aproximadamente en la mitad de la matriz y los elementos “nano” son representados por unos. Entonces, las figuras están formadas por unos, de acuerdo a los movimientos posibles para los elementos “nano”.
Descripción detallada del problema de optimización.
Lo que el agente en principio debe de optimizarse es la forma en la que se hará la figura. Para esto recorrerá los distintos movimientos posibles para formar una figura. El problema se basa en la mejor forma de hacer la figura establecida a realizar, con la mejor selección de movimientos para poder obtener un patrón optimizado de la figura establecida.
Supongamos que tenemos una figura dada inicial, es decir el cuadro en el centro. 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 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Figura final:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
Movimiento uno:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Movimiento dos:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
En el ejemplo es visible que el movimiento uno genera una solución más acertada a la solución final, sin embargo eso no dice con claridad si el movimiento uno es mejor al movimiento dos con respecto a la figura final. Por lo que, el problema de optimización radica en la realización de la mejor serie de movimientos que generen mejor la figura objetivo o final.
Solución planteada usando recocido de simulado.
Configuración.
Para la configuración de esta fase del proyecto definimos por cuestiones de programación que el arreglo inicial tendría que tener las coordenadas de la matriz donde se encontraran los elementos en cuestión.
{{3,3}, {3,4}, {3,5},{4,3},{4,4}, {4,5},{5,3}, {5,4}, {5,5}}
Donde el primer elemento de cada subconjunto es la posición en “x” y la segunda en “y”.
Reordenamiento.
El reordenamiento es aleatorio, pero se realiza de acuerdo a la serie de movimientos dados por los distintos átomos o elementos del arreglo. De acuerdo a un número de reglas, los átomos sólo se podrán mover adyacentes entre sí, sin romper la estructura base de la figura.
Función objetivo.
Ya que el objetivo es maximizar la construcción de la figura con los mejores movimientos posibles, la función objetivo está representada con el siguiente código:
int assess(int board[MAXR][MAXC], int solution[MAXR][MAXC]){
int cquads= 0;
for(i = 0; i < MAXR; i++)
for(j = 0; j < MAXC; j++ )
if(board[i][j] && solution[i][j]) cquads++;
return cquads;
}
Donde se evalúan el número de posiciones correctas con respecto a la figura final y se ejecutan evalúan los posibles movimientos para el que genere una mejor aproximación a la figura final.
Calendario de recocido.
Para esta parte la temperatura que se eligió una de 100, para poder ir bajando correctamente la temperatura y encontrar la solución en su punto mínimo.
Ti+1 = α Ti
Conclusiones después de la programación.
Es interesante la forma en la que el recocido da resultados, ya que en nuestro caso evaluó una cantidad impresionante de figuras. Sin embargo, los elementos asertivos dieron señal a lo que sería la mejor solución. La optimización fue evidente, ya que cuando fue bajando la temperatura, dieron resultados bastantes interesante como la solución exacta o a veces aproximada de su referencia final, es decir, la silla.
Breve descripción del medio ambiente.
Para este avance del proyecto, desarrollamos un ambiente representado por una matriz de 10 por 10. En principio está llena de ceros, excepto por la parte donde inician los elementos “nano”. La posición inicial, se encuentra aproximadamente en la mitad de la matriz y los elementos “nano” son representados por unos. Entonces, las figuras están formadas por unos, de acuerdo a los movimientos posibles para los elementos “nano”.
Descripción detallada del problema de optimización.
Lo que el agente en principio debe de optimizarse es la forma en la que se hará la figura. Para esto recorrerá los distintos movimientos posibles para formar una figura. El problema se basa en la mejor forma de hacer la figura establecida a realizar, con la mejor selección de movimientos para poder obtener un patrón optimizado de la figura establecida.
Supongamos que tenemos una figura dada inicial, es decir el cuadro en el centro. 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 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Figura final:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
Movimiento uno:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Movimiento dos:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
En el ejemplo es visible que el movimiento uno genera una solución más acertada a la solución final, sin embargo eso no dice con claridad si el movimiento uno es mejor al movimiento dos con respecto a la figura final. Por lo que, el problema de optimización radica en la realización de la mejor serie de movimientos que generen mejor la figura objetivo o final.
Solución planteada usando recocido de simulado.
Configuración.
Para la configuración de esta fase del proyecto definimos por cuestiones de programación que el arreglo inicial tendría que tener las coordenadas de la matriz donde se encontraran los elementos en cuestión.
{{3,3}, {3,4}, {3,5},{4,3},{4,4}, {4,5},{5,3}, {5,4}, {5,5}}
Donde el primer elemento de cada subconjunto es la posición en “x” y la segunda en “y”.
Reordenamiento.
El reordenamiento es aleatorio, pero se realiza de acuerdo a la serie de movimientos dados por los distintos átomos o elementos del arreglo. De acuerdo a un número de reglas, los átomos sólo se podrán mover adyacentes entre sí, sin romper la estructura base de la figura.
Función objetivo.
Ya que el objetivo es maximizar la construcción de la figura con los mejores movimientos posibles, la función objetivo está representada con el siguiente código:
int assess(int board[MAXR][MAXC], int solution[MAXR][MAXC]){
int cquads= 0;
for(i = 0; i < MAXR; i++)
for(j = 0; j < MAXC; j++ )
if(board[i][j] && solution[i][j]) cquads++;
return cquads;
}
Donde se evalúan el número de posiciones correctas con respecto a la figura final y se ejecutan evalúan los posibles movimientos para el que genere una mejor aproximación a la figura final.
Calendario de recocido.
Para esta parte la temperatura que se eligió una de 100, para poder ir bajando correctamente la temperatura y encontrar la solución en su punto mínimo.
Ti+1 = α Ti
Conclusiones después de la programación.
Es interesante la forma en la que el recocido da resultados, ya que en nuestro caso evaluó una cantidad impresionante de figuras. Sin embargo, los elementos asertivos dieron señal a lo que sería la mejor solución. La optimización fue evidente, ya que cuando fue bajando la temperatura, dieron resultados bastantes interesante como la solución exacta o a veces aproximada de su referencia final, es decir, la silla.
Friday, January 30, 2009
Fase 1 - Proyecto
1. Descripción detallada del medio ambiente.
El medio ambiente de nuestro proyecto está definido por el espacio directo donde los cubos o figuras (representando los átomos). Los cubos, tienen movimientos regidos por reglas, y los movimientos son adyacentes a los demás cubos con base en su posición actual. Es importante recalcar que los cubos pueden moverse de manera diferente para generar la figura final. En eso se basa el dilema de nuestro proyecto.
2. Plataforma en la que se programara el medio ambiente y lenguaje de programación a ser utilizado.
Con el desarrollo del proyecto aún no se ha determinado el lenguaje y la plataforma en la que se hará. Sin embargo, algunos de nuestras ideas dirigen nuestra atención al lenguaje Java o Phyton.
3. ¿Cuáles problemas de optimización se encuentran en dicho medio?
El problema primordial de optimización se ve reflejado en el menor número de movimientos, dada una figura final, para realizar dicha figura a partir de un estado inicial. Esto se logrará con base en el desarrollo de la figura final
4. ¿Qué conocimiento con incertidumbre necesita ser representado?
El conocimiento con incertidumbre se ve reflejado directamente con el desconocimiento de la ruta o serie de movimientos que se tendrán que realizar para generar la figura final. Así como la incertidumbre de saber si es beneficioso o no, para llegar a la figura final, el movimiento independiente de las figuras.
El medio ambiente de nuestro proyecto está definido por el espacio directo donde los cubos o figuras (representando los átomos). Los cubos, tienen movimientos regidos por reglas, y los movimientos son adyacentes a los demás cubos con base en su posición actual. Es importante recalcar que los cubos pueden moverse de manera diferente para generar la figura final. En eso se basa el dilema de nuestro proyecto.
2. Plataforma en la que se programara el medio ambiente y lenguaje de programación a ser utilizado.
Con el desarrollo del proyecto aún no se ha determinado el lenguaje y la plataforma en la que se hará. Sin embargo, algunos de nuestras ideas dirigen nuestra atención al lenguaje Java o Phyton.
3. ¿Cuáles problemas de optimización se encuentran en dicho medio?
El problema primordial de optimización se ve reflejado en el menor número de movimientos, dada una figura final, para realizar dicha figura a partir de un estado inicial. Esto se logrará con base en el desarrollo de la figura final
4. ¿Qué conocimiento con incertidumbre necesita ser representado?
El conocimiento con incertidumbre se ve reflejado directamente con el desconocimiento de la ruta o serie de movimientos que se tendrán que realizar para generar la figura final. Así como la incertidumbre de saber si es beneficioso o no, para llegar a la figura final, el movimiento independiente de las figuras.
Fase 1 - Proyecto
1. Descripción detallada del medio ambiente.
El medio ambiente de nuestro proyecto está definido por el espacio directo donde los cubos o figuras (representando los átomos). Los cubos, tienen movimientos regidos por reglas, y los movimientos son adyacentes a los demás cubos con base en su posición actual. Es importante recalcar que los cubos pueden moverse de manera diferente para generar la figura final. En eso se basa el dilema de nuestro proyecto.
2. Plataforma en la que se programara el medio ambiente y lenguaje de programación a ser utilizado.
Con el desarrollo del proyecto aún no se ha determinado el lenguaje y la plataforma en la que se hará. Sin embargo, algunos de nuestras ideas dirigen nuestra atención al lenguaje Java o Phyton.
3. ¿Cuáles problemas de optimización se encuentran en dicho medio?
El problema primordial de optimización se ve reflejado en el menor número de movimientos, dada una figura final, para realizar dicha figura a partir de un estado inicial. Esto se logrará con base en el desarrollo de la figura final
4. ¿Qué conocimiento con incertidumbre necesita ser representado?
El conocimiento con incertidumbre se ve reflejado directamente con el desconocimiento de la ruta o serie de movimientos que se tendrán que realizar para generar la figura final. Así como la incertidumbre de saber si es beneficioso o no, para llegar a la figura final, el movimiento independiente de las figuras.
Subscribe to:
Posts (Atom)